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]. Найти количество различных чисел среди
элементов этого массива.
Решение. (1 вариант)
i := 1; k := 1;
{инвариант: k - количество различных чисел среди x[1]..x[i]}
while i <> n do begin
| i := i + 1;
| if x[i] <> x[i-1] then begin
| | k := k + 1;
| end;
end;
(2 вариант) Искомое число на 1 больше количества тех чисел
i из 1..n-1, для которых x[i] <> x[i+1].
k := 1;
for i := 1 to n-1 do begin
| if x[i]<> x[i+1] then begin
| | k := k + 1;
| end;
end;
1.2.6. (Сообщил А.Л.Брудно.) Прямоугольное поле m на n раз-
бито на mn квадратных клеток. Некоторые клетки покрашены в чер-
ный цвет. Известно, что все черные клетки могут быть разбиты на
несколько непересекающихся и не имеющих общих вершин черных пря-
моугольников. Считая, что цвета клеток даны в виде массива типа
array [1..m] of array [1..n] of boolean;
подсчитать число черных прямоугольников, о которых шла речь.
Число действий должно быть порядка m*n.
Решение. Число прямоугольников равно числу их левых верхних
углов. Является ли клетка верхним углом, можно узнать, посмотрев
на ее цвет, а также цвет верхнего и левого соседей. (Не за-
будьте, что их может не быть, если клетка с краю.)
1.2.7. Дан массив x: array [1..n] of integer. Найти коли-
чество различных чисел среди элементов этого массива. (Число
действий должно быть порядка n*n.)
1.2.8. Та же задача, если требуется, чтобы количество
действий было порядка n* log n. (Указание. Смотри главу о сорти-
ровке.)
1.2.9. Та же задача, если известно, что все элементы масси-
ва - числа от 1 до k и число действий должно быть порядка n+k.
1.2.10. Дан массив x [1]..x[n] целых чисел. Не используя
других массивов, переставить элементы массива в обратном поряд-
ке.
Решение. Числа x [i] и x [n+1-i] нужно поменять местами для
всех i, для которых i < n + 1 - i, т.е. 2*i < n + 1 <=> 2*i <= n
<=> i <= n div 2:
for i := 1 to n div 2 do begin
| ...обменять x [i] и x [n+1-i];
end;
1.2.11. (из книги Д.Гриса) Дан массив целых чисел
x[1]..x[m+n], рассматриваемый как соединение двух его отрезков:
начала x[1]..x[m] длины m и конца x[m+1]..x[m+n] длины n. Не ис-
пользуя дополнительных массивов, переставить начало и конец.
(Число действий порядка m+n.)
Решение. (1 вариант). Перевернем (расположим в обратном по-
рядке) отдельно начало и конец массива, а затем перевернем весь
массив как единое целое.
(2 вариант, А.Г.Кушниренко). Рассматривая массив записанным
по кругу, видим, что требуемое действие - поворот круга. Как из-
вестно, поворот есть композиция двух осевых симметрий.
(3 вариант). Рассмотрим более общую задачу - обмен двух
участков массива x[p+1]..x[q] и x[q+1]..x[s]. Предположим, что
длина левого участка (назовем его A) не больше длины правого
(назовем его B). Выделим в B начало той же длины, что и A, назо-
вем его B1, а остаток B2. (Так что B = B1 + B2, если обозначать
плюсом приписывание массивов друг к другу.) Нам надо из A + B1 +
B2 получить B1 + B2 + A. Меняя местами участки A и B1 - они име-
ют одинаковую длину, и сделать это легко,- получаем B1 + A + B2,
и осталось поменять местами A и B2. Тем самым мы свели дело к
перестановке двух отрзков меньшей длины. Итак, получаем такую
схему программы:
p := 0; q := m; r := m + n;
{инвариант: осталось переставить x[p+1]..x[q], x[q+1]..x[s]}
while (p <> q) and (q <> s) do begin
| {оба участка непусты}
| if (q - p) <= (s - q) then begin
| | ..переставить x[p+1]..x[q] и x[q+1]..x[q+(q-p)]
| | pnew := q; qnew := q + (q - p);
| | p := pnew; q := qnew;
| end else begin
| | ..переставить x[q-(r-q)+1]..x[q] и x[q+1]..x[r]
| | qnew := q - (r - q); rnew := q;
| | q := qnew; r := rnew;
| end;
end;
Оценка времени работы: на очередном шаге оставшийся для обработ-
ки участок становится короче на длину A; число действий при этом
также пропорционально длине A.
1.2.12. Коэффициенты многочлена хранятся в массиве a: array
[0..n] of integer (n - натуральное число, степень многочлена).
Вычислить значение этого многочлена в точке x (т. е. a[n]*(x в
степени n)+...+a[1]*x+a[0]).
Решение. (Описываемый алгоритм называется схемой Горнера.)
k := 0; y := a[n];
{инвариант: 0 <= k <= n,
y= a[n]*(x в степени k)+...+a[n-1]*(x в степени k-1)+...+
+ a[n-k]*(x в степени 0)}
while k<>n do begin
| k := k + 1;
| y := y * x + a [n - k];
end;
1.2.13. (Для знакомых с основами анализа. Сообщил А.Г.Куш-
ниренко.) Дополнить алгоритм вычисления значения многочлена в
заданной точке по схеме Горнера вычислением значения его произ-
водной в той же точке.
Решение. Добавление нового коэффициента соответствует пере-
ходу от многочлена P(x) к многочлену P(x)*x + c. Его производная
в точке x равна P'(x)*x + P(x). (Это решение обладает забавным
свойством: не надо знать заранее степень многочлена. Если требо-
вать выполнения этого условия, да еще просить вычислять только
значение производной, не упоминая о самом многочлене, получается
не такая уж простая задача.)
1.2.14. В массивах
a:array [0..k] of integer и b: array [0..l] of integer
хранятся коэффициенты двух многочленов степеней k и l. Помес-
тить в массив c: array [0..m] of integer коэффициенты их произ-
ведения. (Числа k, l, m - натуральные, m = k + l; элемент мас-
сива с индексом i содержит коэффициент при x в степени i.)
Решение.
for i:=0 to m do begin
| c[i]:=0;
end;
for i:=0 to k do begin
| for j:=0 to l do begin
| | c[i+j] := c[i+j] + a[i]*b[j];
| end;
end;
1.2.15. Предложенный выше алгоритм перемножения многочленов
требует порядка n*n действий для перемножения двух многочленов
степени n. Придумать более эффективный (для больших n) алгоритм,
которому достаточно порядка (n в степени (log 4)/(log 3))
действий.
Указание. Представим себе, что надо перемножить два многоч-
лена степени 2k. Их можно представить в виде
A(x)*x^k + B(x) и C(x)*x^k + D(x)
(здесь x^k обозначает x в степени k). Произведение их равно
A(x)C(x)*x^{2k} + (A(x)D(x)+B(x)C(x))*x^k + B(x)D(x)
Естественный способ вычисления AC, AD+BC, BD требует четырех ум-
ножений многочленов степени k, однако их количество можно сокра-
тить до трех с помощью такой хитрости: вычислить AC, BD и
(A+B)(C+D), а затем заметить, что AD+BC=(A+B)(C+D)-AC-BD.
1.2.16. Даны два возрастающих массива x: array [1..k] of
integer и y: array [1..l] of integer. Найти количество общих
элементов в этих массивах (т. е. количество тех целых t, для ко-
торых t = x[i] = y[j] для некоторых i и j). (Число действий по-
рядка k+l.)
Решение.
k1:=0; l1:=0; n:=0;
{инвариант: 0<=k1<=k; 0<=l1<=l; искомый ответ = n + количество
общих элементов в x[k1+1]...x[k] и y[l1+1]..y[l]}
while (k1 <> k) and (l1 <> l) do begin
| if x[k1+1] < y[l1+1] then begin
| | k1 := k1 + 1;
| end else if x[k1+1] > y[l1+1] then begin
| | l1 := l1 + 1;
| end else begin {x[k1+1] = y[l1+1]}
| | k1 := k1 + 1;
| | l1 := l1 + 1;
| | n := n + 1;
| end;
end;
{k1 = k или l1 = l, поэтому одно из множеств, упомянутых в
инварианте, пусто, а n равно искомому ответу}
