ВУЗ:
ных схем в некоторых случаях может даже усложнить изначально простое задание. Рассмотрим следующую задачу.
Когда вы садились в лодку, ваша шляпа упала в воду, но вы этого не заметили. Скорость течения реки 2,5 мили в час, и
ваша шляпа поплыла вниз по течению. Тем временем вы поплыли в лодке вверх против течения со скоростью 4,75 мили в час
(относительно воды). Спустя 10 минут вы заметили пропажу шляпы, развернули лодку и поплыли вниз по реке догонять вашу
шляпу. Через какое время вы поймаете свою шляпу?
Большинство студентов, изучающих алгебру в высшей школе, а также любителей карманных калькуляторов начнут
решение этой задачи с определения, какое расстояние прошла лодка за 10 минут вверх по течению, и какое расстояние за это
время проплыла шляпа вниз по течению. Затем они попытаются вычислить, сколько времени понадобится лодке, чтобы
пройти вниз по течению до той точки, где находится шляпа. Но ведь пока лодка будет идти к этой точке, шляпа будет уплы-
вать дальше вниз по течению! Таким образом, они, весьма вероятно, попадут в цикл вычислений, где будет находиться шля-
па в тот момент, когда лодка достигнет того места, где шляпа была на предыдущем этапе расчета.
На самом же деле задача гораздо проще. Весь фокус состоит в том, чтобы суметь противостоять стремлению писать
формулы и делать вычисления. Необходимо просто отложить эти навыки в сторону и взглянуть на задачу в ее истинном све-
те. Суть всей проблемы в реке. В данном случае тот факт, что вода движется относительно берегов, не имеет никакого зна-
чения. Представьте себе ту же задачу на длинной конвейерной ленте. Сначала решим поставленную задачу, когда лента не-
подвижна. Если вы, стоя на ленте, положите шляпу у своих ног, а затем будете идти вдоль ленты в течение 10 мин, то вер-
нуться к шляпе вы сможете за те же 10 мин. Теперь включим конвейер. Это будет означать, что сначала вы пойдете против
движения ленты. Но поскольку вы, как и шляпа, находитесь на ленте, это не изменит ваших взаимоотношений с лентой и
шляпой. Вам по-прежнему потребуется 10 мин, чтобы вернуться к оставленной шляпе.
В результате можно прийти к заключению, что создание алгоритмов является сложным искусством, которое необходи-
мо постоянно совершенствовать, а не изучать как предмет, состоящий из хорошо определенных методологий. Учить решать
задачи, следуя четко определенным методологиям, значит "загубить" творческие способности учащихся, которые, напротив,
нужно всемерно развивать.
Вопросы для самопроверки
1. Найдите алгоритм решения следующей задачи и ответьте на дополнительные вопросы.
а) Для заданного положительного числа n найдите такую комбинацию целых положительных чисел, произведение ко-
торых максимально среди всех возможных комбинаций целых положительных чисел, сумма которых равна n. Например,
если n равно 4, то искомый список есть (2, 2), так как 2*2 больше, чем 1*1*1*1, 2*1*1 и 3*1. Для n, равного 5, искомая ком-
бинация будет (2, 3).
б) Какова искомая комбинация для n = 2001?
в) Объясните, как вам удалось продвинуться в решении этой задачи.
2. Найдите алгоритм решения следующей задачи и ответьте на дополнительные вопросы.
а) Пусть дана квадратная шахматная доска размером
nn 22
×
, где n – целое положительное число, и коробка с L-
образными фишками, каждая из которых может закрыть в точности три квадрата на доске. Если вырезать из доски один ка-
кой-либо квадрат, сможем ли мы покрыть оставшуюся часть доски фишками таким образом, чтобы они не перекрывались и
не выступали за край доски?
б) Объясните, как предложенное решение этой задачи может быть использовано, чтобы показать, что
12
−
n
делится на
3 для любых целых положительных n.
в) Как ответы на два предыдущих вопроса связаны с фазами решения задач, предложенными математиком Полиа?
3. Декодируйте следующее сообщение и объясните, как вам удалось сделать первый шаг в поисках решения:
Pdeo eo pda yknnayp wjosan.
4.4. ИТЕРАЦИОННЫЕ СТРУКТУРЫ
Теперь нашей задачей является изучение некоторых повторяющихся структур, используемых при описании алгоритми-
ческих процессов. В этом разделе мы обсудим итерационные структуры, в которых выполнение набора инструкций повторя-
ется в циклическом режиме. В следующем разделе рассматривается метод рекурсии. Читатель также сможет познакомиться
с некоторыми популярными алгоритмами – последовательного и двоичного поиска, а также с алгоритмом сортировки мето-
дом вставки. Начнем с рассмотрения алгоритма последовательного поиска.
Алгоритм последовательного поиска. Рассмотрим задачу поиска в списке некоторого заданного значения. Необходи-
мо разработать алгоритм, позволяющий установить, есть ли заданное значение в списке. Если это значение в списке присут-
ствует, поиск будет считаться успешным, в противном случае будем считать его завершившимся неудачей. Будем считать,
что список отсортирован согласно некоторому правилу, позволяющему упорядочить его элементы. Например, если это спи-
сок имен, будем считать, что имена в нем расположены в алфавитном порядке. Если же это список числовых значений, бу-
дем полагать, что его элементы расположены в порядке возрастания.
Давайте попробуем представить, как бы мы действовали при поиске определенного имени в списке гостей, содержащем
около 20 фамилий. В данном случае можно было бы просмотреть весь список от начала и до конца, сравнивая каждый его
элемент с искомым именем. Если требуемое имя будет найдено, поиск завершится успешно. Однако, если будет достигнут
конец списка или обнаружено имя, расположенное по алфавиту после искомого, поиск завершится неудачей. (Не забывайте,
что список упорядочен в алфавитном порядке, поэтому если будет найдено имя, расположенное по алфавиту после требуе-
мого, то это означает, что нужного нам имени в списке нет.) Таким образом, наша задача – выполнять последовательный
просмотр элементов списка в направлении сверху вниз до тех пор, пока не будут проверены все имена или нужное нам имя
не будет найдено.
Страницы
- « первая
- ‹ предыдущая
- …
- 84
- 85
- 86
- 87
- 88
- …
- следующая ›
- последняя »
