Каталог по темам

Задачи

Страница: 1 2 >> [Всего задач: 7]

Задача 76209

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

Сложность: 2-

Даны два натуральных числа a и b, не равные нулю одновременно. Вычислить НОД(a,b) — наибольший общий делитель а и b.

Прислать комментарий Решение

Задача 76210

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

Сложность: 2-

Написать модифицированный вариант алгоритма Евклида, использующий соотношения НОД(a,b) = НОД(a mod b, b) при a≥b, НОД(a,b) = НОД(a, b mod a) при b≥a.

Прислать комментарий Решение

Задача 76211

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

Сложность: 2

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

Прислать комментарий Решение

Задача 76212

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

Сложность: 2

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

Прислать комментарий Решение

Задача 76213

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

Сложность: 2

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

         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).

Прислать комментарий

Решение

Страница: 1 2 >> [Всего задач: 7]