END;
Урок #6. «Запись
и обработка массивов
Глава #1 «Камера
хранения»
*проще простого*
Будет верно сказано, что ни одна олимпиадная задача не
обходится без предварительной записи данных в массив. А массив он зачем?
Вы когда - нибудь сдавали вещи в камеру хранения. У каждой
ячейки есть свой номер – индекс, вы кладете туда свои вещи , а когда надо
вынимаете их оттуда, таких ячеек много, удобно не правда ли.
Так же призван работать массив в Паскале – для временного
хранения данных и последующей их обработки. Описывается массив стандартно в
разделе описания переменных:
Имя массива: ARRAY [
1..N] of тип;
Например как описать массив из 100 элементов целого типа?
MAS:ARRAY[1..100] OF INTEGER;
Заполняют массив чаще всего с помощью циклов. Пример:
FOR I:=1 TO 100 DO MAS[I]:=I; - массив заполнен натуральными
числами от 1 до 100
Обращаются к элементам массива называя
имя и индекс , например
WRITE(MAS[10]); - на экране «10».
Глава #2 «Простая
сумма»
*от урока к олимпиаде*
Нам известен алгоритм генерации простых чисел и его
реализация в Паскале.
А что если записать их в массив с идеей последующей их
обработки?!
Вспомним основной фрагмент программы:
FOR I:=2 TO N DO
BEGIN
K:=0;
FOR J:=1 TO I DO IF I MOD J=0 THEN INC(K);
IF K=2 THEN WRITE (I,’ ‘);
END;
Где у нас вывод простых чисел там поставим запись в
массив.
FOR I:=2 TO N DO
BEGIN
K:=0;
FOR J:=1 TO I DO IF I MOD J=0 THEN INC(K);
IF K=2 THEN MAS[?]:=I;
END;
Знак вопроса означает проблему индексации элементов массива, тем
более , что нам неизвестно их количество ( количество генерируемых простых
чисел).
Решение такое: надо ввести счетчик (
например по переменной R) и составной оператор begin end;
В итоге:
FOR I:=2 TO N DO
BEGIN
K:=0;
FOR J:=1 TO I DO IF I MOD J=0 THEN INC(K);
IF K=2 THEN
BEGIN
INC(R);
MAS[R]:=I;
END;
END;
Все , простые числа записываются в
массив MAS и
количество их – R.
Пора
решать такую олимпиадную задачу:
«Требуется составить программу,
которая находит все возможные разложения числа N на сумму двух простых чисел», районная олимпиада 2003 год
Пример:
INPUT.TXT
5
OUTPUT.TXT
2 3
Алгоритм такой:
1.
Генерируем
простые числа до N
2.
Записываем
их в массив
3.
Генерируем
все возможные суммы из 2 простых чисел
4.
Если
сумма равна N, выводим слагаемые в OUTPUT.TXT
Первые два пункта в таком алгоритме понятно, а
генерация всех возможных сумм из 2 простых чисел это сможет двойной цикл. Вся
программа для записываемых 100 простых
чисел:
var N:integer ;
K,R:integer ;
I,J:integer;
MAS:ARRAY[1..100]
OF INTEGER;
begin
assign(input,’input.txt’);
assign(output,’output.txt’);
reset(input);
rewrite(output);
read(N);
FOR I:=2 TO N DO
BEGIN
K:=0;
FOR J:=1 TO I DO IF I MOD J=0 THEN INC(K);
IF K=2 THEN
BEGIN
INC(R);
MAS[R]:=I;
END;
END;
FOR I:=1 TO R DO
FOR J:=I+1 TO R DO
IF MAS[I]+MAS[J]=N
THEN WRITELN(MAS[I],’ ‘,MAS[J]);
end.
Практическое задание:
1.На диске А создать файл OLIMP2.PAS и ввести программу
2.Во входной файл INPUT.TXT записать 5 и проверить работу программы
3.Протестировать программу на 100,
500 и 1000
Глава #3 «Вопросы для повторения
и ДЗ»
Вопросы для повторения:
1.
Как
описываются массивы в Паскале?
2.
Как
индексируется массив?
3.
Как
записать в массив простые числа?
4.
Как
генерировать все суммы из 2 элементов массива?
5.
Как
выводится массив?
Домашнее
задание:
Написать программу «Дано целое число N.Найти суммы двух простых чисел до
N , которые также являются простыми»
Пример:
INPUT.TXT
10
OUTPUT.TXT
2 3
2 5
