몇 달 전에 인터뷰 준비를 위해 작성한 코드를 발견했습니다.
내가 가진 의견에 따르면이 문제를 해결하려고했습니다.
센트 단위의 달러 가치 (예 : 200 = 2 달러, 1000 = 10 달러)가 주어지면 달러 가치를 구성하는 모든 동전 조합을 찾습니다. 페니 (1 ¢), 니켈 (5 ¢), 다임 (10 ¢) 및 쿼터 (25 ¢) 만 허용됩니다.
예를 들어 100이 주어진 경우 답은 다음과 같아야합니다.
4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies
etc.
나는 이것이 반복적이고 재귀적인 방법으로 해결 될 수 있다고 믿습니다. 내 재귀 솔루션은 매우 버그가 많으며 다른 사람들이이 문제를 어떻게 해결할지 궁금합니다. 이 문제의 어려운 부분은 가능한 한 효율적으로 만드는 것이 었습니다.
답변
나는 이것을 오래 전에 한 번 살펴 보았고 그것에 대한 나의 작은 글을 읽을 수 있습니다 . 다음은 Mathematica 소스 입니다.
생성 함수를 사용하여 문제에 대한 폐쇄 형 상수 시간 솔루션을 얻을 수 있습니다. Graham, Knuth 및 Patashnik의 Concrete Mathematics 는이를위한 책이며 문제에 대한 상당히 광범위한 논의를 포함합니다. 기본적으로 n 번째 계수가 n 달러에 대한 변경 방법의 수인 다항식을 정의합니다 .
이 글의 4 ~ 5 페이지는 Mathematica (또는 기타 편리한 컴퓨터 대수 시스템)를 사용하여 3 줄의 코드로 몇 초 만에 10 ^ 10 ^ 6 달러에 대한 답을 계산하는 방법을 보여줍니다.
(그리고 이것은 75Mhz 펜티엄에서 몇 초 정도 전에 충분히 오래되었습니다 …)
답변
참고 : 이것은 방법의 수만 표시합니다.
스칼라 함수 :
def countChange(money: Int, coins: List[Int]): Int =
if (money == 0) 1
else if (coins.isEmpty || money < 0) 0
else countChange(money - coins.head, coins) + countChange(money, coins.tail)
답변
재귀 솔루션을 선호합니다. 가장 작은 금액이 남은 통화 금액을 균등하게 나눌 수 있다면 교파 목록이 있습니다.
기본적으로 가장 큰 교단에서 가장 작은 교단으로 이동합니다.
재귀 적으로
- 채울 현재 총액과 가장 큰 교단 (1 개 이상 남음)이 있습니다. 교단이 1 개만 남아있는 경우 총액을 채우는 방법은 하나뿐입니다. k * cur denomination <= total이되도록 0에서 k 개의 현재 교파 사본을 사용할 수 있습니다.
- 0에서 k까지의 경우 수정 된 총액과 새로운 가장 큰 액면가로 함수를 호출하십시오.
- 0에서 k까지의 결과를 더합니다. 그것이 현재의 교단에서 총액을 채울 수있는 방법은 많습니다. 이 번호를 반환하십시오.
여기에 200 센트에 대한 귀하의 언급 된 문제의 파이썬 버전이 있습니다. 1463 가지 방법이 있습니다. 이 버전은 모든 조합과 최종 개수 합계를 인쇄합니다.
#!/usr/bin/python
# find the number of ways to reach a total with the given number of combinations
cents = 200
denominations = [25, 10, 5, 1]
names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}
def count_combs(left, i, comb, add):
if add: comb.append(add)
if left == 0 or (i+1) == len(denominations):
if (i+1) == len(denominations) and left > 0:
if left % denominations[i]:
return 0
comb.append( (left/denominations[i], demoninations[i]) )
i += 1
while i < len(denominations):
comb.append( (0, denominations[i]) )
i += 1
print(" ".join("%d %s" % (n,names[c]) for (n,c) in comb))
return 1
cur = denominations[i]
return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))
count_combs(cents, 0, [], None)
답변
스칼라 함수 :
def countChange(money: Int, coins: List[Int]): Int = {
def loop(money: Int, lcoins: List[Int], count: Int): Int = {
// if there are no more coins or if we run out of money ... return 0
if ( lcoins.isEmpty || money < 0) 0
else{
if (money == 0 ) count + 1
/* if the recursive subtraction leads to 0 money left - a prefect division hence return count +1 */
else
/* keep iterating ... sum over money and the rest of the coins and money - the first item and the full set of coins left*/
loop(money, lcoins.tail,count) + loop(money - lcoins.head,lcoins, count)
}
}
val x = loop(money, coins, 0)
Console println x
x
}
답변
여기에 모든 조합이 표시되도록 요구했던 문제를 해결하기위한 절대적으로 간단한 C ++ 코드가 있습니다.
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
if (argc != 2)
{
printf("usage: change amount-in-cents\n");
return 1;
}
int total = atoi(argv[1]);
printf("quarter\tdime\tnickle\tpenny\tto make %d\n", total);
int combos = 0;
for (int q = 0; q <= total / 25; q++)
{
int total_less_q = total - q * 25;
for (int d = 0; d <= total_less_q / 10; d++)
{
int total_less_q_d = total_less_q - d * 10;
for (int n = 0; n <= total_less_q_d / 5; n++)
{
int p = total_less_q_d - n * 5;
printf("%d\t%d\t%d\t%d\n", q, d, n, p);
combos++;
}
}
}
printf("%d combinations\n", combos);
return 0;
}
그러나 나는 단지 조합의 수를 계산하는 하위 문제에 대해 상당히 흥미 롭습니다. 나는 그것에 대한 폐쇄 형 방정식이 있다고 생각합니다.
답변
하위 문제는 일반적인 동적 프로그래밍 문제입니다.
/* Q: Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars),
find the number of 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) */
/* A:
Reference: http://andrew.neitsch.ca/publications/m496pres1.nb.pdf
f(n, k): number of ways of making change for n cents, using only the first
k+1 types of coins.
+- 0, n < 0 || k < 0
f(n, k) = |- 1, n == 0
+- f(n, k-1) + f(n-C[k], k), else
*/
#include <iostream>
#include <vector>
using namespace std;
int C[] = {1, 5, 10, 25};
// Recursive: very slow, O(2^n)
int f(int n, int k)
{
if (n < 0 || k < 0)
return 0;
if (n == 0)
return 1;
return f(n, k-1) + f(n-C[k], k);
}
// Non-recursive: fast, but still O(nk)
int f_NonRec(int n, int k)
{
vector<vector<int> > table(n+1, vector<int>(k+1, 1));
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= k; ++j)
{
if (i < 0 || j < 0) // Impossible, for illustration purpose
{
table[i][j] = 0;
}
else if (i == 0 || j == 0) // Very Important
{
table[i][j] = 1;
}
else
{
// The recursion. Be careful with the vector boundary
table[i][j] = table[i][j-1] +
(i < C[j] ? 0 : table[i-C[j]][j]);
}
}
}
return table[n][k];
}
int main()
{
cout << f(100, 3) << ", " << f_NonRec(100, 3) << endl;
cout << f(200, 3) << ", " << f_NonRec(200, 3) << endl;
cout << f(1000, 3) << ", " << f_NonRec(1000, 3) << endl;
return 0;
}
답변
코드는이 문제를 해결하기 위해 Java를 사용하고 있으며 또한 작동합니다 …이 방법은 루프가 너무 많기 때문에 좋은 생각이 아닐 수 있지만 실제로는 간단한 방법입니다.
public class RepresentCents {
public static int sum(int n) {
int count = 0;
for (int i = 0; i <= n / 25; i++) {
for (int j = 0; j <= n / 10; j++) {
for (int k = 0; k <= n / 5; k++) {
for (int l = 0; l <= n; l++) {
int v = i * 25 + j * 10 + k * 5 + l;
if (v == n) {
count++;
} else if (v > n) {
break;
}
}
}
}
}
return count;
}
public static void main(String[] args) {
System.out.println(sum(100));
}
}
