2010-03-23 17:46:46 Flash999 Задача: Найти количество сложений для вычисления n-го числа Фибоначчи рекурсивным и обычным алгоритмом. Результаты выдать в виде таблицы. Ну с самим числом фибоначчи всё понятно, а вот что такое Рекурсивный и обычный алгоритм, в чем разница?? Подскажите, пожалуйста, кто разбирается. | ||
2010-03-23 18:22:19 yashchar Гугл тебе в помощь. Алгоритмов море. И про рекурсию там куда как более подробно описано, с примерами. Сам так первые алгоритмы писал | ||
2010-03-23 18:26:23 Flash999 yashchar уже искала, то что прочитала - почти ничего не поняла... | ||
2010-03-23 20:55:32 yashchar Flash999 Водишь запрос типа рекурсивный алгоритм чисел Фибоначчи и наслаждаешься информацией. По крайней мере эффективность рекурсивного по сравнению в обычным там точно будет | ||
2010-03-23 21:09:05 Flash999 yashchar я не сказала, что я не нашла информацию, я сказала, что я ее не поняла. а вернее примеры кода (само сравнение). | ||
2010-03-23 21:21:18 Фтвкун Flash999 ну вот тебе код из первой же ссылки=) Function Fibo(n) If n = 1 Or n = 2 Return 1 End If Return Fibo(n - 1) + Fibo(n - 2) End Function function - это функция Fibo - имя функции если n=1 или 2 то возвращаем 1 так как первый и 2ой элемент фибаначи равны 1, в остальных случаях возвращается Fibo(n - 1) + Fibo(n - 2) - вызывается 2 функции Fibo, но уже не для числа n, а для чисел n-1 и n-2 , которая опять проверяет, является ли число n-1 либо n-2 равным 1 или два, иначе снова вызывается функция Fibo для (n-1)-1, (n-1)-2, (n-2)-1, (n-2)-2 итд | ||
2010-03-23 21:27:59 yashchar а вот нерекурсивный алгоритм: #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <iostream.h> void main(void) { clrscr(); int m; int i,i1=1,i2=1; cout<<"M="; cin>>m; while(i1<m) { i=i1+i2; i1=i2; i2=i; cout<<i<<"n"; } cout<<i<<">"<<m; getch(); } | ||
2010-03-23 21:30:01 yashchar В рекурсии сначала спускаются от некого известного n до конча, т.е. когда n==1, и только потом начинаются вычисления сумм, учитывая уже полученный ранее результат | ||
2010-03-23 21:30:29 yashchar
до конца, пальцы мне вырвать | ||
2010-03-23 21:34:05 yashchar А если НЕ(!) рекурсивный алгоритм взять такой, то еще более интересно, чем рекурсия: const max = 25; var i : integer; F : array [0..max] of integer; procedure fibonacci; begin F[0] := 1; F[1] := 1; for i := 2 to max do F[i] := F[i-1]+F[i-2]; end; | ||
2010-03-23 21:42:34 Фтвкун yashchar последний метод понравился) | ||
2010-03-23 21:43:38 yashchar Фтвкун сам в восторге, массив сделать динамическим, max с клавиатуры и нафих ту рекурсию | ||
2010-03-23 21:46:44 Flash999
так я так и делала, значит вопрос заключался не в том, что такое рекурсия, а что такое обычный алгоритм) но теперь вроде понятно) yashchar Фтвкун спасибо) | ||
2010-03-23 21:49:54 MrHide
только надо еще под максимум выделить очень длинный беззнаковый инт | ||
2010-03-23 21:52:45 yashchar MrHide int 64 в плюсах, а на паскале longint, не больше | ||
2010-03-23 22:55:21 MrHide yashchar а, черт, я не уловил, что паскаль, в код не вчитывался, думал Си | ||
2010-03-23 23:25:31 yashchar MrHide Да оно и без разницы. ))) В данном, так сказать, случае | ||
2010-03-24 09:07:56 Flash999 закрыто | ||