50 − 1 = 49,
49 − 3 = 46,
46 − 5 = 41,
41 − 7 = 34,
34 − 9 = 25,
25 − 11 = 14,
14 − 13 = 1.
Нельзя продолжать, не получая отрицательной разности. Последнее нечетное вычитаемое равно 13, поэтому корень есть (13 + 1)/2 = 7 (и остаток 1). Этот способ гораздо лучше подходит для распространения на случай очень больших чисел, потому что вам требуется реализовать только две операции:
— прибавить 2 к большому числу;
— вычесть одно большое число из другого.
Но число шагов цикла равно искомому квадратному корню, а он может оказаться весьма большим.
Можно обобщить предыдущий алгоритм, используя свойства десятичной записи чисел. Данное число разделяется на куски по две цифры, начиная справа; затем мы начинаем вычитать последовательные нечетные числа из крайнего слева куска:
Если это нельзя продолжать дальше, то последнее вычитаемое число увеличивается на единицу, сдвигается на один шаг вправо, и следом за ней приписывается единица. Это — первое нечетное число, которое следует вычитать из предыдущего остатка.
В приведенном выше примере 7 + 1 = 8; приписывая 4, получаем 81 и продолжаем:
Поскольку продолжать дальше нельзя (последнее возможное вычитание из остатка — это крайнее справа), то последнее из вычитаемых чисел нужно увеличить на 1, а затем разделить на 2, чтобы получить корень. Последний остаток и есть остаток квадратного корня:
85 + 1 = 86, 86/2 = 43,
1909 = (43)2 + 60.
Этот алгоритм достаточно прост для программирования при длинных числах, и он дает вполне разумное время вычисления.
У вас много возможностей представлять свои данные. Так как мы оперируем с кусками из двух цифр, то вы можете задавать свои данные таблицами целых чисел в интервале от 0 до 99.
Вы можете представлять свои целые числа как цепочки символов, где используются только числовые символы (цифры) от 0 до 9. Выбор способа зависит от ваших предпочтений и от возможностей вашей машины оперировать с таблицами и цепочками. Тщательно рассмотрите, какие операции нужно сделать. Вы ничем не ограничены: почему бы не запрограммировать и сравнить два разных решения?
Я предложил вам алгоритм без доказательства. Поэтому попытайтесь его проверить…
Я предложил вам алгоритм для десятичной системы счисления. Можно предложить похожий алгоритм для двоичной системы. Тогда не возникнет цикл вычитаний последовательных нечетных чисел из каждого куска, поскольку в куске есть только одно нечетное число: 1. Алгоритм упрощается: если можно вычесть нечетное число — мы его вычитаем, в противном случае мы не делаем ничего. Затем сдвигаем, добавляем 1 и приписываем 1 в конце… Этот алгоритм намного легче реализовать. Но тогда нужно сначала перейти к основанию 2, а затем преобразовать двоичный результат в десятичный. Вам следует посмотреть, что более эффективно…
Головоломка 5.
Аккуратно поставим задачу. То, что от вас требуется, — это не взятая глобально последовательность, а вот что: если начало последовательности выписано, то нужно найти следующее число. Возьмем пример, данный в головоломке 5: какое число следует за 50?
Есть ровно три возможности.
1. Число делится на 2. После однократного деления на 2 оно не будет иметь других делителей нуля, кроме 2, 3 и 5. Следовательно, это число — из последовательности. Так как 50 : 2 = 25, то полученное частное больше, чем 25. Наименьшее число последовательности, большее 25, есть 27. Таким образом, если следующее за 50 число делится на два, то оно равно 2 × 27 = 54.
2. Оно делится на 3. То же рассуждение. 50 : 3 = 16,7. Первое число последовательности, большее 16,7, есть 18. Если следующее за 50 число делится на 3, то это число равно 3 × 18 = 54.
3. Оно делится на 5. 50 : 5 = 10. Следующее за 10 равно 12,
5 × 12 = 60.
Таким образом, у нас 3 кандидата: 54, 54, 60. Наименьшее из этих трех и есть искомое.
Мы получили 54, используя только уже вычисленную часть последовательности Хэмминга.
Я предложил вам идею решения на примере. Вам следует ее обобщить, показать, что это всегда верно, и составить хорошую программу для решения.
Головоломка 6.
Я предлагаю вам начать с образования различных числовых последовательностей, получаемых вычеркиванием чисел. Вот первые из них:
1 : 2 3
2 : 3 5 7
3 : 5 7 11 13 17