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

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

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

Просмотр 8 сообщений - с 1 по 8 (из 8 всего)
  • Автор
    Сообщения
  • #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):-!.

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

Просмотр 8 сообщений - с 1 по 8 (из 8 всего)

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