Поиск пропущенных целых чисел - Пролог - PullRequest
Новая
       11

Поиск пропущенных целых чисел - Пролог

0 голосов
/ 07 октября 2011

Я хочу взять список целых чисел и создать список целых чисел, которые находятся между (или в промежутках) целыми числами в предыдущем списке.Например, я бы хотел, чтобы ?- findmissing([1,3,4,5,6],X). привело к X = [2].Как бы я реализовал такую ​​функцию?

Ответы [ 2 ]

3 голосов
/ 07 октября 2011

Первый трюк с логическим программированием состоит в том, чтобы начать с самых маленьких случаев и продолжить.

Базовые случаи здесь просты, если в списке меньше двух элементов, ничего не пропущено. 

findmissing([], []).
findmissing([_], []).

Второй трюк - делить и побеждать. Чтобы найти все, что отсутствует между каждой парой в Списке, нам понадобится предикат (скажем, числа между (X, Y, Список) / 3), который дает все числа между данной парой чисел, а затем запустить его для каждого пара в списке ввода. Используя встроенную функцию append () / 3, и пока не заботясь о том, как реализовать числа между () / 3, мы можем просто написать: 

 findmissing([X, Y|In], Out) :-
     numbersbetween(X, Y, Between),
     findmissing([Y|In], After),
     append(Between, After, Out).

(Здесь нужно немного позаботиться, чтобы убедиться, что мы рассматриваем каждую пару, в списке [1,2,3] нам нужно проверить [1,2] и [2,3] - поэтому рекурсивный шаг занимает [Y | In], а не только In).

Тогда остается только определить число между () / 3. Если вам случится знать о встроенных предикатах между () / 3 (это верно, если X 

numbersbetween(X, Y, List) :- setof(B, between(X, Y, B), List).

Если вам не известно об этих функциях, вы можете создать свои собственные числа между (), используя арифметику Пролога "is".

1 голос
/ 09 октября 2011

Конрад Ирвин здесь дал хороший анализ рекурсивного решения проблемы, но предполагает, что входной список отсортирован в порядке возрастания (как это было в примере с Hunterhod).

Думая о возможности несортированного ввода, мы предлагаем подход, помимо простой сортировки ввода перед применением метода Конрада.

  1. Найдите элементы Minimum и Maximum из InputList.

  2. Создать список последовательных целых чисел BetweenList = [Minimum,...,Maximum].

  3. Извлечение из BetweenList всех записей не членов InputList в форму MissingList.

...