Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 2006.06.04;
Скачать: [xml.tar.bz2];

Вниз

Представить суму всемя способами   Найти похожие ветки 

 
bogdan   (2006-05-04 22:40) [0]

Привет мастера!
есть задачка:
задано неограниченное количество монет ЛЮБОГО номинала.
(например 2, 3, 7,15 или 1,4,7,25,50,70)
Задана сумма С.
нужно узнать сколько есть РАЗНЫХ способов представить суму С через заданые монеты
пример:
пусть номиналы: 2,3,5 а сумма 12.
тогда
12=2+2+2+2+2+2
  =2+2+2+3+3
  =3+3+3+3
  =2+5+5
  =5+3+2+2     тоесть 5 вариантов
Помогите плиз решить эту задачку..
Есть вариант перебрать все комбинации из номиналов
но если номиналов например 20, то перебирать нужно оч долго...
Заранее спасибо! Жду ответа.


 
oldman ©   (2006-05-04 22:58) [1]

Пора открывать новый форум:
"Помогите написать курсовик тому, кто вместо учебы пиво пил!".


 
Gero ©   (2006-05-04 23:03) [2]

Тебе нужно встретиться с Юликой. Я уверен, вместе вы что-нибудь придумаете.
А задачи — как нибудь потом...


 
API ©   (2006-05-04 23:26) [3]

задано неограниченное количество монет ЛЮБОГО номинала
<...>
Помогите плиз решить эту задачку..


Для начала предоставьте неограниченное количество монет (можно не заморачиваться с монетами, а перейти стразу к купюрам, думаю, по 100$ будет самый раз) - а там уж мы и не такое решим! ;-)


 
Труп Васи Доброго ©   (2006-05-04 23:29) [4]

bogdan   (04.05.06 22:40)
Есть вариант перебрать все комбинации из номиналов
но если номиналов например 20, то перебирать нужно оч долго...

Да хоть 200 номиналов, хоть триста. С мощью современных процессоров это займёт не больше 1-2 минут, а это не долго.


 
API ©   (2006-05-04 23:32) [5]

Да хоть 200 номиналов, хоть триста. С мощью современных процессоров это займёт не больше 1-2 минут, а это не долго.

Вот кабы банкоматы по 2 минуты деньги для выдачи считали... :-)


 
McSimm ©   (2006-05-04 23:47) [6]

А скажите, кому не жалко, только честно. Все ли из тех, кто отметился в ветке имеют представление о том, как это количество вариантов отыскивать?
:))


 
Хозяин   (2006-05-04 23:53) [7]

Что-то наподобие решал, только по подбору труб. Вспоминать неохота.


 
Хозяин   (2006-05-04 23:57) [8]

[7] + там не точно нужно было, какой-то зазор допускался.


 
Yegorchic ©   (2006-05-04 23:58) [9]


> McSimm ©   (04.05.06 23:47) [6]


Решал такое в этом году на олимпиаде по информатике.


 
Yegorchic ©   (2006-05-04 23:59) [10]


> Yegorchic ©   (04.05.06 23:58) [9]


Перечитал ещё раз [0] - решал чуть-чуть по легче. Совсем чуть-чуть...


 
bogdan   (2006-05-05 00:29) [11]

Впринципе ответов много но по сути ни одного, наверное вы все такие умные что даже идею не знаете.... А все решали... все знают....
Перебором НЕ ПОДХОДИТ, по-этому здесь и спросил !!!!!!!!!!!!


 
Хозяин   (2006-05-05 00:31) [12]

Подожди до утра, тут ведь дело такое, народ заинтерисовать нужно.


 
bogdan   (2006-05-05 00:32) [13]


>
> McSimm ©   (04.05.06 23:47) [6]
> А скажите, кому не жалко, только честно. Все ли из тех,
> кто отметился в ветке имеют представление о том, как это
> количество вариантов отыскивать?
> :))

Хоть кто то сообразил.... А не просто написал что попало...


 
bogdan   (2006-05-05 00:33) [14]


> Хозяин   (05.05.06 00:31) [12]
> Подожди до утра, тут ведь дело такое, народ заинтерисовать
> нужно.

и чем.????????


 
Хозяин   (2006-05-05 00:35) [15]

bogdan   (05.05.06 0:33) [14]
Кому интересно - тот и будет решать. Вроде так.


 
DrPass ©   (2006-05-05 00:40) [16]

В случае произвольного набора номиналов эта задачка решается ТОЛЬКО перебором. Разве не так?


 
API ©   (2006-05-05 00:46) [17]

[6] McSimm ©   (04.05.06 23:47)

Дык, если Ньютон, в пору своей молодости, был в состоянии, так отчего ж и нам, на заре 21 века, не посчитать?


 
SergP ©   (2006-05-05 00:54) [18]


> bogdan   (04.05.06 22:40)  


Завтра пятница. Проси МВО чтобы он разместил задачу в завтрашнем выпуске пятничных задачек. Тогда будет большая вероятность что ее решат.


 
Alx2 ©   (2006-05-05 02:27) [19]

Проста она слишком для пятницы.


{$APPTYPE CONSOLE}
Type
 TIntegerArray = array of integer;
procedure Solve(Const Nominals : TIntegerArray; Sum : Integer);
Var sCount : Integer;
   Solution : TIntegerArray;
procedure PrintSolution(idx : Integer);
Var k : Integer;
begin
for k := Length(Nominals)-1 downto idx+1 do
if Solution[k]<>0 then
  write(Nominals[k],"*",Solution[k]," ");
writeln;
end;

procedure subSolve(idx,rest : Integer);
Var newRest : Integer;
Begin
if rest = 0 then
begin
   inc(sCount);
   printSolution(idx);
end;
if (idx>=0) and (rest>0) then
begin
  newRest := rest;
  Solution[idx] := 0;
  while newRest>=0 do
  begin
   subSolve(idx-1,newRest);
   inc(Solution[idx]);
   dec(newRest,Nominals[idx]);
  end;
end;
End;
Begin
sCount := 0;
SetLength(Solution,Length(Nominals));
subSolve(Length(Nominals)-1,Sum);
Writeln("Count: ",sCount);
End;
Var Nominals : TIntegerArray;
begin
 SetLength(Nominals,6);
 Nominals[0] := 2;
 Nominals[1] := 3;
 Nominals[2] := 5;
 Nominals[3] := 15;
 Nominals[4] := 23;
 Nominals[5] := 27;
 Solve(Nominals,100);
end.


 
bogdan   (2006-05-05 02:55) [20]


> Проста она слишком для пятницы.

хоть она и проста, но СПАсибо

> Alx2 ©

ПОПРОбую разобраться.....
Большой сенкс....


 
Хозяин   (2006-05-05 05:21) [21]

Alx2 ©   (05.05.06 2:27) [19]

Немогу найти, например, вот это:
15*6 3*2 2*2

Ведь на примере(у автора) показано, что необязательно использовать все номиналы.


 
Alx2 ©   (2006-05-05 09:12) [22]

>Хозяин   (05.05.06 05:21) [21]

???
Не понял вопроса. В приведенном примере оно (15*6 3*2 2*2
) идет 524 строкой.


 
Хозяин   (2006-05-05 09:15) [23]

А у меня все начинаются на 27 :(

Сейчас посчитаю строки, а итог 1368 (D6)


 
Хозяин   (2006-05-05 09:19) [24]

не может быть 1368, это у меня консольное окно обрезало :)

начало
27*1 15*1 5*4 3*12 2*1
конец
27*3 15*1 2*2

Извени
:)


 
Alx2 ©   (2006-05-05 09:20) [25]

>Хозяин   (05.05.06 09:19) [24]
Так запускать лучше: file.exe > lst.txt
А потом смотреть lsts.txt :)


 
Хозяин   (2006-05-05 09:22) [26]

Ну а я из Делпхи, только поставил readln; :)


 
Rulikkk   (2006-05-05 11:10) [27]

Господа, а Вам часом не кажется, что это задачка на динамическое программирование? То есть например надо предстваить 100, имея 5, 7, 2 (например).
Заводим массив - от 1 до 100. На самом деле реально хватит хранить только 7 или 8 его последних элементов (т.к. максимальный номинал - 7).
В нём будем хранить кол-во вариантов представления для номера элемента. То есть в первом элементе - 0, т.к 1 никак не получишь. Во втором - 1, т.к. только одним способом можно представить.
Изначально он будет заполнен нулями. Заполняя i-ый элемент мы будем смотреть, есть ли не нули в элементах (i-5), (i-7), (i-2) и суммировать все эти значения. И так далее, до 100.


 
bogdan   (2006-05-05 15:52) [28]


> [27]

А например, а то динамическое программирование для меня оч слабовато,
..............

Я вот еще не могу понять до конца как работает [19]

тяжело доходит, а еще на delphi "переносить"....


 
Alx2 ©   (2006-05-05 16:17) [29]

>bogdan   (05.05.06 15:52) [28]

Оно уже на Delphi. Куда еще переносить? Заменить или выкинуть вывод через writeln - весь перенос.

>Я вот еще не могу понять до конца как работает [19]

Рекурсия. Есть набор монет и есть сумма. Если мы возьмем одну монету из набора, то сумма уменьшится. Получили снова такую же задачу, с тем же набором монет, но новой суммой. Значит, действуем точно так-же. Как только от новой суммы остался "0" - значит, разменяли все.


 
TUser ©   (2006-05-05 16:25) [30]

Не надо использовать рекурсию, там где можно обойтись ДП. Увы - в классчиеских книгах по программизму ДП обходят молчанием (кроме Кормена). Поэтому изложу тут общюю идею.

Мысль состоит в том, чтобы получить решение не одной, а множества возможных задач. Применительно к здесь - найти число способов, которыми можно выразить сумму 1, сумму2, 3, 4, ..., 100. Допустим значения для сумм 1..N известны. Тогда легко найдем значения для N+1. Например, если у нас есть монеты достоинства 2 и 3, то число таких способов есть С[N-1] + С[N-2]. Так потихоньку до сотни доберешься.


 
Alx2 ©   (2006-05-05 16:30) [31]

>Не надо использовать рекурсию, там где можно обойтись ДП.

Закон, и номер статьи, пожалуйста :)

Понеслось. Числа Каталана, комбинаторные порождающие функции, интегрирование в комплексной плоскости вокруг полюса. :) Из пушек по воробьям.


 
TUser ©   (2006-05-05 17:09) [32]

> Alx2 ©   (05.05.06 16:30) [31]

Закон о неполучении по шеям от препода, Заказчика и Здравого Смысла при неиспользовании экспоненциального алгоритма, когда есть простой линейный. Все статьи.


 
Alx2 ©   (2006-05-05 19:19) [33]

>TUser ©   (05.05.06 17:09) [32]

Сижу, глотаю сопли... Уел, блин, отповедью :)

Извини, что привел переборный и к тому же рекурсивный алгоритм и покоробил чувство прекрасного. :) Впредь всегда буду стремиться в ДП к отсутствию рекурсии, а в алгоритмах - к минимальной сложности. :)

"Не надо использовать рекурсию, там где можно обойтись ДП" - теперь моя максима.


 
TUser ©   (2006-05-05 19:30) [34]

Зря ты ерничаешь.


 
Alx2 ©   (2006-05-05 19:39) [35]

>TUser ©   (05.05.06 19:30) [34]

На самом деле вопрос серьезный. Не будем лезть в философию где использовать рекурсию, а где - нет. И будем тратить усилия на поиска оптимума по сложности, тогда, когда он нужен.

PS
По этой задачке сразу можешь написать линейный алгоритм?
У меня смутные сомнения, что тут дело обстоит посложнее, чем в просто поиске количества разбиений числа в сумму положительных слагаемых, его не превышающих.


 
Alx2 ©   (2006-05-05 19:46) [36]

Я через рекуррентное соотношение, следуещее из той самой рекурсии, получил нечто подобное.


 
MBo ©   (2006-05-05 19:48) [37]

>TUser
На мой взгляд, в данной задаче ДП не имеет явных преимуществ.
Если бы нужно было одно решение получить - тогда, наверно, эффективнее было бы ДП использовать (подобно рюкзаку), и не перебирать все, а тут нужно выдать все решения - и рекурсивное вычерпывание хорошо справляется


 
Alx2 ©   (2006-05-05 19:51) [38]

>MBo ©   (05.05.06 19:48) [37]

>а тут нужно выдать все решения

Теперь только  количество.


 
MBo ©   (2006-05-05 19:51) [39]

[37] continued...
c, похоже, меньшими затратами памяти  - стек глубиной в VerySmallConst*Sum/MinValue против весьма солидного дерева у ДП (тут могут быть варианты, возможно, я преувеличиваю)


 
MBo ©   (2006-05-05 19:57) [40]

>Alx2 ©   (05.05.06 19:51) [38]
>Теперь только  количество"

Пардон, не обратил внимания. Тогда ДП значительно упрощается по сравнению с тем вариантом, о котором я думал.



Страницы: 1 2 вся ветка

Форум: "Прочее";
Текущий архив: 2006.06.04;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.54 MB
Время: 0.05 c
15-1147168601
Kolan
2006-05-09 13:56
2006.06.04
Где взять описание языка UML


15-1146834675
Jeer
2006-05-05 17:11
2006.06.04
Еще один Gesserex ?


2-1146918105
Квэнди
2006-05-06 16:21
2006.06.04
Ошибка при работе с Mysql 5


15-1146896035
igorserg
2006-05-06 10:13
2006.06.04
Как отловить, что комп уходит в спящий или ждущий режим?


2-1148039229
kitti
2006-05-19 15:47
2006.06.04
Microsoft SQL Server





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский