Upload
renato-batista
View
215
Download
0
Embed Size (px)
Citation preview
CES-10 INTRODUÇÃO CES-10 INTRODUÇÃO À COMPUTAÇÃOÀ COMPUTAÇÃO
Aulas Práticas – 2014Aulas Práticas – 2014
Capítulo IX Capítulo IX Subprogramação e Subprogramação e
RecursividadeRecursividade
Programa 9.1: Subprograma bem simples Programa 9.1: Subprograma bem simples para somarpara somar
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
int soma (int x, int y)int soma (int x, int y){return x + y;}{return x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);c = soma (a, b);c = soma (a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Copiar, salvar e executar
Programa 9.2: Mesmo efeito, porém sem Programa 9.2: Mesmo efeito, porém sem retornar valorretornar valor
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Copiar, salvar e executar
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
a b c
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
a b c
Leitura de a e b: 151 346
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
151
a 346
b c
Leitura de a e b: 151 346
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
151
a 346
b c
Alocação das variáveis de soma
Função soma
x y z
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
151
a 346
b c
Passagem dos argumentos aos parâmetros
Função soma
x y z
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
151
a 346
b c
Passagem dos argumentos aos parâmetros
Função soma
151
x 346
y z
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
151
a 346
b c
z recebeu o endereço de cz é um ponteiro (apontando para c)
Função soma
151
x 346
y z
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){{*z = x + y;*z = x + y;}}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
151
a 346
b c
O local cujo endereço está em z (*z) recebe o valor de x+y
Função soma
151
x 346
y z
497
c
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
151
a 346
b
Função soma
151
x 346
y z
497
c
Desalocação das variáveis de soma
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
151
a 346
b 497
c
Desalocação das variáveis de soma
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>
void soma (int *z, int x, int y)void soma (int *z, int x, int y){*z = x + y;}{*z = x + y;}
int main ( ) {int main ( ) {int a, b, c;int a, b, c;printf ("Digite a e b: ");printf ("Digite a e b: ");scanf ("%d%d", &a, &b);scanf ("%d%d", &a, &b);soma (&c, a, b);soma (&c, a, b);printf ("\nc = a + b = %d + %d = %d", a, b, c);printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Função main
151
a 346
b 497
c
Será escrito: c = a + b = 151 + 346 = 497
#include <stdio.h>#include <stdio.h>#include <stdlib.h>#include <stdlib.h>#include <conio.h>#include <conio.h>
int fat (int n) {int fat (int n) {int f;int f;if (n < 0) f = -1;if (n < 0) f = -1;else if (n <= 1) f = 1;else if (n <= 1) f = 1;else f = n * fat(n - 1);else f = n * fat(n - 1);return f;return f;
}}
int main() {int main() {int n;int n;
printf ("Calculo de fatorial de n");printf ("Calculo de fatorial de n"); printf ("\n\n\tDigite n: ");printf ("\n\n\tDigite n: ");
scanf ("%d", &n);scanf ("%d", &n); printf ("\n\tFat(%d) = %d", n, fat(n));printf ("\n\tFat(%d) = %d", n, fat(n)); printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;}}
Copiar, salvar e executar
Formula recursiva
-1, para n < 0n! = 1, para 0 ≤ n ≤ 1
n * (n-1)!, para n > 1
Programa 9.3: Cálculo recursivo de fatorial
int v = 0; //Numero da versao de fat: globalint v = 0; //Numero da versao de fat: globalint fat (int n) {int fat (int n) {
int f;int f;int i;int i;v++;v++;
printf ("\n");printf ("\n");for (i = 1; i <= v; i++) printf (" ");for (i = 1; i <= v; i++) printf (" ");printf ("Entrada em fat versao %d; n = %d; ", v, n);printf ("Entrada em fat versao %d; n = %d; ", v, n);printf ("Digite algo: "); getche (); printf ("\n");printf ("Digite algo: "); getche (); printf ("\n");if (n < 0) f = -1;if (n < 0) f = -1;else if (n <= 1) f = 1;else if (n <= 1) f = 1;else f = n * fat(n - 1);else f = n * fat(n - 1);
printf ("\n");printf ("\n");for (i = 1; i <= v; i++) printf (" ");for (i = 1; i <= v; i++) printf (" ");printf ("Saida de fat versao %d; n = %d; fat = %d; ", printf ("Saida de fat versao %d; n = %d; fat = %d; ", v, n, f);v, n, f);printf ("Digite algo: "); getche (); printf ("\n");printf ("Digite algo: "); getche (); printf ("\n");v--;v--;
if (v == 0) printf ("\n");if (v == 0) printf ("\n");return f;return f;
}}
Copiar, salvar e executar
Programa 9.4: Cálculo recursivo instrumentado de fatorial
Alterar a função fat do programa anterior
Exercício 9.1: Potência de expoentes inteiros Exercício 9.1: Potência de expoentes inteiros e não negativose não negativos
AAnn (n inteiro e não negativo) (n inteiro e não negativo)
Escrever um programa para implementar a Escrever um programa para implementar a seguinte seguinte fórmula recursivafórmula recursiva::
A função A função main main pode ser parecida com a do pode ser parecida com a do programa do programa do fatorialfatorial
1, para n = 0An = A * An-1, para n > 0
Exercício 9.2: Raiz quadradaExercício 9.2: Raiz quadrada
Escrever um programa para implementar a Escrever um programa para implementar a seguinte seguinte fórmula recursivafórmula recursiva::
aa é uma é uma aproximaçãoaproximação para a raiz quadrada; para a raiz quadrada; ee é a é a precisãoprecisão desejada desejada
A A primeira aproximaçãoprimeira aproximação e a e a precisãoprecisão devem devem ser lidas na função ser lidas na função mainmain
a, p/ (|a2 - n| < e)RaizQuad (n, a, e) = RaizQuad (n, (a2+n)/(2*a), e), caso contrário
Exercício 9.3: Números de Fibonacci Exercício 9.3: Números de Fibonacci (procriação de (procriação de coelhos)coelhos)
Gerar a sequência de números de Gerar a sequência de números de FibonacciFibonacci para um para um dado valor de dado valor de nn, usando a seguinte , usando a seguinte fórmula fórmula recursivarecursiva::
O programa deve montar uma O programa deve montar uma tabelatabela com os números com os números de de FibonacciFibonacci e com o número de chamadas e com o número de chamadas recursivas para gerar cada um delesrecursivas para gerar cada um deles
Para tanto, o programa deve ser devidamente Para tanto, o programa deve ser devidamente instrumentadoinstrumentado (ver como exemplo a tabela a seguir) (ver como exemplo a tabela a seguir)
-1, p/ n < 00, p/ n = 0
Fib (n) = 1, p/ n = 1
Fib (n-2) + Fib (n-1), p/ n > 1
Exemplo: tabela para n = 20Exemplo: tabela para n = 20 n | Fib(n) | Chamadas recursivasn | Fib(n) | Chamadas recursivas---------------------------------------------------------------------------------------------------------------- 0 | 0 | 10 | 0 | 1 1 | 1 | 11 | 1 | 1 2 | 1 | 32 | 1 | 3 3 | 2 | 53 | 2 | 5 4 | 3 | 94 | 3 | 9 5 | 5 | 155 | 5 | 15 6 | 8 | 256 | 8 | 25 7 | 13 | 417 | 13 | 41 8 | 21 | 678 | 21 | 67 9 | 34 | 1099 | 34 | 109 10 | 55 | 17710 | 55 | 177 11 | 89 | 28711 | 89 | 287 12 | 144 | 46512 | 144 | 465 13 | 233 | 75313 | 233 | 753 14 | 377 | 121914 | 377 | 1219 15 | 610 | 197315 | 610 | 1973 16 | 987 | 319316 | 987 | 3193 17 | 1597 | 516717 | 1597 | 5167 18 | 2584 | 836118 | 2584 | 8361 19 | 4181 | 1352919 | 4181 | 13529 20 | 6765 | 2189120 | 6765 | 21891
Tarefa 1 do Lab 9: Função binomialTarefa 1 do Lab 9: Função binomial Em Análise Combinatória, o Em Análise Combinatória, o coeficiente binomialcoeficiente binomial
tem a seguinte formulação recursiva:tem a seguinte formulação recursiva:
Usando esta formulação, escrever um programa para Usando esta formulação, escrever um programa para ler um inteiro positivo ler um inteiro positivo mm e montar duas matrizes e montar duas matrizes quadradas:quadradas: A primeira de nome A primeira de nome A(m x m)A(m x m), onde , onde
A[i][j] = Binom (i, j)A[i][j] = Binom (i, j), para , para 0 0 i i m-1 m-1 e e 0 0 j j m-1m-1
A segunda de nome A segunda de nome B(m x m)B(m x m), onde , onde B[i][j] B[i][j] deverá deverá conter o número de chamadas recursivas para conter o número de chamadas recursivas para calcular calcular A[i][j]A[i][j], para , para 0 0 i i m-1 m-1 e e 0 0 j j m-1 m-1
-1, p/ n < 0, k < 0 ou k >nBinom (n, k) = 1, p/ k = 0 ou k = n
Binom (n-1, k-1) + Binom (n-1, k), p/ outros casos
Exemplo: matrizes para m = 8Exemplo: matrizes para m = 8Matrizes quadradas com valores e chamadas recursivas da funcao binomialMatrizes quadradas com valores e chamadas recursivas da funcao binomial
Digite a dimensao das matrizes: 8Digite a dimensao das matrizes: 8
Matriz A com os valores da funcao binomial:Matriz A com os valores da funcao binomial:
1 -1 -1 -1 -1 -1 -1 -11 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -11 1 -1 -1 -1 -1 -1 -1 1 2 1 -1 -1 -1 -1 -11 2 1 -1 -1 -1 -1 -1 1 3 3 1 -1 -1 -1 -11 3 3 1 -1 -1 -1 -1 1 4 6 4 1 -1 -1 -11 4 6 4 1 -1 -1 -1 1 5 10 10 5 1 -1 -11 5 10 10 5 1 -1 -1 1 6 15 20 15 6 1 -11 6 15 20 15 6 1 -1 1 7 21 35 35 21 7 11 7 21 35 35 21 7 1
Matriz B com os numeros de chamadas recursivas da funcao binomial:Matriz B com os numeros de chamadas recursivas da funcao binomial:
1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 3 1 1 1 1 1 11 3 1 1 1 1 1 1 1 5 5 1 1 1 1 11 5 5 1 1 1 1 1 1 7 11 7 1 1 1 11 7 11 7 1 1 1 1 1 9 19 19 9 1 1 11 9 19 19 9 1 1 1 1 11 29 39 29 11 1 11 11 29 39 29 11 1 1 1 13 41 69 69 41 13 11 13 41 69 69 41 13 1
i
i
j
j
Tarefa 2 do Lab 9: Função com aninhamento Tarefa 2 do Lab 9: Função com aninhamento de recursividadede recursividade
Uma função Uma função h(n)h(n) tem a seguinte formulação tem a seguinte formulação recursiva aninhada:recursiva aninhada:
Usando esta formulação, escrever um programa Usando esta formulação, escrever um programa para ler um inteiro positivo para ler um inteiro positivo mm e montar uma e montar uma tabela de tabela de h(nh(n) e do número de chamadas ) e do número de chamadas recursivas para o cálculo de recursivas para o cálculo de h(nh(n), para ), para 0 0 n n mm
-1, p/ n < 0 0, p/ n = 0
h (n) = n, p/ n > 4 h (2 + h (2*n)), p/ 1
≤ n ≤ 4
Exemplo: tabela para m = 8Exemplo: tabela para m = 8 n | h(n) | Chamadas recursivasn | h(n) | Chamadas recursivas---------------------------------------------------------------------------------------------------------------- 0 | 0 | 10 | 0 | 1 1 | 14 | 71 | 14 | 7 2 | 12 | 52 | 12 | 5 3 | 8 | 33 | 8 | 3 4 | 10 | 34 | 10 | 3 5 | 5 | 15 | 5 | 1 6 | 6 | 16 | 6 | 1 7 | 7 | 17 | 7 | 1 8 | 8 | 18 | 8 | 1
Tarefa 3 do Lab 9: Função AckermannTarefa 3 do Lab 9: Função Ackermann Uma importante função teórica conhecida como Uma importante função teórica conhecida como
função de Ackermannfunção de Ackermann tem a seguinte formulação tem a seguinte formulação recursiva:recursiva:
Usando esta formulação, escrever um programa para Usando esta formulação, escrever um programa para ler dois inteiros positivos ler dois inteiros positivos pp e e qq e montar duas matrizes: e montar duas matrizes: A primeira de nome A primeira de nome A(p x q)A(p x q), onde , onde A[i][j] = Acker (i, j)A[i][j] = Acker (i, j), para , para 0 0 i i p-1 p-1 e e 0 0 j j q- q-
11 A segunda de nome A segunda de nome B(p x q)B(p x q), onde , onde B[i][j] B[i][j] deverá deverá
conter o número de chamadas recursivas para conter o número de chamadas recursivas para calcular calcular A[i][j]A[i][j], para , para 0 0 i i p-1 p-1 e e 0 0 j j q-1 q-1
-1, p/ m < 0 ou n < 0Acker (m, n) = n+1, p/ m = 0 e n ≥ 0
Acker (m-1, 1) p/ n = 0 e m > 0
Acker (m-1, Acker (m, n-1), p/ outros casos
Exemplo: matrizes para p = 4 e q = 8Exemplo: matrizes para p = 4 e q = 8Matrizes com valores e chamadas recursivas da funcao ackermannMatrizes com valores e chamadas recursivas da funcao ackermann
Digite as dimensoes das matrizes: 4 8Digite as dimensoes das matrizes: 4 8
Matriz A com os valores da funcao acker:Matriz A com os valores da funcao acker:
1 2 3 4 5 6 7 81 2 3 4 5 6 7 8 2 3 4 5 6 7 8 92 3 4 5 6 7 8 9 3 5 7 9 11 13 15 173 5 7 9 11 13 15 17 5 13 29 61 125 253 509 10215 13 29 61 125 253 509 1021
Matriz B com os numeros de chamadas recursivas da funcao acker:Matriz B com os numeros de chamadas recursivas da funcao acker:
1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 2 4 6 8 10 12 14 162 4 6 8 10 12 14 16 5 14 27 44 65 90 119 1525 14 27 44 65 90 119 152 15 106 541 2432 10307 42438 172233 69396415 106 541 2432 10307 42438 172233 693964
i
i
j
j