VPF::Задача с бидонами - Форум программистов

belphegor

Дата 17.3.2007, 23:03 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 28
Регистрация: 17.12.2006
Где: Молдова, Кишинев

Репутация: нет
Всего: нет

Здравствуйте если ктото может мне помочь, буду очень благодарен.
У меня такая задача:
Дано три бидона 8-ми,5-ти,3-х литровые.
В начале в 8-ми литровый бидон полный.
Найти последовательность действий в результате которых в 8-ми и 5-ти литровом бидоне
будет по 4 литра.
Возможный действия которые можно производить:
---бидон может быть наполнен
---бидон может быть опусташен
---бидон может быть перелит из одного бидона в другой

заранее спасибо.

Artemios

Дата 29.3.2007, 12:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 2
Всего: 50

Код


% каждый бидон представляем парой [Емкость,ЗанятыйОбъем]

% первые два аргумента - начальные два бидона,
% вторые два - те же бидоны после перелития из 1-го во 2-й
перелить([E1,S1],[E2,S2],[E1,Sn1],[E2,Sn2]):-
    S1>0,        % есть что перелить
    P2 is E2-S2,    % количество свободного места во 2-м бидоне
    P2>0,        % есть куда перелить
    (    P2=<S1, Sn1 is S1-P2, Sn2 is S2+P2;
        P2>S1, Sn1 is 0, Sn2 is S2+S1
    ).

% действие над тремя бидонами, которые храним в списке
действие(L1,L2):-
    select(B1,L1,L11),
    select(B2,L11,L111),
    перелить(B1,B2,Bn1,Bn2),
    select(Bn2,L22,L111),
    select(Bn1,L_2,L22),
    sort(L_2,L2).

% если в качестве узла принять тройку бидонов,
% а переход из одного узла в другой рассматривать,
% как действие перелития из некоторого одного бидона тройки
% в другой (описано предикатом "действие", только на графе направление перехода обратное),
% то множество узлов и переходов (ребер) образуют
% ориентированный граф, на котором требуется найти путь от
% узла [[3,0],[5,4],[8,4]] до узла  [[3,0],[5,0],[8,8]]

% поиск пути без повторений
путь(А,[А|Путь],[А|Путь]).
путь(А,[Б|Путь1],Путь):-
    действие(Б,В),
    not(member(В,Путь1)),
    путь(А,[В,Б|Путь1],Путь).

вывод_списка([]).
вывод_списка([Г|Х]):-
    write(Г),nl,
    вывод_списка(Х).

решение:-
    путь([[3,0],[5,4],[8,4]],[[[3,0],[5,0],[8,8]]],ПоследовательностьДействий),
    reverse(ПоследовательностьДействий,L),
    вывод_списка(L).

Проверка:

Цитата

?- решение.
[[3, 0], [5, 0], [8, 8]]
[[3, 3], [5, 0], [8, 5]]
[[3, 0], [5, 3], [8, 5]]
[[3, 3], [5, 3], [8, 2]]
[[3, 1], [5, 5], [8, 2]]
[[3, 0], [5, 5], [8, 3]]
[[3, 3], [5, 2], [8, 3]]
[[3, 0], [5, 2], [8, 6]]
[[3, 2], [5, 0], [8, 6]]
[[3, 2], [5, 5], [8, 1]]
[[3, 3], [5, 4], [8, 1]]
[[3, 0], [5, 4], [8, 4]]

Yes
?-

Вообще, неуверен, что находится оптимальная по длине последовательность действий,
по-хорошему бы искать кратчайший путь на графе, а не только первый попавшийся.
Но это уже не сложно smile

попробуй сам.

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Artemios

Дата 2.4.2007, 17:10 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 2
Всего: 50

Не стерпел, даю полный вариант (но без комментариев):

Код


:-dynamic(ребро/2).

перелить([E1,S1],[E2,S2],[E1,Sn1],[E2,Sn2]):-
    S1>0,
    P2 is E2-S2,
    P2>0,
    (    P2=<S1, Sn1 is S1-P2, Sn2 is S2+P2;
        P2>S1, Sn1 is 0, Sn2 is S2+S1
    ).

действие(L1,L2):-
    ребро(L2,L1).

действие(L1,L2):-
    select(B1,L1,L11),
    select(B2,L11,L111),
    перелить(B1,B2,Bn1,Bn2),
    append([Bn1,Bn2],L111,L22),
    sort(L22,L2),
    not(ребро(L2,L1)),
    assert(ребро(L2,L1)).

путь(А,[А|Путь],[А|Путь]).
путь(А,[Б|Путь1],Путь):-
    действие(Б,В),
    not(member(В,Путь1)),
    путь(А,[В,Б|Путь1],Путь).

последовательность_действий(L):-
    путь([[3,0],[5,4],[8,4]],[[[3,0],[5,0],[8,8]]],L).

мин_последовательность(L1,L2):-
    length(L1,D1),
    последовательность_действий(L),
    length(L,D),
    D<D1,
    мин_последовательность(L,L2).
мин_последовательность(L,L).

вывод_списка([]).
вывод_списка([Г|Х]):-
    write(Г),nl,
    вывод_списка(Х).

решение:-
    последовательность_действий(L1),
    мин_последовательность(L1,L2),
    reverse(L2,L),
    вывод_списка(L).

и результат работы:

Цитата

?- решение.
[[3, 0], [5, 0], [8, 8]]
[[3, 0], [5, 5], [8, 3]]
[[3, 3], [5, 2], [8, 3]]
[[3, 0], [5, 2], [8, 6]]
[[3, 2], [5, 0], [8, 6]]
[[3, 2], [5, 5], [8, 1]]
[[3, 3], [5, 4], [8, 1]]
[[3, 0], [5, 4], [8, 4]]

Yes
?-

Добавлено через 5 минут и 16 секунд
конечно все жутко неоптимально, но вроде корректно и работает.

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »