找到硬币的所有组合的时候给予一定的美元价值 [英] Find all combinations of coins when given some dollar value

问题描述

我发现了一块，我是几个月前写面试preP code。

I found a piece of code that I was writing for interview prep few months ago.

据评论我，这是试图解决这个问题：

According to the comment I had, it was trying to solve this problem:

鉴于美分一些美元价值（例如：200 = 2元，1000 = 10元）， 发现硬币组成的美元价值的所有组合。 只有一分钱，镍，角钱，和四分之一。 （季= 25美分，一分钱= 10美分，镍= 5毛钱，一分钱= 1分）

Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars), find all the combinations of coins that make up the dollar value. There are only penny, nickel, dime, and quarter. (quarter = 25 cents, dime = 10 cents, nickel = 5 cents, penny = 1 cent)

例如，如果100被赋予，答案应该是...
4季度（S）0毛钱（S）0镍（S）0便士
3季度（S）1毛钱（S）0镍（S）15便士
等等。

For example, if 100 was given, the answer should be...
4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies
etc.

这可以在两个迭代和递归的方式来解决，我相信。我的递归解决方案是相当越野车，我不知道别人怎么会解决这个问题。这个问题的困难之处是使它尽可能高效。

This can be solved in both iterative and recursive ways, I believe. My recursive solution is quite buggy, and I was wondering how other people would solve this problem. The difficult part of this problem was making it as efficient as possible.

更新
使这个线程进入一个社区维基，因为很明显，我们已经聚集了许多不同的实现：）

UPDATE
Making this thread into a community wiki, because apparently, we have gathered many different implementations :)

推荐答案

我看着这个曾经很长一段时间以前，你可以阅读我的​​就可以少写了。这里的数学源。

I looked into this once a long time ago, and you can read my little write-up on it. Here’s the Mathematica source.

通过使用产生的功能，你可以得到一个封闭形式固定时间的解决问题的方法。格雷厄姆，克努特和Patashnik的具体数学的是这本书对于这一点，并且包含的​​问题相当广泛的讨论。基本上你定义一个多项式，其中* N *个系数是使得变化的 N 的美元的方法的数量。

By using generating functions, you can get a closed-form constant-time solution to the problem. Graham, Knuth, and Patashnik’s Concrete Mathematics is the book for this, and contains a fairly extensive discussion of the problem. Essentially you define a polynomial where the *n*th coefficient is the number of ways of making change for n dollars.

的书面记录显示如何使用数学（或任何其他方便的计算机代数系统）来计算10 ^ 10 ^ 6美元的回答在一两秒钟三行code第4-5页。

Pages 4-5 of the writeup show how you can use Mathematica (or any other convenient computer algebra system) to compute the answer for 10^10^6 dollars in a couple seconds in three lines of code.

（这是足够长的时间以前，这是一个为75Mhz的奔腾......几秒钟）

(And this was long enough ago that that’s a couple of seconds on a 75Mhz Pentium...)

这篇关于找到硬币的所有组合的时候给予一定的美元价值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！