Указания исполнителю. Наиболее трудным в предлагаемой задаче является отслеживание всех автомобилей на дороге[24]. Можно организовать цикл и примерно через одну сотую — одну десятую секунды модельного времени должным образом подправлять положение каждого автомобиля. Если интервал достаточно мал, заметного накопления ошибок не произойдет, а выглядеть программа будет красиво — как семейство вложенных циклов. Однако при использовании метода пошаговой фиксации цикл может выполняться слишком большое число раз. В нашем случае эксперимент продлится примерно 12 минут модельного времени, в каждый момент на дороге будет около 90 машин, и, даже если выбрать большой интервал в одну десятую секунды, потребуется примерно 1200 циклов, или около 650 000 операций с отдельными автомобилями. Если программа тратит много времени на продвижение одного автомобиля, эксперимент слишком затянется. Положение можно подправить, варьируя интервал в зависимости от дорожной обстановки.
Другой подход состоит в том, чтобы подправлять положение автомобилей только в моменты критических событий. При таком подходе заводится список всех событий, ожидаемых в недалеком будущем; например, запускается или исчезает автомобиль, одна машина догоняет другую, прошло две минуты с момента исчезновения первого автомобиля, пора вновь ускорять автомобиль-виновник. Головным элементом списка событий всегда должно быть ближайшее событие; список в целом не обязан быть упорядоченным — его можно представить и как очередь с приоритетами, и как кучу. В основном цикле от списка отделяется головной элемент, описывающий очередное событие, все автомобили устанавливаются в позиции, соответствующие новому времени, запоминаются все события, которые следует планировать, эти события вставляются в список и список переупорядочивается, чтобы ближайшее событие оказалось в голове. Достоинство моделирования методом критических событий в том, что порой довольно долго, 4–5 секунд, ничего не происходит. Сэкономленное время можно употребить на более сложную обработку списка событий.
Инструментовка. Для решения этой задачи естественно воспользоваться языками моделирования, такими, как Симскрипт или Симула. Если они недоступны, подойдет любой процедурный язык. Независимо от метода моделирования существенным подспорьем будут хорошие структуры данных для представления информации об автомобилях и для реализации очереди событий.
Длительность исполнения. Одному исполнителю на 3 недели; еще неделя на изготовление фильма.
Развитие темы. Строго говоря, в предложенной задаче не изучается ситуация, описанная в нескольких первых абзацах. Вместо выяснения того, что происходит с ударной волной при различных средних скоростях движения на автостраде, в эксперименте рассматривались удары различной силы. Проделайте все еще раз, взяв диапазон начальных скоростей от 40 до 50 или от 60 до 70 миль в час. Попробуйте для некоторых переменных нормальное распределение вместо равномерного. Поварьируйте законы торможения и ускорения. Иными словами, изучите влияние всех параметров, а не только одного, выбранного нами.
Герман, Гардел (Herman R., Gardels К). Vehicular Traffic Flow. Scientific American, pp. 35–43, December 1963.
Авторы описывают проведение нескольких физических экспериментов над движением транспорта и развитие математической теории. Конечно, использовавшийся ими Голландский туннель в Нью-Йорке для большинства из нас недоступен Если вам интересно проследить за работами по этой тематике после 1963 г., научитесь пользоваться Science Citation Index или другими библиографическими средствами, помогающими довести старую информацию до наших дней.
18.
Читаем, пишем, считаем,
или Конструирование интерпретатора форматов
Вам, вероятно, пришлось написать по крайней мере одну программу, которая исторгала из машины бумажный поток, несущий искусно оформленные данные. Строка за строкой сомкнутыми рядами выступали из печатающего устройства целые батальоны чисел под предводительством четких заголовков. Интересовали вас только лишь два или три числа, но не напечатать всего было как-то неловко — ведь это так просто! А вдруг кому-то и в самом деле захочется узнать точную сумму налога для служащего 1793 на рабочем месте 907, выплаченную им в сентябре пять лет назад.
24
Дополнительную трудность вызывает использование традиционных английских мер. Однако сделано это умышленно, и вы должны выдавать результаты в тех же единицах. Если бы скорость измерялась в д/д, т. е. в дюймах в день, было бы еще хуже…