ВУЗ:
until (Счетчик = 1)
22. Разработайте рекурсивную версию алгоритма Евклида (вопрос 3 к разделу 4.2).
23. Предположим, что на вход процедур Testl и Test2, приведенных ниже, передано значение 1. Чем будут отли-
чаться напечатанные этими процедурами результаты?
procedure Test1 (Счетчик)
if (Счетчик ≠ 5)
then {напечатать значение параметра Счетчик;
выполнить процедуру Test1(Счетчик + 1)}
procedure Test2 (Счетчик)
if (Счетчик ≠ 5)
then {выполнить процедуру Test2(Счетчик + 1);
напечатать значение параметра Счетчик}
24. Определите основные составляющие механизма управления в предыдущей задаче. В частности, какое условие вы-
зывает окончание процесса? Где происходит модификация состояния процесса, приближающая его к условию завершения?
Где инициализируется состояние управляющего процесса?
25. Разработайте алгоритм генерации последовательности целых положительных чисел (в возрастающем порядке), ко-
торые имеют только два простых множителя – 2 и 3, т.е. программа должна генерировать последовательность чисел 2, 3, 4, 6,
8, 9, 12, 16, 18, 24, 27, ... . Представляет ли эта программа алгоритм в строгом смысле этого слова?
26. Ответьте на следующие вопросы применительно к списку имен Alice, Byron, Carol, Duane, Elaine, Floyd, Gene,
Henry, Iris.
а) Какой алгоритм поиска (последовательный или двоичный) позволит быстрее найти имя Gene?
б) Какой алгоритм поиска (последовательный или двоичный) позволит быстрее найти имя Alice?
в) Какой алгоритм поиска (последовательный или двоичный) позволит быстрее обнаружить отсутствие в списке имени
Bruce?
г) Какой алгоритм поиска (последовательный или двоичный) позволит быстрее обнаружить отсутствие в списке имени
Sue?
д) Сколько элементов будет рассмотрено при поиске имени Elaine с использованием метода последовательного поиска?
Сколько элементов будет рассмотрено при поиске этого имени с использованием метода двоичного поиска?
27. По определению факториал числа 0 равен 1. Факториал целого положительного числа – это произведение данного
целого положительного числа и факториала предшествующего ему целого положительного числа. Для обозначения факто-
риала целого положительного числа п используется запись п!. Таким образом, факториал числа 3 (обозначается как 3!) – это
3!= 3*(2!)= 3*(2*(1!))= 3*(2*(1*(0!))) = 3*(2*(1*(1))) = 6. Разработайте рекурсивный алгоритм вычисления факториала задан-
ного числа.
28. а) Предположим, что вам необходимо отсортировать список из пяти имен и что вы уже разработали раньше алго-
ритм для сортировки списка из четырех имен. Разработайте алгоритм сортировки списка из пяти имен, использующий ранее
разработанный алгоритм.
б) Разработайте рекурсивный алгоритм сортировки списка произвольной длины, основанный на методе, используемом
для решения предыдущей задачи.
29. Головоломка "Ханойская башня" состоит из трех вертикальных стержней, на один из которых надето несколько ко-
лец последовательно уменьшающихся (в направлении снизу вверх) размеров. Задача состоит в том, чтобы переместить набор
колец на другой стержень. Разрешается перемещать только одно кольцо за один ход, причем нельзя надевать большее коль-
цо поверх меньшего. Заметим, что головоломка с одним кольцом решается предельно просто. Если колец несколько, то, пе-
реместив на другой стержень все кольца, кроме наибольшего, наибольшее кольцо можно было бы перенести на третий стер-
жень. После этого задача была бы сведена к перемещению всех остальных колец на наибольшее. Исходя из этого, разрабо-
тайте рекурсивный алгоритм для решения головоломки "Ханойская башня" с произвольным числом колец.
30. Еще один подход к решению головоломки "Ханойская башня" (упр. 29) состоит в следующем. Представьте себе, что
стержни расставлены по кругу в положениях, соответствующих отметкам 4, 8 и 12 часов на циферблате. Кольца, находящие-
ся исходно на одном из стержней, нумеруются числами 1, 2, 3 и т.д., начиная с верхнего. Кольца с нечетными номерами, на-
ходящиеся сверху набора, разрешается перемещать только на стержень, следующий по часовой стрелке, кольца с четными номе-
рами можно перемещать только против часовой стрелки (при условии, что такое перемещение не приведет к помещению больше-
го кольца над меньшим). Учитывая вышеизложенные требования, вы всегда должны выбирать кольцо с наибольшим номером из
числа тех, которые доступны для перемещения. Используя такой подход, разработайте нерекурсивный алгоритм решения голово-
ломки "Ханойская башня".
31. Разработайте циклический и рекурсивный алгоритмы для распечатки дневной заработной платы рабочего, который
в каждый последующий день получает вдвое больше, чем в предыдущий (первый платеж равен одному пенни), за 30 дней
работы. С какими проблемами, касающимися хранения данных, вам придется столкнуться при реализации вашего решения
Страницы
- « первая
- ‹ предыдущая
- …
- 103
- 104
- 105
- 106
- 107
- …
- следующая ›
- последняя »
