Глава 1. Переменные, выражения, присваивания. 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) состоит из объедине- * * * * ния вертикальных столбцов убывающей высоты. * * * * * Идея решения состоит в том, чтобы "двигаться вдоль его границы", спускаясь по верхнему его краю, как по лестнице. Координаты движущейся точки обозначим . Введем еще одну переменную 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; 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 равно искомому ответу} Замечание. В третьей альтернативе достаточно было бы увеличивать одну из переменных k1, l1; вторая добавлена для симметрии. 1.2.17. Решить предыдущую задачу, если известно лишь, что x[1] <= ... <= x[k] и y[1] <= ... <= y[l] (возрастание заменено неубыванием). Решение. Условие возрастания было использовано в третьей альтернативе выбора: сдвинув k1 и l1 на 1, мы тем самым уменьша- ли на 1 количество общих элементов в x[k1+1]...x[k] и x[l1+1]...x[l]. Теперь это придется делать сложнее. ... end else begin {x[k1+1] = y[l1+1]} | t := x [k1+1]; | while (k1 k) or (l1 <> l) do begin | if k1 = k then begin | | {l1 < l} | | l1 := l1 + 1; | | z[k1+l1] := y[l1]; | end else if l1 = l then begin | | {k1 < k} | | k1 := k1 + 1; | | z[k1+l1] := x[k1]; | end else if x[k1+1] <= y[l1+1] then begin | | k1 := k1 + 1; | | z[k1+l1] := x[k1]; | end else if x[k1+1] >= y[l1+1] then begin | | l1 := l1 + 1; | | z[k1+l1] := y[l1]; | end else begin | | { такого не бывает } | end; end; {k1 = k, l1 = l, массивы соединены} Этот процесс можно пояснить так. Пусть у нас есть две стопки карточек, отсортированных по алфавиту. Мы соединяем их в одну стопку, выбирая каждый раз ту из верхних карточек обеих стопок, которая идет раньше в алфавитном порядке. 1.2.20. Даны два массива x[1] <= ... <= x[k] и y[1] <= ... <= y[l]. Найти их "пересечение", т.е. массив z[1] <= ... <= z[m], содержащий их общие элементы, причем кратность каждого элемента в массиве z равняется минимуму из его кратностей в мас- сивах x и y. Число действий порядка k+l. 1.2.21. Даны два массива x[1]<=...<=x[k] и y[1]<=...<=y[l] и число q. Найти сумму вида x[i]+y[j], наиболее близкую к числу q. (Число действий порядка k+l, дополнительная память - фиксиро- ванное число целых переменных, сами массивы менять не разрешает- ся.) Указание. Надо найти минимальное расстояние между элемента- ми x[1]<=...<=x[k] и q-y[l]<=..<=q-y[1], что нетрудно сделать в ходе их слияния в один (воображаемый) массив. 1.2.22. (из книги Д.Гриса) Некоторое число содержится в каждом из трех целочисленных неубывающих массивов x[1] <= ... <= x[p], y[1] <= ... <= y[q], z[1] <= ... <= z[r]. Найти одно из таких чисел. Число действий должно быть порядка p + q + r. Решение. p1:=1; q1=1; r1:=1; {инвариант: x[p1]..x[p], y[q1]..y[q], z[r1]..z[r] содержат общий элемент } while not ((x[p1]=y[q1]) and (y[q1]=z[r1])) do begin | if x[p1] первые элементы оставшихся частей равны} while not eq do begin | s := 1; k := 1; | {a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]} | while k <> n do begin | | k := k + 1; | | if a[k][b[k]] < a[s][b[s]] then begin | | | s := k; | | end; | end; | {a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]} | b [s] := b [s] + 1; | for k := 2 to n do begin | | eq := eq and (a[1][b[1]] = a[k][b[k]]); | end; end; writeln (a[1][b[1]]); 1.2.25. Приведенное решение предыдущей задачи требует по- рядка m*n*n действий. Придумать способ с числом действий порядка m*n. Указание. Придется пожертвовать симметрией и выбрать одну из строк за основную. Двигаясь по основной строке, поддерживаем такое соотношение: во всех остальных строках отмечен макси- мальный элемент, не превосходящий текущего элемента основной строки. 1.2.26. (Двоичный поиск) Дана последовательность x[1] <= ... <= x[n] целых чисел и число a. Выяснить, содержится ли a в этой последовательности, т. е. существует ли i из 1..n, для ко- торого x[i]=a. (Количество действий порядка log n.) Решение. (Предполагаем, что n > 0.) l := 1; r := n+1; {если a есть вообще, то есть и среди x[l]..x[r-1], r > l} while r - l <> 1 do begin | m := l + (r-l) div 2 ; | {l < m < r } | if x[m] <= a then begin | | l := m; | end else begin {x[m] > a} | | r := m; | end; end; (Обратите внимание, что и в случае x[m] = a инвариант не наруша- ется.) Каждый раз r-l уменьшается примерно вдвое, откуда и вытека- ет требуемая оценка числа действий. Замечание. l + (r-l) div 2 = (2l + (r-l)) div 2 = (r+l) div 2. 1.2.27. (Из книги Д.Гриса) Дан массив x: array [1..n] of array [1..m] of integer, упорядоченный по "строкам" и по "столбцам": x[i][j] <= x[i+1][j], x[i][j] <= x[i][j+1] и число a. Требуется выяснить, встречается ли a среди x[i][j]. Решение. Представляя себе массив a как матрицу (прямо- угольник, заполненный числами), мы выберем прямоугольник, в ко- тором только и может содержаться a, и будем его сужать. Прямо- угольник этот будет содержать x[i][j] при 1<=i<=l и k<=j<=m. 1 k m ----------------------------------- 1| |***********| | |***********| | |***********| l| |***********| |---------------------------------| | | n| | ----------------------------------- (допускаются пустые прямоугольники при l = 0 и k = m+1). l:=n; k:=1; {l>=0, k<=m+1, если a есть, то в описанном прямоугольнике} while (l > 0) and (k < m+1) and (x[l][k] <> a) do begin | if x[l][k] < a then begin | | k := k + 1; {левый столбец не содержит a, удаляем его} | end else begin {x[l][k] > a} | | l := l - 1; {нижняя строка не содержит a, удаляем ее} | end; end; {x[l][k] = a или прямоугольник пуст } answer:= (l > 0) and (k < m+1) ; Замечание. Здесь та же ошибка: x[l][k] может оказаться не- определенным. (Её исправление предоставляется читателю.) 1.2.28. (Московская олимпиада по программированию) Дан не- убывающий массив положительных целых чисел a[1] <= a[2] <=...<= a[n]. Найти наименьшее целое положительное число, не представи- мое в виде суммы нескольких элементов этого массива (каждый эле- мент массива может быть использован не более одного раза). Число действий порядка n. Решение. Пусть известно, что числа, представимые в виде суммы элементов a[1],...,a[k], заполняют отрезок от 1 до некото- рого N. Если a[k+1] > N+1, то N+1 и будет минимальным числом, не представимым в виде суммы элементов массива a[1]..a[n]. Если же a[k+1] <= N+1, то числа, представимые в виде суммы элементов a[1]..a[k+1], заполняют отрезок от 1 до N+a[k+1]. k := 0; N := 0; {инвариант: числа, представимые в виде суммы элементов массива a[1]..a[k], заполняют отрезок 1..N} while (k <> n) and (a[k+1] <= N+1) do begin | N := N + a[k+1]; | k := k + 1; end; {(k = n) или (a[k+1] > N+1); в обоих случаях ответ N+1} writeln (N+1); (Снова тот же дефект: в условии цикла при ложном первом условии второе не определено.) 1.2.29. (Для знакомых с основами алгебры) В целочисленном массиве a[1]..a[n] хранится перестановка чисел 1..n (каждое из чисел встречается по одному разу). (а) Определить четность перестановки. (И в (а), и в (б) ко- личество действий порядка n.) (б) Не используя других массивов, заменить перестановку на обратную (если до работы программы a[i]=j, то после должно быть a[j]=i). Указание. (а) Четность перестановки определяется коли- чеством циклов. Чтобы отличать уже пройденные циклы, у их эле- ментов можно, например, менять знак. (б) Обращение производим по циклам. 1.2.30. Дан массив a[1..n] и число b. Переставить числа в массиве таким образом, чтобы слева от некоторой границы стояли числа, меньшие или равные b, а справа от границы - большие или равные b. Решение. l:=0; r:=n; {инвариант: a[1]..a[l]<=b; a[r+1]..a[n]>=b} while l <> r do begin | if a[l+1] <= b then begin | | l:=l+1; | end else if a[r] >=b then begin | | r:=r-1; | end else begin {a[l+1]>b; a[r]b} while m <> r do begin | if a[m+1]=b then begin | | m:=m+1; | end else if a[m+1]>b then begin | | обменять a[m+1] и a[r] | | r:=r-1; | end else begin {a[m+1], где n - элемент множества N, а m - элемент множества M) в N, для которой f() = F (f (), x[n]). Схема алгоритма вычисления индуктивной функции: k := 0; f := f0; {инвариант: f - значение функции на } while k<> n do begin | k := k + 1; | f := F (f, x[k]); end; Здесь f0 - значение функции на пустой последовательности (последовательности длины 0). Если функция f определена только на непустых последовательностях, то первая строка заменяется на "k := 1; f := f ();". Индуктивные расширения. Если функция f не является индуктивной, полезно искать ее индуктивное расширение - такую индуктивную функцию g, значения которой определяют значения f (это значит, что существует такая функция t, что f () = t (g ()) при всех ). Можно доказать, что среди всех индуктивных расширений существует минимальное расширение F (минимальность означает, что для любого индуктивного расширения g значения F определяются значениями g). 1.3.1. Указать индуктивные расширения для следующих функций: а) среднее арифметическое последовательности вещественных чисел; б) число элементов последовательности целых чисел, равных ее максимальному элементу; в) второй по величине элемент последовательности целых чисел (тот, который будет вторым, если переставить члены в неубывающем порядке); г) максимальное число идущих подряд одинаковых элементов; д) максимальная длина монотонного (неубывающего или невоз- растающего) участка из идущих подряд элементов в последова- тельности целых чисел; е) число групп из единиц, разделенных нулями (в последова- тельности нулей и единиц). Решение. а) <сумма всех членов последовательности; длина>; б) <число элементов, равных максимальному; значение макси- мального>; в) <наибольший элемент последовательности; второй по величине элемент>; г) <максимальное число идущих подряд одинаковых элементов; чис- ло идущих подряд одинаковых элементов в конце последова- тельности; последний элемент последовательности>; д) <максимальная длина монотонного участка; максимальная длина неубывающего участка в конце последовательности; макси- мальная длина невозрастающего участка в конце последова- тельности; последний член последовательности>; е) <число групп из единиц, последний член>. 1.3.2. (Сообщил Д.Варсонофьев.) Даны две последовательности x[1]..x[n] и y[1]..y[k] целых чисел. Выяснить, является ли вто- рая последовательность подпоследовательностью первой, т. е. мож- но ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка n+k. Решение. (1 вариант) Будем сводить задачу к задаче меньшего размера. n1:=n; k1:=k; {инвариант: искомый ответ <=> возможность из x[1]..x[n1] по- лучить y[1]..y[k1] } while (n1 > 0) and (k1 > 0) do begin | if x[n1] = y[k1] then begin | | n1 := n1 - 1; | | k1 := k1 - 1; | end else begin | | n1 := n1 - 1; | end; end; {n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1 <> 0 (и n1 = 0), то ответ - нет} answer := (k1 = 0); Мы использовали то, что если x[n1] = y[k1] и y[1]..y[k1] - подпоследовательность x[1]..x[n1], то y[1]..y[k1-1] - подпосле- довательность x[1]..x[n1-1]. (2 вариант) Функция x[1]..x[n1] |-> (максимальное k1, для которого y[1]..y[k1] есть подпоследовательность x[1]..x[n1]) ин- дуктивна. 1.3.3. Даны две последовательности x[1]..x[n] и y[1]..y[k] целых чисел. Найти максимальную длину последовательности, явля- ющейся подпоследовательностью обеих последовательностей. Коли- чество операций порядка n*k. Решение (сообщено М.Н.Вайнцвайгом, А.М.Диментманом). Обоз- начим через f(n1,k1) максимальную длину общей подпоследова- тельности последовательностей x[1]..x[n1] и y[1]..y[k1]. Тогда x[n1] <> y[k1] => f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1)); x[n1] = y[k1] => f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1), f(n1-1,k1-1)+1 ); (Поскольку f(n1-1,k1-1)+1 >= f(n1,k1-1), f(n1-1,k1), во втором случае максимум трех чисел можно заменить на третье из них.) Поэтому можно заполнять таблицу значений функции f, имеющую размер n*k. Можно обойтись и памятью порядка k (или n), если ин- дуктивно (по n1) выписать (как функция от n1 этот набор индуктивен). 1.3.4 (из книги Д.Гриса) Дана последовательность целых чи- сел x[1],..., x[n]. Найти максимальную длину ее возрастающей подпоследовательности (число действий порядка n*log(n)). Решение. Искомая функция не индуктивна, но имеет следующее индуктивное расширение: в него входит помимо максимальной длины возрастающей подпоследовательности (обозначим ее k) также и чис- ла u[1],...,u[k], где u[i] = (минимальный из последних членов возрастающих подпоследовательностей длины i). Очевидно, u[1] <= ... <= u[k]. При добавлении нового члена x значения u и k кор- ректируются. n1 := 1; k := 1; u[1] := x[1]; {инвариант: k и u соответствуют данному выше описанию} while n1 <> n do begin | n1 := n1 + 1; | ... | {i - наибольшее из тех чисел отрезка 1..k, для кото- | рых u[i] < x[n1]; если таких нет, то i=0 } | if i = k then begin | | k := k + 1; | | u[k+1] := x[n1]; | end else begin {i < k, u[i] < x[n1] <= u[i+1] } | | u[i+1] := x[n1]; | end; end; Фрагмент ... использует идею двоичного поиска; в инвариан- те условно полагаем u[0] равным минус бесконечности, а u[k+1] - плюс бесконечности; наша цель: u[i] < x[n1] <= u[i+1]. i:=0; j:=k+1; {u[i] < x[n1] <= u[j], j > i} while (j - i) <> 1 do begin | s := i + (j-i) div 2; {i < s < j} | if u[s] >= x[n1] then begin | | j := s; | end else begin {u[s] < x[n1]} | | i := s; | end; end; {u[i] < x[n1] <= u[j], j-i = 1} Замечание. Более простое (но не минимальное) индуктивное расширение получится, если для каждого i хранить максимальную длину возрастающей подпоследовательности, оканчивающейся на x[i]. Это расширение приводит к алгоритму с числом действий по- рядка n*n. 1.3.5. Какие изменения нужно внести в решение предыдущей задачи, если надо искать максимальную неубывающую последова- тельность?