Рабочие листы
к вашим урокам
Скачать
1 слайд
Интегрированный урок математики и информатики
«Программирование циклических алгоритмов на примерах задач элементарной математики по теме «Делимость и алгоритм Евклида»
2 слайд
Виды циклических алгоритмов
Цикл «Пока»
Цикл «До»
Цикл с параметром
3 слайд
Структура цикла «Пока»
While условие выполнения цикла do оператор 1;
На языке блок-схем данную структуру можно указать следующим образом:
условие
Оператор 1
да
нет
4 слайд
Структура цикла с параметром
for параметр := нач.знач to кон.знач do оператор 1;
На языке блок-схем структура цикла запишется следующим образом:
Параметр цикла
действие
5 слайд
Делители
Определение. Если остаток от деления целого числа a на целое число b равен нулю (a mod b = 0), то b называется делителем a. Говорят также, что a делиться на b без остатка.
Можно записать другие эквивалентные формулировки:
a = (a div b)*b
a = n*b, где n – целое число
Определение. Если b является делителем a, то говорят, что a кратно b. Обозначается а b
6 слайд
Нахождение делителей
Задача: дано натуральное число X. Вывести на экран все его положительные делители.
Эту задачу легко решить так: переберем все натуральные числа из отрезка [1; X] и проверим, на какие из них X делится.
x := 50;
n := 1;
while n <= x do begin
if x mod n = 0 then
WriteLn(n);
n := n + 1;
end;
7 слайд
На самом деле можно перебирать числа до и выводить сразу делитель y и соответствующие ему x div y, поскольку делитель соответствующий , то есть , и это означает, что дальше пойдут большие делители, соответствующие которым (маленькие, то есть меньшие, чем ) уже встретились раньше.
x := 50;
n := 1;
while n <= sqrt(x) do begin
if x mod n = 0 then begin
WriteLn(n);
if x div n <> n then begin // Если - целое число, он встретится два раза.
WriteLn(x div n);
end;
end;
n := n + 1;
8 слайд
Общий делитель, НОД
Определение. Если число c является одновременно делителем числа a и делителем числа b, то число c называется общим делителем чисел a и b.
Примеры: 30 - общий делитель 150 и 90, а 6 – общий делитель 24 и 42.
Из сказанного выше следует, что общие делители натуральных чисел x и y лежат в отрезке
[1; min{x, y}]. Из этого в частности следует, что для любой пары натуральных чисел x, y существует наибольший общий делитель, то есть такой общий делитель k, что любой другой общий делитель чисел x и y не n превосходит k: . Наибольший общие делитель чисел x и y будем обозначать НОД(x, y).
9 слайд
Поиск НОД
Задача: даны натуральные x и y. Найти НОД(x, y). Очевидное решение этой задачи таково: перебрать все делители от 1 до min(x, y) и найти максимум.
if x > y then
min := y
else min := x;
max := 1;
n := 1;
while n <= min div 2 do begin
if (x mod n = 0) and (y mod n = 0) then max := n;
n := n + 1; end;
if (x mod min = 0) and (y mod min = 0) then max := min;
WriteLn(max);
10 слайд
Примечание
Заметим, что здесь нет необходимости сравнивать новый делитель с текущим максимумом, поскольку делители перебираются в порядке возрастания, и нам нужно запомнить последний.
Вообще говоря, лучше перебирать числа в порядке убывания, тогда нужно остановиться, найдя первый делитель, не перебирая остальные – заведомом меньшие.
max := min;
while max > 0 do begin
if (x mod max = 0) and (y mod max = 0) then begin
break;
end;
max := max – 1;
end;
11 слайд
Алгоритм Евклида
Утверждение. Если x ≥ y, то НОД(x, y) = НОД(x – y, y)
Доказательство.
Пусть n = НОД(x, y), тогда
x = n * k
y = n * m
где k и m – целые числа.
(x – y) = n * (k – m), следовательно n – делитель x – y. То есть n – общий делитель y и x – y.
Допустим, что существует p – общий делитель x – y и y, такой, что p ≥ n. Тогда y = p* h и (x – y) = p * q, то есть
x = p * q + p * h = p * (q + h).
То есть p – делитель x, следовательно – общий делитель x и y.
Но если p ≥ n, а n = НОД(x, y), то p = n.
Утверждение доказано.
Следствие. НОД(x, y) = НОД(x mod y, y)
Доказательство.
НОД(x, y) = НОД(x – y, y) = НОД(x – 2*y, y) = … = НОД(x – k*y, y) = …
Причем x mod y = x – (x div y) * y = x – m * y.
Следствие доказано.
12 слайд
Алгоритм Евклида
x := 50;
y := 49;
while (x > 0) and (y > 0) do begin
if x > y then
x := x mod y;
else
y := y mod x;
end;
WriteLn(x + y);
13 слайд
НОК
Определение. Пусть x > 0. Если a – делитель x и b – делитель x, то x называется общим кратным a и b.
Примеры:
число x*y всегда является общим кратным x и y.
30 – общее кратное 30 и 2
18 – общее кратное 6 и 9
Определение. Наименьшим общим кратным чисел x и y (НОК(x, y)) называется их общее кратное n, такое, что любое другое общее кратное этих чисел k не превосходит n.
Заметим, что общее кратное x и y не может быть меньше никакого из них. Следовательно НОК существует.
14 слайд
Связь НОК и НОД
Утверждение. x*y = НОД(x, y) * НОК(x, y)
xy := x * y;
x := 50;
y := 49;
while (x > 0) and (y > 0) do
if x > y then x := x mod y; else y := y mod x;
WriteLn(xy div (x + y));
15 слайд
Задачи на использование стандартных типов данных и основных алгоритмических конструкций.
Задача 1. Сколько существует двузначных чисел, сумма квадратов цифр которых делится на 13.
Задача 2. Найти двузначное число, равное сумме цифры его десятков и квадрата цифры его единиц.
Задача 3. Если к сумме цифры двузначного числа прибавить квадрат этой суммы, то снова получится это двузначное число.
Найти все такие числа.
Задача 4. Долгожитель (т.е.человек, проживший более 100лет) заметил, что если к сумме квадратов цифр его возраста
прибавить число его дня рождения (т.е. одно из
чисел от 1 до 31), то получится как раз его возраст. Сколько лет долгожителю?
Задача 5. Найти четырехзначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке
111.
Задача 6. В магазине имеется мастика в ящиках по 16 кг., 17 кг., 21 кг. Как организации получить 185 кг. не вскрывая ящики?
Задача 7. Напечатать все четырехзначные натуральные числа, в десятичной записи которых нет двух одинаковых цифр.
Задача 8. Найти все трехзначные числа, равные сумме кубов своих цифр.
16 слайд
sergey_gartung@mail.ru
17 слайд
Спасибо за внимание!
Рабочие листы
к вашим урокам
Скачать
Данную разработку можно использовать при изучении темы "Циклические алгоритмы", кроме того урок помогает обяснить учащимся, для чего нужно изучение данной темы в программировании.
Кроме этого данный урок позволяет повторить материал, изученный ранее на уроках математики, и кроме того закрепляет знания учащихся по данной теме.
Данная разработка содержит фрагменты программ:
Задачи на использование стандартных типов данных и основных алгоритмических конструкций.
данная разработка поможет начинающим учителям информатики
6 661 650 материалов в базе
Настоящий материал опубликован пользователем Гартунг Сергей Александрович. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
300/600 ч.
Курс профессиональной переподготовки
300/600 ч.
Курс повышения квалификации
36 ч. — 180 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.