и впишем в инвариант условия 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) состоит из объедине-
* * * * ния вертикальных столбцов убывающей высоты.
* * * * * Идея решения состоит в том, чтобы "двигаться
вдоль его границы", спускаясь по верхнему его краю, как по
лестнице. Координаты движущейся точки обозначим . Введем
еще одну переменную s и будем поддерживать истинность такого ус-
ловия:
находится сразу над k-ым столбцом;
s - число точек в предыдущих столбцах.
Формально:
l - минимальное среди тех l >= 0, для которых не принад-
лежит X;
s - число пар натуральных x, y, для которых x < k и при-
надлежит X.
Обозначим эти условия через (И).
k := 0; l := 0;
while "<0,l> принадлежит X" do begin
| l := l + 1;
end;
{k = 0, l - минимальное среди тех l >= 0,
для которых не принадлежит X }
s := 0;
{инвариант: И}
while not (l = 0) do begin
| s := s + l;
| {s - число точек в столбцах до k-го включительно}
| k := k + 1;
| {точка лежит вне X, но, возможно, ее надо сдвинуть
| вниз, чтобы восстановить И }
| while (l <> 0) and (" не принадлежит 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;
