3.5.7. Разбиения целых чисел. Определите количество вычислений, совершаемых FUNCTION Q{M, N) для получения Q{M, N). Нужно ли знать все значения Q{A, В) для А<-М и В<:Л/, чтобы вычислить Q(M, N)?

**3.5.8. Разбиения целых чисел. Предположим, мы хотим послать по почте посылку и почтовая плата составляет 84 цента. Предположим далее, что все, что у нас есть, это Б большом количестве 4-, 6- и 10-центовые марки. Сколькими разными способами можно отобрать марки для посылки? Пусть S{N) означает число разбиений целого N, использующих только числа 4, 6 и 10. Выразите рекурсивно S{N), обобщив рекуррентное соотношение для чисел Фибоначчи.

3.5.9. Идентификаторы Фортрана. Напишите программу, принимающую в качестве ввода произвольную цепочку символов X и выдающую YES, если X - правильный идентификатор. Предположите, что X считывается по одному символу.

***3.5.10. Вероятностная рекурсия. Игра имеет следующие правила. Перед вами большое число ящиков с деньгами. Сумма денег в каждом ящике - случайная величина, равномерно распределенная на [О, 1]. Вы выбираете ящик, открываете его и или берете деньги из ящика, или отказываетесь от них. Если вы берете деньги, игра кончается. В противном случае вы можете выбрать другой.япдак. Эта процедура повторяется максимум до пяти ящиков (деньги из пятого ящика должны быгь взяты, если он открыт). Каким образом можно попытаться максимизировать ожидаемый выигрыш?

**3.5.11. Пусть требуется провести на плоскости п замкнутых кривых Ci, . . . , С„ Б соответствии со следующими правилами: (а) никакая кривая не пересекает саму себя; (б) Ci проводится произвольно; (в) для каждого i>2 С,- пересекает каждую из кривых Cj, Q, . . ., C,--i ровно в двух различных точках; (г) никакие три кривые не пересекаются в одной точке. Пусть R (п) обозначает число областей на плоскости, определенных построением п замкнутых кривых по указанным выше правилам. Верно ли, что R(\)=2 и /?(2)=4? (Заметим, что всегда есть неограниченная область, содержащая «точку» бесконечности.)

Выведите общее рекуррентное соотношение для R{n) через R{n-\). Вычислите

R(\), R{2)...../?(25). Если вам не знаком никакой рекурсивный язык, проделайте

это, проходя последовательно от R{\) до R{2b).

3.6. Моделирование

Большая часть алгоритмов, представленных в этой книге, решает относительно простые задачи. Многие из этих задач легко сформулировать и смоделировать. Они содержат не много параметров, и обычно их можно решить аналитически. Более того, получающиеся алгоритмы довольно компактны.

Эти задачи резко отличаются от задач, описывающих большие системы, например, для (1) военных расчетов, (2) космических полетов, (3) принятия административных решений, (4) управления производством, (5) сетей связи или (6) картотек и инвентаризационных описей.

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

Появление ЭВМ позволило подойти к изучению таких сложных систем при помощи моделирования. Машинное моделирование - это

процесс экспериментирования на ЭВМ над моделью динамической системы. Непосредственная цель этих экспериментов - наблюдение за поведением системы при заданных предположениях, условиях и значениях параметров. Конечной целью может быть: (1) формулирование стратегии управления, (2) определение оптимальных или возможных конфигураций системы, (3) установление реальных производственных планов или (4) решение вопроса об оптимальных экономических стратегиях.

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

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

Кто-то вполне может задать вопрос: почему мы не прибегаем к моделированию во всех случаях? Существует несколько частичных ответов на этот вопрос. Во-первых, моделирование - это экспериментальный метод. Поэтому всегда возникает серьезный вопрос, как истолковать результаты. Важно пойять, что достоверность выходных данных зависит от того, в какой степени модель и основные допущения отражают характеристики системы. Машинная имитация может стать дорогостоящей, если модель становится чрезмерно детализированной.

Область имитационного моделирования слишком обширна, чтобы всесторонне охватить ее здесь. Для наших целей достаточно будет представить несколько важных соображений, относящихся к построению имитационных моделей; мы также проиллюстрируем их одним-двумя примерами. Это должно помочь читателю подойти к разработке и анализу вычислительного имитационного алгоритма достаточно разумно.

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

машинных моделях. Задачи об очередях допускают также большое число разных предположений и обобь1ений, что делает их хорошими примерами для дальнейшего изучения.

Основными объектами в простой очереди (линии обслуживания) являются клиенты, прибывающие через случайные интервалы времени, и обслуживающее устройство, которое обслуживает каждого клиента в течение случайного интервала времени. Когда клиенты прибывают, их или сразу обслуживают, или они выстраиваются, образуя очередь, и их обслуживают по принципу: первым пришел - первым обслужен. Рис. 3.6.1 иллюстрирует систему одна очередь/ одно обслуживающее устройство.

ЛрииыНтщае

О О О О О о

Очередь 0с/!1/жа6ающее

устройстдо

Piic. 3.6.1. Система «одна очередь / o.iho обслуживающее устройство».

Функциопирование такой очереди определяется следующими характерными особенностями и предположениями:

1. Имеется случайная переменная X, которая определяет время прибытия следующего клиента. Существует несколько возможностей для решения вопроса о времени прибытия клиента. Мы будем предполагать, что если клиент К прибывает в момент времени t, то клиент /С+1 прибывает в момент t VT, где Т - случайная перегленная, значение которой лежит между 1 и некоторым фиксированным целым числом МАХА, с заданным распределением вероятностей.

2. Имеется случайная переменная S, определяющая, сколько времени длится обслуживание клиента /\. Предполагается, что значение величины S лежит между 1 и некоторым другим фиксированным целым числом МАХС с заданным распределением вероятностей. Если обслуживание начато, оно продолжается до полного завершения, т. е. не допускается прерывание или обслуживание с приоритетом.

3. Существует очередь клиентов, обслуживаемая по принципу: первым пришел - первым обслужен. Как только клиент встает в очередь, он остается в ней, пока не будет обслужен. Сразу после обслуживания он покидает систему.

4. Все действия в системе описываются дискретными «событиями»; отсюда название «моделкровение дискретных событий». Событие, грубо говоря, может быть описано как что-то меняющее «состояние» Или конфигурацию системы. Говорят, что событие является первичным или независимым, если оно не вызвано другим событием; в противном