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

Интегрированный урок математики и информатики«Программирование циклических алгоритмов на примерах задач элементарной математики по теме «Делимость и алгоритм Евклида» Виды циклических алгоритмовЦикл «Пока»Цикл «До»Цикл с параметром Структура цикла «Пока»While условие выполнения цикла do оператор 1;На языке блок-схем данную структуру можно указать следующим образом:условиеОператор 1данет Структура цикла с параметромfor параметр := нач.знач to кон.знач do оператор 1;На языке блок-схем структура цикла запишется следующим образом:Параметр цикладействие ДелителиОпределение. Если остаток от деления целого числа a на целое число b равен нулю (a mod b = 0), то b называется делителем a. Говорят также, что a делиться на b без остатка.Можно записать другие эквивалентные формулировки:a = (a div b)*ba = n*b, где n – целое числоОпределение. Если b является делителем a, то говорят, что a кратно b. Обозначается а b Нахождение делителейЗадача: дано натуральное число 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;  На самом деле можно перебирать числа до и выводить сразу делитель 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; Общий делитель, НОДОпределение. Если число 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). Поиск НОДЗадача: даны натуральные x и y. Найти НОД(x, y). Очевидное решение этой задачи таково: перебрать все делители от 1 до min(x, y) и найти максимум. if x > y then min := yelse 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; Алгоритм ЕвклидаУтверждение. Если x ≥ y, то НОД(x, y) = НОД(x – y, y) Доказательство.Пусть n = НОД(x, y), тогдаx = n * ky = 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.Следствие доказано. Алгоритм Евклида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); НОКОпределение. Пусть x > 0. Если a – делитель x и b – делитель x, то x называется общим кратным a и b. Примеры: число x*y всегда является общим кратным x и y.30 – общее кратное 30 и 218 – общее кратное 6 и 9Определение. Наименьшим общим кратным чисел x и y (НОК(x, y)) называется их общее кратное n, такое, что любое другое общее кратное этих чисел k не превосходит n. Заметим, что общее кратное x и y не может быть меньше никакого из них. Следовательно НОК существует. Связь НОК и НОДУтверждение. 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)); Задачи на использование стандартных типов данных и основных алгоритмических конструкций. Задача 1. Сколько существует двузначных чисел, сумма квадратов цифр которых делится на 13.Задача 2. Найти двузначное число, равное сумме цифры его десятков и квадрата цифры его единиц.Задача 3. Если к сумме цифры двузначного числа прибавить квадрат этой суммы, то снова получится это  двузначное число. Найти все такие числа.Задача 4. Долгожитель (т.е.человек, проживший более 100лет) заметил, что если к сумме квадратов цифр его возраста прибавить число его дня рождения (т.е. одно из чисел от 1 до 31), то получится как раз его возраст. Сколько лет долгожителю?Задача 5. Найти четырехзначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111.Задача 6. В магазине имеется мастика в ящиках по 16 кг., 17 кг., 21 кг. Как организации получить 185 кг. не вскрывая ящики?Задача 7. Напечатать все   четырехзначные натуральные числа, в десятичной записи которых нет двух одинаковых цифр.Задача 8. Найти все трехзначные числа, равные сумме кубов своих цифр. sergey_gartung@mail.ru Спасибо за внимание!