Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
2.5. ПРЕДСТАВЛЕНИЕ ПРОСТРАНСТВ СОСТОЯНИЙ ПОСРЕДСТВОМ НЕДЕТЕРМИНИРОВАННЫХ ПРОГРАММПроцесс порождения пространства состояний может быть представлен блок-схемой, изображенной на рис. 2.2. Здесь символы х и у используются для обозначения произвольных совокупностей данных. Заметим, что оператор присваивания «положить у равным некоторому члену множества
Рис. 2.2. Представление пространства состояний с помощью недетерминированной программы. Исходное положение: программная переменная у (пробегающая описания состояний) полагается равной входной структуре данных Множество (возможно, бесконечное) всех возможных способов выполнения программы, представленной этой блок-схемой, охватывает тогда полное пространство состояний. (При такой формулировке состояния описываются возможными величинами программной переменной у, которая может быть произвольно сложной совокупностью данных.) Программы, в которых используются операторы присваивания (и другие), допускающие во время выполнения недетерминированные выборы, получили название недетерминированных (Строго говоря, на нашей блок-схеме на рис. 2.2 нужно было бы дать условия для окончания и привести другие подробности, такие, как тест для проверки непустоты множества В общем недетерминированные программы связаны с расширением определений оператора обычного присваивания и оператора ветвления детерминированных программ. Мы уже видели, как можно пользоваться, недетерминированными операторами присваивания. Этот тип операторов присваивания, называемый операторами типа ВЫБОР, на блок-схемах обозначается так:
Здесь совокупность данных х есть входная величина этой программы. Функция Рис. 2.3. (см. скан) Представление игры в пятнадцать в виде недетерминированной программы. Кроме того, мы расширяем понятие оператора ветвления. В операторе обозначается следующим образом:
Отметим, что обычные детерминированные присваивания и ветвления — это простые частные случаи недетерминированных операторов. При конкретном выполнении недетерминированной программы в операторах В качестве того как некоторой задаче можно придать форму недетерминированной программы, на рис. 2.3 дается одна возможная программа для игры в пятнадцать. Здесь состояние описывается значением программной переменной у, принадлежащем пространству массивов Оказывается, что можно определить также и другие элементы недетерминированных программ. Эти элементы полезны при обсуждении формулировок, основанных на сведении задачи к подзадачам. Они будут рассмотрены в гл. 4.
|
1 |
Оглавление
|