Жанр: Учеба
Программирование в теоремах и задачах
ПРОГРАММИРОВАНИЕ: ТЕОРЕМЫ И ЗАДАЧИ
НЕСКОЛЬКО ЗАМЕЧАНИЙ ВМЕСТО ПРЕДИСЛОВИЯ
Книга написана по материалам занятий программированием со
школьниками математических классов школы N 57.
Книга написана в убеждении, что программирование имеет свой
предмет, не сводящийся ни к конкретным языкам и системам, ни к
методам построения быстрых алгоритмов.
Кто-то однажды сказал, что можно убедить в правильности алгоритма,
но не в правильности программы. Одна из целей книги - попытаться
продемонстрировать, что это не так.
В принципе, возможность практического исполнения программ не является
непременным условием изучения программирования. Однако
она является сильнейшим стимулом - без такого стимула вряд ли у
кого хватит интереса и терпения.
Выбранный жанр книги по необходимости ограничивает ее "программированием
в малом", оставляя в стороне необходимую часть программистского
образования - работу по модификации больших программ.
Автор продолжает мечтать о наборе учебных программных систем
эталонного качества, доступных для модификации школьниками.
Кажется, Хоар сказал, что эстетическая прелесть программы - это
не архитектурное излишество, а то, что отличает в программировании
успех от неудачи. Если, решая задачи из этой книги, читатель
почувствует прелесть хорошо написанной программы, в которой "ни
убавить, ни прибавить", и сомнения в правильности которой кажутся
нелепыми, то автор будет считать свою цель достигнутой.
Характер глав различен: в одних предлагается набор мало связанных
друг с другом задач с решениями, в других по существу излагается
один-единственный алгоритм. Темы глав во многом пересекаются,
и мы предпочли кое-какие повторения формальным ссылкам.
Уровень трудности задач и глав весьма различен. Мы старались
включить как простые задачи, которые могут быть полезны для начинающих,
так и трудные задачи, которые могут посадить в лужу и
сильного школьника. (Хоть и редко, но это бывает полезно.)
В качестве языка для записи программ был выбран паскаль Паскаль
достачно прост и естествен, имеет неплохие реализации (например,
Turbo Pascal 3.0 и 5.0 фирмы Borland) и позволяет записать решения
всех рассматриваемых задач. Возможно, Модула-2 или Оберон
были бы более изящным выбором, но пока что они труднее доступны.
Неудачный опыт писания "популярных" учебников по программированию
учит: никакого сюсюканья! писать надо так, чтобы потом самим
было не стыдно прочесть.
Практически все задачи и алгоритмы, разумеется, не являются новыми.
(В некоторых редких случаях приведены ссылки на конкретную
книгу или конкретного человека. См. также список книг для
дальнейшего чтения.) Вместе с тем мы надеемся, что в некоторых
случаях алгоритмы (и особенно доказательства) изложены более коротко
и отчетливо.
Это не только и не столько учебник для школьника, сколько справочник
и задачник для преподавателя, готовящегося к занятию.
Об "авторских правах": право формулировать задачу и объяснять её
решение является неотчуждаемым естественным правом всякого, кто
на это способен. В соответствии с этим текст (в ASCII и TeX-версиях)
является свободно распространяемыми. С ним можно делать
всё, что угодно, и если Вы внесли в него ошибки, не указав, что
они принадлежат Вам, или использовали текст в коммерческих целях,
не поделившись прибылью - Бог Вам судья.
Благодарности. Я рад случаю поблагодарить всех, с кем имел честь
сотрудничать, преподавая программирование, особенно тех, кто был
"по другую сторону баррикады".
Н Е П О К У П А Й Т Е Э Т У К Н И Г У !
(Предупреждение автора)
В этой книге ничего не говорится об особенностях BIOSа,
DOSа, OSа, GEМа и Windows, представляющих основную сложность при
настоящем программировании.
В ней нет ни слова об объектно-ориентированном программировании,
открывшем новую эпоху в построении дружественных и эффективных
программных систем.
Из нее Вы не узнаете о графических возможностях компьютера,
без которых немыслимо современное программирование, о богатстве
и разнообразии мира видеоадаптеров.
Не рассказано в ней и о написании резидентных программ,
тонкости взаимодействия которых должен знать каждый.
Искусственный интеллект, открывший новые рынки сбыта для
программного обеспечения, обойден презрительным молчанием.
Экспертные системы, которые в скором будущем займут место
на рабочем столе каждого, даже не упоминаются.
Логическое программирование, постепенно вытесняющее устаревший
операторный стиль программирования, не затронуто.
Драматический поворот от баз данных к базам знаний, вызвавший
в жизни новую профессию — инженер знаний — остался незамеченным
автором.
Проблемы отладки и сопровождения программ, занимающие, по
общему мнению профессионалов, 90% в программировании, игнорируются.
В книге используются лишь самые элементарные возможности
паскаля. Обширные возможности, предоставляемые современными интегрированными
программными средами, остаются невостребованными.
(Не говоря уже о том, что паскаль уже вообще устарел, вытесненный
языком Си.)
Игрушечные головоломки, которым посвящена книга, никому не
нужны. Если же перед Вами встанет действительно важная задача,
неужели Вы не справитесь с ней сами, без непрошеных учителей и
советчиков?
Короче говоря, покупать эту книгу глупо - особенно теперь,
когда выходит столько переводных руководств, написанных в цивилизованных
странах настоящими профессионалами.
1.1. Задачи без массивов
1.1.1. Даны две целые переменные a, b. Составить фрагмент
программы, после исполнения которого значения переменных поменялись
бы местами (новое значение a равно старому значению b и наоборот).
Решение. Введем дополнительную целую переменную t.
t := a;
a := b;
b := t;
Попытка обойтись без дополнительной переменной, написав
a := b;
b := a;
не приводит к цели (безвозвратно утрачивается начальное значение
переменной a).
1.1.2. Решить предыдущую задачу, не используя дополнительных
переменных (и предполагая, что значениями целых переменных
могут быть произвольные целые числа).
Решение. (Начальные значения a и b обозначим a0, b0.)
a := a + b; {a = a0 + b0, b = b0}
b := a - b; {a = a0 + b0, b = a0}
a := a - b; {a = b0, b = a0}
1.1.3. Дано целое число а и натуральное (целое неотрицательное)
число n. Вычислить а в степени n. Другими словами, необходимо
составить программу, при исполнении которой значения
переменных а и n не меняются, а значение некоторой другой переменной
(например, b) становится равным а в степени n. (При этом
разрешается использовать и другие переменные.)
Решение. Введем целую переменную k, которая меняется от 0
до n, причем поддерживается такое свойство: b = (a в степени
k).
k := 0; b := 1;
{b = a в степени k}
while k "" n do begin
| k := k + 1;
| b := b * a;
end;
Другое решение той же задачи:
k := n; b := 1;
{a в степени n = b * (a в степени k)}
while k "" 0 do begin
| k := k - 1;
| b := b * a;
end;
1.1.4. Решить предыдущую задачу, если требуется, чтобы число
действий (выполняемых операторов присваивания) было порядка
log n (то есть не превосходило бы C*log n для некоторой константы
C; log n - это степень, в которую нужно возвести 2, чтобы получить
n).
Решение. Внесем некоторые изменения во второе из предложенных
решений предыдущей задачи:
k := n; b := 1; c:=a;
{a в степени n = b * (c в степени k)}
while k "" 0 do begin
| if k mod 2 = 0 then begin
| | k:= k div 2;
| | c:= c*c;
| end else begin
| | k := k - 1;
| | b := b * c;
| end;
end;
Каждый второй раз (не реже) будет выполняться первый вариант
оператора выбора (если k нечетно, то после вычитания единицы
становится четным), так что за два цикла величина k уменьшается
по крайней мере вдвое.
1.1.5. Даны натуральные числа а, b. Вычислить произведение
а*b, используя в программе лишь операции +, -, =, "".
Решение.
var a, b, c, k : integer;
k := 0; c := 0;
{инвариант: c = a * k}
while k "" b do begin
| k := k + 1;
| c := c + a;
end;
{c = a * k и k = b, следовательно, c = a * b}
1.1.6. Даны натуральные числа а и b. Вычислить их сумму
а+b. Использовать операторы присваивания лишь вида
"переменная1" := "переменная2",
"переменная" := "число",
"переменная1" := "переменная2" + 1.
Решение.
{инвариант: c = a + k}
1.1.7. Дано натуральное (целое неотрицательное) число а и
целое положительное число d. Вычислить частное q и остаток r при
делении а на d, не используя операций div и mod.
Решение. Согласно определению, a = q * d + r, 0 "= r " d.
{a "= 0; d " 0}
r := a; q := 0;
{инвариант: a = q * d + r, 0 "= r}
while not (r " d) do begin
| {r "= d}
| r := r - d; {r "= 0}
| q := q + 1;
end;
1.1.8. Дано натуральное n, вычислить n!
(0!=1, n! = n * (n-1)!).
1.1.9. Последовательность Фибоначчи определяется так:
a(0)= 1, a(1) = 1, a(k) = a(k-1) + a(k-2) при k "= 2. Дано n,
вычислить a(n).
1.1.10. Та же задача, если требуется, чтобы число операций
было пропорционально log n. (Переменные должны быть целочисленными.)
Указание. Пара соседних чисел Фибоначчи получается из предыдущей
умножением на матрицу
|1 1|
|1 0|
так что задача сводится к возведению матрицы в степень n. Это
можно сделать за C*log n действий тем же способом, что и для чисел.
1.1.11. Дано натуральное n, вычислить 1/0!+1/1!+...+1/n!.
1.1.12. То же, если требуется, чтобы количество операций
(выполненных команд присваивания) было бы не более C*n для некоторой
константы С.
Решение. Инвариант: sum = 1/1! +...+ 1/k!, last = 1/k!
(важно не вычислять заново каждый раз k!).
1.1.13. Даны два натуральных числа a и b, не равные нулю
одновременно. Вычислить НОД (a,b) - наибольший общий делитель а
и b.
Решение (1 вариант).
if a " b then begin
| k := a;
end else begin
| k := b;
end;
{k = max (a,b)}
{инвариант: никакое число, большее k, не является об-
щим делителем}
while not (((a mod k)=0) and ((b mod k)=0)) do begin
| k := k - 1;
end;
{k - общий делитель, большие - нет}
(2 вариант - алгоритм Евклида). Будем считать , что НОД
(0,0) = 0. Тогда НОД (a,b) = НОД (a-b,b) = НОД (a,b-a); НОД
(a,0) = НОД (0,a) = a для всех a,b"=0.
m := a; n := b;
{инвариант: НОД (a,b) = НОД (m,n); m,n "= 0 }
while not ((m=0) or (n=0)) do begin
| if m "= n then begin
| | m := m - n;
| end else begin
| | n := n - m;
| end;
end;
if m = 0 then begin
| k := n;
end else begin
| k := m;
end;
1.1.14. Написать модифицированный вариант алгоритма Евклида,
использующий соотношения НОД (a, b) = НОД (a mod b, b) при
a "= b, НОД (a, b) = НОД (a, b mod a) при b "= a.
1.1.15. Даны натуральные а и b, не равные 0 одновременно.
Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b*y.
Решение. Добавим в алгоритм Евклида переменные p, q, r, s
и впишем в инвариант условия m = p*a + q*b; n = r*a + s*b.
m:=a; n:=b; p := 1; q := 0; r := 0; s := 1;
{инвариант: НОД (a,b) = НОД (m,n); m,n "= 0
m = p*a + q*b; n = r*a + s*b.}
while not ((m=0) or (n=0)) do begin
| if m "= n then begin
| | m := m - n; p := p - r; q := q - s;
| end else begin
| | n := n - m; r := r - p; s := s - q;
| end;
end;
if m = 0 then begin
| k :=n; x := r; y := s;
end else begin
| k := m; x := p; y := q;
end;
1.1.16. Решить предыдущую задачу, используя в алгоритме
Евклида деление с остатком.
1.1.17. (Э.Дейкстра). Добавим в алгоритм Евклида дополнительные
переменные u, v, z:
m := a; n := b; u := b; v := a;
{инвариант: НОД (a,b) = НОД (m,n); m,n "= 0 }
while not ((m=0) or (n=0)) do begin
| if m "= n then begin
| | m := m - n; v := v + u;
| end else begin
| | n := n - m; u := u + v;
| end;
end;
if m = 0 then begin
| z:= v;
end else begin {n=0}
| z:= u;
end;
Доказать, что после исполнения алгоритма z равно удвоенному наименьшему
общему кратному чисел a, b: z = 2 * НОК (a,b).
Решение. Заметим, что величина m*u + n*v не меняется в ходе
выполнения алгоритма. Остается воспользоваться тем, что вначале
она равна 2*a*b и что НОД (a, b) * НОК (a, b) = a*b.
1.1.18. Написать вариант алгоритма Евклида, использующий
соотношения
НОД(2*a, 2*b) = 2*НОД(a,b)
НОД(2*a, b) = НОД(a,b) при нечетном b,
не включающий деления с остатком, а использующий лишь деление на
2 и проверку четности. (Число действий должно быть порядка log k
для исходных данных, не превосходящих k.)
Решение.
m:= a; n:=b; d:=1;
{НОД(a,b) = d * НОД(m,n)}
while not ((m=0) or (n=0)) do begin
| if (m mod 2 = 0) and (n mod 2 = 0) then begin
| | d:= d*2; m:= m div 2; n:= n div 2;
| end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
| | m:= m div 2;
| end else if (m mod 2 = 1) and (n mod 2 = 0) then begin
| | n:= n div 2;
| end else if (m mod 2=1) and (n mod 2=1) and (m"=n)then begin
| | m:= m-n;
| end else if (m mod 2=1) and (n mod 2=1) and (m"=n)then begin
| | n:= n-m;
| end;
end;
{m=0 =" ответ=d*n; n=0 =" ответ=d*m}
Оценка числа действий: каждое второе действие делит хотя бы одно
из чисел m и n пополам.
1.1.19. Дополнить алгоритм предыдущей задачи поиском x и y,
для которых ax+by=НОД(a,b).
Решение. (Идея сообщена Д.Звонкиным) Прежде всего заметим,
что одновременое деление a и b пополам не меняет искомых x и y.
Поэтому можно считать, что с самого начала одно из чисел a и b
нечетно. (Это свойство будет сохраняться и далее.)
Теперь попытаемся, как и раньше, хранить такие числа
p,q,r,s, что
m = ap + bq
n = ar + bs
Проблема в том, что при делении, скажем, m на 2 надо разделить p
и q на 2, и они перестанут быть целыми (а станут двоично-рациональными).
Двоично-рациональное число естественно хранить в виде
пары (числитель, показатель степени двойки в знаменателе). В
итоге мы получаем d в виде комбинации a и b с двоично-рациональными
коэффициентами. Иными словами, мы имеем
(2 в степени i)* d = ax + by
для некоторых целых x,y и натурального i. Что делать, если i "
1? Если x и y чётны, то на 2 можно сократить. Если это не так,
положение можно исправить преобразованием
x := x + b
y := y - a
(оно не меняет ax+by). Убедимся в этом. Напомним, что мы считаем,
что одно из чисел a и b нечётно. Пусть это будет a. Если при
этом y чётно, то и x должно быть чётным (иначе ax+by будет нечётным).
А при нечётном y вычитание из него нёчетного a делает y
чётным.
1.1.20. Составить программу, печатающую квадраты всех натуральных
чисел от 0 до заданного натурального n.
Решение.
k:=0;
writeln (k*k);
{инвариант: k"=n, напечатаны все
квадраты до k включительно}
while not (k=n) do begin
| k:=k+1;
| writeln (k*k);
end;
1.1.21. Та же задача, но разрешается использовать из арифметических
операций лишь сложение и вычитание, причем общее число
действий должно быть порядка n.
Решение. Введем переменную k_square (square - квадрат),
связанную с k соотношением k_square = k*k:
k := 0; k_square := 0;
writeln (k_square);
while not (k = n) do begin
| k := k + 1;
| {k_square = (k-1) * (k-1) = k*k - 2*k + 1}
| k_square := k_square + k + k - 1;
| writeln (k_square);
end;
1.1.22. Составить программу, печатающую разложение на простые
множители заданного натурального числа n " 0 (другими словами,
требуется печатать только простые числа и произведение напечатанных
чисел должно быть равно n; если n = 1, печатать ничего
не надо).
Решение (1 вариант).
k := n;
{инвариант: произведение напечатанных чисел и k равно
n, напечатаны только простые числа}
while not (k = 1) do begin
| l := 2;
| {инвариант: k не имеет делителей в интервале (1,l)}
| while k mod l "" 0 do begin
| | l := l + 1;
| end;
| {l - наименьший делитель k, больший 1, следовательно,
| простой}
| writeln (l);
| k:=k div l;
end;
(2 вариант).
k := n; l := 2;
{произведение k и напечатанных чисел равно n; напеча-
танные числа просты; k не имеет делителей, меньших l}
while not (k = 1) do begin
| if k mod l = 0 then begin
| | {k делится на l и не имеет делителей,
| | меньших l, значит, l просто}
| | k := k div l;
| | writeln (l);
| end else begin
| | { k не делится на l }
| | l := l + 1;
| end;
end;
1.1.23. Составить программу решения предыдущей задачи, использующую
тот факт, что составное число имеет делитель, не
превосходящий квадратного корня из этого числа.
Решение. Во втором варианте решения вместо l:=l+1 можно написать
if l*l " k then begin
| l:=k;
end else begin
| l:=l+1;
end;
1.1.24. Проверить, является ли заданное натуральное число
n " 1 простым.
1.1.25. (Для знакомых с основами алгебры). Дано целое гауссово
число n + mi (принадлежащее Z[i]). (a) Проверить, является
ли оно простым (в Z[i]); (б) напечатать его разложение на
простые (в Z[i]) множители.
1.1.26. Разрешим использовать команды write (i) лишь при i
= 0,1,2,...,9. Составить программу, печатающую десятичную запись
заданного натурального числа n " 0. (Случай n = 0 явился
бы некоторым исключением, так как обычно нули в начале числа не
печатаются, а для n = 0 - печатаются.)
Решение.
base:=1;
{base - степень 10, не превосходящая n}
while 10 * base "= n do begin
| base:= base * 10;
end;
{base - максимальная степень 10, не превосходящая n}
k:=n;
{инвариант: осталось напечатать k с тем же числом
знаков, что в base; base = 100..00}
while base "" 1 do begin
| write(k div base);
| k:= k mod base;
| base:= base div 10;
end;
{base=1; осталось напечатать однозначное число k}
write(k);
(Типичная ошибка при решении этой задачи: неправильно обрабатываются
числа с нулями посередине. Приведенный инвариант допускает
случай, когда k " base; в этом случае печатание k начинается
со старших нулей.)
1.1.27. То же самое, но надо напечатать десятичную запись в
обратном порядке. (Для n = 173 надо напечатать 371.)
Решение.
k:= n;
{инвариант: осталось напечатать k в обратном порядке}
while k "" 0 do begin
| write (k mod 10);
| k:= k div 10;
end;
1.1.28. Дано натуральное n. Подсчитать количество решений
неравенства x*x + y*y " n в натуральных (неотрицательных целых)
числах, не используя действий с вещественными числами.
Решение.
k := 0; s := 0;
{инвариант: s = количество решений неравенства
x*x + y*y " n c x " k}
while k*k " n do begin
| ...
| {t = число решений неравенства k*k + y*y " n
| (при данном k) }
| k := k + 1;
| s := s + t;
end;
{k*k "= n, поэтому s = количество всех решений
неравенства}
Здесь ... - пока еще не написанный кусок программы, который
будет таким:
l := 0; t := 0;
{инвариант: t = число решений
неравенства k*k + y*y " n c y " l }
while k*k + l*l " n do begin
| l := l + 1;
| t := t + 1;
end;
{k*k + l*l "= n, поэтому t = число
всех решений неравенства k*k + y*y " n}
1.1.29. Та же задача, но количество операций должно быть
порядка (n в степени 1/2). (В предыдущем решении, как можно
подсчитать, порядка n операций.)
Решение. Нас интересуют точки решетки (с целыми координата-
* ми) в первом квадранте, попадающие внутрь круга
* * * радиуса (n в степени 1/2). Интересующее нас
* * * * множество (назовем его X) состоит из объедине-
* * * * ния вертикальных столбцов убывающей высоты.
* * * * * Идея решения состоит в том, чтобы "двигаться
вдоль его границы", спускаясь по верхнему его краю, как по
лестнице. Координаты движущейся точки обозначим "k,l". Введем
еще одну переменную s и будем поддерживать истинность такого условия:
"k,l" находится сразу над k-ым столбцом;
s - число точек в предыдущих столбцах.
Формально:
l - минимальное среди тех l "= 0, для которых "k,l" не принад-
лежит X;
s - число пар натуральных x, y, для которых x " k и "x,y" при-
надлежит X.
Обозначим эти условия через (И).
k := 0; l := 0;
while ""0,l" принадлежит X" do begin
| l := l + 1;
end;
{k = 0, l - минимальное среди тех l "= 0,
для которых "k,l" не принадлежит X }
s := 0;
{инвариант: И}
while not (l = 0) do begin
| s := s + l;
| {s - число точек в столбцах до k-го включительно}
| k := k + 1;
| {точка "k,l" лежит вне X, но, возможно, ее надо сдвинуть
| вниз, чтобы восстановить И }
| while (l "" 0) and (""k, l-1" не принадлежит X") do begin
| | l := l - 1;
| end;
end;
{И, l = 0, поэтому k-ый столбец и все следующие пусты, а
s равно искомому числу}
Оценка числа действий очевидна: сначала мы движемся вверх не более
чем на (n в степени 1/2) шагов, а затем вниз и вправо - в
каждую сторону не более чем на (n в степени 1/2) шагов.
1.1.30. Даны натуральные числа n и k, n " 1. Напечатать k
десятичных знаков числа 1/n. (При наличии двух десятичных разложений
выбирается то из них, которое не содержит девятки в периоде.)
Программа должна использовать только целые переменные.
Решение. Сдвинув в десятичной записи числа 1/n запятую на k
мест вправо, получим число (10 в степени k)/n. Нам надо напечатать
его целую часть, т. е. разделить (10 в степени k) на n нацело.
Стандартный способ требует использования больших по величине
чисел, которые могут выйти за границы диапазона представимых
чисел. Поэтому мы сделаем иначе (следуя обычному методу "деления
уголком") и будем хранить "остаток" r:
l := 0; r := 1;
{инв.: напечатано l разрядов 1/n, осталось напечатать
k - l разрядов дроби r/n}
while l "" k do begin
| write ( (10 * r) div n);
| r := (10 * r) mod n;
| l := l + 1;
end;
1.1.31. Дано натуральное число n " 1. Определить длину периода
десятичной записи дроби 1/n.
Решение. Период дроби равен периоду в последовательности
остатков (докажите это; в частности, надо доказать, что он не
может быть меньше). Кроме того, в этой последовательности все
периодически повторяющиеся все члены различны, а предпериод имеет
длину не более n. Поэтому достаточно найти (n+1)-ый член последовательности
остатков и затем минимальное k, при котором
(n+1+k)-ый член совпадает с (n+1)-ым.
l := 0; r := 1;
{инвариант: r/n = результат отбрасывания l знаков в 1/n}
while l "" n+1 do begin
| r := (10 * r) mod n;
| l := l + 1;
end;
c := r;
{c = (n+1)-ый член последовательности остатков}
r := (10 * r) mod n;
k := 0;
{r = (n+k+1)-ый член последовательности остатков}
while r "" c do begin
| r := (10 * r) mod n;
| k := k + 1;
end;
1.1.32 (Э. Дейкстра). Функция f с натуральными аргументами
и значениями определена так: f(0) = 0, f(1) = 1, f (2n) = f(n),
f (2n+1) = f (n) + f (n+1). Составить программу вычисления f (n)
по заданному n, требующую порядка log n операций.
Решение.
k := n; a := 1; b := 0;
{инвариант: 0 "= k, f (n) = a * f(k) + b * f (k+1)}
while k "" 0 do begin
| if k mod 2 = 0 then begin
| | l := k div 2;
| | {k = 2l, f(k) = f(l), f (k+1) = f (2l+1) = f(l) + f(l+1),
| | f (n) = a*f(k) + b*f(k+1) = (a+b)*f(l) + b*f(l+1)}
| | a := a + b; k := l;
| end else begin
| | l := k div 2;
| | {k = 2l + 1, f(k) = f(l) + f(l+1),
| | f(k+1) = f(2l+2) = f(l+1),
| | f(n) = a*f(k) + b*f(k+1) = a*f(l) + (a+b)*f(l+1)}
| | b := a + b; k := l;
| end;
end;
{k = 0, f(n) = a * f(0) + b * f(1) = b, что и требовалось}
1.1.33. То же, если f(0) = 13, f(1) = 17, а f(2n) =
43 f(n) + 57 f(n+1), f(2n+1) = 91 f(n) + 179 f(n+1) при n"=1.
Указание. Хранить коэффициенты в выражении f(n) через три
соседних числа.
1.1.34. Даны натуральные числа а и b, причем b " 0. Найти
частное и остаток при делении а на b, оперируя лишь с целыми
числами и не используя операции div и mod, за исключением деления
на 2 четных чисел; число шагов не должно превосходить
C1*log(a/b) + C2 для некоторых констант C1, C2.
Решение.
b1 := b;
while b1 "= a do begin
| b1 := b1 * 2;
end;
{b1 " a, b1 = b * (некоторая степень 2)}
q:=0; r:=a;
{инвариант: q, r - частное и остаток при делении a на b1,
b1 = b * (некоторая степень 2)}
while b1 "" b do begin
| b1 := b1 div 2 ; q := q * 2;
| { a = b1 * q + r, 0 "= r, r " 2 * b1}
| if r "= b1 then begin
| | r := r - b1;
| | q := q + 1;
| end;
end;
{q, r - частное и остаток при делении a на b}
1.2. Массивы.
В следующих задачах переменные x, y, z предполагаются описанными
как array [1..n] of integer (n - некоторое натуральное
число, большее 0), если иное не оговорено явно.
1.2.1. Заполнить массив x нулями. (Это означает, что нужно
составить фрагмент программы, после выполнения которого все значения
x[1]..x[n] равнялись бы нулю, независимо от начального
значения переменной x.)
Решение.
i := 0;
{инвариант: первые i значений x[1]..x[i] равны 0}
while i "" n do begin
| i := i + 1;
| {x[1]..x[i-1] = 0}
| x[i] := 0;
end;
1.2.2. Подсчитать количество нулей в массиве x. (Составить
фрагмент программы, не меняющий значения x, после исполнения которого
значение некоторой целой переменной k равнялось бы числу
нулей среди компонент массива x.)
Решение.
{инвариант: k= число нулей среди x[1]...x[i] }
1.2.3. Не используя оператора присваивания для массивов,
составить фрагмент программы, эквивалентный оператору x:=y.
Решение.
i := 0;
{инвариант: значение y не изменилось, x[l] = y[l] при l "= i}
while i "" n do begin
| i := i + 1;
| x[i] := y[i];
end;
1.2.4. Найти максимум из x[1]..x[n].
Решение.
i := 1; max := x[1];
{инвариант: max = максимум из x[1]..x[i]}
while i "" n do begin
| i := i + 1;
| {max = максимум из x[1]..x[i-1]}
| if x[i] " max then begin
| | max := x[i];
| end;
end;
1.2.5. Дан массив x: array [1..n] of integer, причём x[1]
"= x[2] "= ... "= x[n
...Закладка в соц.сетях
