Фильтр
Задачи
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 40]
Дано натуральное (целое неотрицательное) число а
и целое положительное число d. Вычислить частное q
и остаток r при делении а на d, не используя
операций div и mod.
Даны натуральные a и b, не равные 0
одновременно. Найти d = НОД(a,b) и такие
целые x и y, что
d = a . x + b . y.
Решить предыдущую задачу, используя в алгоритме Евклида
деление с остатком.
(Э. Дейкстра) Добавим в алгоритм Евклида дополнительные
переменные u, v, z:
Написать вариант алгоритма Евклида, использующий
соотношения
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 40]
Задача 76203 |
|
|
|
|
Решение |
Задача 76211 |
|
|
|
|
|
Решение |
Задача 76212 |
|
|
|
|
|
Решение |
Задача 76213 |
|
|
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
равно удвоенному наименьшему общему кратному
чисел a, b:
z = 2 . НОК(a, b).
|
|
|
Решение |
Задача 76214 |
|
|
НОД(2a, 2b) = 2·НОД(a,b),
НОД(2a,b) = НОД(a,b)
при нечётном b,
не включающий деления с остатком, а использующий лишь
деление на 2 и проверку чётности. (Число действий
должно быть порядка
log k для исходных данных,
не превосходящих k.)
|
|
|
Решение |
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 40]
