显示等于X的所有硬币组合(四分硬币、一角硬币、五分硬币、便士硬币)

Question

编写一个程序，要求用户输入美元金额X。显示等于X的所有硬币组合（四分之一、一角硬币、五分硬币、一便士硬币）。。。。。。

package p1;
public class Combination {
    public static void findCombination(Double value){
        int totalCents = (int) (value*100);
        int aq = totalCents/25;
        int ad = totalCents/10;
        int an = totalCents/5;
        int ap = totalCents;
        for(int q=0; q<= aq; q++){
            for(int d=0; d<= ad; d++){
                for(int n=0;n<= an; n++){
                    for(int p=0;p<=ap; p++){
                        if(((q*25) + (d*10) + (n*5) + p ) == totalCents){
                            System.out.println("Q: "+q+" D: "+d+" N: "+n+" P: "+p );
                        }
                    }
                }
            }
        }

还有比这更优化的解决方案吗？我想不出一个了。

Answer 1

您可以编辑for循环的布尔值中使用的最大值。也许会把顺序颠倒过来。

类似于：

int p=0, n=0, d=0, q=0;
for(p=0; p <= (totalcents-q*25-d*10-n*5) ; p++){
    for(n=0; (n*5) <= (totalcents-q*25-d*10) ; n++){
        for(d=0; (d*10) <= (totalcents-q*25) ; d++){
            for(q=0; (q*25) <= totalcents ; q++){
                if(((q*25) + (d*10) + (n*5) + p ) == totalCents){
                    System.out.println("Q: "+q+" D: "+d+" N: "+n+" P: "+p );
                }
            }
        }
    }
}

我还没有测试它是否会加速你的代码，但在X的非常大的值下，随着最大值的减小，它可能会比遍历Q D N p的所有可能值更快。

同样，这种方式你不需要：

int aq = totalCents/25;
int ad = totalCents/10;
int an = totalCents/5;
int ap = totalCents;