Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Конспекты / Факультативное занятие по информатике "Алгоритмы целочисленной арифметики"

Факультативное занятие по информатике "Алгоритмы целочисленной арифметики"



57 вебинаров для учителей на разные темы
ПЕРЕЙТИ к бесплатному просмотру
(заказ свидетельства о просмотре - только до 11 декабря)


  • Информатика

Поделитесь материалом с коллегами:

6

Факультативное занятие по информатике (программированию)

по теме «Алгоритмы целочисленной арифметики»

Цель урока:

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

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

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

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

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


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

Учащиеся должны знать:

  • алгоритм нахождения делителей натурального числа,

  • алгоритм проверки простое ли число,

  • алгоритм Решета Эратосфена

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


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

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


Ход урока

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

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

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

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

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

1

1

15

20


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

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

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

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

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

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

5
2 4 7 14 9

2


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

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

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

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

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

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

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


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

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

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

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

Write (1, ‘ ‘, x);

For d:=2 to x div 2 do

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

- Какова сложность выполнения данного алгоритма? Успеет ли он при x=109 за 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=109 за 1 секунду найти все делители? (Ответ: ), следовательно, успеет за 1 сек.)

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

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

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

Ребята обычно предлагают воспользоваться Задачей 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≤106).

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

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

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Используем для решения задачи логический массив p из N элементов. Составляем программу:

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*log2 (log2N), значит при N=106 будет около 4,5 млн. действий и за 1 секунду успеем найти ответы.


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

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

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

Предлагаю учащимся сделать задачу двумя способами: при помощи функции Prost и при помощи Решета Эратосфена (если осталось мало времени на уроке, то учащиеся делятся на два варианта и реализуют по одному способу).


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

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

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

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


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

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

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



Учитель информатики высшей категории ГУО «Гимназия №8 г.Витебска» Лактина В.П.



57 вебинаров для учителей на разные темы
ПЕРЕЙТИ к бесплатному просмотру
(заказ свидетельства о просмотре - только до 11 декабря)


Краткое описание документа:

Тема «Алгоритмизация и программирование» в школьном курсе информатики является наиболее сложной для большинства учащихся. Но для «выращивания» будущих программистов и этого материала очень мало. Для мотивированных школьников и заинтересованного учителя на помощь приходит факультатив. В представленной разработке факультативного занятия по теме «Целочисленная арифметика» отражены мои подходы к обучению программирования учащихся средних классов. Урок проникнут проблемным обучением, исследовательской направленностью и способствует интенсивному развитию различных видов мышления учащихся.

Автор
Дата добавления 06.11.2016
Раздел Информатика
Подраздел Конспекты
Просмотров15
Номер материала ДБ-324720
Получить свидетельство о публикации

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх