Читать онлайн «Алгоритмы на C++»

Р. СIЩЖ ВИК АлГОРIml<Ы на С ++ Рис. 5. 9. Двоич ный подсчет и функция рисования линейки Вычисление функции рисования линейки эквивалентно под счету количества оконечных нулей в четных N -разрядны х числах. Программа 5. 9 - альтернативный способ рисования линейки , на который натолкнуло соответствие с двоичными числами (см. рис . 5. 10). Эту версию алгоритма называют восходящей (bottom -up) реализацией. Она не является рекурсивной, но определенно навеяна рекурсивным алгоритмом. Эта связь между ал горитмами "разделяй и властвуй " и двоичными пр едставлениями чисел часто помогает найти решение при анализе и р азработке усовершенствованны х версий , таких как восходящие подходы. Мы будем рассматривать данную возможность , чтобы понять и, возможно , усоверше нс твовать каждый рассматриваемый алгоритм вида ' 'разделяй и властвуй ". Восходящий подход предполагает изм ене ни е порядка выполнения вычислений при рисовании л ин ейки. На рис. 5. 11 показан еще один при мер , в котором изменен порядок следования трех вызовов функций в рекурсивной реализации. Этот прим ер соответствует рекурсивному рисованию первоначально описанным способом: нанесение средней метки, затем левой половины, а затем правой. Последовательность нан есения меток выглядит сложной , но является результатом простой п еремены мест двух операторов в прогр амме 5. 8. Как будет показано в разд еле 5. 6, взаимосвязь междУ ри с. 5. 8 и рис . 5. 11 срадни различию между постфиксными и пр ефиксными арифметическими выражениями. Программа 5. 9. Нерекурсивная программа для рисования л ин ейки В отличие от про граммы 5. 8, линейку можно нарисовать, вначале и зобраз ив все метки длиной 1, затем все метки длиной 2 и т. д. Переменная t пр едставляет длину меток, а переменная j - количество меток между д вумя последовательными метками дли ной t. Внешний циЮl for увеличивает значение t при сохранении соотноше ния j = 2 -1 .