2 задачки. Размен денег и произведение многочленов

← →
trxnet © (2009-11-03 21:13) [0]

Всем привет. Помогите пожайлуста решить задачи и помоч составить алгоритм.

Задача1: Для заданной суммы денег, напечатать способ ее представления минимальным числом купюр и манет.

Задача2: Произведение многочленов. По заданным коэффициентам многочлена n-й степени А(х) и многочлена m-й степени B(х) определить коэффициенты многочлена С(х) = А(х) * В(х)

Спасибо!

← →
Pavia © (2009-11-03 21:17) [1]

1 Линейное программирование
2 Свертка через БПФ.

← →
vrem (2009-11-03 21:23) [2]

1 - вычитание из суммы денег сначала самых крупных купюр(может по несколько штук), потом мельче, потом так же монеты

← →
korneley © (2009-11-03 21:26) [3]

В приципе, уже всё сказано, но не могу удежаться: "манет" пишется через "о" А вот другое, через "а".

← →
korneley © (2009-11-03 21:46) [4]

В приципе = в принципе. Начинаю ненавидеть неполноразмерные клавиатуры ещё больше :))

← →
trxnet © (2009-11-03 21:51) [5]

А по подробнее про свертку через БПФ можно? Мне эту программу нужно сделать именно с массивом(

Вот как я думаю: Например, перемножаем скобки
(2х^2+3х+8х)*(4х^4+5х+7х) = 8x^6+10х^3+14x^3+
+12x^5+15x^2+21x^2+
+32x^5+40x^2+56x^2

повторяющиеся степени, их числа складываем и помещаем в массив с индексом этой степени, например: ...15x^2+21x^2... - 15+21=36 и помещаем в массив с индексом 2, т.к степень 2, ну и так делее... Так будет правильно?

← →
TUser © (2009-11-03 22:04) [6]

> Так будет правильно?

да, так и надо сделать

← →
trxnet © (2009-11-03 22:11) [7]

А по первой задачи, нарзрело только это:

Отнимаем например 5000 тыщ, если число отричательное получилось, то отнимаем меньше, если неотрицательно, то пробуем отнять это же еще, если не отрицательное, пробуем еще, если отрицательное, то отнимаем еще меньшуюю купюру, в потом сложим результат и сравним с введеной сумой (или вычтем из нее), если совпадает или при вычитании 0, то все верно. Вот так можно реализовать ?

← →
palva © (2009-11-03 22:48) [8]

> (2х^2+3х+8х)*(4х^4+5х+7х)

По-моему, следует привести подобные в исходных многочленах перед их умножением. А коэффициенты каждого многочлена нужно разместить в массиве, включая нули для пропущенных степеней. Например, многочлен
4х^4+12х будет записан в массиве так (0,12,0,0,4) Порядок коэффициентов лучше сделать обратным, так многочлены будет проще складывать и умножать.

← →
Styx (2009-11-03 23:42) [9]

> 1 - вычитание из суммы денег сначала самых крупных купюр(может
> по несколько штук), потом мельче, потом так же монеты

Допустим, есть монеты по рублю, девять и десять рублей (такая вот забавная монетная система). И есть сумма 27 рублей. Тогда получится 2*10+7*1, а не 3*9...

← →
trxnet © (2009-11-04 11:49) [10]

Про деньги не получается сделать алгоритм(

← →
oldman © (2009-11-04 11:58) [11]

> Styx (03.11.09 23:42) [9]

А вот кассиры в магазинах сдают именно 2*10+7*1 а не 3*9 :)))

← →
cwl © (2009-11-04 13:32) [12]

> oldman © (04.11.09 11:58) [11]
в вашем государстве есть копюра/монета достоинством в 9 денег?

← →
cwl © (2009-11-04 13:33) [13]

oldman © (04.11.09 11:58) [11]
> +7*1
неа. 5+2, 2+2+2+1. получить 7 раз по рублю - редкость :>

← →
TUser © (2009-11-04 13:39) [14]

> в вашем государстве есть копюра/монета достоинством в 9
> денег?

нарисуем

← →
Inovet © (2009-11-04 13:49) [15]

> [12] cwl © (04.11.09 13:32)
> > oldman © (04.11.09 11:58) [11]
> в вашем государстве есть копюра/монета достоинством в 9
> денег?

Ну а чё. В Британии вон выпустили монету 99 пенсов, а то цены все 14.99, например.

← →
Игорь Шевченко © (2009-11-04 13:55) [16]

Сумма денег за помощь не озвучена

> Про деньги не получается сделать алгоритм(

Ну так алгоритм же уже подсказали:

> vrem (03.11.09 21:23) [2]
>
> 1 - вычитание из суммы денег сначала самых крупных купюр(может
> по несколько штук), потом мельче, потом так же монеты

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

А что касается реализации алгоритмя, то например на Дельфи он может выглядеть так:

//summa -сумма в копейках
//A - массив с номиналами банкнот и монет в копейках, отсортированый по убыванию
//B - результат (количество купюр и монет каждого типа (т.е. результат)
s:=summa;
for i:=low(A) to high(A) do
begin
B[i]:=s div A[i];
s:= s mod A[i];
end;

SergP, спасибо вот теперь разобрался. Я тоже хотел через деление попробовать, но руки не долши)) Через разность кучу условий нужно и сложнее делается.

Как уже сказали, не для всех денежных систем работает "жадное" решение, при котором сначала крупные купюры выбираются.
В общем случае задача решается динамическим программированием (coin change problem)

> korneley © (03.11.09 21:26) [3]
> В приципе, уже всё сказано, но не могу удежаться: "манет" пишется через "о" А вот другое, через "а".

Шипните, плиз, что это за "другое", которое "пишется через а"? никак не могу придумать.

> [20] KSergey © (05.11.09 09:41)
> > korneley © (03.11.09 21:26) [3]
> > В приципе, уже всё сказано, но не могу удежаться: "манет"
> пишется через "о" А вот другое, через "а".
>
> Шипните, плиз, что это за "другое", которое "пишется через
> а"? никак не могу придумать.

Наверно "мани", хотя и другая буква на клавиатуре недалеко.

1 задачу препод приняла, а вот 1 нет.

Вобщем многочлен может иметь вид (2х^2 + 3x+2) * (3x^3 + 4x + 3).
Перемножить то я их перемножил, но вот подобные неудается привести, т.к неучитывается степень. Вот незнаю как степень учитывать.

> 1 задачу препод приняла, а вот 1 нет.

у форума принял ? Это радует, тут вообще народ неглупый

2 задачки. Размен денег и произведение многочленов Найти похожие ветки