Главная страница
Навигация по странице:

  • Введите целое число: Введите целое число: 1234 1242 Нет. Да. Задания-2

  • «4»: Ввести целое число и определить, верно ли, что все его цифры четные.

  • Задания-2

  • Введите целое число: Введите целое число: 1238 1274 Да. Нет. «6»: Ввести целое число и «перевернуть» его, так чтобы первая цифра стала последней и т.д.

  • НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7) НОД (1998, 2) = НОД (1996, 2) = … = 2 Пример

  • НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7 Пример: Еще один вариант: НОД(2·a,2·b)= 2·НОД(a, b)

  • «3»: Составить программу для вычисления НОД с помощью алгоритма Евклида. «4»: Составить программу для вычисления НОД с помощью модифицированного алгоритма Евклида и заполнить таблицу

  • Язык Си. Алгоритм Свойства алгоритма дискретность состоит из отдельных шагов (команд) понятность


    Скачать 4.66 Mb.
    НазваниеАлгоритм Свойства алгоритма дискретность состоит из отдельных шагов (команд) понятность
    Дата05.02.2023
    Размер4.66 Mb.
    Формат файлаppt
    Имя файлаЯзык Си.ppt
    ТипПрограмма
    #921318
    страница5 из 11
    1   2   3   4   5   6   7   8   9   10   11

    Задания





    «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»: Составить программу для вычисления НОД с помощью модифицированного алгоритма Евклида и заполнить таблицу:


    a


    64168


    358853


    6365133


    17905514


    549868978


    b


    82678


    691042


    11494962


    23108855


    298294835


    НОД(a,b)

    1   2   3   4   5   6   7   8   9   10   11


    написать администратору сайта