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) состоит из объедине-
