6. (а) Если п - не простое число, то по определению п имеет делитель d, такой, что 1 < d < п. Если d> то n/d - делитель, такой, что 1 < n/d < Уп. (Ь) Если N не является простым числом, то N имеет простой делитель d, такой, что 1 < d < \/N. Алгоритм подтвердил, что N не имеет простых делителей < р = PRIME [К]; кроме того, N = pQ-l-R<pQ--p<p+p<(p--l). Любой простой делитель N, следовательно, больше р + 1 > Vn.

Необходимо также доказать, что если N простое, то существует достаточно большое простое число, меньшее N, т. е. что (А;--1)-е простое число pk+i меньше р1+Рк- В противном случае К превышало бы J и PRIME [К] было бы нулем, когда нам понадобилось бы, чтобы оно было большим. Доказательство следует из "постулата Бертрана": если р - простое, то существует простое число, большее р, но меньшее 2р.

7. (а) Это ссылка на метку строки 29. (Ь) Программа вьшолнена не будет; строка 14 будет ссылаться на строку 15, а не на строку 25; строка 24 будет ссылаться на строку 15, а не на строку 12.

8. Печатает 100 строк. Если все 12 ООО символов этих строк расположить так, чтобы они примыкали друг к другу, то они займут довольно много места и это будет выглядеть так: пять пробелов, пять букв А, десять пробелов и пять букв А, пятнадцать пробелов, ... 5к пробелов и пять букв А, 5{к + 1) пробелов ... и т. д., пока не будут напечатаны все 12 ООО символов. Третья qt конца строка заканчивается последовательностью букв ААААА и 35 пробелами; последние две строки полностью пусты. Общий результат представляет собой пример манипуляций полем ОП.

9. В поле (4:4) каждого элемента следующей таблицы содержится максимальное значение F, а в поле (1:2) - адрес соответствующей программы проверки допустимости.

ENNXGOOD

CMPAFL0AT(5:5)

CMP1FIELD(5:5)

JMP BAD VALID CMPX 3999,6(6)

CMPXFIELD(5:5)

10. Главная трудность этой задачи состоит в том, что в строке или столбце может быть несколько минимумов или максимумов и каждый из них - это потенциальная седловая

Решение 1. В этом варианте решения по очереди просматриваются все строки, создается список всех столбцов для минимальных элементов строк, а затем проверяется, является ли минимальный элемент строки максимальным элементом столбца. гХ текущий минимум; по мере просмотра матрицы гП пробегает значения от 72 до О, если только не будет найдена седловая точка; г12 = индекс столбца для элемента из гП; г13 = размер списка минимумов. Обратите внимание, что в любом случае цикл заканчивается тогда, когда содержимое индексного регистра < 0.

Решение 2. Добавив немного математики, получаем еще один алгоритм.

Теорема. Пусть R{i) - miiij a,j, C{j) = max, a,j. Элемент aojo является седловой точкой тогда и только тогда, когда R(io) = max, R{i) = С{]о) = miiij C{j).

Доказательство. Если a,gjg - седловая точка, то для любого фиксированного г выполняется R(io) = C{jo)>atjo >Р{г), поэтому R{io) = max, R{i). Аналогично C(jo) = mmj C(j).

Обратно, имеем R(i) < o,j < C{j) для всех г и j, отсюда R(io) = C{jo) и, следовательно, a,gjo - седловая точка

(Из этого доказательства видно, что всегда выполняется неравенство max, R(t) < mmj C(j) Поэтому седловой точки не существует тогда и только тогда, когда R{i) строго меньше всех C{j))

Согласно теореме достаточно найти наименьший максимум столбца, а затем - равный ему минимум строки Во время фазы 1 гИ = индекс столбца, г12 пробегает по матрице Во время фазы 2 гП = возможный ответ, г12 пробегает по матрице, г13 = индекс строки, умноженный на 8, г14 = индекс столбца

Предоставляем читателю возможность найти более удачное решение, в котором на этапе 1 записываются все возможные строки, являющиеся кандидатами на проверку наличия седловой точки на этапе 2 Совсем необязательно выполнять поиск во всех строках, достаточно проверить только те строки го, для которых C{jo) = mmj C{j) влечет a,ojo = C{jo) Как правило, существует максимум одна такая строка