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

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

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

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

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

Цель урока:

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

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

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

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

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

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

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

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

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

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

Ход урока

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

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

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

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

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

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

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

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

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

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

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

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

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

чисел?

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

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

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

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

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

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

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

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

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

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

, 100 2, 50                   4, 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=10⁹ за 1 секунду найти все делители? (Ответ: ), успеет за 1 сек.)

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

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

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

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

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

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

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

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

         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≤10⁶).

Ребята обычно предлагают в цикле воспользоваться функцией Prost из Задачи2. Выясняем сложность такого алгоритма: N*. При N=10⁶ получим 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, ‘ ‘);

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

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

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

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

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

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

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

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

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

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

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

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

Витебск, 2013г.