ВУЗ:
на реальной машине?
32. Разработайте алгоритм для нахождения значения квадратного корня из положительного числа с помощью следую-
щего метода. В качестве первого приближения выбирается само это число, а последующие приближения получаются из пре-
дыдущих путем вычисления среднего арифметического для предыдущего приближения и числа, полученного при делении ис-
ходного числа на предыдущее приближение. Проанализируйте возможности управления этим повторяющимся процессом. В част-
ности, какое условие должно использоваться для его окончания?
33. Разработайте алгоритм, который печатает все возможные варианты перестановки символов в строке из пяти различ-
ных символов.
34. Разработайте алгоритм, который в заданном списке имен находит самое длинное имя. Определите, как поведет себя
алгоритм, предложенный вами в качестве решения, если "самых длинных" имен в списке будет несколько. В частности, как
поведет себя ваш алгоритм, если все имена в списке будут одной длины?
35. Разработайте алгоритм, который в заданном списке из пяти или более чисел находит пять наименьших и пять наи-
больших чисел, не сортируя полностью весь список.
36. Расположите имена Brenda, Doris, Raymond, Steve, Timothy и William в таком порядке, который при использовании
алгоритма сортировки методом вставки потребует выполнения наименьшего числа сравнений (рис. 4.11).
37. Какое максимальное количество элементов может быть проверено при применении алгоритма двоичного поиска
(рис. 4.13) к списку, содержащему 4000 строк? Как оно соотносится с аналогичным значением для метода последовательного
поиска (рис. 4.6)?
38. Используя нотацию тета-классов, классифицируйте традиционные школьные алгоритмы для сложения и умножения в
столбик. Другими словами, определите, сколько отдельных операций сложения необходимо выполнить при суммировании двух
чисел значностью п и сколько отдельных операций умножения потребуется для их перемножения.
39. Иногда небольшое изменение условия задачи может вызвать существенные изменения в способе ее решения. Например,
найдите простой алгоритм решения следующей задачи и определите его тета-класс.
Разделите группу людей на две непересекающиеся подгруппы (произвольных размеров), такие, чтобы разность между
суммами возрастов членов этих подгрупп была максимальной. Теперь измените условие задачи так, чтобы требуемая раз-
ность была минимальной, и вновь классифицируйте ваше решение.
40. Из следующего списка выделите несколько чисел, сумма которых равна 3165. Насколько эффективен ваш метод ре-
шения задачи?
26, 39, 104, 195, 403, 504, 793, 995, 1156, 1673
41. Завершится ли цикл в следующей программе? Поясните свой ответ. Объясните, что могло бы случиться, если бы эта
программа в действительности выполнялась машиной (см. раздел 1.7)
X ← 0;
Y ← 1/2;
while (X ≠ 1) do
{X ← X+Y;
Y ← Y-2}
42. Следующий фрагмент программы разработан для вычисления произведения двух неотрицательных целых чисел X и
Y путем вычисления суммы X копий числа Y. Выражение 3 × 4 вычисляется посредством нахождения суммы трех четверок.
Правильно ли составлен данный фрагмент? Поясните свой ответ.
Произведение ← 0;
Счетчик ← 0;
repeat {Произведение ← Произведение + Y;
Счетчик ← Счетчик + 1}
until (Счетчик = X)
43. Следующий фрагмент программы составлен для определения, какое из двух целых чисел X и Y является большим.
Является ли этот фрагмент правильным? Поясните свой ответ.
Разность ← X—Y;
if (Разность положительна)
then {напечатать "X больше Y"}
else {напечатать "Y больше X"}
44. Следующий фрагмент программы должен находить наибольший элемент в непустом списке целых чисел. Правиль-
но ли он составлен? Поясните свой ответ.
Значение ← значение первого элемента списка;
Текущий ← значение первого элемента списка;
while (Текущий ≠ последнему элементу списка) do
{if (Текущий > Значение)
then {Значение ← Текущий}
Текущий ← значение следующего элемента списка}
45. а) Определите предусловия для алгоритма последовательного поиска. Установите инвариант цикла для структуры
while в этой программе, который, будучи объединен с условием окончания цикла, предполагает, что по окончании этого
цикла алгоритм правильно сообщит об успехе или неудаче.
б) Приведите аргументы в пользу того, что цикл while действительно завершается.
46. Опираясь на предусловие для приведенной ниже программы, утверждающее, что параметрам X и Y присвоены не-
отрицательные целые значения, определите инвариант цикла ее структуры while, который, будучи объединен с указанным
условием окончания, предполагает, что значение переменной Z по завершении цикла будет X – Y.
Z ← X;
J ← 0;
while (J < Y) do
Страницы
- « первая
- ‹ предыдущая
- …
- 104
- 105
- 106
- 107
- 108
- …
- следующая ›
- последняя »
