Минимальный и предминимальный элементы и их позиции

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

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

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

    questioner
    Участник

    Здравствуйте! Помогите пожалуйста решить задачу на swi prolog без использования встроенный функций.

    Найти за один проход по списку минимальный и предминимальный элементы и их номера(позиции). Используя 4 накопителя — значения элементовтов и их номера.

    Не могу разобраться:

    1. как задать изначально минимальные элементы, перед тем чтобы сравнивать поочередно с элементами списка;
    2. как правильно счетчик I установить;
    3. удаление элемента.

    Мой код сырой и нерабочий:

    poisk([], _):-
      !, fail.
    poisk([], min1, n1, min2, n2):-
      poisk([], min1,n1,min2,n2,I).
     
    poisk([], min1,n1,min2,n2,1):-
      g([H|T]),
      H<min1,!,(min2:=min1, min1:=H, n1:=????, n2:=I, delete(), poisk()));
      (H<min2,!, min2:=H, n1:=I, delete(),poisk()).

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

  • #1829

    Вы решаете задачу в корне не правильно. На вопросы по порядку:

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

      p([A, B], Min, NextMin):-
        A > B, Min = A, NextMin = B; Min = B, NextMin = A.

      Я привел код без индексов, вставите их сами, это просто.

    • Видимо начальное значение счетчика — единица (или ноль) явно передается в предикат. На каждом шагу от списка отделяется элемент и рекурсивно обрабатывается хвост. При обработке хвоста передается увеличенное значение счетчика.
    • в вашей задаче удалять элемент не требуется.

      В общем, я напишу как бы я это делал для поиска минимума, а вы допишите сами.

      min([H|T], VMin, IMin):-
        min(H, 1, 2, T, VMin, IMin).
      min(VMin, IMin, _, [], VMin, IMin):-!.
      min(TMin, IMin, I, [H|T], RVMin, RIMin):-
        II is I + 1, (
          H < TMin, !, min(H, I, II, T, RVMin, RIMin);
          min(TMin, IMin, II, T, RVMin, RIMin)
        ).

    Описан вспомогательный предикат, без накопителей, он нужен чтобы вашей поделкой было удобно пользоваться. Без такой обертки программисту придется постоянно думать над тем как правильно надо инициализировать накопители;

    • В основную функцию первыми двумя аргументами передаются значение и индекс текущего минимального элемента (накопитель), третий аргумент — текущее значение индекса (оно на единицу больше, т.к. первый элемент списка мы уже не обрабатываем). Четвертый аргумент — хвост списка, а пятый и шестой — результат (передаются несвязанные переменные);
    • Обрабатывается случай пустого исходного списка. Очевидно, что если на вход поступил пустой список, то надо вернуть в качестве результата работы значения накопителей (пятый и шестой аргументы совпадают с первым и вторым);
    • Исходный список разделяется на голову (H) и хвост (T);
    • вычисляется новое значение счетчика;
    • в зависимости от отношения порядка, существующего между текущим значением минимума (первым аргументом) и текущим обрабатываемым элементом (H) формируются значения первого и второго аргумента функции для рекурсивной обработки хвоста списка (T).

    Если коротко, то пролог — это язык, очень близкий к математике. Если бы Вы попробовали записать поиск минимального значения списка и его индекса только при помощи математических обозначений, то получили бы что-то очень похожее на эту программу. Однако, по наброскам кода, который вы привели видно, что вы пытаетесь писать на прологе как на каком-то С++ или Паскале. Не надо так делать, все гораздо проще. Пролог обладает бешеной выразительной мощью в математических задачах. Еще более выразительным (ваша задача решается в 1 строку) его можно сделать написав несколько вспомогательных функций (которые есть в стандартной библиотеке), но Вам их нельзя использовать…

    • #1830

      questioner
      Участник

      Не могу понять как дописать второй минимальный элемент.
      Очень сложно перестроиться под логику Пролога.

      Подозреваю, что надо еще одно условие добавить, но не знаю куда.

      • #1831

        Напишите как бы Вы решали эту задачу на С++, например, а я перепишу на пролог.
        Приводите код (или словесное описание алгоритма, хотя бы), а под кодом пояснения к нему — за образец оформления можно взять мое описание предиката min.
        Пишите без ошибок, в том числе стилистических. В технических текстах предложения с союза начинать не принято. Пишите так, чтобы мне не править не пришлось.

        • #1832

          questioner
          Участник

          Мне проще написать на Паскале.

          var
            ms: array [1..1000] of integer;
            i,n,min1,min2:integer;
          begin
            readln(n);
            for i:=1 to n do
              readln(ms[i]);
           
            min1:=maxint;
            min2:=maxint;
            i1:=0; i2:=0;
           
            for i:=1 to n do
            begin
              if ms[i] 14. begin
                min2:=min1;
                min1:= ms[i];
                i2:=i1;
                i1:=I;
              end;
              else
                if ms[i] 22. begin
                  min2:=ms[i];
                  i2:=I;
                end;
              end;
            writeln(min1,’ ‘,i1, ‘ ‘,min2,’ ‘, i2);
          end.

          Объяснение кода по строчкам:
          1-2) Объявляем массив целочисленных чисел;
          3) Объявляем I – счетчик для цикла, n – количество элементов массива, min1 и min2 – значения двух минимальных элементов, i1 и i2 – индексы минимальный элементов соответственно;
          4) Начало программы;
          5) Считываем с клавиатуры n;
          6-7) Задаем цикл, считывающий элементы массива с клавиатуры;
          8-9) минимальным элементам присваиваем максимально возможное значение;
          10) Индексам задаем начальное значение ноль;
          11) Задаем цикл по всем элементам массива;
          12) Начало цикла;
          13) Задаем условие: текущий элемент меньше min1. Если оно выполняется, то переходим к строке 14, если нет, то к 20.
          14) begin;
          15) Второй минимальный элемент принимает значение первого;
          16) Первый минимальный принимает значение текущего элемента массива.
          17) Индексу второго минимального элемента присваиваем значение первого;
          18) Индексу первого минимального элемента присваивается текущее значение счетчика;
          19) end;
          20) Если первое условие(13 строка) не выполнилось, то переходим сюда;
          21) Задаем условие: текущий элемент меньше min2.
          22) begin;
          23) Второму минимальному элементу присваиваем значение текущего элемента;
          24) Индексу второго минимального элемента присваиваем текущее значение счетчика.
          27) Выводим на экран значения и индексы минимальных элементов.

          • #1833

            На прологе можно сделать так:

            min([A, B|T], VPrevMin, IPrevMin, VMin, IMin):-
              A < B, !, min(B, 2, A, 1, 3, T, VPrevMin, IPrevMin, VMin, IMin);
              min(A, 1, B, 2, 3, T, VPrevMin, IPrevMin, VMin, IMin).
             
            min(VPrevMin, IPrevMin, VMin, IMin, _, [], VPrevMin, IPrevMin, VMin, IMin):-!.
            min(VPrevMin, IPrevMin, VMin, IMin, I, [H|T], RVPrevMin, RIPrevMin, RVMin, RIMin):-
              II is I + 1, (
                H =< VMin, !, min(VMin, IMin, H, I, II, T, RVPrevMin, RIPrevMin, RVMin, RIMin);
                H =< VPrevMin, !, min(H, I, VMin, IMin, II, T, RVPrevMin, RIPrevMin, RVMin, RIMin);
                min(VPrevMin, IPrevMin, VMin, IMin, II, T, RVPrevMin, RIPrevMin, RVMin, RIMin)
              ).

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

            • #1834

              questioner
              Участник

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

              • #1835

                Вы не правы, мне кажется.
                Чисто математически:

                • X — минимальный элемент списка L, если для любого элемента E списка L выполняется E >= X.
                  • S — предминимальный элемент списка L, если для любого элемента E списка L выполняется:

                  • S < E, если Е - минимальный элемент L
                  • E >= X, в противном случае.

                В общем, минимальный элемент и предминимальный — это два разных элемента. Если список содержит только один элемент — то в нем нет предминимального по определению.

                В коде, который я привел такая проверка выполняется в первой строке:
                [A, B|T]

                Тут входной список разделяется на A — первый элемент, B — второй элемент и T — остаток списка. Если нет элемента A или B — то правило завершается неудачей.

                Проверка того, что в списке содержится всего один элемент на языке Prolog может быть записана так:

                p([X], X, X):-!.

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

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