Язык Си. Алгоритм Свойства алгоритма дискретность состоит из отдельных шагов (команд) понятность
Скачать 4.66 Mb.
|
Задания«5»: Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом. Пример: Введите целое число: Введите целое число: 1232 1224 Нет. Да. «6»: Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры, НЕ обязательно стоящие рядом. Пример: Введите целое число: Введите целое число: 1234 1242 Нет. Да. Задания-2«3»: Ввести целое число и определить, верно ли, что в нём ровно 1 цифра «9». Пример: Введите число: Введите число: 193 1994 Да. Нет. «4»: Ввести целое число и определить, верно ли, что все его цифры четные. Пример: Введите число: Введите число: 2684 2994 Да. Нет. Задания-2«5»: Ввести целое число и определить, верно ли, что все его цифры расположены в порядке возрастания. Пример: Введите целое число: Введите целое число: 1238 1274 Да. Нет. «6»: Ввести целое число и «перевернуть» его, так чтобы первая цифра стала последней и т.д. Пример: Введите целое число: Введите целое число: 1234 782 4321 287 Вычисление НОДНОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. Перебор: Записать в переменную k минимальное из двух чисел. Если a и b без остатка делятся на k, то стоп. Уменьшить k на 1. Перейти к шагу 2. Где будет НОД? ? Почему алгоритм обязательно закончится? ? это цикл с условием! Алгоритм ЕвклидаЕвклид (365-300 до. н. э.) НОД(a,b)= НОД(a-b, b) = НОД(a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7) НОД (1998, 2) = НОД (1996, 2) = … = 2 Пример: много шагов при большой разнице чисел: = НОД (7, 7) = 7 Надо: вычислить наибольший общий делитель (НОД) чисел a и b. Блок-схема алгоритмаa = b? да нет a > b? да a = a - b нет b = b - a начало конец Алгоритм Евклидаwhile ( a != b ) { if ( a > b ) a = a – b; else b = b – a; } Где будет НОД? Как его вывести? ? Как вывести НОД в формате НОД(14,21) = 7? ? А без дополнительных переменных? ? Модифицированный алгоритм ЕвклидаНОД(a,b)= НОД(a % b, b) = НОД(a, b % a) Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее — это НОД. НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7 Пример: Еще один вариант: НОД(2·a,2·b)= 2·НОД(a, b) НОД(2·a,b)= НОД(a, b) | при нечетном b Алгоритм Евклида«3»: Составить программу для вычисления НОД с помощью алгоритма Евклида. «4»: Составить программу для вычисления НОД с помощью модифицированного алгоритма Евклида и заполнить таблицу:
|