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-}
), иначе она
вам такого тут наоптимизирует…