Размен

Izh · Post by **Izh** » 21 Feb 2006 01:15

Сколькими способами можно разменять 1 доллар, при условии, что имеется любое необходимое количество монет номиналом в 1, 5, 10, 25, 50 центов? Очевидно, что монеты одного номинала не различимы между собой.

Dimchik · Post by **Dimchik** » 21 Feb 2006 01:38

Я не буду говорить, в какой книге эта задача идет под первым номером, может, кто-то ее захочет сам прямым подсчетом сделать, но это, имхо, перебор слегка:)

ArtemiZagagulin · Post by **ArtemiZagagulin** » 21 Feb 2006 01:39

Izh · Post by **Izh** » 21 Feb 2006 02:01

ArtemiZagagulin wrote:292

Хорошо, а общую формулу можете написать? Которая бы вычисляла за O(1)?

Dimchik · Post by **Dimchik** » 21 Feb 2006 02:03

Стоп, а вы что, имели ввиду это на компьютере считать?

Izh · Post by **Izh** » 21 Feb 2006 02:07

Dimchik wrote:Стоп, а вы что, имели ввиду это на компьютере считать?

Я не знаю, как результат был получен, поэтому и спрашиваю. К тому же мне действительно интересна конечная формула, поскольку мне самому было лень ее выводить. Кстати, что за учебник вы имели в виду?

Dimchik · Post by **Dimchik** » 21 Feb 2006 02:12

Полиа и Сеге, только это задачник, а не учебник.

Izh · Post by **Izh** » 21 Feb 2006 02:19

Dimchik wrote:Полиа и Сеге, только это задачник, а не учебник.

Это?:

http://www.amazon.com/gp/product/3540636404/sr=8-4/qid=1140484500/ref=pd_bbs_4/104-6562988-4848754?%5Fencoding=UTF8

Задачку я подсмотрел у Polya, но и из другой книжки: "How to solve it". Я ее решил, построив таблицу, поскольку при решение возникших рядов результатирующие формулы получались весьма громоздкие, и вывод я так до конца и не довел. Вот мне и стало любопытно посмотреть на конечную формулу

Dimchik · Post by **Dimchik** » 21 Feb 2006 02:28

Izh wrote:Это?:

http://www.amazon.com/gp/product/3540636404/sr=8-4/qid=1140484500/ref=pd_bbs_4/104-6562988-4848754?%5Fencoding=UTF8

ага

ArtemiZagagulin · Post by **ArtemiZagagulin** » 21 Feb 2006 14:21

Izh wrote:Задачку я подсмотрел у Polya, но и из другой книжки: "How to solve it". Я ее решил, построив таблицу, поскольку при решение возникших рядов результатирующие формулы получались весьма громоздкие, и вывод я так до конца и не довел. Вот мне и стало любопытно посмотреть на конечную формулу

Задача решается на пальцах! В смысле загибаете пальчики для каждой комбинации и получается 292. :mrgreen:

Когда палцы на руках и ногах заканчиваются занимаете их у соседа и т.д. Dimchik, а ну быстро, без вычеслений - сколько понадобиться тебе товарищей чтобы вычислить все 292 комбинации? (учитывая, что среднестатистически, каждый 10 человек рожден с 6 пальцами на одной руке, каждый 20-ый с шестью на обоих и та же статистика для пальцев ног) :mrgreen: