Программирование на языке Пролог для искусственного интеллекта




Упражнения



Упражнения

    Напишите процедуру слияния двух упорядоченных списков в один третий список. Например:

        ?-  слить( [2, 5, 6, 6, 8], [1, 3, 5, 9], L).
        L = [1, 2, 3, 5, 5, 6, 6, 8, 9]

    Программы сортировки, показанные на рис. 9.2 и 9.3, отличаются друг от друга способом представления списков. Первая из них использует обычное представление, в то время как вторая - разностное представление. Преобразование из одного представления в другое очевидно и может быть автоматизировано. Введите в программу рис. 9.2 необходимые изменения, чтобы преобразовать ее в программу рис. 9.3.

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

    Существует еще одна хорошая идея относительно механизма сортировки списков, позволяющая избавиться от недостатков программы быстрсорт, а именно: разбить список на два меньших списка, отсортировать их, а затем слить вместе. Итак, для того, чтобы отсортировать список L, необходимо

  • разбить L на два списка L1 и L2 примерно одинаковой длины;
  • произвести сортировку списков L1 и L2,получив списки S1 и S2;
  • слить списки S1 и S2, завершив на этом сортировку списка L.

Реализуйте этот принцип сортировки и сравните его эффективность с эффективностью программы быстрсорт.

Посмотреть ответ









Начало  Назад  Вперед