Презентация, доклад интегрированного урока математики и информатики по теме Программирование циклических алгоритмов на примерах задач элементарной математики по теме Делимость и алгоритм Евклида

математики по теме «Делимость и алгоритм Евклида»

данную структуру можно указать следующим образом:

условие

Оператор 1

да

нет

1;
На языке блок-схем структура цикла запишется следующим образом:

Параметр цикла

действие

b равен нулю (a mod b = 0), то b называется делителем a. Говорят также, что a делиться на b без остатка.
Можно записать другие эквивалентные формулировки:
a = (a div b)*b
a = n*b, где n – целое число
Определение. Если b является делителем a, то говорят, что a кратно b. Обозначается а b

его положительные делители.
Эту задачу легко решить так: переберем все натуральные числа из отрезка [1; X] и проверим, на какие из них X делится. 
x := 50;
n := 1;
while n <= x do begin
if x mod n = 0 then
WriteLn(n);
n := n + 1;
end;
 

выводить сразу делитель 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;

и делителем числа 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).

решение этой задачи таково: перебрать все делители от 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);

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

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;

– 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.
Следствие доказано.

> 0) do begin
if x > y then
x := x mod y;
else
y := y mod x;
end;
WriteLn(x + y);

b – делитель x, то x называется общим кратным a и b. 
Примеры:
число x*y всегда является общим кратным x и y.
30 – общее кратное 30 и 2
18 – общее кратное 6 и 9
Определение. Наименьшим общим кратным чисел x и y (НОК(x, y)) называется их общее кратное n, такое, что любое другое общее кратное этих чисел k не превосходит n. 
Заметим, что общее кратное x и y не может быть меньше никакого из них. Следовательно НОК существует.

:= 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));

1. Сколько существует двузначных чисел, сумма квадратов цифр которых делится на 13.
Задача 2. Найти двузначное число, равное сумме цифры его десятков и квадрата цифры его единиц.
Задача 3. Если к сумме цифры двузначного числа прибавить квадрат этой суммы, то снова получится это  двузначное число.
Найти все такие числа.
Задача 4. Долгожитель (т.е.человек, проживший более 100лет) заметил, что если к сумме квадратов цифр его возраста
прибавить число его дня рождения (т.е. одно из
чисел от 1 до 31), то получится как раз его возраст. Сколько лет долгожителю?
Задача 5. Найти четырехзначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке
111.
Задача 6. В магазине имеется мастика в ящиках по 16 кг., 17 кг., 21 кг. Как организации получить 185 кг. не вскрывая ящики?
Задача 7. Напечатать все   четырехзначные натуральные числа, в десятичной записи которых нет двух одинаковых цифр.
Задача 8. Найти все трехзначные числа, равные сумме кубов своих цифр.