Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Представить суму всемя способами 
:(
    Опции темы
_snikers_
  Дата 4.5.2006, 21:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 15
Регистрация: 20.8.2004

Репутация: нет
Всего: нет
Привет мастера!
есть задачка: 
задано неограниченное количество монет ЛЮБОГО номинала. 
(например 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, то перебирать нужно оч долго...
Заранее спасибо! Жду ответа.

 
PM MAIL   Вверх
Yanis
Дата 4.5.2006, 23:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 4
Всего: 111
http://www.delphimaster.ru/cgi-bin/forum.p...6768050&n=3 


--------------------
user posted image *щёлк*
PM MAIL WWW ICQ   Вверх
_snikers_
Дата 4.5.2006, 23:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 15
Регистрация: 20.8.2004

Репутация: нет
Всего: нет
Цитата(Yanis @  4.5.2006,  23:12 Найти цитируемый пост)
http://www.delphimaster.ru/cgi-bin/forum.p...6768050&n=3  

Если бы там хоть что-то додумались, а то все оч умные а ничего и сказать по поводу не могут 
PM MAIL   Вверх
Rouse_
Дата 5.5.2006, 00:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 469
Регистрация: 23.4.2005

Репутация: 1
Всего: 29
Цитата(_snikers_ @  5.5.2006,  00:34 Найти цитируемый пост)
Если бы там хоть что-то додумались, а то все оч умные а ничего и сказать по поводу не могут  

MOD тебе поможет. Начинай с старшего числа. 


--------------------
 Vae Victis
(Горе побежденным (лат.))
Демо с открытым кодом: http://rouse.drkb.ru 
PM MAIL WWW ICQ   Вверх
nostromo
Дата 5.5.2006, 17:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 4
Всего: 10
Простая переборная задача. Действительно, начиная со старшего номинала рекурсивно можно свести исходную задачу к этой задаче с меньшими значениями параметров.
Вот реализация на Smalltalk (VisualWorks). (Предполагается, что последовательность список номиналов монет отсортирован по возрастанию. Если это не так, то все равно работает, только эффективность меньше.)
Код

countWays: nominals sum: sum 
    | maxM nn res newNominals newSum |
    nominals size = 1 "Если монеты только одного вида, то делаем проверку на делимость и возвращаем 1 или 0"
        ifTrue: [^sum \\ (nominals at: 1) = 0 ifTrue: [1] ifFalse: [0]].
    maxM := nominals last.    "Монета максимального достоинства"
    nn := sum // maxM.    "Максимальное число раз, которое может быть взята монета maxM"
    res := 0.
    newNominals := nominals allButLast.
    (0 to: nn) do: 
            [:i | 
            newSum := sum - (i * maxM).
            res := res + (self countWays: newNominals sum: newSum)].
    ^res


Проверяем:
Код

Object new countWays: #(1 3) sum: 10 
"4"

Object new countWays: #(3 5) sum: 10  
"1"

Object new countWays: #(1 2 3 4) sum: 10  
"23"


Добавлено @ 17:17 
Код

Object new countWays: #(2 3 5) sum: 12
"5"
 
--------------------
На пыльных тропинках далеких планет останутся наши следы.
PM MAIL   Вверх
Rockie
Дата 5.5.2006, 19:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

Репутация: 13
Всего: 31
если еще актуально.. Подбельский Вадим Валерьевич =)
.."программа находит разложение чисел, то есть разложение 4 это 4, 3+1, 2+2, 2+1+1, 1+1+1+1"
в функции partition m - число, n - это максимальная часть на которую он раскладывается ( монета макс достоинства у nostromo) - в данном случае тоже 4.
Код
#include <iostream.h>
#include <conio.h>

int partition(int,int);

int partition(int m,int n){
  if(m == 1 || n == 1) return 1;
  if(m <= n) return( 1 + partition(m, m-1) );
  return( partition(m,n-1) + partition(m-n,n));
}

int main()
{ cout<<partition(4,4);
  getch();
  return 0;
}


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


--------------------
Чтобы иметь большой гардероб - надо иметь большой гардероб.
PM   Вверх
_snikers_
Дата 10.5.2006, 16:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 15
Регистрация: 20.8.2004

Репутация: нет
Всего: нет
как раз актуально.... это то что нада....... торлько бы на delphi (pascal) 
PM MAIL   Вверх
nostromo
Дата 10.5.2006, 17:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 4
Всего: 10
Замечу, что программа Rockie не "находит разложение чисел", а подсчитывает количество вариантов в частном случае задачи, когда заданы N монет достоинством 1, 2, ...,N.

Добавлено @ 17:36 
Прошу прощения, не "N монет", а N номиналов монет. 
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0710 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.