программистов, многие из ее уроков очень подходят для задач программирования. Адаме определил концептуальную блокаду как "умозрительные стены, которые препятствуют человеку, решающему задачу, правильно понять задачу или представить себе решение". Над задачами 9 и 10 вам предстоит поломать голову.
Глава 2. Ага! АЛГОРИТМЫ
Активно работающему программисту изучение алгоритмов дает очень много. Курс по этому предмету вооружает студентов алгоритмами решения важных задач и методами разработки алгоритмов для наступления на новые задачи. В следующих главах мы увидим, как более совершенные алгоритмические средства оказывают существенное влияние на системы программного обеспечения, сокращая время разработки и увеличивая скорость выполнения программ.
Кроме того, алгоритмы играют существенную роль в решении общих задач программирования. В своей книге "Ага! Озарение" (Martin Gardner. Aha! Insight), откуда я бесстыдно украл заглавие, М. Гарднер упоминает о той роли, которую я имею в виду: "Задача, которая кажется сложной, может иметь простое, неожиданное решение". В отличие от более совершенных методов, ага! Озарение происходит не только после всестороннего изучения; оно доступно любому программисту, который готов серьезно подумать до, во время и после написания программы.
2.1. ТРИ ЗАДАЧИ
Но довольно общих рассуждений. Материал этой главы основывается на трех маленьких задачах; попытайтесь их решить перед тем, как читать дальше.
А. Имеется магнитная лента, содержащая не более миллиона 20-битовых целых чисел в случайном порядке. Требуется найти 20-битовое число, которого нет на ленте (должен иметься по меньшей мере один пропуск - кстати, почему?). Как бы вы решали эту задачу, имея а) ОЗУ достаточного объема; б) несколько лентопротяжек, но только пару дюжин слов в ОЗУ?
Б. Осуществите циклический сдвиг одномерного массива из N элементов влево на I позиций. Например, при N = 8 и 1 = 3 вектор ABCDEFGH после сдвига превратится в вектор DEFGHABC. Чтобы выполнить эту работу за N шагов, простая программа использует промежуточный буфер из N элементов. Можете ли вы выполнить циклический сдвиг за время, пропорциональное N, используя только несколько дополнительных слов памяти?
21
