Пример 8.3. Сортировка выбором

Идея алгоритма сортировки выбором очень проста. В списке находим минимальный элемент (используя предикат min_list, который мы придумали в начале этой лекции). Удаляем его из списка (с помощью предиката delete_one, рассмотренного в предыдущей лекции). Оставшийся список сортируем. Приписываем минимальный элемент в качестве головы к отсортированному списку. Так как этот элемент был меньше всех элементов исходного списка, он будет меньше всех элементов отсортированного списка. И, следовательно, если его поместить в голову отсортированного списка, то порядок не нарушится.

Запишем:

/* отсортированный пустой список остается пустым списком */

choice([ ],[ ]).

/* приписываем X (минимальный элемент списка L) к отсортированному списку T */

choice(L,[X|T]):-

min_list(L,X), /* X — минимальный элемент списка L */

delete_one(X,L,L1), /* L1 — результат удаления 1го вхождения элемента X из L*/

choice(L1,T). /* сортируем список L1, результат обозначаем T */

9. Строки

Пример 9.1. Разделение исходной строки на «голову» и «хвост»

Разработаем предикат frontchar, который послужит для разделения исходной строки на первый символ и "хвост", состоящий из оставшихся после удаления первого символа, символов строки. Это чем-то напоминает представление списка в виде головы и хвоста.

frontchar('', '', ''):-!.

frontchar(S, H, T):-

sub_string(S, 0, 1, _, H),

string_length(S, L),

L1 is L-1,

sub_string(S, 1, L1, _, T).

Пример 9.2. Разбиение строки на две части с заданным разделителем

Разработаем предикат frontstr, который послужит для разделения исходной строки S на две подстроки (S1 и S2), где разделителем будет символ, стоящий на заданной I-й позиции в исходной строке.

/* у пустой строки нет подстрок */

frontstr(_, '', '', ''):-!.

/* если позиция = 0, то вся строка помещ. во 2ю подстроку */

frontstr(0, S, '', S):-!.

/* вычисляем подстроки напрямую */

frontstr(I, S, S1, S2):-

sub_string(S, 0, I, _, S1),

string_length(S, L),

L1 is L-I,

sub_string(S, I, L1, _, S2).

Пример 9.3. Преобразование строки в список символов

Предикат будет иметь два аргумента. Первым аргументом будет данная строка, вторым — список, состоящий из символов исходной строки. Решение будет рекурсивным. Базис: пустой строке будет соответствовать пустой список. Шаг: с помощью встроенного предиката frontchar разобьем строку на первый символ и остаток строки, остаток строки перепишем в список, после чего добавим первый символ исходной строки в этот список в качестве первого элемента.

/* пустой строке соответствует пустой список */

str_list("",[]).

str_list(S,[H|T]):-

/* H — первый символ строки S, S1 — остаток строки */

frontchar(S,H,S1),

/* T — список, состоящий из символов, входящих в строку S1*/

str_list(S1,T).

Пример 9.4. Подсчет кол-ва вхождений заданного символа в строку

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

Решение будет рекурсивным. Рекурсия по строке, в которой ведется подсчет количества вхождений данного символа. Если строка пустая, то не важно, вхождения какого символа мы считаем, все равно ответом будет ноль. Это базис. Шагов рекурсии будет два в зависимости от того, будет ли первым символом строки символ, вхождения которого мы считаем, или нет. В первом случае нужно подсчитать, сколько раз искомый символ встречается в остатке строки, и увеличить полученное число на единицу. Во втором случае (когда первый символ строки отличен от символа, который мы считаем) увеличивать полученное число не нужно. При расщеплении строки на первый символ и хвост нужно воспользоваться уже знакомым нам предикатом frontchar.

char_count("",_,0). /* Любой символ не встречается в пустой строке ни разу*/

char_count(S,C,N):-

/* символ C оказался первым символом в S, в S1 — оставшиеся символы строки S */

frontchar(S,C,S1),!,

/* N1 — количество вхождений символа C в строку S1 */

char_count(S1,C,N1),

/* N — количество вхождений символа C в строку S получается */

N is N1+1.

char_count(S,C,N):-

/* первым символом строки S оказался символ, отличный от исходного символа C */

/* в S1 — оставшиеся символы строки S */

frontchar(S,_,S1),

/* количество вхождений символа C в строку S совпадает с количеством вхождений символа C в строку S1 */

char_count(S1,C,N).

Пример 9.5. Поиск первого вхождения заданного символа в строку.

У предиката будет три параметра. Первые два — входные — символ и строка, третий — выходной — первая позиция вхождения первого параметра во второй параметр или ноль.

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

Вначале с помощью предиката frontchar разделим исходную строку на первый символ и остаток строки. Если первым символом строки окажется тот самый символ, позицию которого мы ищем, значит, больше ничего делать не нужно. Ответом будет единица. В этом случае нам даже неважно, какие символы оказались в хвосте строки, поскольку мы ищем первое вхождение данного символа в строку.

В противном случае, если первым символом исходной строки является какой-то символ, отличный от искомого, нам нужно искать позицию вхождения символа в остаток строки. Если искомый символ найдется в хвосте, позиция вхождения символа в исходную строку будет на единицу больше, чем позиция вхождения этого символа в остаток строки. Во всех остальных ситуациях наш символ не встречается в исходной строке и, следовательно, мы должны означить третий аргумент нулем.

str_pos(C,S,1):-

/* Искомый символ C оказался первым символом данной строки S */

frontchar(S,C,_),!.

str_pos(C,S,N) :-

/* S1 — состоит из всех символов строки S, кроме первого, который отличается от искомого символа C */

frontchar(S,_,S1),

/* N1 — это позиция, в которой символ C встречается первый раз в хвосте S1 или ноль*/

str_pos(C,S1,N1),

/* если позиция вхождения символа C в строку S1 не равна нулю, то есть если он встречается в строке S1 */

N1=\=0,!,

/* то, увеличив позицию его вхождения на единицу, мы получим позицию его вхождения в исходную строку */

N is N1+1.

/* искомый символ не входит в данную строку */

str_pos(_,_,0).

?- str_pos('2', '1234', X).

X = 2