Урок #5. «Двойные циклы.

Генерация простых чисел.»

Глава #1  «Популярное имя »

*что нужно знать и что делать*

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

Приведем образный пример на основе двойных циклов. Как выяснить самое популярное имя среди учащихся вашей школы, то есть если в Америке это Джон, в Англии Смит, а в вашей школе? Предложим такой алгоритм:

1.      Построим всех в шеренгу по порядку 1,2,3..,N

2.      Спросим имя у первого ученика и пройдя по шеренге выполним опрос, если имя совпадает включаем счетчик и  делаем метку (шаг назад во вторую шеренгу) ученику имеющему такое же имя, в конце шеренги записываем показание счетчика этого имени

3.      Переходим к следующему по порядку стоящему в первой шеренге и повторяем процедуру из пункта 2, пока не просмотрим всех

4.      Находим максимальное показание счетчиков всех имен, например Николай – 11

5.      Объявляем имя  популярного имени в вашей школе и премируем всех 11 Николаев ценными призами

А как технически в Паскале записывается двойной цикл, один цикл с параметром мы знаем

FOR I:=1 TO N DO <ТЕЛО ЦИКЛА>;  

А двойной так, выберем еще имя переменной цикла чаще это J или K и запишем вместе:

FOR I:=1 TO N DO

FOR J:=1 TO N DO <ТЕЛО ЦИКЛА>;   

Цикл по J – внутренний, по I – внешний.

Начало и конец циклов числа произвольные, число операций по внутреннему циклу  равно N*N=N² вот и все.

Глава #2  «Генерация простых чисел»

*с чего начать и что делать*

На прошлом уроке при знакомстве с простыми числами один ученик хотел написать программу вывода первых 100 простых чисел, да сегодня ему это удастся.

Вспомним как мы определяем простоту числа – по количеству делителей, должно быть два, сама программа . точнее ее основная часть,имела  такой вид:

K:=0;

FOR I:=1 TO N DO  IF N MOD I=0 THEN INC(K);

IF K=2 THEN WRITE(‘1’) ELSE  WRITE (‘0’);

Здесь K – счетчик , N MOD I=0 – условие отбора делителя

         Но здесь нет потока данных для каждого числа из которого мы можем применить этот алгоритм , например из чисел 2,3,4,..,99,100 выбрать все простые числа. Все просто.

Внешний цикл по I генерирует поток чисел, внутренний по J определяет простоту числа.

         Разберемся с внешним циклом, он генерирует числа от 2 до 100, а внутренний с какого числа должен начаться и каким заканчиваться? Так , вспомним пример на «7», чтобы проверить является ли оно простым пришлось организовать деление этого числа на 1,2,3.4,5,6 и 7, в результате только 7 mod 1=0 и 7 mod 7=0 , а раз так два делителя число 7 – простое! Теперь все ясно внутренний цикл по J меняется от 1 до I! Запишем программу:

FOR I:=2 TO 100 DO

K:=0;

FOR J:=1 TO I DO IF I MOD J=0 THEN INC(K);

IF K=2 THEN WRITE (I,’  ‘);

Здесь все верно, но эта программа не будет работать, нужно с помощью составного оператора begin end; выделить в отдельный блок этот фрагмент программы:

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 100 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;

На районной олимпиаде 1992 года была такая задача

«Вывести все простые числа до N».

Условия: во входном файле INPUT.TXT число N, причем 2<=N<=1000 , в выходном через пробел все простые числа от 2 до N.

Пример:

INPUT.TXT

10

OUTPUT.TXT

2 3 5 7

Вот ее решение:

var    N: integer ;      

         K: integer ;

        I,J: 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 WRITE (I,’’  ‘);

END;

end.

Практическое задание:

1.На диске А создать файл OLIMP1.PAS  и ввести программу

2.Во входной файл INPUT.TXT записать 10 и проверить работу программы

3.Протестировать программу на года 100, 500 и 1000

Глава #3  «Вопросы для повторения и ДЗ»

Вопросы для повторения:

1.      Как записываются двойные циклы?

2.      Как записать составной оператор?

3.      Как записать составной оператор в двойных циклах?

4.      Как записать полный оператор условия?

5.      Как создается счетчик?

Домашнее задание:

Написать программу «Дано целое число N.Найти сумму всех простых чисел до N » в режиме работы с входными и выходными файлами

Пример:

INPUT.TXT

6

OUTPUT.TXT

10