ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

Написать вариант алгоритма Евклида, использующий соотношения

НОД(2a, 2b) = 2·НОД(a,b),
НОД(2a,b) = НОД(a,b)      при нечётном b,

не включающий деления с остатком, а использующий лишь деление на 2 и проверку чётности. (Число действий должно быть порядка log k для исходных данных, не превосходящих k.)

   Решение

Задачи

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 40]      



Задача 76203

Тема:   [ Знакомство с циклами ]
Сложность: 2

Дано натуральное (целое неотрицательное) число а и целое положительное число d. Вычислить частное q и остаток r при делении а на d, не используя операций div и mod.
Прислать комментарий     Решение


Задача 76211

Темы:   [ Знакомство с циклами ]
[ Задачи с целыми числами ]
[ НОД и НОК. Алгоритм Евклида ]
Сложность: 2

Даны натуральные a и b, не равные 0 одновременно. Найти d = НОД(a,b) и такие целые x и y, что d = a . x + b . y.
Прислать комментарий     Решение


Задача 76212

Темы:   [ Знакомство с циклами ]
[ Задачи с целыми числами ]
[ НОД и НОК. Алгоритм Евклида ]
Сложность: 2

Решить предыдущую задачу, используя в алгоритме Евклида деление с остатком.
Прислать комментарий     Решение


Задача 76213

Темы:   [ Знакомство с циклами ]
[ Задачи с целыми числами ]
[ НОД и НОК. Алгоритм Евклида ]
Сложность: 2

(Э. Дейкстра) Добавим в алгоритм Евклида дополнительные переменные u, vz:

         m := a; n := b; u := b; v := a;
        {инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
        while not ((m=0) or (n=0)) do begin
        | if m >= n then begin
        | | m := m - n; v := v + u;
        | end else begin
        | | n := n - m; u := u + v;
        | end;
        end;
        if m = 0 then begin
        | z:= v;
        end else begin {n=0}
        | z:= u;
        end;
Доказать, что после исполнения алгоритма значение z равно удвоенному наименьшему общему кратному чисел ab: z = 2 . НОК(a, b).
Прислать комментарий     Решение

Задача 76214

Темы:   [ Знакомство с циклами ]
[ Задачи с целыми числами ]
[ НОД и НОК. Алгоритм Евклида ]
Сложность: 2

Написать вариант алгоритма Евклида, использующий соотношения

НОД(2a, 2b) = 2·НОД(a,b),
НОД(2a,b) = НОД(a,b)      при нечётном b,

не включающий деления с остатком, а использующий лишь деление на 2 и проверку чётности. (Число действий должно быть порядка log k для исходных данных, не превосходящих k.)
Прислать комментарий     Решение


Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 40]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .