Стили и методы программирования
Схема построения циклической программы называется
int fact(int n) {if (n==0) return(1); else return(n*fact(n-1));}
Схема построения циклической программы называется потоковой обработкой. Значения на следующей итерации цикла зависят от значений на предыдущей.
Для чисел Фибоначчи (та же схема (14.1.2)) структура уже несколько сложнее предыдущих, поскольку каждое следующее число Фибоначчи зависит от двух предыдущих, но метод потоковой обработки применим и здесь.
int fib(int n) {int fib1,fib2; fib1=1; fib2=1; if (n>2){ for (int i=2;i<n;i++){ int j; j=fib1+fib2; fib1=fib2; fib2=j; } }; return(fib2); }
Итак, в потоке изменяется структура из двух элементов. Ее можно было бы прямо описать как структуру данных, и это следовало бы сделать, будь программа хоть чуть-чуть посложнее. Тогда вместо подпорки j пришлось бы ввести в качестве подпорки новое значение структуры.
В программе имеется еще одна подпорка - параметр цикла i, который нужен лишь для формальной организации цикла.
Рекурсивная реализация чисел Фибоначчи пишется еще проще и служит великолепным примером того, как презренная материя убивает красивую, но неглубокую идею.
int fib(int n) { if (n<3) return(1); else return(fib(n-1)+fib(n-2)); }
Если n достаточно велико, каждое из предыдущих значений функции Фибоначчи будет вычисляться много раз, причем без всякого толку: результат всегда будет один и тот же! Зато все подпорки убраны...
В следующем примере неэффективность рекурсии по сравнению с хорошо организованным циклом еще более очевидная. Пусть надо найти путь, на котором можно собрать максимальное количество золота, через сеть значений, подобную показанной на рис. 14.1.
Рис. 14.1. Золотая гора
При циклической организации вычислений нам придется посчитать значение в каждой точке горы всего один раз (найти добычу на оптимальном пути в эту точку). Здесь используется то свойство оптимальных путей, которое делает возможным так называемые методы волны или динамического программирования: каждый начальный отрезок локально оптимального пути локально оптимален.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий