Фильтр
Задачи
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 34]
Даны натуральные a и b, не равные 0
одновременно. Найти d = НОД(a,b) и такие
целые x и y, что
d = a . x + b . y.
Решить предыдущую задачу, используя в алгоритме Евклида
деление с остатком.
(Э. Дейкстра) Добавим в алгоритм Евклида дополнительные
переменные u, v, z:
Написать вариант алгоритма Евклида, использующий
соотношения
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 34]
Задача 64152 |
|
|
Задача Иосифа Флавия Существует легенда, что Иосиф Флавий - известный историк первого века - выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю. В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелеет только один человек. (Например, если N=10, k=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.) Задача: определить номер уцелевшего. Входные данные: числа N и k вводятся из файла INPUT.TXT. Ограничения: 1<=N<=500, 1<=k<=100. Выходные данные: Программа должна выдавать номер уцелевшего человека в файл OUTPUT.TXT. Пример входного файла: 10 3 Пример выходного файла: 4
|
|
Решение |
Задача 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 >> [Всего задач: 34]
