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

Задачи

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

Задача 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).

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

Решение

Задача 76214

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

Сложность: 2

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

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

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

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

Задача 76217

Темы:	[	Знакомство с циклами	]
Темы:	[	Задачи с целыми числами	]

Сложность: 2

Та же задача, но разрешается использовать из арифметических операций лишь сложение и вычитание, причём общее число действий должно быть порядка n.

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

Задача 76226

Темы:	[	Знакомство с циклами	]
	[	Задачи с целыми числами	]
	[	Десятичная запись числа	]

Сложность: 2

Даны натуральные числа n и k, n > 1. Напечатать k десятичных знаков числа 1/n. (При наличии двух десятичных разложений выбирается то из них, которое не содержит девятки в периоде.) Программа должна использовать только целые переменные.

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

Задача 76228

Темы:	[	Знакомство с циклами	]
	[	Задачи с целыми числами	]
	[	Десятичная запись числа	]

Сложность: 2

(Сообщил Ю. В.Матиясевич) Дана функция f : {1...N} $\to$ {1...N} Найти период последовательности 1, f(1), f(f(1), ... Количество действий должно быть пропорционально суммарной длине предпериода и периода (эта сумма может быть существенно меньше N)

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

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