Посчитать количество цифр на первом и третьем уровне вложенности

      Комментарии к записи Посчитать количество цифр на первом и третьем уровне вложенности отключены

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

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

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

    questioner
    Участник

    Здравстуйте!
    Помогите, пожалуйста, с заданием которое нужно реализовать на Prolog.

    Дан список из подсписками вида [[1, [a, 4, b, 6], c, ], 9, d, … ]. Подсчитать количество атомов, которые являются цифрами, на первом и третьем уровне вложенности.

    Заранее спасибо!

  • #1903

    Выделить все элементы, находящиеся на заданном уровне вложенности можно следующим образом:

    % возвращает список элементов заданного уровня вложенности
    % getNestedLevelElements(SourceList, Level, ResultList)
    getNestedLevelElements([], _Level, []):-
      !.
    getNestedLevelElements([], Level, _R):-
      Level < 0, !.
    getNestedLevelElements(E, 0, [E]):-
      !.
    getNestedLevelElements(L, _Level, []):-
      \+ is_list(L), !.
    getNestedLevelElements([H|T], Level, R):-
      TLevel is Level - 1,
      getNestedLevelElements(H, TLevel, TRHead),
      getNestedLevelElements(T, Level, TRTail),
      append(TRHead, TRTail, R).

    Приведенный код соответствует следующему алгоритму:
    1) если на вход подан пустой список или требуемая глубина меньше нуля — вернуть пустой список;
    2) если глубина равна нулю — вернуть список, содержащий исходный список;
    3) если первым аргументом оказался атом, то результат — пустой список;
    4.1) получить новое значение уровня вложенности (TLevel);
    4.2) обработать первый элемент исходного списка рекурсивно со значением вложенности списков TLevel. Результат — TRHead;
    4.3) обработать рекурсивно хвост исходного списка, результат — TRTail;
    4.4) вернуть результат конкатенации TRHead и TRTail.

    Осталось только посчитать количество чисел в списке:

    countNumberInList(List, Count):-
      findall(X, (member(X, List), number(X)), Numbers),
      length(Numbers, Count).

    Стандартный предикат findall формирует список из элементов, удовлетворяющих условию: элемент входит в список (проверяется стандартной функцией member) и является число (проверку выполняет стандартный предикат number). Функция length вернет искомое количество чисел в списке.

    Если не нравится стандартный findall, можно и без него:

    countNumberInList([], 0):-!.
    countNumberInList([Head|Tail], NumberCount):-
      number(Head), !, countNumberInList(Tail, TailNumberCount), NumberCount is TailNumberCount + 1;
      countNumberInList(Tail, NumberCount).

    В пустом списке нет чисел, поэтому функция возвращает ноль, в противном случае:

    1. исходный список разделяется на голову (Head) и хвост (Tail);
    2. если первый элемент является числом, то к результату рекурсивной обработки хвоста прибавляется единица
    3. иначе (если первый элемент — не число) — результат работы функции вычисляется полностью во время обработки хвоста

    Тут два более-менее универсальных правила — для извлечения элементов заданного уровня и для подсчета количества чисел в списке. Такие правила легко тестировать и воспринимаются они тоже без труда.
    Константы, такие как 1 и 3 содержатся только в коде, который вызывает эти правила:

    count_num_on_1_and_3_levels(List, Count):-
      getNestedLevelElements(List, 1, Level_1),
      getNestedLevelElements(List, 3, Level_3),
      countNumberInList(Level_1, Count_1),
      countNumberInList(Level_3, Count_3),
      Count is Count_1 + Count_3.

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

  • #1904

    questioner
    Участник

    Немного почитав о прологе решил задачу так:

    is_list([]) :- !.
    is_list([_|_]) :- !.
      
    count(List, Count) :-
      count(List, 1, Count).
    count([], _, 0) :- !.
    count([Atom | Tail], Lvl, Count) :-
      (Lvl = 1; Lvl = 3),
      count(Tail, Lvl, C1),
      (
        number(Atom) -> C2 = 1;
        is_list(Atom) -> L is 1 + Lvl, count(Atom, L, C2);
        C2 = 0
      ),
      Count is C1 + C2, !.
    count([Atom | Tail], 2, Count) :-
      (
        is_list(Atom) ->count(Atom, 3, C1);
        C1 = 0
      ),
      count(Tail, 2, C2),
      Count is C1 + C2, !.
    count(_, 4, 0) :- !.

    • #1905

      Спасибо за ответ. Я проверял, оно действительно работает, но сходу я не смог разобраться как именно это происходит :).
      Однако, есть встроенный предикат is_list, а если вдруг его не оказалось, то можно сделать свой так:
      is_list([_]).
      Есть в программировании (любом, не только на прологе) принцип единой ответственности (Single Responsibility Principle), по нему каждая часть вашей программы должна выполнять только одну задачу. В частности, это упростит тестирование кода (можно написать к коду более специализированные тесты и их будет меньше).
      В общем, я не думаю, что смешивать подсчет уровня вложенности и подсчет элементов — это хорошая идея…

      За вариант решения еще раз спасибо.

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