Решение задач целочисленной арифметики (поиск делителей и простых чисел)

Факультативное занятие по теме

«Решение задач целочисленной арифметики (поиск делителей и простых чисел)»

целочисленная арифметика программа программирование Цель урока:

Ш закрепление материала предыдущего урока;

Ш формирование навыков и умений составления структурных программ для решения практических задач по теме «целочисленная арифметика»;

Ш развитие познавательного интереса, логического и алгоритмического мышления, навыков самоконтроля, ответственности, внимания.

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

Тип урока: урок усвоения новых знаний.

Учащиеся должны знать: алгоритм нахождения делителей натурального числа, алгоритм проверки простое ли число, алгоритм Решета Эратосфена Учащиеся должны уметь: выполнять практические задачи с использованием изученных алгоритмов Программное и методическое обеспечение урока: система программирования Free Pascal, интернет на ученических компьютерах Техническое обеспечение урока: компьютеры Ход урока

1. Проверка и закрепление знаний и умений предыдущего урока К доске вызываю два человека написать решение домашних задач:

1) Сайт acmp.ru № 383 «Красивые числа-2»

Будем называть число красивым, если сумма его цифр делится на количество цифр в нем. Необходимо найти N-ое в порядке возрастания красивое число. (1 <= N <= 100 000)

2) Сайт dl.gsu.by раздел «Методы алгоритмизации» задача «Взаимно простые тройки»

Дано N различных чисел. Определить какое количество троек из этого набора являются попарно взаимно простыми.

Формат ввода:

N — количество чисел. 1<=N<=100

Последовательность из N чисел. 2<=A[i]<=1000

С остальными учащимися провожу фронтальный опрос по теме предыдущего занятия:

— Какие числа называют четными? Нечетными? Как написать в команде ветвления условие проверки на четность?

— Что называется наибольшим общим делителем двух натуральных чисел. Рассказать функцию нахождения НОД двух чисел.

— Какие числа называют взаимно-простыми?

— Какое число называют кратным данного числа? Как получить наименьшее общее кратное двух

чисел?

— Как в программе найти сумму цифр натурального числа и количество цифр?

Выясняю, прошли ли у учащихся в домашнем задании все тесты. Обсуждаем правильность выполнения домашнего задания (на доске), выявляем проблемы, с которыми столкнулись учащиеся при выполнении домашнего задания. Даю рекомендации по их устранению.

2. Актуализация знаний учащихся на изучение учебного материала. Объяснение нового материала. Составление и реализация алгоритмов (метод проблемного изложения в сочетании с частично-поисковым методом, фронтальная форма работы)

— Что называют делителем числа? Как найти все делители натурального числа?

Задача1. Найти все делители натурального числа X (1⁹).

Обычно ребята предлагают нерациональный алгоритм, который записываем и разбираем его недостатки:

Write (1, ` `, x);

For d:=2 to x div 2 do

if x mod d = 0 then write (` `, d);

— Какова сложность выполнения данного алгоритма? Успеет ли он при X=10⁹ за 1 секунду найти все делители? (Ответ: О (X/2), не успеет).

— Как усовершенствовать алгоритм?

— Заметим особенность, что все делители у целого числа парные. Выпишем все пары делителей, например у числа 100:

1, 100 2, 50 4, 25 5, 20 10, 10

Сделаем вывод, что искать делители у числа нужно только до его корня.

write (1, ` `, x);

d:=2;

while int64(d)*d < x do begin

if x mod d = 0 then write (` `, d, ` `, x div d);

d:=d+1;

end;

if int64(d)*d=x then write (` `, d);

— Какова теперь сложность выполнения данного алгоритма? Успеет ли он при X=10⁹ за 1 секунду найти все делители? (Ответ:), успеет за 1 сек.)

— Какие числа называются простыми? Какие составными?

— Как определить простое ли число?

Задача2. Составить функцию, определяющую является ли натуральное число X простым? (1?X?10⁹)

Ребята обычно предлагают воспользоваться Задачей 1, подсчитав количество делителей. Предлагаю найти пути усовершенствования алгоритма. Замечаем, что:

а) простое число не может быть четным (за исключением 2),

б) нечетное число не может иметь четных делителей,

в) если нашли хоть один делитель, то число — составное и можно остановить цикл.

Учитывая замечания, составляем функцию:

Function Prost (x: longint): boolean;

Var d: longint;

Begin

If x mod 2 =0 then Prost:=(x=2)

else begin

d:=3;

while (int64(d)*d<=x) and (x mod d <> 0) do

d:= d+2;

Prost:= (int64(d)*d > x) and (x<> 1);

end;

end;

— Как найти все простые числа на заданном целочисленном промежутке?

Задача3. Найти все простые числа на промежутке от 2 до N (N?10⁶).

Ребята обычно предлагают в цикле воспользоваться функцией Prost из Задачи2. Выясняем сложность такого алгоритма: N*. При N=10⁶ получим 1 млрд. действий. Следовательно, надо искать более быстрое решение.

— Слышал ли кто-нибудь из вас о Решете Эратосфена?

Выписываю на доске в ряд все числа от 1 до 27 и показываю принцип Решета:

вычеркиваю 1, вычеркиваю все числа кратные 2, кратные 3, кратные 5 (кроме их самих). Остались только простые числа на доске. Составляем программу:

p[1]: =false;

for i:=2 to N do p[i]: =true;

i:=2;

while int64(i)*i<=N do begin

if p[i] then begin j:= int64(i)*i;

while j<=N do begin

p[j]: = false; j:=j+i;

end;

end;

if i=2 then i:=3 else i:=i+2;

end;

for i:=2 to N do if p[i] then write (i, ` `);

— В высшей математике доказано, что сложность алгоритма: N*log₂ (log₂N), значит при N=10⁶ получаем 4,5 млн. действий и успеем за 1 сек найти ответы.

3. Закрепление нового материала (репродуктивный метод обучения, индивидуальная форма работы).

Самостоятельная работа в тестирующей системе. Учащимся предлагается загрузить систему программирования Free Pascal, зайти на сайт acmp.ru, самостоятельно составить и отослать на проверку в тестирующую систему программу для решения Задачи под № 349.

Задача (№ 349). Найти все простые числа от M до N. (2 <= M <= N <= 10⁶)

Делю учащихся на два варианта и предлагаю решить задачу при помощи функции Prost и при помощи Решета Эратосфена.

4. Подведение итогов урока. Рефлексия.

Выясняю, сколько времени выполнялась программа задачи № 349 каждым из способов.

— Во сколько раз алгоритм Решета Эратосфена оказался быстрее, чем использование функции Prost?

— Какие новые алгоритмы сегодня вы узнали на уроке? Расскажите основную идею этих алгоритмов.

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

1) Повторить алгоритмы: НОД, нахождение делителей, определения простое ли число, алгоритм Решета Эратосфена;

2) на сайте acmp.ru сдать № 60 (Сверхпростое число), № 171 (Количество делителей).

Учитель информатики Лактина В.П.

Витебск, 2013 г.