Стили и методы программирования


Сети данных - часть 2


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.  Золотая гора

При циклической организации вычислений нам придется посчитать значение в каждой точке горы всего один раз (найти добычу на оптимальном пути в эту точку). Здесь используется то свойство оптимальных путей, которое делает возможным так называемые методы волны или динамического программирования: каждый начальный отрезок локально оптимального пути локально оптимален.


Начало  Назад  Вперед



Книжный магазин