Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/08/04
003
004// Eficiencia = algoritmos + estuturas de dados + matematica + ...
005// Sequencia de Fibonacci: Fi = 1, se i=1 ou i=2 e Fi = F(i-1)+F(i-2), se i>2
006
007#include <stdio.h>
008#include <time.h> // clock_t, clock()
009
010// Fibonacci iterado: computa de modo "guloso", a partir do menor indice, nunca repetindo (O(n))
011int fib (int n) {
012  int i, F1=1, F2=1, F;
013  if (n<3) return 1;
014  for (i=3; i<=n; i++) {
015    F = F1+F2;
016    F1 = F2;
017    F2 = F;
018    }
019  return F;
020  }
021
022// Fibonacci recursivo: computa repetidas vezes (O(2^n))
023int fibRec (n) { // os finalizadores ';' sao opcionais em Python
024  if (n==1 || n==2) return 1;     // final de recorrencia
025  return fibRec(n-1) + fibRec(n-2); // senao devolve 
026  }
027
028int main (void) {
029  int n, fibA; clock_t tempo_inicial, tempo_final;
030  scanf("%d", &n);
031
032  tempo_inicial = clock(); // "dispara o cronometro"...
033  fibA = fib(n);
034  tempo_final = clock();
035  printf("Iterativo: %3d -> %3d em %f segundos\n", n, fibA, (double)(tempo_final - tempo_inicial) / CLOCKS_PER_SEC);
036
037  tempo_inicial = clock(); // "dispara o cronometro"...
038  fibA = fibRec(n);
039  tempo_final = clock();
040  printf("Recursivo: %3d -> %3d em %f segundos\n", n, fibA, (double)(tempo_final - tempo_inicial) / CLOCKS_PER_SEC);
041  return 0;
042  }