6.12. Все задачи

Задача 6.1: Докажите все эти утверждения.

Задача 6.2: Додумайте тут все оставшиеся детали, т.е., как, зная период, предпериод и \(N\), найти \(N\)-й член последовательности. Не забудьте про существование предпериода: а именно, как про то, что \(N\) может оказаться меньше длины предпериода, так и про то, что период начинается не с первого члена.

Задача 6.3: На первый взгляд может показаться, что надо бы делать проверку \(a=b\) два раза за цикл: после каждого увеличения \(b\):

...
  a:=f(a);
  b:=f(a);
  if a=b then break;
  b:=f(a);
...

типа того (т.е. и соответственно исправить подсчёт длин периода и предпериода), чтобы не получилось так, что \(b\) «перескочит» через \(a\). Поймите, почему этого можно не делать.

Задача 6.4: Попробуйте написать этот код сами. Я его приведу ниже, но постарайтесь как-нибудь написать его сами, прежде чем читать дальше.

Задача 6.5: Поэкспериментируйте с операцией not в других типах. В частности, верно ли, что в знаковых типах (shortint, integer, longint) not может давать отрицательные значения? Должен бы.

Задача 6.6: Поэкспериментируйте с операцией shl в других типах. В частности, верно ли, что в знаковых типах (shortint, integer, longint) shl может давать отрицательные значения? Вроде действительно может давать.

Задача 6.7: Как быстро с помощью битовых операций вычислить максимальную степень двойки, на которую делится данное число? Ответ должен быть просто арифметическим выражением, без всяких циклов и т.п. и, например, для числа 40 давать ответ 8.

Обязательное :) задание 6.8: Напишите простую программу, которая будет считать время выполнения разных операций — просто выполняя их много раз подряд и считая время выполнения такого блока, примерно по следующему шаблону:

begin
вывести текущее время
for i:=1 to 1000000 do begin
    c:=a+b;
    c:=a+b;
    ...
    c:=a+b;
end;
вывести текущее время
end.

Несколько сложений внутри цикла сделано, чтобы основное время программа тратила именно на сложение, а не на «накладные расходы»: увеличение i и сравнение его с верхним пределом цикла. Верхний предел цикла, конечно, стоит подбирать, чтобы программа работала не слишком быстро (иначе таймер успеет слишком мало измениться), но и не слишком медленно (чтобы вам не надоело ждать :)), имхо оптимальное время работы порядка секунды. Обратите внимание на то, как я считаю время работы. Посмотрите, сколько времени занимает сложение/вычитание, умножение, деление (div и mod) целых чисел (на примере integer и/или longint), сколько занимают аналогичные операции с вещественными числами (можете сравнить все четыре вещественных типа: single, double, extended и real); посмотрите, сколько времени занимают shr, shl, побитовые and, or и т.д. При желании можете посмотреть, как влияет {$R+} на время работы с массивами и т.п. Только делайте все c отключённой оптимизацией ({$O-}), иначе она вам такого тут наоптимизирует…