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


              

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



Упражнения

    Напишите процедуру слияния двух упорядоченных списков в один третий список. Например:
        ?-  слить( [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.
Реализуйте этот принцип сортировки и сравните его эффективность с эффективностью программы быстрсорт.
Посмотреть ответ

Содержание  Назад  Вперед