ВУЗ:
2. Приведите примеры алгоритмов, относящихся к каждому из следующих классов: Θ(lgn), Θ(n), Θ(n
2
).
3. Перечислите следующие классы в порядке убывания их эффективности: Θ(n
2
), Θ(lgn), Θ(n), Θ(n
3
).
4. Проанализируйте следующую задачу и предлагаемый ответ. Является ли этот ответ правильным? Поясните свои вы-
воды.
Задача. Предположим, что в коробке находятся три карточки. У одной из них обе стороны черного цвета, у второй обе
стороны красного цвета, а у третьей одна сторона черного цвета, а другая – красного. Из коробки вынимают одну карточку,
и вам разрешается посмотреть на одну из ее сторон. Какова вероятность того, что вторая сторона этой карточки того же цве-
та, что и та, которую вам показали?
Предлагаемый ответ. Одна вторая. Предположим, что показанная вам сторона карточки была красного цвета. (Рассу-
ждения будут аналогичны и в том случае, если она будет черного цвета, так как задача симметрична.) Из трех карточек толь-
ко у двух есть красная сторона. Следовательно, карточка, которую вы увидели, – одна из этих двух. У одной из этой пары
карточек вторая сторона красная, а у другой – черная. Следовательно, вторая сторона у выбранной из коробки карточки с
равной вероятностью может быть как черной, так и красной.
5. Приведенный ниже программный сегмент используется, чтобы вычислить частное (не принимая во внимание оста-
ток) двух целых положительных чисел (делимого и делителя) путем подсчета, сколько раз делитель можно вычесть из дели-
мого, пока оставшаяся часть станет меньше делителя. Например, при делении по этому методу числа 7 на 3 получится 2, так
как число 3 можно вычесть из 7 дважды. Правильно ли составлена эта программа? Обоснуйте свои выводы.
Счетчик ← 0;
Остаток ← Делимое;
repeat {Остаток ← Остаток – Делитель;
Счетчик ← Счетчик + 1}
until (Остаток < Делитель)
Частное ← Счетчик
6. Приведенный ниже программный сегмент предназначен для определения произведения двух неотрицательных целых
чисел X и Y посредством вычисления суммы X копий числа Y. Другими словами, выражение 3 × 4 вычисляется как сумма
трех четверок. Правильно ли составлена эта программа? Обоснуйте это.
Произведение ← Y;
Счетчик ← 1;
while (Счетчик < X) do
{Произведение ← Произведение + Y;
Счетчик ← Счетчик + 1}
7. Приняв как предусловие, что значение N – целое положительное число, установите инвариант цикла, который приво-
дит к заключению, что по окончании приведенной ниже программы переменной Сумма будет присвоено значение, равное 0
+ 1 + ... + N.
Сумма ← 0;
I ← 0;
while (I < N) do
{I ← I + 1;
Сумма ← Сумма + I}
Приведите аргументы в пользу того, что эта программа действительно завершится.
8. Предположим, что программа и выполняющая ее аппаратура были формально проверены на корректность. Гаранти-
рует ли это правильность их работы?
Упражнения
1. Приведите примеры последовательности этапов, удовлетворяющей неформальному определению алгоритма, приве-
денному в начале раздела 4.1, но не удовлетворяющей определению, приведенному на рис. 4.1.
2. Объясните различие между неоднозначностью в предложенном алгоритме и неоднозначностью в представлении ал-
горитма.
3. Поясните, как использование примитивов помогает устранить неоднозначность в представлении алгоритмов?
4. Представляет ли следующая программа алгоритм в строгом смысле этого слова? Поясните свой ответ.
Счетчик ← 0;
while (Счетчик ≠ 5) do
{Счетчик ← Счетчик + 2}
5. По какой причине приведенная ниже последовательность этапов не образует алгоритм?
Этап 1. Провести отрезок прямой линии, соединяющий точки с координатами (2, 5) и (6, 11).
Этап 2. Провести отрезок прямой линии, соединяющий точки с координатами (1, 3) и (3, 6).
Этап 3. Провести окружность с радиусом 2 и центром в точке пересечения проведенных отрезков.
6. Перепишите следующий сегмент программы, используя структуру repeat-until вместо while-do. Убедитесь,
что новая версия программы печатает те же значения, что и исходная.
Счетчик ← 2;
while (Счетчик < 7) do
{напечатать значение переменной Счетчик;
Счетчик ← Счетчик +1}
Страницы
- « первая
- ‹ предыдущая
- …
- 101
- 102
- 103
- 104
- 105
- …
- следующая ›
- последняя »
