K******g
发帖数: 1870 | 1 8.7 Given an infinite number of quarters (25 cents), dimes (10 cents),
nickels (5 cents) and pennies (1 cent), write code to calculate the number
of ways of representing n cents.
好像careercup上的答案不对，请大家有什么好的方法吗？ | d**********o
发帖数: 279 | | f*********5
发帖数: 576 | 3 //assume that a[]={1,5,10,25} already sorted
void GetCombination(int a[],int size,int target,vector& vec)
{
if(target==0) {cout<< <
if(target<=0) return;
for(int i=0,i
{
if(vec.size()>0)
{
if(a[i]
}
if (a[i]>target) break;
vec.push_back(a[i]);
GetCombination(a,size,target-a[i],vec);
vec.pop_back();
}
return;
}
【在 K******g 的大作中提到】
: 8.7 Given an infinite number of quarters (25 cents), dimes (10 cents),
: nickels (5 cents) and pennies (1 cent), write code to calculate the number
: of ways of representing n cents.
: 好像careercup上的答案不对，请大家有什么好的方法吗？
| K******g
发帖数: 1870 | 4 你这个好像会有这种情况，比如6cents
你的程序会输出5 和 1 还有 1和5 两种情况，但是其实这是一种
【在 f*********5 的大作中提到】
: //assume that a[]={1,5,10,25} already sorted
: void GetCombination(int a[],int size,int target,vector& vec)
: {
: if(target==0) {cout<< <: if(target<=0) return;
: for(int i=0,i: {
: if(vec.size()>0)
: {
: if(a[i]
| f*********5
发帖数: 576 | 5 did u try it on computer?
i have below code...
if(vec.size()>0)
{
if(a[i]
}
【在 K******g 的大作中提到】
: 你这个好像会有这种情况，比如6cents
: 你的程序会输出5 和 1 还有 1和5 两种情况，但是其实这是一种
| A*H
发帖数: 127 | 6 works great!
【在 f*********5 的大作中提到】
: //assume that a[]={1,5,10,25} already sorted
: void GetCombination(int a[],int size,int target,vector& vec)
: {
: if(target==0) {cout<< <: if(target<=0) return;
: for(int i=0,i: {
: if(vec.size()>0)
: {
: if(a[i]
| x***y
发帖数: 633 | 7 another way to use backtracking
//find all the commbination
typedef vector::size_type VecIndex;
void find_all_comb ( unsigned target, vector & vec, vector
>& eleCount, VecIndex vIndex){
//vec is assumed sorted
if(vIndex==vec.size())
return ;
unsigned mul = target/vec[vIndex];
eleCount[vIndex] = mul;
if(!(target%vec[vIndex])){
for(VecIndex vi=0; vi
for(VecIndex vc=0; vc
cout<< vec[vi] <<
【在 K******g 的大作中提到】
: 8.7 Given an infinite number of quarters (25 cents), dimes (10 cents),
: nickels (5 cents) and pennies (1 cent), write code to calculate the number
: of ways of representing n cents.
: 好像careercup上的答案不对，请大家有什么好的方法吗？
| I**A
发帖数: 2345 | 8 这个有问题么？
int findCoinsCombination(int sum, int[] coins){
if(sum==0)
return 1;
if(sum<0)
return 0;
if((coins.length<=0))
return 0;
int[] subcoins = new int[coins.length-1];
for(int i=0; i
subcoins[i] = coins[i];
return findCoinsCombination(sum, subcoins) + findCoinsCombination(
sum-coins[coins.length-1], coins);
}
【在 K******g 的大作中提到】
: 8.7 Given an infinite number of quarters (25 cents), dimes (10 cents),
: nickels (5 cents) and pennies (1 cent), write code to calculate the number
: of ways of representing n cents.
: 好像careercup上的答案不对，请大家有什么好的方法吗？
| i*****e
发帖数: 113 | 9 另类解法，缺点是把中间结果都存起来了
Prelude> let n = 100
Prelude> [(x,y,z,u)|x<-[1..(div n 25)], y<-[1..(div n 10)], z<-[1..(div n 5)
], u<-[1..n], 25*x+10*y+5*z+u==n]
[(1,1,1,60),(1,1,2,55),(1,1,3,50),(1,1,4,45),(1,1,5,40),(1,1,6,35),(1,1,7,30
),(1,1,8,25),(1,1,9,20),(1,1,10,15),(1,1,11,10),(1,1,12,5),(1,2,1,50),(1,2,2
,45),(1,2,3,40),(1,2,4,35),(1,2,5,30),(1,2,6,25),(1,2,7,20),(1,2,8,15),(1,2,
9,10),(1,2,10,5),(1,3,1,40),(1,3,2,35),(1,3,3,30),(1,3,4,25),(1,3,5,20),(1,3
,6,15),(1,3,7,10),(1,3,8,5),(1,4,1,30),(1 |
|
