Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу 25 задач по Прологу к экзамену
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Майка Майка вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.04.2006
По умолчанию 25 задач по Прологу к экзамену - 20.06.2006, 18:50

Помогите решить задачи!!!!!!!!!!!!!! Очень нужно!!!!!!!!!!!
Примерный перечень практических заданий к экзамену

1. На основе алгоритма восхождения на гору, решите задачу классической головоломки – «Восьмерка». В головоломке принимает участие восемь пронумерованных фишек, которые перемещаются по игровому полю 3х3 Цель состоит в том, чтобы из некоторого случайного расположения фишек перейти к упорядоченному. Дозволенные ходы: выше, ниже, слева, справа. В качестве оценочной функции выберите: количество фишек, которые стоят не на своем месте. Позволяет ли данный метод учитывать такие ситуации, как: а) Все ходы одинаково «хороши» или «плохи» (ситуация «плато»). в) Можно ли решить задачу локальных максимумов, из которых возможен только спуск (например, я могу передвинуть фишку и после этого ухудшить результат

2. Решите головоломку о «миссионерах и каннибалах которая схематически представлена на рисунке. На левом берегу находятся три миссионера и три каннибала. К этому же берегу причалена лодка. На лодке нужно переправить всех миссионеров и каннибалов на правый берег, при условии, что лодка одновременно может перевозить не более двоих, а в обратный путь на лодке должен отправиться хотя бы один человек. Дозволены следующие варианты переправ: К одного каннибала с левого берега на правый, КК двух каннибала с левого берега на правый, МК одного миссионера и одного каннибала с левого берега на правый, ММ двух миссионеров с левого берега на правый, М одного миссионера с левого берега на правый. Такие же варианты с правого берега на левый. Если каннибалов на одном из берегов окажется больше, то миссионеров съедят. Постройте пространства поиска в головоломке используя поиск в ширину. Обозначьте узлы, приводящие к образованию петель символом «°», а узлы, соответствующие недозволенным состояниям символом «●».

3. Допустим, у нас есть монеты достоинством 50, 10, 5, копеек и 1 копейка и нужно вернуть сдачу 63 копейки. Используя «жадный» алгоритм, постройте алгоритм выбора сдачи. На каждой отдельной стадии "жадный" алгоритм выбирает тот вариант, который является локально оптимальным в том или ином смысле. Алгоритм для определения сдачи обеспечивает в целом оптимальное решение лишь вследствие особых свойств монет. Поясните, будет ли работать алгоритм, если у нас будут монеты достоинством 1 копейка, 5 и 11 копеек и нужно бы дать сдачу 15 копеек, как будет работать «жадный» алгоритм, и какой вариант будет оптимальным.

4. Сформируйте пространство решений создания анаграммы с использованием алгоритма порождения и проверки. Приведите два основных варианта поиска: поиск в глубину и поиск в ширину. Поясните алгоритм порождения и проверки. Для анаграммы используйте слово «стоп»

5. Используйте правила Р1 Р2 для формирования полиндромов. Пусть А – это алфавит {a,b} и пусть в этом алфавите существуют аксиомы ab, ba. Какие строки будут сформированы следующими порождающими правилами (P1) $ а  $ab и (P2) b$  $bа. Приложенные к символу а и b. Пусть А – это алфавит {a,b} и пусть в этом алфавите существуют аксиомы ab,ba. Какой набор порождающих правил может сформировать строки вида: aa, bb, aabb, bbaa, aabbaa,bbaabb, aabbaabb, bbaabbaa.

6. Постройте семантическую сеть «Сессия». Включите сущности: институт, факультет, группа, семестр, преподаватель, предмет, оценка, ведомость.

7. Предположим, что «необычная оценка из десяти» определено, как нечеткое множество:
Fнеобычно ={(0, 1.0), (1, 0.9), (2, 0.7), (3, 0.5), (4, 0.3), (5, 0.1), (6, 0.1), (7, 0.3), (8, 0.5), (9, 0.9), (10, 0.9)},
а понятие «высокая оценка из десяти» определено как НМ
Fнеобычно ={(0, 0), (1, 0), (2, 0), (3, 0.1), (4, 0.2), (5, 0.3), (6, 0.4), (7, 0.6), (8, 0.7), (9, 0., (10, 1.0)}.
Постройте сложную функцию «необыкновенно высокая оценка».


8. Создайте функциональную структуру предметной области представленную на рисунке в виде концептуальной схемы описывающей входные и выходные данные. Какие связи использованы в представленной концептуальной схеме. В функциональной структуре используйте до трех рекомендаций с разной степенью уверенности на шкале [1,10].

9.Провести интерпретацию значения рост, определив понятие через базовые понятия : высокий, средний, маленький. Используя функции принадлежности нечетких множеств описать лингвистическую переменную.
Используя Excel, и встроенные стандартные функции ВПР, ГПР, ЕСЛИ, ЕНД, постройте исследовательскую экспертную систему, которая по числовому значению роста будет определять какого роста является данный человек.

10.Провести интерпретацию значения скорость движения автомобиля, определив понятие через базовые понятия: медленно, быстро, вжжить. Используя функции принадлежности нечетких множеств описать лингвистическую переменную.
Используя Excel, и встроенные стандартные функции ВПР, ГПР, ЕСЛИ, ЕНД, постройте исследовательскую экспертную систему, которая по числовому значению скорости будет определять как движется данный автомобиль.

11. Провести интерпретацию значения веса взрослого человека, определив понятие через базовые понятия: худой, стройный, толстый. Используя функции принадлежности нечетких множеств описать лингвистическую переменную.
Используя Excel, и встроенные стандартные функции ВПР, ГПР, ЕСЛИ, ЕНД, постройте исследовательскую экспертную систему, которая по числовому значению веса будет определять к какой категории можно отнести данного человека.

12. Провести интерпретацию значения температуры воздуха в летнее время, определив понятие через базовые понятия: жарко, приятно,брр. Используя функции принадлежности нечетких множеств описать лингвистическую переменную.
Используя Excel, и встроенные стандартные функции ВПР, ГПР, ЕСЛИ, ЕНД, постройте исследовательскую экспертную систему, которая по числовому значению температуры будет определять какой сегодня день

13. Провести интерпретацию значения температуры воздуха в летнее время, определив понятие через базовые понятия: жарко, приятно, брр. Используя функции принадлежности нечетких множеств описать лингвистическую переменную.
Используя Excel, и встроенные стандартные функции ВПР, ГПР, ЕСЛИ, ЕНД, постройте исследовательскую экспертную систему, которая по числовому значению температуры будет определять какой сегодня день

14. Провести интерпретацию значения температуры воздуха в зимнее время, определив понятие через базовые понятия: мороз, холодно, тепло. Используя функции принадлежности нечетких множеств описать лингвистическую переменную.
Используя Excel, и встроенные стандартные функции ВПР, ГПР, ЕСЛИ, ЕНД, постройте исследовательскую экспертную систему, которая по числовому значению температуры будет определять какой сегодня день

15. Рассмотрим стратегию прямого вывода. Имеются несколько фактов. Обозначим их Fl, F2, F3, F5, F7, F8.
Допустим, существует несколько правил. Представим их, как на рис.
Правило 1 гласит, если мы имеем факт F3, F4 то получим вывод (результат) F6,
Правило 2 гласит, если мы имеем факт F6, F2 то получим вывод (результат) F9,
Правило 3 гласит: если мы имеем факт F1, получим вывод (результат) F4,
Эти правила представляют базу знаний. Найти результат F9, используя механизм прямого вывода.
Какая модель знаний используется в этой базе знаний. Поясните.

Задачи на повтор

1. Вывести целые числа кратные 3 из диапазона [21, 35].

2. Кто является сестрой Семена, если отец семена Федор, мать Маша, Отец Дуни Петя, мать Нина, отец Кати Федор, мать Маша. Отношение быть сестрой обеспечивается общностью родителей.
3. Вычислить сумму шести первых членов ряда для
4. Извлечь квадратный корень методом итераций. Для решения задачи воспользуйтесь формулой:

5. Произведите возведение в степень с использованием алгоритма: четная степень получается возведением в квадрат половинной степени, а нечетная – умножением на основание предыдущей четной.

6. Найти смежные числа Фиббоначи. Два начальных числа Фиббоначи равны единице, а каждое из последующих равно сумме двух предыдущих.

7. Вычислить число π с использованием алгоритма удвоения числа сторон вписанного в круг правильного многоугольника. Для шестиугольника сторона равна радиусу, первое приближение для числа π равно 3. Радиус круга предполагается = 1. Программа должна вывести номер приближения и значение невязки DP относительно заданной константой числа π = 3,1415926536. с – высота треугольника к1 – старое число сторон, К – новое число сторон. D-высота сегмента, b – длина новой стороны. PN приближение к Pi PN = K1*B.


Отсечение
1. Студенту в зависимости от набранной в процессе обучения суммы баллов Z присваивается квалификация : Z.>80 магистр, 80>Z.>60 специалист, 60>Z>40 бакалавр 40>Z>0 продолжить обучение.

2. Используя оператор отрицания запишите в пролог программе утверждение, что: Маша любит всех животных кроме мышей.

3. Решите квадратное уравнение: а*х*х + b*х + с = 0, для D>0, D=0, D<0. Ввод коэффициентов a, b, c осуществить с использованием стандартного предиката readreal. Извлечение корня квадратного – sgrt.


Ответить с цитированием
  (#2 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 21.06.2006, 12:02

Хорошие задачи. Правда кое-где не хватает формул, схем, рисунков и описаний алгоритмов.

Вот вторая с самого конца.
Цитата:
2. Используя оператор отрицания запишите в пролог программе утверждение, что: Маша любит всех животных кроме мышей.
Код:
predicates
nondeterm любит(symbol Кто,symbol КогоИлиЧто)
nondeterm животное(symbol)
clauses
животное(лев).
животное(слон).
животное(мышь).

любит("Маша",X):- животное(X),not(X=мышь).
goal
любит(Кто,Кого).
Ответить с цитированием
  (#3 (permalink)) Старый
Мошкович_Александр Мошкович_Александр вне форума
Новичок
 
Сообщений: 3
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.05.2006
По умолчанию 18.07.2006, 18:07

Решение последней задачки.

Код:
domains
число=real
predicates
квадратное_уравнение
ответ(число, число, число)

clauses

квадратное_уравнение:-
    write("Введите коэф-т а\n"),
    readreal(А),
    write("Введите коэф-т b\n"),
    readreal(Б),
    write("Введите коэф-т c\n"),
    readreal(С), !,
    Д=Б*Б-4*А*С,
    ответ(Д, А, Б).
квадратное_уравнение:-
    write("Введены некоректные данные"), nl.
ответ(Д, А, Б):-
    Д=0, !,
    Х=-Б/(2*А),
    write("Один корень: ", Х), nl.
ответ(Д, А, Б):-
    Д>0, !,
    Х1=(sqrt(Д)-Б)/(2*А),
    Х2=(-sqrt(Д)-Б)/(2*А),
    write("Решения: \n", Х1, "\n", Х2), nl.
ответ(_, _, _):-
    write("Корней нет\n").

goal квадратное_уравнение.
Ответить с цитированием
  (#4 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 18.07.2006, 18:32

А если так:
Код:
Введите коэф-т а
0
Введите коэф-т b
0
А дальше что угодно.
Тогда программа вылетает.
Ответить с цитированием
  (#5 (permalink)) Старый
KDimanB KDimanB вне форума
Member
 
Сообщений: 28
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.09.2005
По умолчанию 23.07.2006, 16:22

Интересно просто порешать некоторые из этих задач. Написаны на SWI-Prolog'e.
Буду рад, если кто-нибудь поможет с моим вариантом задачи чисел Фиббоначи:
-Как сделать так, чтобы она не выводила "сгенерированное число" после вывода всех чисел
-Как сделать так, чтобы она выводила числа столбцом, а не создавала список


Код:
%Квадратное уравнение   A*x*x+B*x+C=0
%
%
%

deskr(A,B,C,D):-
  D is (B*B) - (4*A*C).

koren1(A,B,D,X):-
  X is (-(B*B) + sqrt(D))/(A*A).

koren2(A,B,D,X):-
  X is (-(B*B) - sqrt(D))/(A*A).

uravnenie(A,_,_,X1,X2):-
  A =:= 0, !,
  X1 = nothing,
  X2 = nothing.

uravnenie(A,B,C,X1,X2):-
  deskr(A,B,C,D),
  D < 0, !,
  X1 = nothing,
  X2 = nothing.

uravnenie(A,B,C,X1,X2):-
  deskr(A,B,C,D),
  D > 0, !,
  koren1(A,B,D,X1),
  koren2(A,B,D,X2).

uravnenie(A,B,C,X1,X2):-
  deskr(A,B,C,D),
  D = 0, !,
  koren1(A,B,D,X1),
  koren1(A,B,D,X2).



%Квалификация
%
%
%

kto(Score,again):-
  Score < 40, !.
kto(Score,bakalavr):-
  Score < 60, !.
kto(Score,spec):-
  Score < 80, !.
kto(Score,magistr).



%Числа кратные 3 из диапазона [a,b]
%пример: beetween(2,_,29,Spisok).
%
%

%Поиск чисел кратных 3
divthree([],[]).
divthree([Head|Tail],[Head|Tail2]):-
  Head mod 3 =:= 0,
  divthree(Tail,Tail2), !.
divthree([Head|Tail],Tail2):-
  divthree(Tail,Tail2).

%Поиск чисел в интервале
beetween(A,[X],B,Spisok):-
  B - A =:= 2, !,
  X is A + 1,
  divthree([X],Spisok).
beetween(A,[Head|Tail],B,Spisok):-
  B - A > 2,
  Head is A + 1,
  beetween(Head,Tail,B,_),
  divthree([Head|Tail],Spisok).



%Числа Фиббоначи
%
%
%

fibbo(A,B,Max,_):-
  Max < A + B, !.

fibbo(A,B,Max,[Head|Tail]):-
  Head is A + B,
  fibbo(B,Head,Max,Tail).
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,862
Сказал(а) спасибо: 2
Поблагодарили 287 раз(а) в 287 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 24.07.2006, 14:40

KDimanB пишет:
Код:
uravnenie(A,_,_,X1,X2):-
   A =:= 0, !,
   X1 = nothing,
   X2 = nothing.
Почему? Если коэффициент при квадрате равен нулю, то корень существует, т.к. мы имеем уравнение bx+c=0. Следовательно x=-c/b:
Код:
uravnenie(0,B,C,X,X):-!,X = -C/B.
KDimanB пишет:
Код:
uravnenie(A,B,C,X1,X2):-
   deskr(A,B,C,D),
   D < 0, !,
   X1 = nothing,
   X2 = nothing.
Почему? Если дискриминант отрицательный, то корни существуют и они комплексные.

KDimanB пишет:
Код:
uravnenie(A,B,C,X1,X2):-
  deskr(A,B,C,D),
  D = 0, !,
  koren1(A,B,D,X1),
  koren1(A,B,D,X2).
Если дискриминант равен нулю, то корень один X=-B/2A.

KDimanB пишет:
Код:
koren1(A,B,D,X):-
  X is (-(B*B) + sqrt(D))/(A*A).
koren2(A,B,D,X):-
  X is (-(B*B) - sqrt(D))/(A*A).
Здесь две размноженные математические ошибки. Правильно будет так:
Код:
koren1(A,B,D,X):-
  X is (-B + sqrt(D))/(2*A).
koren2(A,B,D,X):-
  X is (-B - sqrt(D))/(2*A).
Вот числа кратные 3 из диапазона [a,b] на Visual Prolog одним предикатом:
Код:
крат3(А,Б):-А>Б,!.
крат3(А,Б):-
   А mod 3 = 0,!,
   write(A),
   A1=A+1,
   крат3(А1,Б).
крат3(А,Б):-
   A1=A+1,
   крат3(А1,Б).
Вот числа кратные 3 из диапазона [a,b] на Visual Prolog одним предикатом В ФУНКЦИОНАЛЬНОМ СТИЛЕ:
Код:
крат3(А,Б):-А>Б,!.
крат3(А,Б):-
   А mod 3 = 0,!,
   write(A),
   крат3(А+1,Б).
крат3(А,Б):-
   крат3(А+1,Б).
Цитата:
6. Найти смежные числа Фиббоначи. Два начальных числа Фиббоначи равны единице, а каждое из последующих равно сумме двух предыдущих.
Что значит "смежные"? Если соседние в натуральном ряде, то это 2 и 3.

KDimanB пишет:
Цитата:
Как сделать так, чтобы она выводила числа столбцом, а не создавала список
Так не создавайте список:
Код:
%Числа Фиббоначи
fibbo(A,B,Max):-
  Max < A + B, !.

fibbo(A,B,Max):-
  Head is A + B,
  write(Head),
  fibbo(B,Head,Max).
И ещё, правильная фамилия - Фибоначчи. Словарь Корнов.
На форуме есть разные проги про эти числа Ф. Можете поискать.
Ответить с цитированием
  (#7 (permalink)) Старый
KDimanB KDimanB вне форума
Member
 
Сообщений: 28
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.09.2005
По умолчанию 25.07.2006, 00:18

Да, с квадратным уравнением я порядочно напортачил:

Цитата:
Почему? Если коэффициент при квадрате равен нулю, то корень существует, т.к. мы имеем уравнение bx+c=0. Следовательно x=-c/b
Да. Я просто подумал, что уравнение ищется по формуле (-B+sqrt(D))/2*A, и если A=0, то это деление на 0, что делать нельзя(т.е. можно, но не нужно). А вообще-то в этом случае уравнение решается по-другому - намного проще =) Перемудрил...

Цитата:
Почему? Если дискриминант отрицательный, то корни существуют и они комплексные.
Да, я просто рассматривал с точки зрения школьной математики. Но уже исправил. Теперь пишет что корни комплексные, а не то, что их нет.

Цитата:
Если дискриминант равен нулю, то корень один X=-B/2A
Возможно я ошибаюсь, но корней два, просто они совпадают. Поэтому и в ответе два.

Ну а просто опечатки(B*B или A*A), это тоже, конечно, плохо. Надеюсь теперь правильно:
Код:
%Квадратное уравнение   A*x*x+B*x+C=0
%
%
%

deskr(A,B,C,D):-
  D is (B*B) - (4*A*C).

koren1(A,B,D,X):-
  X is (-(B) + sqrt(D))/(2*A).

koren2(A,B,D,X):-
  X is (-(B) - sqrt(D))/(2*A).

uravnenie(A,B,C,X1,X2):-
  A =:= 0, !,
  X1 is -(C/B),
  X2 = nothing.

uravnenie(A,B,C,X1,X2):-
  deskr(A,B,C,D),
  D < 0, !,
  X1 = kompleksnoe,
  X2 = kompleksnoe.

uravnenie(A,B,C,X1,X2):-
  deskr(A,B,C,D),
  D > 0, !,
  koren1(A,B,D,X1),
  koren2(A,B,D,X2).

uravnenie(A,B,C,X1,X2):-
  deskr(A,B,C,D),
  D = 0, !,
  koren1(A,B,D,X1),
  X2 = X1.
Уважаемый Винитарх, очень интересна ваша программа про числа, которые делятся на 3. Но я никогда раньше не использовал write, т.к. учусь по книжке Братко, а там такого нет, и все задачи решаются без явного вывода чисел, или значений переменных. Хотя, я только что проверил, write() в SWI-Prologe тоже работает. Это достаточно интересно, так как программы с его использованием сокращаются в размерах.

Таким образом и задача Фибоначчи решается проще и быстрее. И понятно как выводить не используя список.

P.S.: а его фамилию я написал так, как это было написано в задании, потому что сам - не помнил.

Вот попробовал решить задачу про автомат дающий сдачу. Программа работает по принципу, согласно которому дает максимальную из возможных монет. Если монета больше сдачи, она удаляется из списка, и работа программы продожается. Это наверно и есть "жадный" алгоритм сдачи.
Написано на SWIprolog'e (а здесь кроме меня все на Visual работают? помнится примерно так мне ответили, когда я только выбирал где работать - на SWI или Visual)

Код:
%Алгоритм выдачи сдачи
%
%
%

%Минимальное из двух чисел
min(A,B,A):-
  A =< B.
min(A,B,B):-
  B < A.

%Максимальное из двух чисел
max(A,B,A):-
  A >= B.
max(A,B,B):-
  B > A.

%Максимальный элемент в списке
maxlist([A],A).
maxlist([Head|Tail],Max):-
  maxlist(Tail,Max1),
  max(Head,Max1,Max).

%Минимальный элемент в списке
minlist([A],A).
minlist([Head|Tail],Min):-
  minlist(Tail,Min1),
  min(Head,Min1,Min).

%Удаление элемента из списка
del(_,[],[]).
del(X,[X | Tail],Tail2):-
  del(X,Tail,Tail2), !.
del(X,[Y | Tail],[Y | Tail2]):-
  del(X,Tail,Tail2).

%Итак, выдаем сдачу
%Если больше сдачи не надо
sdacha(Sum,_):-
  Sum =< 0, !.

%Если сдача нужна, а монет таких нет
sdacha(Sum,Spisok):-
  minlist(Spisok,Min),
  Min > Sum, !.

%Если сдача это максимальная из доступных монет
sdacha(Sum,Spisok):-
  maxlist(Spisok,Max),
  Sum = Max, !,
  write(Max),
  Sum is 0.

%Если максимальная монета первышает сдачу
sdacha(Sum,Spisok):-
  maxlist(Spisok,Max),
  Max > Sum, !,
  del(Max,Spisok,SpisokNew),
  sdacha(Sum,SpisokNew).

%Если все нормально, то даем максимальную монет из имеющихся
sdacha(Sum,Spisok):-
  maxlist(Spisok,Max),
  SumNew is Sum - Max,
  writeln(Max),
  sdacha(SumNew,Spisok).
Ответить с цитированием
  (#8 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,862
Сказал(а) спасибо: 2
Поблагодарили 287 раз(а) в 287 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 29.07.2006, 13:39

KDimanB пишет:
Цитата:
Почему? Если дискриминант отрицательный, то корни существуют и они комплексные.
Код:
uravnenie(A,B,C,X1,X2):-
  deskr(A,B,C,D),
  D < 0, !,
  X1 = kompleksnoe,
  X2 = kompleksnoe.
Так ведь здесь надо вычислить действительную и мнимую части, а не просто писать, что "корни комплексные".

KDimanB пишет:
Код:
uravnenie(A,B,C,X1,X2):-
  deskr(A,B,C,D),
  D = 0, !,
  koren1(A,B,D,X1),
  X2 = X1.
Проще будет так:
Код:
uravnenie(A,B,C,X,X):-
  deskr(A,B,C,D),
  D = 0, !,
  koren1(A,B,D,X).
А вообще-то Ваша прога неоптимальна, т.к. вычисляет дискриминант несколько раз.

KDimanB пишет:
Цитата:
Вот попробовал решить задачу про автомат дающий сдачу.
Эта задача называется так - "поиск минимального подмножества с заданной суммой элементов". Эта задача считается NP-полной задачей, т.к. принцип оптимальности Беллмана здесь не работаети. Следовательно, эта задача не имеет точного решения. Жадный алгоритм найдёт в общем случае лишь подоптимальное решение и не самое лучшее. Если использовать статистически оправданные эвристики, то можно найти гораздо лучшее решение. Об этой задаче (и не только) есть статья в журнале "Информационные технологии", апрель-май, 2006г.
Пример: есть монеты с номиналами в 50,40,5,4,3,1 коп. Требуемая сдача 87 коп.
Решение по Беллману: 50+5+5+5+5+5+5+5+1+1=87 коп. Всего 10 монет.
Оптимальное решение: 40+40+4+3=87 коп. Всего 4 монеты.
Ответить с цитированием
  (#9 (permalink)) Старый
KDimanB KDimanB вне форума
Member
 
Сообщений: 28
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.09.2005
По умолчанию 02.08.2006, 18:20

Сечас стараюсь решить задачу "алгоритма выдачи сдачи" или задачу поиска минимального подмножества с заданной суммой элементов.
Изобрел такой велосипед:
У кажой монеты есть свой "вес". Рассмотрим задачу со сдачей в 87, и монетами 50, 40, 5, 4, 3, 1. Вес монеты Х для задачи "87" вычисляется по формуле: ВесХ = 87 div X. Т.е. вес монет получается такой:
50 - 1
40 - 2
5 - 17
4 - 21
3 - 29
1 - 87
Ищется по две монеты, нужно найти их таким образом, чтобы их суммарный вес был минимален. К примеру жадный алгоритм сразу берет 50, вес которой равен 1. И максимальное, что он потом сможет взять это 5, вес которой 17. Общий вес монет 50 и 5 равен 18. Оптимальный вариант - 40 и 40, т.к. общий вес равен 4, и это минимальный вес, который можно получить. Далее по идее надо брать 5 с весом 17. Но тогда максимальную монету которую мы сможем взять после 5 это монета 1 с весом в 87. Общий вес 104. Если взять 4 и 3, то общий вес равен 50. Что, меньше всех других вариантов.

Точно так же для задачи в 15, где даны монеты 11, 5, 1. Вес монет:
11 - 1
5 - 3
1 - 15
Если взять монету 11, то потом придется брать 1. Суммарный вес тогда 16. А если взять 5, то потом можно снова взять 5, а суммарный вес всего 6. Ну и берется еще одна 5, т.к. на этом работа алгоритма заканчивается(сдача выдана).

Пока пытаюсь это реализовать на Прологе.
Интересно услышать мнения посетителей форума по этой проблеме.
Ответить с цитированием
  (#10 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 02.08.2006, 19:15

Цитата:
Ищется по две монеты, нужно найти их таким образом, чтобы их суммарный вес был минимален.
Вес монеты обратно пропорционален ее достоинству, поэтому он не является ее "новой" характеристикой.
Взять две монеты наименьшего веса, суммарное достоинство которых укладывается в заданную сумму - это все равно, что взять две монеты, суммарное достоинство которых максимально из всех таких пар монет, сумма стоимостей которых укладывается в заданную сумму.
Так что выбирать по весу и по достоинству - это одно и то же.

И метод брать именно две монеты, наверное, не общий.
Если искать точное решение, то уменьшить перебор, наверное, можно с помощью указания для каждого текущего подмножества - кандидата в решение, набор монет, из которых можно набрать оставшуюся сумму.
Например, {50} - осталась сумма 37, а монеты 5, 4, 3, 1;
{40} - осталась сумма 47, а монеты 40, 5, 4, 3, 1;
...
{40, 40} - осталась сумма 7, а монеты 5, 4, 3, 1;
...
Для приближенного решения в качестве эвристики, наверное, можно брать какую-нибудь оценку каждого такого состояния. По крайней мере, это первое, что пришло мне в голову.
Ответить с цитированием
  (#11 (permalink)) Старый
KDimanB KDimanB вне форума
Member
 
Сообщений: 28
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.09.2005
По умолчанию 02.08.2006, 21:22

Цитата:
Вес монеты обратно пропорционален ее достоинству, поэтому он не является ее "новой" характеристикой.
Взять две монеты наименьшего веса, суммарное достоинство которых укладывается в заданную сумму - это все равно, что взять две монеты, суммарное достоинство которых максимально из всех таких пар монет, сумма стоимостей которых укладывается в заданную сумму.
Так что выбирать по весу и по достоинству - это одно и то же
Я думаю, что по максимальной сумме искать нельзя. Вот пример. Задача со сдачей в 15. Даны монеты 1,5, и 11. Максимальная сумма это 11+1=12, а не 5+5=10! А минимальный вес именно у 5+5, а не у 11+1! В итоге алгоритм пойдет по ложному пути. А ведб оптимальный вариант это 5+5+5, а не 11+1+1+1+1
Ответить с цитированием
  (#12 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 02.08.2006, 22:56

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

Я предлагала оценивать состояния.
Например, в качестве оценки можно взять разность между остатком и номиналом наибольшей из доступных монет. Двигаться надо в сторону наименьшей оценки, добавляя на каждом шагу в каждое подмножество по одной доступной монете.
Здесь будет примерно так (для точного решения):
Шаг 1.
{11}, остаток: 4, возможные монеты: 1. Оценка = 3.
{5}, остаток: 10, возможные монеты: 5, 1. Оценка = 5.
{1}, остаток: 14, возможные монеты: 11, 5, 1. Оценка = 3.
Шаг 2.
{11, 1}, остаток 3, монеты: 1. Оценка = 2.
{1, 5}, остаток 9, монеты: 5, 1. Оценка = 4.
{1, 1}, остаток 13, монеты: 11, 5, 1. Оценка = 2.
{5, 5}, остаток 5, монеты: 5, 1. Оценка = 0.
Шаг 3.
{5, 5, 5}, остаток 0.

Но с моей стороны - это все просто импровизация.
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 03.08.2006, 11:33

Кстати, вычисления этим методом можно существенно уменьшить.
В качестве подмножеств можно брать только такие подмножества монет, чтобы разность между остатком и наибольшей из доступных монет не превышала наибольшей монеты в подмножестве. Ну и монеты, конечно, должны быть упорядочены.
Теперь для сдачи 15 получим:
Шаг 1.
{11}, остаток 4, монеты: 1. Оценка 3.
{5}, остаток 10, монеты: 5, 1. Оценка 5.
Шаг 2.
{11, 1}, остаток 3, монеты: 1. Оценка 2.
{5, 5}, остаток 5, монеты: 5, 1. Оценка 0.
Следовательно, {5, 5, 5} - оптимальное решение.

Если использовать этот метод, то для сдачи 15 оптимальное решение, как было видно, можно найти на 4-м подмножестве, а для сдачи 87 оно находится на 17-м подмножестве. Причем решение гарантированно оптимальное, без дополнительных проверок.
Ответить с цитированием
  (#14 (permalink)) Старый
KDimanB KDimanB вне форума
Member
 
Сообщений: 28
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.09.2005
По умолчанию 03.08.2006, 13:26

Цитата:
Если использовать этот метод, то для сдачи 15 оптимальное решение, как было видно, можно найти на 4-м подмножестве, а для сдачи 87 оно находится на 17-м подмножестве. Причем решение гарантированно оптимальное, без дополнительных проверок.
Да, это очень интересная версия.
Ответить с цитированием
  (#15 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 03.08.2006, 23:59

Перебор здесь можно еще ограничить. Думаю, что можно ограничить добавление монет в одно и то же подмножество: делать доступными монеты, не превосходящие последней добавленной монеты. Оценка некоторых состояний ухудшится, но общность не уменьшится и на результат это не повлияет.
Например, для сдачи 63 и набора монет 50, 10, 5, 1 с помощью данного метода будет так.
Шаг 1.
{50}, остаток 13, монеты 10, 5, 1. Оценка 3.
Шаг 2.
{50, 10}, остаток 3, монеты 1. Оценка 2.
{50, 5}, остаток 8, монеты 5, 1. Оценка 3.
{50, 1}, остаток 12, монеты 1. Оценка 11.
Шаг 3.
{50, 10, 1}, остаток 2, монеты 1. Оценка 1.
{50, 5, 5}, остаток 3, монеты 1. Оценка 2.
{50, 5, 1}, остаток 7, монеты 5, 1. Оценка 2.
{50, 1, 1}, остаток 11, монеты 1. Оценка 10.
Шаг 4.
{50, 10, 1, 1}, остаток 1, монеты 1. Оценка 0.
Решение: {50, 10, 1, 1, 1}.

Всем удачи!
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
БИБЛИОТЕКА ПО ПРОЛОГУ!!! Винитарх Prolog 88 09.12.2015 01:58
Требуется помощь подготовка к экзамену ketti868 Pascal 1 24.06.2011 02:03
Где взять ответы на вопросы к экзамену по "Информационным системам"? NERO_1 Любые вопросы от новичков 11 12.02.2011 13:16
Контрольная по прологу Killer25m Prolog 0 23.11.2010 16:26
помогите допуститься к экзамену! sovsem_ novichok Prolog 0 14.07.2010 18:03
5 задач по прологу kotofey Prolog 14 31.05.2010 22:57
Пара задач по турбо прологу Midous Prolog 5 11.01.2010 13:08
три задачки по прологу imported_Жора Prolog 6 08.06.2007 00:34
лабы про прологу myrlogriz Prolog 4 02.11.2006 12:37
Тесты по Прологу IRINCHA Prolog 10 19.12.2005 15:25
задача по прологу dimants Prolog 1 07.11.2005 23:08
Контр. по Прологу Doom3 Prolog 0 22.05.2005 16:18



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов