В следующих задачах переменные предполагаются описанными как 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, причем
. Найти количество
различных чисел среди элементов этого массива.
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 (Сообщил А.Л. Брудно.) Прямоугольное поле
разбито на
квадратных клеток.
Некоторые клетки покрашены в черный цвет. Известно, что все
черные клетки могут быть разбиты на несколько непересекающихся и
не имеющих общих вершин черных прямоугольников. Считая, что
цвета клеток даны в виде массива типа
подсчитать число черных прямоугольников, о которых шла речь.
Число действий должно быть порядка
.
1.2.7. Дан массив x: array[1..n] of integer. Найти
количество различных чисел среди элементов этого массива. (Число
действий должно быть порядка
.)
1.2.8. Та же задача, если требуется, чтобы количество действий
было порядка
.
1.2.9. Та же задача, если известно, что все элементы массива
-- числа от 1 до k и число действий должно быть порядка
.
1.2.10. Дан массив x[1]..x[n] целых чисел. Не используя других
массивов, переставить элементы массива в обратном порядке.
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. Не используя дополнительных массивов, переставить начало
и конец. (Число действий порядка .)
Вариант 1. Перевернем (расположим в обратном порядке) отдельно начало и конец массива, а затем перевернем весь массив как единое целое.
Вариант 2, А.Г. Кушниренко. Рассматривая массив записанным по кругу, видим, что требуемое действие -- поворот круга. Как известно, поворот есть композиция двух осевых симметрий.
Вариант 3. Рассмотрим более общую задачу -- обмен двух участков массива x[p+1]..x[q] и x[q+1]..x[r]. Предположим, что длина левого участка (назовем его 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..q], x[q+1..r]} while (p <> q) and (q <> r) do begin | {оба участка непусты} | if (q - p) <= (r - 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. Коэффициенты многочлена лежат в массиве
(n -- натуральное число, степень многочлена).
Вычислить значение этого многочлена в точке x,
то есть
.
(Описываемый алгоритм называется схемой Горнера.)
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. (Для знакомых с основами анализа. Сообщил
А.Г. Кушниренко) Дополнить алгоритм вычисления значения
многочлена в заданной точке по схеме Горнера вычислением
значения его производной в той же точке.
Общее утверждение о сложности вычисления производных таково:
1.2.14. Дана программа вычисления
значения некоторого многочлена
, содержащая
только команды присваивания. Их правые части -- выражения,
содержащие сложение, умножение, константы, переменные
и ранее встречавшиеся (в левой части) переменные.
Доказать, что существует программа того же типа, вычисляющая
все n производных
,причем общее число арифметических операций не более чем в C
раз превосходит число арифметических операций в исходной
программе. Константа C не зависит от n .
(В. Баур, Ф. Штрассен)
1.2.15. В массивах
хранятся коэффициенты двух многочленов
степеней k и l. Поместить в массив c: array[0..m] of
integer коэффициенты их произведения. (Числа
--
натуральные,
; элемент массива с индексом i содержит
коэффициент при степени 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.16. Предложенный выше алгоритм перемножения многочленов требует
порядка n2 действий для перемножения двух многочленов степени
n . Придумать более эффективный (для больших n ) алгоритм,
которому достаточно порядка
действий.
1.2.17. Даны два возрастающих массива x: array[1..k] of
integer и
y: array[1..l] of integer. Найти количество общих
элементов в этих массивах, то есть количество тех целых t, для
которых
для некоторых i и j.
(Число действий порядка
.)
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.18. Решить предыдущую задачу, если известно лишь, что
и
(возрастание заменено неубыванием).
... end else begin {x[k1+1] = y[l1+1]} | t := x [k1+1]; | while (k1<k) and (x[k1+1]=t) do begin | | k1 := k1 + 1; | end; | while (l1<l) and (x[l1+1]=t) do begin | | l1 := l1 + 1; | end; end;`
Замечание. Эта программа имеет дефект: при проверке условия
Но если мы не хотим полагаться на такое свойство используемой нами реализации паскаля (не предусмотренное его автором Н. Виртом), то можно поступить так. Введем дополнительную переменную b: boolean и напишем:
if k1 < k then b := (x[k1+1]=t) else b:=false; {b = (k1<k) and (x[k1+1] = t)} while b do begin | k1:=k1+1; | if k1 < k then b := (x[k1+1]=t) else b:=false; end;Можно также сделать иначе:
end else begin {x[k1+1] = y[l1+1]} | if k1 + 1 = k then begin | | k1 := k1 + 1; | | n := n + 1; | end else if x[k1+1] = x [k1+2] then begin | | k1 := k1 + 1; | end else begin | | k1 := k1 + 1; | | n := n + 1; | end; end;Так будет короче, хотя менее симметрично.
Наконец, можно увеличить размер массива в его описании, включив в него фиктивные элементы.
1.2.19. Даны два неубывающих массива x: array[1..k] of
integer и y: array[1..l] of integer. Найти число
различных элементов среди
. (Число
действий порядка
.)
1.2.20. Даны два массива
и
. << Соединить>> их в массив
(
; каждый элемент
должен входить в массив z столько раз, сколько раз он входит
в общей сложности в массивы x и y). Число действий
порядка m.
k1 := 0; l1 := 0; {инвариант: ответ получится, если к z[1]..z[k1+l1] добавить справа соединение массивов x[k1+1]..x[k] и y[l1+1]..y[l]} 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]