Палиндром и почти палиндром – проверка на Prolog

Главная Форумы Программирование Помощь с решением задач на Prolog Задачи на списки Палиндром и почти палиндром – проверка на Prolog

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 8 мес. назад.

  • Автор
    Сообщения
  • #1906

    questioner
    Участник

    Помогите пожалуйста с задачей в SWI prologe на списки.

    Фразы называющиеся палиндромами — это такие фразы, которые одинаково читаются как слева направо,так и справа налево. Например, «А РОЗА УПАЛА НА ЛАПУ АЗОРА».

      Написать программу, которая определяет:

    • палиндром,
    • почти палиндром(различие в одной букве «я иду с мечом судия»)
    • не палиндром.

    Рассмотреть случай, когда разные буквы на границах, т.е в начале или в конце фраз.

    Например: «я иду с мечем судия» и «я иду с мечем судья» в первом случаи имеем полупалиндром, во втором — чистый палиндром.
    Мой исходный код с использованием встроенных функций (полупалиндром)^

    palindrome([], [], _):-!.
    palindrome(_, _, N):-
      N < 0, !, fail.
    palindrome([H|T1], [H|T2], N):-
      !, palindrome(T1, T2, N).
    palindrome([_|T1], [_|T2], N):-
      NN is N - 1, palindrome(T1, T2, NN).
     
    pal_1(S):-
      reverse(SWS, RSWS),
      palindrome(SWS, RSWS, 2).

    Палиндром:
    палиндром([]).
    палиндром([_СредняяБуква]).
    палиндром([_Первый|_Остальные]):-
      слияние(_Середина,[_Первый],_Остальные),
      палиндром(_Середина).
      слияние([],_L,_L).
    слияние([_X|_L1],_L2,[_X|_L3]):-
      слияние(_L1,_L2,_L3).

    Функцией reverse, мы переворачиваем список, в результате на вход palindrome подаем 2 списка и вводим количество допустимых различий. Проблема состоит в том, что преподаватель запретил использовать встроенные функции, в частности reverse. Я видел как Вы описываете эту функцию, но не понимаю как встроить ее в мою программу.

  • #1907

    Если использовать встроенные функции нельзя – скопируйте себе предикат reverse из статьи про обработку списков.

    %% почти палиндром, с разрешенным количеством
    %% отличающихся символов
    % оба списка одновременно кончились - палиндром
    palindrome([], [], _):-!.
    % превышено разрешенное количество различий - не палиндром
    palindrome(_, _, N):- N < 0, !, fail.
        % первые символы совпали
    palindrome([H|T1], [H|T2], N):-
        % не изменяя N обработаем хвосты
        !, palindrome(T1, T2, N).
        % первые символы отличаются
    palindrome([_|T1], [_|T2], N):-
        % уменьшим N, рекурсивно обработаем хвосты списков
        NN is N - 1, palindrome(T1, T2, NN).
     
    %% проверка, является ли символ пробельным
    is_space(C):- char_type(C, space).
     
    % палиндром
    pal_0(S):-
        % удаляем пробельные символы из строки
        exclude(is_space, S, SWS),
        % переворачиваем строку
        reverse(SWS, SWS).
    % почти палиндром
    pal_1(S):-
        % удаляем пробельные символы из строки
        exclude(is_space, S, SWS),
        % переворачиваем строку
        reverse(SWS, RSWS),
        % сравниваем списки с одним разрешенным различием
        palindrome(SWS, RSWS, 2).

Для ответа в этой теме необходимо авторизоваться.