Александр Кулаков
(продолжение; начало в КвШ № 2, 1998)
Решения задач:
Задача 1.
Делители числа 24={1,2,3,4,6,8,12,24};
Делители числа 54={1,2,3,6,9,18,27,54};
Общие делители чисел 24 и 54 ={1,2,3,6}; НОД(24,54)=6.
Задача 3.
Число различных делителей равно (m1 +1)(m2 +1) ... ( mk +1).
Степень, например, при p1 может принимать (m1 + 1) различных значений от 0 до
m1 включительно, и т. д.
Задача 4.
НОД (27563, 4773) = 43.
Задача 5.
Число m делится на k - это означает, что существует целое
число m1 такое, что m= m1 k; число n делится на k - это означает, что существует
целое число n1, такое, что m= n1 k. Тогда m - n = m1 k - n1 k = (m1 - n1 ) k.
т. е. разность тоже делится на k. Точно так же доказывается утверждение про
сумму.
Задача 6.
При решении задачи 6 помогает прием, который мы не раз будем
применять. "Перевернем" вопрос в задаче. Зададим себе вопрос: какое наибольшее
число можно получить, выполняя АЛГ3 в обратном порядке? Если НОД(m,n)=k, то
на k можно поделить - число выполнений шага 1 в работе нашего алгоритма не изменится.
Поэтому мы на самом деле будем решать другую задачу: какого наибольшего числа
можно достичь за s шага 1, выполняя АЛГ3 в обратном порядке, если НОД(m,n)=1?
Алгоритм АЛГ3, написанный в обратном порядке, выглядит так:
n0 = n1 =1; nk+1 = nk + nk-1 (1)
Действительно, чтобы достичь наибольшего числа, мы должны
каждый раз от пары (m,n) к паре (m+n,m), тогда на следующем шаге мы получим
большее число, ведь (m+n)+m > (m+n)+n. Числа nk, удовлетворяющие условиям (1),
называются числами Фибоначчи и обозначаются Fk . А теперь обратим полученный
ответ: если числа m>n таковы, что Fs-1 < m ( Fs , то мы получим НОД(m,n) не
более чем за s шагов. А если мы будем не вычитать каждый раз, а делить, то число
шагов только уменьшится. Итак, мы решили несколько иную задачу (для математика
это обычное явление - изменить условие в процессе решения, главное, вместе с
водой не выплеснуть ребенка).
Задача.
Даны числа m и n (m>n). За какое число операций выполнения
шага 1 в АЛГ-Е (в самом худшем варианте) мы найдем НОД(m,n)?
Ответ: если Fs-1 < m ( Fs, то не более чем за s шагов,
причем наихудший вариант достигается на соседней паре чисел Фибоначчи.
Известно, что числа Фибоначчи растут в геометрической прогрессии,
а именно, что Fs < (s +1, т. е. наибольшее из чисел пары (m,n) уменьшается не
менее, чем в ( раз, где ( - больший корень уравнения (2 +( - 1 = 0. Это утверждение
можно рассматривать как еще одну задачу, а можно спросить о свойствах чисел
Фибоначчи у математиков. Итак, если наибольшее из чисел m записывается s цифрами,
то АЛГ-Е найдет НОД(m,n) не более чем за c s операций, где константа c, как
говорят математики, универсальная, т. е. не зависит от чисел m и n.
Вернемся теперь к задаче А.
Первое и самое естественное решение задачи А - это взвешивать
монеты по парам. В самом худшем варианте, когда фальшивая монета окажется в
последней паре, нам придется сделать 49 взвешиваний. При этом мы не до конца
используем свои ресурсы - каждая монета будет взвешиваться только один раз.
Вообще, задачи на определение фальшивых монет - алгоритмического
характера. Каждому из вас когда-то приходилось решать такую задачу:
Задача 7.
Дано 9 монет, одна из них фальшивая (более легкая). Найдите
ее за 3 взвешивания (если этого сделать нельзя, то решите задачу и сформулируйте
ответ в виде алгоритма). Эту задачу можно обобщить:
Задача 8.
Дано n монет, одна из них фальшивая (более легкая). За какое
наименьшее число взвешиваний всегда можно найти фальшивую монету? Решение задач
подразумевает создание алгоритма, с помощью которого независимо от "входных
данных" (в данном случае от того, какая монета фальшивая) можно найти фальшивую
монету и вычисление максимального числа взвешиваний по всем таким "входным данным".
Мы хотим, чтобы это максимальное число было как можно меньше.
Алгоритм решения этой задачи вам хорошо известен.
АЛГ4
Дано n монет.
Шаг 1. Поделим монеты на 3 примерно равные кучки, в
двух из которых равное число монет. Пусть число монет в кучках (n1, n1,m), (|n1-m|<2)
Шаг 2. Положим первую и вторую кучку на весы и взвесим.
Если весы в равновесии, то сравним число m с 1
Если m=1, то фальшивая монета на столе,
если m>1, то перейдем к шагу 1 с третьей кучкой.
Если равновесие нарушено, то перейдем к шагу 1 с более легкой
кучкой, предварительно сравнив число n1 с 1.
В любой ситуации каждый раз число монет уменьшается примерно
в 3 раза. Переформулируем вопрос в задаче 8:
Задача 9.
Из какого наибольшего числа монет в условиях задачи 8 за s
взвешиваний можно выделить фальшивую монету?
Алгоритм АЛГ4 дает решение задачи 9. А именно, если 3(s-1)
< n ( 3 s, то фальшивую можно найти за не более чем s взвешиваний. Алгоритмы
с такой оценкой числа операций называются логарифмическими (для тех, кто знает,
что такое логарифм: s ~ log n).
Но алгоритм АЛГ4 не решает задачу А. Может оказаться, что
фальшивая монета все время попадает на весы. Ситуация, описанная в задаче А,
может быть вполне реальной. Ведь вместо слова "взвешивание" в задаче можно поставить
слово "сравнение". В этом случае, вполне возможно, окажется, что каждое такое
"сравнение" немного разрушает объекты, которые мы сравниваем. Мы же хотим в
результате работы работы эксперта не только узнать, что "фальшивой" монетой
оказалась уже полностью "разрушенная" монета, например с номером 57, но и получить
саму эту монету. Может быть, она для нас по какой-то причине бесценна.