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

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

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

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

Цель урока:

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

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

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

Øосвоение различных методов решения задач, реализуемых на языке программирования

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

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

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

Учащиеся должны уметь: выполнять практические задачи с использованием изученных алгоритмов

Программное и методическое обеспечение урока: система программирования Free Pascal, интернет на ученических компьютерах

Техническое обеспечение урока: компьютеры

Ход урока

1.Проверка и закрепление знаний и умений предыдущего урока

К доске вызываю два человека написать решение домашних задач:

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

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

Пример ввода:Пример вывода:111520

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

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

Формат ввода:- количество чисел. 1<=N<=100

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

Пример ввода:Пример вывода:5 2 4 7 14 92

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

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

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

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

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

чисел?

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

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

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

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

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

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

Write (1, , x);d:=2 to x div 2 do

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

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

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

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

, 100 2, 504, 25 5, 20 10, 10

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

write (1, ,x ); :=2; int64(d)*d < x do beginx mod d = 0 then write ( , d, , x div d);:=d+1;;int64(d)*d=x then write ( , d);

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

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

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

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

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

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

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

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

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

Function Prost (x: longint): boolean;d: longint;

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+2;

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

end;

end;

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

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

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

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

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

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

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

i:=2;int64(i)*i<=N do beginp[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;;i:=2 to N do if p[i] then write (i, );

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

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

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

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

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

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

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

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

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

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

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

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

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

Витебск, 2013г.

Больше работ по теме: