Если для некоторой пары i, j эта сумма максимальна, то отсюда следует

S(i, j) > S(i + 1, j)

и, следовательно, a_i > 0. Точно так же a_i + a_i+1 > 0.

Если обобщить любое «начало» (левая часть) S(i, j) положительно, и точно так же любой «конец» положителен. Можно продолжать:

a_i−1 отрицателен…

И я таким образом не получил ничего. Это не означает утверждения, что на этом пути нельзя найти решения. Это я его не нашел.

Как я уже говорил, вы можете обратиться к математике за помощью в решении вашей задачи по информатике[28]. Но у информатики есть и свой собственный творческий дух. Почему бы ему не довериться? Эта задача сбивает вас с толку по причине ограничений на сложность алгоритма. Забудем их. Если вам сказано, что нужно решить задачу, и вам предоставлена свобода вплоть до максимальной сложности, что вы будете делать? Вы составите таблицу S (i, j) для i = 1, …, n и j = i, …, n. В этой таблице вы возьмете максимальный элемент.

Чтобы помочь вам, я предлагаю вам рассмотреть следующий вектор:

3 4 −8 2 −3 7 5 −6 1

Образуйте треугольную таблицу чисел S (i, j) и запишите ее. Посмотрите, как каждая строчка образуется из предыдущей. Вы увидите, что только три строчки могут содержать максимальное S и, кроме того, не во всей их полной длине. В этом примере максимум нужно искать среди

(1, 1 : 3), (4, 4 : 5), (6, 6 : 9).

Следовательно, есть в точности n значений S, которые нужно рассматривать. Таким способом вы и получаете алгоритм, линейный по n.

Закончить предоставляю вам.

Головоломка 1.

Первая стратегия. Нужно сравнить u_2i и u_i. Они равны, если 2i = i + kp для целого k, следовательно, если i делится на p. Кроме того, i должно превосходить r. Следовательно, нужно искать наименьшее кратное p, большее или равное r.

Положим v_i = u_2i. Тогда

v_i+1 = u_2i+2 = f(f(u_2i)) = f(f(v_i)).

Если вы начинаете u с u₁ = a, то вы начинаете v с v₁ = f(а).

Таким образом, получаем начало программы:

Теперь вы получили два равных элемента. Чтобы получить период, нужно пройти интервал между полученными числами — например, начиная с u — считая число элементов:

Мне пришлось рассказать вам все…

Вторая стратегия. Начните с d = 1 и h = 1. Если вы не находите периодичности в интервале от d + 1 до d + h (сравнивая u на этом интервале со значением u на элементе d, сохраняемым в некоторой переменной, например, x), возьмите значение u в d + h в качестве нового значения x, d + h в качестве нового d, и удвойте k.

Вы непосредственно получаете период. Тщательно подсчитайте количество вычислений f в каждом из этих двух алгоритмов. Второй способ определенно лучше,

Игра 4.

Если вы представляете игровое ноле прямоугольной таблицей, то перемещение обозначается изменением координат точки: добавлением или вычитанием чисел 1 или 2. Я разместил эти добавляемые количества (целые числа со знаком) в два вектора DX, DY из 8 элементов. Одно направление перемещения задается номером поля в этой таблице, следовательно, целым числом от 1 до 8.

Головоломка 3.

Остановитесь, когда вы получите 5 в качестве цифры единиц с нулем «в уме».

Головоломка 4.

Представленный здесь алгоритм эквивалентен алгоритму, который можно найти в старых книгах по арифметике, и который действует на целые числа, разбитые на куски но 2 цифры в каждом куске. Вы можете либо разыскать доказательство в этих книгах, либо посмотреть в моей книге «Основы программирования», как можно доказать, что программа, реализующая этот алгоритм, действительно вычисляет квадратный корень. Но это рассуждение слишком сложно, чтобы воспроизводить его здесь.

Лично я работаю по основанию 10. Я представляю числа цепочками цифр. Присоединить 1 справа легко: это просто конкатенация. Сдвинуть вправо легко: используется индекс, сообщающий, начиная с какой позиции нужно урезать. Именно этот индекс и изменяется. Складывать с 2 легко, так как может быть не более одного переноса. Единственная тонкая операция — вычитание, Не проводите сравнения перед вычитанием: оно стоит так же дорого, как и само вычитание. Сделайте копию той части, которая должна была бы быть изменена при вычитании, и если вы обнаружите, что вы не можете осуществить вычитание, — возьмите сохраненное значение.

Головоломка 5.

Задайте три индекса и три значения: i₂, i₃, i₅, x₂, x₃, x₅. Число i₂ есть индекс элемента последовательности, который, будучи умноженным на 2, дает подходящего кандидата на роль ближайшего значения (иначе говоря, удвоение числа с индексом i₂ − 1 дает число, которое содержится в уже сформированной части последовательности, но удвоение числа с индексом i₂ дает число, которое в сформированной части не содержится). Число x₂ получается удвоением числа с индексом i₂. Вы определяете аналогично i₃ и x₃ заменяя «удвоение» на «утроение» (произведение на 3 числа с индексом i₃ − 1 содержатся в построенной части последовательности, а число x₃ — утроенное число с индексом i₃ — в ней не содержится). Наконец, вы делаете то же самое для i₅ и x₅. Ближайшее число в последовательности есть наименьшее из чисел x₂, x₃, x₅. Назовем его х. Если x = x₂, то i₂ увеличивается на 1 и x₂ пересчитывается. То же самое для i₃ и i₅.