Wzór Bineta, rekurencja i iteracja, co działa najszybciej?
Odpowie nam poniższy porogram (uwaga! Visual C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | //Autor: Mikołaj Miller #include <iostream> #include <math.h> #include <chrono> using namespace std; long long int fib2(long int n) { //rekurencja if (n == 1 || n == 2) return 1; return fib2(n - 1) + fib2(n - 2); } long long int fib(long int n) { //wzór Bineta return 1.0 / sqrt(5.0) * (pow((1.0 + sqrt(5.0)) / 2.0, (double)(n)) - pow((1.0 - sqrt(5.0)) / 2.0, (double)(n))); } long long int fib3(long int n) { //iteracja if ((n == 0) || (n == 1)) return n; unsigned int a, b; a = 1; b = 1; for (unsigned int i = 0; i < n - 2; i++) { std::swap(a, b); b += a; } return b; } int main() { auto start = std::chrono::high_resolution_clock::now(); //startowy moment pomiaru czasu cout << "wynik:" << fib(45); auto finish = std::chrono::high_resolution_clock::now(); //koniec pomiaru std::chrono::duration<double> elapsed = finish - start; //czas trwania std::cout << "Elapsed time: " << elapsed.count() << " s\n"; start = std::chrono::high_resolution_clock::now(); //od nowa - czas startowy... cout << "wynik2:" << fib2(45); finish = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> elapsed2 = finish - start; std::cout << "Elapsed time: " << elapsed2.count() << " s\n"; start = std::chrono::high_resolution_clock::now(); cout << "wynik iteracyjny:" << fib3(45); finish = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> elapsed3 = finish - start; std::cout << "Elapsed time: " << elapsed3.count() << " s\n"; start = std::chrono::high_resolution_clock::now(); return 0; } |