Программирование на языке ПРОЛОГ для искуственного интеллекта
aa13d773

у которого есть сестра, имеет


1. 3.    Оттранслируйте следующие утверждения в правила на Прологе:
(a)    Всякий, кто имеет ребенка, - счастлив (введите одноаргументное отношение счастлив).
(b)    Всякий X, имеющий ребенка, у которого есть сестра, имеет двух детей (введите новое отношение иметьдвухдетей).
Посмотреть ответ
1. 4.    Определите отношение внук, используя отношение родитель. Указание: оно будет похоже на отношение родительродителя (см. рис. 1.3).
Посмотреть ответ
1. 5.    Определите отношение тетя( X, Y) через отношение родитель и сестра. Для облегчения работы можно сначала изобразить отношение тетя в виде диаграммы по типу тех, что изображены на рис. 1.3.
Посмотреть ответ

1. 1.    Считая, что отношение родитель определено так же, как и раньше в данном разделе (см. рис. 1.1), найдите, какими будут ответы пролог-системы на следующие вопросы:
        (a)        ?   -  родитель ( джим, X).


        (b)        ?   -  родитель( X, джим).
        (c)        ?   -  родитель( пам,Х), родитель( Х, пат).
        (d)        ?   -  родитель( пам, X), родитель( Х, Y),
                        родитель( Y, джим).
Посмотреть ответ
1. 2.    Сформулируйте на Прологе следующие вопросы об отношении родитель:
        (a)        Кто родитель Пат?
        (b)        Есть ли у Лиз ребенок?
        (c)        Кто является родителем родителя Пат?
Посмотреть ответ
Назад | Содержание | Вперёд


11. 1.    Напишите процедуру поиска в глубину (с обнаружением циклов)
        вглубину1( ПутьКандидат, Решение)
отыскивающую решающий путь Решение как продолжение пути ПутьКандидат. Оба пути представляйте списками вершин, расположенных в обратном порядке так, что целевая вершина окажется в голове списка Решение.
Посмотреть ответ
11. 2.    Напишите процедуру поиска в глубину, сочетающую в себе обнаружение циклов с ограничением глубины, используя рис. 11.7 и 11.8.
11. 3.    Проведите эксперимент по применению программы поиска в глубину к задаче планирования в "мире кубиков" (рис. 11.1).
11. 4.    Напишите процедуру
        отобр( Ситуация)
для отображения состояния задачи "перестановки кубиков". Пусть Ситуация - это список столбиков, а столбик, в свою очередь, - список кубиков. Цель
        отобр( [ [a], [e, d], [с, b] ] )
должна отпечатать соответствующую ситуацию, например так:
                е         с
      a        d         b
      ================
Назад | Содержание | Вперёд


11. 5.    Перепишите программу поиска в ширину рис. 11.10, используя разностное представление для списка путей-кандидатов и покажите, что в результате получится программа, приведенная на рис. 11.11. Зачем в программу рис. 11.11 включена цель
        Пути \== Z
Проверьте, что случится при поиске в пространстве состояний рис. 11.9, если эту цель опустить. Различие в выполнении программы, возникнет только при попытке найти новые решения в ситуации, когда не осталось больше ни одного решения.
11. 6.    Как программы настоящего раздела можно использовать для поиска, начинающегося от стартового множества вершин, вместо одной стартовой вершины?
Посмотреть ответ
11. 7.    Как программы этой главы можно использовать для поиска в обратном направлении, т.е. от целевой вершины к стартовой вершине (или к одной из стартовых вершин, если их несколько). Указание: переопределите отношение после. В каких ситуациях обратный поиск будет иметь преимущества перед прямым поиском?
11. 8.    Иногда выгодно сделать поиск двунаправленным, т. е. продвигаться одновременно с двух сторон от стартовой и целевой вершин. Поиск заканчивается, когда оба пути "встречаются". Определите пространство поиска (отношение после) и целевое отношение для заданного графа таким образом, чтобы наши процедуры поиска в действительности выполняли двунаправленный поиск.
11. 9.    Проведите эксперименты с различными методами поиска применительно к задаче планирования в "мире кубиков".
Назад | Содержание | Вперёд


10. 1.    Определите отношение
        внутри( Эдем, Дер)
для поиска элемента Элем в 2-3 справочнике Дер.
Посмотреть ответ
10. 2.    Введите в программу рис. 10. 6 изменения для устранения лишних возвратов (определите отношения встав2 и соединить).
line(); %  Отображение 2-3 справочников
        отобр(Д) :-                                                                                                         15
            отобр( Д, 0).                                                                                             --
        отобр( nil, _ ).                                                                                            15


13. 1.    Закончите составление программы поиска в глубину (с ограничением) для И / ИЛИ-графов, намеченную в настоящем разделе.
13. 2.    Определите на Прологе И / ИЛИ-пространство для задачи "ханойская башня" и примените к нему процедуры поиска настоящего раздела.
13. 3.    Рассмотрите какую-нибудь простую детерминированную игру двух лиц с полной информацией и дайте определение ее И / ИЛИ-представления. Используйте программу поиска в И / ИЛИ-графах для построения выигрывающих стратегий в форме И / ИЛИ-деревьев.
Назад | Содержание | Вперёд


14. 1.    Рассмотрите "если-то"-правила рис. 14.2-14.4 и транслируйте их в нашу систему обозначений для правил. Предложите расширение нотации, чтобы, при необходимости, можно было работать с оценками уверенности.
line(); % Небольшая база знаний для локализации неисправностей в
% электрической схеме
% Если прибор включен, но не работает, и предохранитель цел,
% то прибор неисправен.
        правило_поломки:
                                        если
                                                вкл( Прибор) и
                                                прибор( Прибор) и
                                                не работает( Прибор) и
                                                соед( Прибор, Предохр) и
                                                доказано( цел( Предохр) )


2. 1.    Какие из следующих выражений представляют собой правильные объекты в смысле Пролога? Что это за объекты (атомы, числа, переменные, структуры)?
    (а)        Диана
    (b)        диана
    (с)        'Диана'
    (d)        _диана
    (e)        'Диана едет на юг'
    (f)        едет( диана, юг)
    (g)        45
    (h)        5( X, Y)
    (i)        +( север, запад)
    (j)        три( Черные( Кошки) )
Посмотреть ответ
2. 2.    Предложите представление для прямоугольников, квадратов и окружностей в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 2.4. Например, прямоугольник можно представить четырьмя точками (а может быть, только тремя точками). Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.
Назад | Содержание | Вперёд


2. 3.    Будут ли следующие операции сопоставления успешными или неуспешными? Если они будут успешными, то какова будет результирующая конкретизация переменных?
    (а)        точка( А, В) = точка( 1, 2)
    (b)        точка( А, В) = точка( X, Y, Z)
    (c)        плюс( 2, 2) = 4
    (d)        +( 2, D)= +( Е, 2)
    (е)        треугольник( точка( -1, 0), Р2, Р3) =
                 треугольник( Р1, точка( 1, 0), точка( 0, Y)
Результирующая конкретизация определяет семейство треугольников. Как бы Вы описали это семейство?
Посмотреть ответ
2. 4    Используя представление отрезков, применявшееся в данной разделе, напишите терм, соответствующий любому отрезку на вертикальной прямой x = 5.
Посмотреть ответ
2. 5.    Предположим, что прямоугольник представлен термом прямоугольник( P1, P2, P3, Р4), где Р - вершины прямоугольника, положительно упорядоченные. Определите отношение
        регулярный( R)
которое имеет место, если R - прямоугольник с вертикальными и горизонтальными сторонами.
Посмотреть ответ
Назад | Содержание | Вперёд


2. 6.    Рассмотрим следующую программу:
    f( 1, один).
    f( s(1), два).
    f(    s(s(1)),    три).
    f( s(s(s(X))),  N) :-
               f(X,   N).
Как пролог- система ответит на следующие вопросы? Там, где возможны несколько ответов, приведите по крайней мере два.
    (a)        ?- f( s( 1), A).
    (b)        ?- f( s(s(1)), два).
    (c)        ?- f(   s(s(s(s(s(s(1)))))), С).
    (d)        ?- f( D, три).
Посмотреть ответ
2. 7.    В следующей программе говорится, что два человека являются родственниками, если
    (a)        один является предком другого, или
    (b)        у них есть общий предок, или
    (c)        у них есть общий потомок.
    родственники( X, Y) :-
          предок( X, Y).
    родственники( X, Y) :-
          предок( Y, X).
    родственники( X, Y) :-
                      % X и Y имеют общего предка
          предок( Z, X),
          предок( Z, Y).
    родственники( X, Y) :-
                      % X и Y имеют общего потомка
          предок( X, Z),
          предок( Y, Z).
Сможете ли вы сократить эту программу, используя запись с точками с запятой?
Посмотреть ответ
2. 8.    Перепишите следующую программу, не пользуясь точками с запятой.
    преобразовать( Число, Слово) :-
          Число = 1,  Слово = один;
          Число = 2,  Слово = два;
          Число = 3,  Слово = три.
Посмотреть ответ
Назад | Содержание | Вперёд


3. 12.    Если принять такие определения
        :- ор( 300, xfy, играет_в).
        :- ор( 200, xfy, и).
то два следующих терма представляют собой синтаксически правильные объекты:
        Tepмl = джимми играет_в футбол и сквош
        Терм1 = сьюзан играет_в теннис и баскетбол и волейбол
Как эти термы интерпретируются пролог-системой? Каковы их главные функторы и какова их структура?
Посмотреть ответ
3. 13.    Предложите подходящее определение операторов ("работает", "в", "нашем"), чтобы можно было писать предложения типа:
        диана работает секретарем в нашем отделе.
а затем спрашивать:
        ?- Кто работает секретарем в нашем отделе.
        Кто = диана
        ?- диана работает Кем.
        Кем = секретарем в нашем отдела
Посмотреть ответ
3. 14.    Рассмотрим программу:
        t( 0+1, 1+0).
        t( X+0+1, X+1+0).
        t( X+1+1, Z) :-
            t( X+1, X1),
            t( X1+1, Z).
Как данная программа будет отвечать на ниже перечисленные вопросы, если '+' "- это (как обычно) инфиксный оператор типа yfx?
(a)    ?- t( 0+1, А).
(b)    ?- t( 0+1+1, В).
(с)    ?- t( 1+0+1+1+1, С).
(d)    ?- t( D, 1+1+1+0).
Посмотреть ответ
3. 15.    В предыдущем разделе отношения между списка ми мы записывали так:
        принадлежит( Элемент, Список),


3. 16. Определите отношение
        mах( X, Y, Мах)
так, чтобы Мах равнялось наибольшому из двух чисел Х и Y.
Посмотреть ответ
3. 17.    Определите предикат
        максспис( Список, Мах)
так, чтобы Мах равнялось наибольшему из чисел, входящих в Список.
Посмотреть ответ
3. 18.    Определите предикат
        сумспис( Список, Сумма)
так, чтобы Сумма равнялось сумме чисел, входящих в Список.
Посмотреть ответ
3. 19.    Определите предикат
        упорядоченный( Список)
который принимает значение истина, если Список представляет собой упорядоченный список чисел. Например: упорядоченный [1, 5, 6, 6, 9, 12] ).
Посмотреть ответ
3. 20.    Определите предикат
        подсумма( Множ, Сумма, ПодМнож)
где Множ это список чисел, Подмнож подмножество этих чисел, а сумма чисел из ПодМнож равна Сумма. Например:
        ?- подсумма( [1, 2. 5. 3. 2], 5, ПМ).
        ПМ = [1, 2, 2];
        ПМ = [2, 3];
        ПМ = [5];
        . . .
Посмотреть ответ
3. 21.    Определите процедуру
        между( Nl, N2, X)
которая, с помощью перебора, порождает все целые числа X, отвечающие условию Nl <=X <=N2.
Посмотреть ответ
3. 22.    Определите операторы 'если', 'то', 'иначе' и ':=" таким образом, чтобы следующее выражение стало правильным термом:
        если Х > Y то Z := Х иначе Z := Y
Выберите приоритеты так, чтобы  'если' стал главным функтором. Затем определите отношение 'если' так, чтобы оно стало как бы маленьким интерпретатором выражений типа 'если-то-иначе'.


3. 1. (а)    Используя отношение конк, напишите цель, соответствующую вычеркиванию трех последних элементов списка L, результат - новый список L1. Указание: L - конкатенация L1 и трехэлементного списка.
(b)    Напишите последовательность целей для порождения списка L2, получающегося из списка L вычеркиванием его трех первых и трех последних элементов.
Посмотреть ответ
3. 2.    Определите отношение
        последний( Элемент, Список)
так, чтобы Элемент являлся последним элементом списка Список. Напишите два варианта определения:    (а)    с использованием отношения конк,     (b)    без использования этого отношения.
Посмотреть ответ


3. 3.    Определите два предиката
        четнаядлина( Список)    и    нечетнаядлина( Список)
таким образом, чтобы они были истинными, если их аргументом является список четной или нечетной длины соответственно. Например, список [а, b, с, d] имеет четную длину, a [a, b, c] - нечетную.
Посмотреть ответ
3. 4.    Определите отношение
        обращение( Список, ОбращенныйСписок),
которое обращает списки. Например,
        обращение( [a, b, c, d], [d, c, b, a] ).
Посмотреть ответ
3. 5.    Определите предикат
        палиндром( Список).
Список называется палиндромом, если он читается одинаково, как слева направо, так и справа налево. Например,  [м, а, д, а, м].
Посмотреть ответ
3. 6.    Определите отношение
        сдвиг( Список1, Список2)
таким образом, чтобы Список2 представлял собой Список1, "циклически сдвинутый" влево на один символ. Например,
        ?-  сдвиг( [1, 2, 3, 4, 5], L1),
             сдвиг1( LI, L2)
дает
        L1 = [2, 3, 4, 5, 1]
        L2 = [3, 4, 5, 1, 2]
Посмотреть ответ
3. 7.    Определите отношение
        перевод( Список1, Список2)
для перевода списка чисел от 0 до 9 в список соответствующих слов. Например,
        перевод( [3, 5, 1, 3], [три, пять, один, три] )
Используйте в качестве вспомогательных следующие отношения:
        означает( 0, нуль).
        означает( 1, один).
        означает( 2, два).


4. 1.    Напишите вопросы для поиска в базе данных о семьях.
(а)        семей без детей;
(b)        всех работающих детей;
(с)        семей, где жена работает, а муж нет,
(d)        всех детей, разница в возрасте родителей которых составляет не менее 15 лет.
Посмотреть ответ
4. 2.    Определите отношение
        близнецы( Ребенок1, Ребенок2)
для поиска всех близнецов в базе данных о семьях.
Посмотреть ответ
Назад | Содержание | Вперёд


4. 4.    Почему не могло возникнуть зацикливание модели исходного автомата на рис. 4.3, когда в его графе переходов не было "спонтанного цикла"?
Посмотреть ответ
4. 5.    Зацикливание при вычислении допускается можно предотвратить, например, таким способом: подсчитывать число переходов, сделанных к настоящему моменту. При этом модель должна будет искать пути только некоторой ограниченной длины. Модифицируйте так отношение допускается. Указание: добавьте третий аргумент - максимально допустимое число переходов:
        допускается( Состояние, Цепочка, Макс_переходов)
Посмотреть ответ
Назад | Содержание | Вперёд


5. 1.    Пусть есть программа:
        р( 1).
        р( 2) :-  !.
        р( 3).
Напишите все ответы пролог-системы на следующие вопросы:
    (a)        ?-  р( X).
    (b)        ?-  р( X),   p(Y).
    (c)        ?-  р( X),   !,  p(Y).
Посмотреть ответ
5. 2.    Следующие отношения распределяют числа на три класса - положительные, нуль и отрицательные:
        класс( Число, положительные) :- Число > 0.
        класс( 0, нуль).
        класс( Число, отрицательные) :- Число < 0.
Сделайте эту процедуру более эффективной при помощи отсечений.
Посмотреть ответ
5. 3.    Определите процедуру
        разбить( Числа, Положительные, Отрицательные)
которая разбивает список чисел на два списка: список, содержащий положительные числа (и нуль), и список отрицательных чисел. Например,
        разбить( [3, -1, 0, 5, -2], [3, 0, 5], [-1, -2] )
Предложите две версии: одну с отсечением, другую - без.
Посмотреть ответ
Назад | Содержание | Вперёд


6. 1.    Пусть f  -   файл термов. Определите процедуру
        найтитерм( Терм)
которая выводит на терминал новый терм из f, сопоставимый с Терм'ом.
Посмотреть ответ
6. 2.    Пусть f  -   файл термов. Напишите процедуру
        найтивсетермы( Терм)
которая выводит на экран все термы из f, сопоставимые с Tepм'ом. Обеспечьте при этом, чтобы во время поиска Терм не конкретизировался (это могло бы помешать ему сопоставиться с другими термами дальше по файлу).
Посмотреть ответ
Назад | Содержание | Вперёд


5. 4.    Даны два списка Кандидаты и Исключенные, напишите последовательность целей (используя принадлежит и not), которая, при помощи перебора, найдет все элементы списка Кандидаты, не входящие в список Исключенные.
Посмотреть ответ
5.5.    Определите отношение, выполняющее вычитание множеств:
line();         решение( [ ]).
        решение( [X/Y | Остальные] ) :-
                решение( Остальные),
                принадлежит( Y, [1, 2, 3, 4, 5, 6, 7, 8] ),
                not бьет( X/Y, Остальные).
        бьет( X/Y, Остальные) :-
                принадлежит( X1/Y1, Остальные),
                ( Y1 = Y;
                        Y1 is Y + X1 - X;
                        Y1 is Y - X1 + X ).
        принадлежит( А, [А | L] ).
        принадлежит( А, [В | L] ) :-
                принадлежит( А, L).
        % Шаблон решения
        шаблон( [1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).
line(); Рис. 5. 3.  Еще одна программа для решения задачи о восьми ферзях.
        разность( Множ1, Множ2, Разность)


6. 4.    Определите отношение
        начинается( Атом, Символ)
для проверки, начинается ли Атом с символа Символ.
Посмотреть ответ
6. 5.    Определите процедуру plural, которая преобразует английские существительные из единственного числа во множественное, добавляя к слову окончание s. Например:
        ?-  plural( table, X).
        Х  =  tables
Посмотреть ответ
6. 6.    Напишите процедуру
        поиск( Ключслово, Предложение)
которая при каждом вызове находит в текущем входном файле предложение, содержащее заданное ключевое слово Ключслово. Предложение в своей исходной форме должно быть представлено в виде последовательности символов или в виде атома (процедуру читпредложение из данного раздела можно соответственно модифицировать).
Назад | Содержание | Вперёд


7. 1.    Напишите процедуру упростить для упрощения алгебраических сумм, в которых участвуют числа и символы (строчные буквы). Пусть эта процедура переупорядочивает слагаемые так, чтобы символы предшествовали числам. Вот примеры ее использования:
        ?-  упростить( 1 + 1 + а, Е).
        Е = а + 2
        ?-  упростить( l + a + 4 + 2 + b + с, E).
        Е = а + b + с + 7
        ?-  упростить( 3 + х + х, Е).
        Е = 2*х + 3
7. 2.  Определите процедуру
        добавить( Элемент, Список)
для добавления нового элемента в список. Предполагается, что все элементы, хранящиеся в списке, - атомы. Список состоит из всех хранящихся в нем элементов, а за ними следует хвост, который не конкретизирован и служит для принятия новых элементов. Пусть, например, в списке уже хранятся а, b и с, тогда
        Список = [а, b, с | Хвост]
где Хвост - переменная. Цель
        добавить( d, Список)
вызовет конкретизацию
        Xвoст = [d | НовыйХвост] и
        Список = [а, b, с, d | НовыйХвост]
Таким способом структура может наращиваться, включая в себя новые элементы. Определите также соответствующее отношение принадлежности.
Посмотреть ответ
Назад | Содержание | Вперёд


7. 3.    Определите предикат конкрет(Терм) так, чтобы он принимал значение истина, когда в Tepм'e нет ни одной неконкретизированной переменной.
7. 4.    Процедура подставить из данного раздела производит, при наличии разных вариантов, лишь самую "внешнюю" подстановку.
Модифицируйте эту процедуру так, чтобы она находила все возможные варианты при помощи автоматического перебора. Например:
        ?-  подставить( a+b, f( A+B), новый, НовыйТерм).
        А = а
        В = b
        НовыйТерм = f( новый);
        А = а+b
        В = а+b
        НовыйТерм = f( новый + новый)
Наша исходная версия нашла бы только первый из этих двух ответов.
7. 5.    Определите отношение
        включает( Tepмl, Терм2)
которое выполняется, если Терм1 является более общим, чем Терм2. Например:
        ?-  включает( X, с).
        yes
        ?-  включает( g( X), g( t( Y))).
        yes
        ?-  включает f( X,X), f( a,b)).
        no
Назад | Содержание | Вперёд


7. 6.   (а)         Напишите вопрос к пролог-системе, который удаляет из базы данных всю таблицу произв.
           (b)         Измените этот вопрос так, чтобы он удалил из таблицы только те строки, в которых произведение равно 0.
7. 7.        Определите отношение
        копия( Терм, Копия)
которое порождает такую копию Терм'а Копия, в которой все переменные переименованы. Это легко сделать, используя assert и retract.
Назад | Содержание | Вперёд


7. 8. Используя bagof, определите отношение
        множподмножеств( Мн, Подмн)
для вычисления множества всех подмножеств данного множества (все множества представлены списками).
7. 9.    Используя bagof, определите отношение
        копия( Терм, Копия)
чтобы Копия представляла собой Терм, в котором все переменные переименованы.


8. 1. Все показанные ниже процедуры подсп1, подсп2 и подсп3 реализуют отношение взятия подсписка. Отношение подсп1 имеет в значительной мере процедурное определение, тогда как подсп2 и подсп3 написаны в декларативном стиле. Изучите поведение этих процедур на примерах нескольких списков, обращая внимание на эффективность работы. Две из них ведут себя одинаково и имеют одинаковую эффективность. Какие? Почему оставшаяся процедура менее эффективна?
        подсп1( Спис, Подспис) :-
                начало( Спис, Подспис).
        подсп1( [ _ | Хвост], Подспис) :-
                                                % Подспис - подсписок хвоста
                подсп1( Хвост, Подспис).
        начало( _, [ ]).
        начало( [X | Спис1], [X | Спис2] ) :-
                начало( Спис1, Спис2).
        подсп2( Спис, Подспис) :-
                конк( Спис1, Спис2, Спис),
                конк( Спис3, Подспис, Cпис1).
        подсп3( Спис, Подспис) :-
                конк( Спис1, Спис2, Спис),
                конк( Подспис, _, Спис2).
8. 2.    Определите отношение
        добавить_в_конец( Список, Элемент, НовыйСписок)
добавляющее Элемент в конец списка Список; результат - НовыйСписок. Оба списка представляйте разностными парами.
Посмотреть ответ
8. 3.    Определите отношение
        обратить( Список, ОбращенныйСписок)
где оба списка представлены разностными парами.
Посмотреть ответ
8. 4.    Перепищите процедуру собрать из разд. 8.5.2, используя разностное представление списков, чтобы конкатенация выполнялась эффективнее.


9. 1. Определите отношение
        список( Объект)
для распознавания случаев, когда Объект является стандартным прологовским списком.
Посмотреть ответ
9. 2.    Определите отношение принадлежности к списку, используя систему обозначений, введенную в этой разделе: "затем - ничего_не_делать".
Посмотреть ответ
9. 3.    Определите отношение
        преобр( СтандСпис, Спис)
для преобразования списков из стандартного представления в систему "затем-ничего_не_делать". Например:
        преобр( [а, b], а затем b затем ничего_не_делать)
Посмотреть ответ
9. 4.    Обобщите отношение преобр на случай произвольного альтернативного представления списков. Конкретное представление задается символом, обозначающим пустой список, и функтором для соединения головы с хвостом. В отношении преобр придется добавить два новых аргумента:
        преобр( СтандСпис, Спис, Функтор, ПустСпис)
Примеры применения этого отношения:
        ?-  пpeoбp( [а, b], L, затем, ничего_не_делать).
        L = а затем b затем ничего_не_делать
        ?-  преобр( [а, b, с], L, +, 0).
        L = а+(b+(с+0) )
Посмотреть ответ


9. 5.    Напишите процедуру слияния двух упорядоченных списков в один третий список. Например:
        ?-  слить( [2, 5, 6, 6, 8], [1, 3, 5, 9], L).
        L = [1, 2, 3, 5, 5, 6, 6, 8, 9]
9. 6.    Программы сортировки, показанные на рис. 9.2 и 9.3, отличаются друг от друга способом представления списков. Первая из них использует обычное представление, в то время как вторая - разностное представление. Преобразование из одного представления в другое очевидно и может быть автоматизировано. Введите в программу рис. 9.2 необходимые изменения, чтобы преобразовать ее в программу рис. 9.3.
9. 7.    Наша программа быстрсорт в случае, когда исходный список уже упорядочен или почти упорядочен, работает очень неэффективно. Проанализируйте причины этого явления.
9. 8.    Существует еще одна хорошая идея относительно механизма сортировки списков, позволяющая избавиться от недостатков программы быстрсорт, а именно: разбить список на два меньших списка, отсортировать их, а затем слить вместе. Итак, для того, чтобы отсортировать список L, необходимо
  • разбить L на два списка L1 и L2 примерно одинаковой длины;
  • произвести сортировку списков L1 и L2,получив списки S1 и S2;
  • слить списки S1 и S2, завершив на этом сортировку списка L.
Реализуйте этот принцип сортировки и сравните его эффективность с эффективностью программы быстрсорт.
Посмотреть ответ
Назад | Содержание | Вперёд


9. 9.    Определите предикаты
        двдерево( Объект)
        справочник( Объект)
распознающие, является ли Объект двоичным деревом или двоичным справочником соответственно. Используйте обозначения, введенные в данном разделе.
Посмотреть ответ
9. 10.    Определите процедуру
        глубина( ДвДерево, Глубина)
вычисляющую глубину двоичного дерева в предположении, что глубина пустого дерева равна 0, а глубина одноэлементного дерева равна 1.
Посмотреть ответ
9. 11.    Определите отношение
        линеаризация( Дерево, Список)
соответствующее "выстраиванию" всех вершин дерева в список.
Посмотреть ответ
9. 12.    Определите отношение
        максэлемент( Д, Элемент)
таким образом, чтобы переменная Элемент приняла значение наибольшего из элементов, хранящихся в дереве Д.
Посмотреть ответ
9. 13.    Внесите изменения в процедуру
        внутри( Элемент, ДвСправочник)
добавив в нее третий аргумент Путь таким образом, чтобы можно было бы получить путь между корнем справочника и указанным элементом.
Посмотреть ответ
Назад | Содержание | Вперёд

Содержание раздела