Жанр: Учеба
Программирование в теоремах и задачах
...лансированность в x нарушилась. При этом разница высот
равна 2 (больше она быть не может, так как высота Z отличается
от высоты Y не более чем на 1). Разберем два варианта.
(2а) Выше правое (не заменявшееся) поддерево вершины x.
Пусть высота левого (т.е. Z) равна k, правого - k+2. Высота старого
левого поддерева вершины x (т.е. Y) была равна k+1. Поддерево
с корнем x имело в исходном дереве высоту k+3, и эта высота
не изменилась после прививки.
По предыдущей задаче вращение преобразует поддерево с корнем
в x в сбалансированное поддерево высоты k+2 или k+3. То есть
высота поддерева с корнем x - в сравнении с его прежней высотой
- не изменилась или уменьшилась на 1, и мы можем воспользоваться
предположением индукции.
------------- ----------------
------------- ----------------
-------------k ----------------k
2а 2б
(2б) Выше левое поддерево вершины x. Пусть высота левого
(т.е. Z) равна k+2, правого - k. Высота старого левого поддерева
(т.е. Y) была равна k+1. Поддерево с корнем x в исходном дереве
X имело высоту k+2, после прививки она стала равна k+3. После
подходящего вращения (см. предыдущую задачу) поддерево с корнем
в x станет сбалансированным, его высота будет равна k+2 или k+3,
так что изменение высоты по сравнению с высотой поддерева с корнем
x в дереве X не превосходит 1 и можно сослаться на предположение
индукции.
12.2.5. Составить программы добавления и удаления элементов,
сохраняющие сбалансированность. Число действий не должно
превосходить C*(высота дерева). Разрешается хранить в вершинах
дерева дополнительную информацию, необходимую при балансировке.
Решение. Будем хранить для каждой вершины разницу между
высотой ее правого и левого поддеревьев:
diff [i] = (высота правого поддерева вершины с номером i) -
(высота левого поддерева вершины с номером i).
Нам потребуются четыре процедуры, соответствующие большим и малым
правым и левым вращениями. Но вначале два замечания.
(1) Нам нужно, чтобы при вращении поддерева номер его корня
не менялся. (В противном случае потребовалось бы корректировать
информацию в отце корня, что нежелательно.) Этого можно достичь,
так как номера вершин дерева можно выбирать независимо от их
значений. (На картинках номер указан сбоку от вершины, а значение
- внутри.)
Малое правое вращение
Большое правое вращение
(2) После преобразований мы должны также изменить соответственно
значения в массиве diff. Для этого достаточно знать
высоты деревьев P, Q, ... с точностью до константы, поэтому можно
предполагать, что одна из высот равна нулю.
Вот процедуры вращений:
procedure SR (a:integer); {малое правое вращение с корнем a}
| var b: 1..n; val_a,val_b: T; h_P,h_Q,h_R: integer;
begin
| b := right [a]; {b "" null}
| val_a := val [a]; val_b := val [b];
| h_Q := 0; h_R := diff[b]; h_P := (max(h_Q,h_R)+1)-diff[a];
| val [a] := val_b; val [b] := val_a;
| right [a] := right [b] {поддерево R}
| right [b] := left [b] {поддерево Q}
| left [b] := left [a] {поддерево P}
| left [a] := b;
| diff [b] := h_Q - h_P;
| diff [a] := h_R - (max (h_P, h_Q) + 1);
end;
procedure BR (a:integer);{большое правое вращение с корнем a}
| var b,c: 1..n; val_a,val_b,val_c: T;
| h_P,h_Q,h_R,h_S: integer;
begin
| b := right [a]; c := left [b]; {b,c "" null}
| val_a := val [a]; val_b := val [b]; val_c := val [c];
| h_Q := 0; h_R := diff[c]; h_S := (max(h_Q,h_R)+1)+diff[b];
| h_P := 1 + max (h_S, h_S-diff[b]) - diff [a];
| val [a] := val_c; val [c] := val_a;
| left [b] := right [c] {поддерево R}
| right [c] := left [c] {поддерево Q}
| left [c] := left [a] {поддерево P}
| left [a] := c;
| diff [b] := h_S - h_R;
| diff [c] := h_Q - h_P;
| diff [a] := max (h_S, h_R) - max (h_P, h_Q);
end;
Левые вращения (большое и малое) записываются симметрично.
Процедуры добавления и удаления элементов пишутся как
раньше, но только добавление и удаление должно сопровождаться
коррекцией массива diff и восстановлением сбалансированности.
При этом используется процедура с такими свойствами:
дано: левое и правое поддеревья вершины с номером a сбалан-
сированы, в самой вершине разница высот не больше 2, в
поддереве с корнем a массив diff заполнен правильно;
надо: поддерево с корнем a сбалансировано и массив diff со-
ответственно изменен, d - изменение его высоты (равно 0
или -1); в остальной части все осталось как было}
procedure balance (a: integer; var d: integer);
begin {-2 "= diff[a] "= 2}
| if diff [a] = 2 then begin
| | b := right [a];
| | if diff [b] = -1 then begin
| | | BR (a); d := -1;
| | end else if diff [b] = 0 then begin
| | | SR (a); d := 0;
| | end else begin {diff [b] = 1}
| | | SR (a); d := - 1;
| | end;
| end else if diff [a] = -2 then begin
| | b := left [a];
| | if diff [b] = 1 then begin
| | | BL (a); d := -1;
| | end else if diff [b] = 0 then begin
| | | SL (a); d := 0;
| | end else begin {diff [b] = -1}
| | | SL (a); d := - 1;
| | end;
| end else begin {-2 " diff [a] " 2, ничего делать не надо}
| | d := 0;
| end;
end;
Восстановление сбалансированности требует движения от
листьев к корню, поэтому будем хранить в стеке путь от корня к
рассматриваемой в данный момент вершине. Элементами стека будут
пары (вершина, направление движения из нее), т.е. значения типа
record
| vert: 1..n; {вершина}
| direction : (l, r); {l - левое, r- правое}
end;
Программа добавления элемента t теперь выглядит так:
if root = null then begin
| get_free (root);
| left [root] := null; right [root] := null; diff[root] := 0;
| val [root] := t;
end else begin
| x := root; ..сделать стек пустым
| {инвариант: осталось добавить t к непустому поддереву с
| корнем в x; стек содержит путь к x}
| while ((t " val [x]) and (left [x] "" null)) or
| | ((t " val [x]) and (right [x] "" null)) do begin
| | if t " val [x] then begin
| | | ..добавить в стек пару "x, l"
| | | x := left [x];
| | end else begin {t " val [x]}
| | | ..добавить в стек пару "x, r"
| | | x := right [x];
| | end;
| end;
| if t "" val [x] then begin {t нет в дереве}
| | get_free (i); val [i] := t;
| | left [i] := null; right [i] := null; diff [i] := 0;
| | if t " val [x] then begin
| | | ..добавить в стек пару "x, l"
| | | left [x] := i;
| | end else begin {t " val [x]}
| | | ..добавить в стек пару "x, r"
| | | right [x] := i;
| | end;
| | d := 1;
| | {инвариант: стек содержит путь к изменившемуся поддереву,
| | высота которого увеличилась по сравнению с высотой в
| | исходном дереве на d (=0 или 1); это поддерево сбалан-
| | сировано; значения diff для его вершин правильны; в ос-
| | тальном дереве все осталось как было - в частности,
| | значения diff}
| | while (d "" 0) and ..стек непуст do begin {d = 1}
| | | ..взять из стека пару в "v, direct"
| | | if direct = l then begin
| | | | if diff [v] = 1 then begin
| | | | | c := 0;
| | | | end else begin
| | | | | c := 1;
| | | | end;
| | | | diff [v] := diff [v] - 1;
| | | end else begin {direct = r}
| | | | if diff [v] = -1 then begin
| | | | | c := 0;
| | | | end else begin
| | | | | c := 1;
| | | | end;
| | | | diff [v] := diff [v] + 1;
| | | end;
| | | {c = изменение высоты поддерева с корнем в v по сравне-
| | | нию с исходным деревом; массив diff содержит правиль-
| | | ные значения для этого поддерева; возможно нарушение
| | | сбалансированности в v}
| | | balance (v, d1); d := c + d1;
| | end;
| end;
end;
Легко проверить, что значение d может быть равно только 0 или 1
(но не -1): если c = 0, то diff [v] = 0 и балансировка не производится.
Программа удаления строится аналогично. Ее основной фрагмент
таков:
{инвариант: стек содержит путь к изменившемуся поддереву,
высота которого изменилась по сравнению с высотой в
исходном дереве на d (=0 или -1); это поддерево
сбалансировано; значения diff для его вершин правильны;
в остальном дереве все осталось как было -
в частности, значения diff}
while (d "" 0) and ..стек непуст do begin
| {d = -1}
| ..взять из стека пару в "v, direct"
| if direct = l then begin
| | if diff [v] = -1 then begin
| | | c := -1;
| | end else begin
| | | c := 0;
| | end;
| | diff [v] := diff [v] + 1;
| end else begin {direct = r}
| | if diff [v] = 1 then begin
| | | c := -1;
| | end else begin
| | | c := 0;
| | end;
| | diff [v] := diff [v] - 1;
| end;
| {c = изменение высоты поддерева с корнем в v по срав-
| нению с исходным деревом; массив diff содержит
| правильные значения для этого поддерева;
| возможно нарушение сбалансированности в v}
| balance (v, d1);
| d := c + d1;
end;
Легко проверить, что значение d может быть равно только 0 или -1
(но не -2): если c = -1, то diff [v] = 0 и балансировка не производится.
Отметим также, что наличие стека делает излишними переменные
father и direction (их роль теперь играет вершина стека).
12.2.6. Доказать, что при добавлении элемента
(а) второй из трех случаев балансировки (см. рисунок выше)
невозможен;
(б) полная балансировка требует не более одного вращения
(после чего все дерево становится сбалансированным),
в то время как при удалении элемента может понадобиться
много вращений.
Замечание. Мы старались записать программы добавления и
удаления так, чтобы они были как можно более похожими друг на
друга. Используя специфику каждой из них, можно многое упростить.
Существуют и другие способы представления множеств, гарантирующие
число действий порядка log n на каждую операцию. Опишем
один из них (называемый Б-деревьями).
До сих пор каждая вершина содержала один элемент хранимого
множества. Этот элемент служил границей между левым и правым
поддеревом. Будем теперь хранить в вершине k "= 1 элементов множества
(число k может меняться от вершины к вершине, а также при
добавлении и удалении новых элементов, см. далее). Эти k элементов
служат разделителями для k+1 поддерева. Пусть фиксировано
некоторое число n "= 1. Будем рассматривать деревья, обладающие
такими свойствами:
(1) Каждая вершина содержит от n до 2n элементов (за исключением
корня, который может содержать любое число элементов от 0
до 2n).
(2) Вершина с k элементами либо имеет k+1 сына, либо не
имеет сыновей вообще (такие вершины называются листьями).
(3) Все листья находятся на одной и той же высоте.
Добавление элемента происходит так. Если лист, в который он
попадает, неполон (т.е. содержит менее 2n элементов), то нет
проблем. Если он полон, то 2n+1 элемент (все элементы листа и
новый элемент) разбиваем на два листа по n элементов и разделяющий
их серединный элемент. Этот серединный элемент надо добавить
в вершину предыдущего уровня. Это возможно, если в ней менее
2n элементов. Если и она полна, то ее разбивают на две, выделяют
серединный элемент и т.д. Если в конце концов мы захотим
добавить элемент в корень, а он окажется полным, то корень расщепляется
на две вершины, а высота дерева увеличивается на 1.
Удаление элемента. Удаление элемента, находящемся не в листе,
сводится к удалению непосредственно следующего за ним, который
находится в листе. Поэтому достаточно научиться удалять элемент
из листа. Если лист при этом становится неполным, то его
можно пополнить за счет соседнего листа - если только и он не
имеет минимально возможный размер n. Если же оба листа имеют
размер n, то на них вместе 2n элементов, вместе с разделителем -
2n+1. После удаления одного элемента остается 2n элементов - как
раз на один лист. Если при этом вершина предыдущего уровня становится
меньше нормы, процесс повторяется и т.д.
12.2.7. Реализовать описанную схему хранения множеств, убедившись,
что она также позволяет обойтись C*log(n) действий для
операций включения, исключения и проверки принадлежности.
12.2.8. Можно определять сбалансированность дерева иначе:
требовать, чтобы для каждой вершины ее левое и правое поддеревья
имели не слишком сильно отличающиеся количества вершин. (Преимущество
такого определения состоит в том, что при вращениях изменяется
сбалансированность только в одной вершине.) Реализовать
на основе этой идеи способ хранения множеств, гарантирующий
оценку в C*log(n) действий для включения, удаления и проверки
принадлежности. (Указание. Он также использует большие и малые
вращения. Подробности см. в книге Рейнгольда, Нивергельта и Део
"Комбинаторные алгоритмы".)
Н Е П О К У П А Й Т Е Э Т У К Н И Г У !
(Предупреждение автора)
В этой книге ничего не говорится об особенностях BIOSа,
DOSа, OSа, GEМа и Windows, представляющих основную сложность при
настоящем программировании.
В ней нет ни слова об объектно-ориентированном программировании,
открывшем новую эпоху в построении дружественных и эффективных
программных систем.
Из нее Вы не узнаете о графических возможностях компьютера,
без которых немыслимо современное программирование, о богатстве
и разнообразии мира видеоадаптеров.
Не рассказано в ней и о написании резидентных программ,
тонкости взаимодействия которых должен знать каждый.
Искусственный интеллект, открывший новые рынки сбыта для
программного обеспечения, обойден презрительным молчанием.
Экспертные системы, которые в скором будущем займут место
на рабочем столе каждого, даже не упоминаются.
Логическое программирование, постепенно вытесняющее устаревший
операторный стиль программирования, не затронуто.
Драматический поворот от баз данных к базам знаний, вызвавший
в жизни новую профессию — инженер знаний — остался незамеченным
автором.
Проблемы отладки и сопровождения программ, занимающие, по
общему мнению профессионалов, 90% в программировании, игнорируются.
В книге используются лишь самые элементарные возможности
паскаля. Обширные возможности, предоставляемые современными интегрированными
программными средами, остаются невостребованными.
(Не говоря уже о том, что паскаль уже вообще устарел, вытесненный
языком Си.)
Игрушечные головоломки, которым посвящена книга, никому не
нужны. Если же перед Вами встанет действительно важная задача,
неужели Вы не справитесь с ней сами, без непрошеных учителей и
советчиков?
Короче говоря, покупать эту книгу глупо - особенно теперь,
когда выходит столько переводных руководств, написанных в цивилизованных
странах настоящими профессионалами.
Глава 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. Проверить, являет
...Закладка в соц.сетях
