Рекуррентные модели и вычисления до заданной точности

1. Рекуррентная модель

На уроке информатики нас интересует не вывод физических формул, а алгоритм. Все необходимые формулы уже приведены в условиях задач.

Мы храним текущее состояние системы и много раз пересчитываем его:

текущее состояние -> изменение -> новое состояние

Один шаг обычно прост. Смысл программы появляется, когда таких шагов десятки, сотни или тысячи.

2. Если величин несколько

Новые значения часто нужно вычислять из одного и того же старого состояния.

dA = A * P div 1000
dB = B * Q div 1000

A_new = A - dA
B_new = B + dA - dB

Сначала вычисляем все новые значения, и только потом выполняем присваивания A = A_new, B = B_new.

3. Применение цикла

Иногда число шагов заранее неизвестно. Например, падение моделируется, пока высота положительна:

while h > 0: 
    # один шаг модели

Здесь цикл заканчивается из-за события: тело достигло земли.

4. Считаем до заданной точности

Иногда процесс математически может продолжаться очень долго, но изменения становятся настолько малы, что дальнейший расчёт уже несущественен.

Пусть eps — допустимая малая величина. Тогда общий шаблон такой:

while True: 
    new_value = ...

    if abs(new_value - value) < eps: 
        value = new_value    # этот шаг тоже учитываем
        break
    

    value = new_value

Важно: если в условии сказано, что первый шаг с изменением меньше eps считается последним, этот шаг нужно выполнить и включить в результат.

5. Ряд до точности

Пусть сумма строится по одному слагаемому:

S_new = S + a

Тогда

abs(S_new - S) = abs(a)

Поэтому условие точности можно проверять либо по изменению суммы, либо по модулю очередного слагаемого — если это прямо следует из модели.

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

6. Один алгоритмический шаблон — разные сюжеты

Критерий abs(new - old) < eps встречается не только в суммах рядов.

• остывание: температура почти перестала меняться;
• зарядка конденсатора: заряд почти достиг предельного значения;
• отскоки мяча: очередной отскок почти не меняет суммарный путь;
• итерационные вычисления: новое приближение почти совпало с предыдущим.

Алгоритмически это один и тот же микропаттерн.

7. Симуляция как часть другого алгоритма

После того как вы научились запускать одну модель, её можно вызывать много раз для разных параметров:

for каждый parameter:
    result = simulate(parameter)
    if result подходит :
        ...

Так решаются задачи на самый поздний момент раскрытия парашюта или максимальную безопасную скорость.

Чеклист

1. Что является состоянием?
2. Как вычисляется следующий шаг?
3. Все ли новые величины считаются из старого состояния?
4. Когда заканчивается цикл: по событию, по числу шагов или по точности?
5. Если остановка по eps, учитывается ли последний шаг?
6. Что нужно накапливать во время процесса?
7. Нужно ли запускать модель один раз или много раз?