java - Project Euler 9 Solution没有给出正确的结果

标签 java algorithm combinatorics

问题是:
毕达哥拉斯三元组是三个自然数的集合,a为此,
a^2+b^2=c^2例如,3^2+4^2=9+16=25=5^2。
恰好有一个毕达哥拉斯三重态,其中a+b+c=
1000英镑找到产品ABC。
因此,使用函数tripletP()我认为程序会为数字1000生成3个求和器的所有可能组合。
在这段代码中,函数istriplet(a,b,c)永远不会返回true,最后int乘积的值为0。
我似乎找不到我逻辑上的缺陷,任何帮助都将不胜感激。
下面是我的Java类,其中包含我认为可以解决问题9的代码:

public class ProblemNine {


    public static void main(String[] args) {

        ProblemNine f = new ProblemNine();
        System.out.println(f.tripletP());

    }

    boolean isTriplet(int a, int b, int c){

        if((a*a)+(b*b)==(c*c)){
            return true;
        } else return false;    
    }

    int tripletP(){
        int a=1,b=2,c=997;
        int product = 0;

        //outerloop generates all possible combinations of 3 summators for the number 1000, if b>c>a is true
        outerloop:
        for(int i = 997; i>499; i--){
            c = i;
            b = 999-i;
            a = 1;

            while(b>(a+2) && (a+b) == (1000-i) && a!=b && c>b){
                b--;
                a++;
                // supposedly checks if a,b,c are a triplet.
                if (isTriplet(a,b,c)){
                    product=a*b*c;
                    break outerloop;
                }
            }   

            if(c>997 || b>499 || a>249){
                break outerloop;
            }
        }

        return product;
    }

}

最佳答案

for(int i = 997; i>499; i--){

你停得太早了如果a<b<ca+b+c == 1000,c的最小可能值不是500,而是335。
for(int i = 997; i>335; i--){

有了这个新的下限,b偶尔会大于c,这会过早地触发一些条件。不过,你可以删除它们,仍然可以得到正确的答案。
    for(int i = 997; i>335; i--){
        c = i;
        b = 999-i;
        a = 1;

        while(b>(a+2)){
            b--;
            a++;
            if (isTriplet(a,b,c)){
                product=a*b*c;
                break outerloop;
            }
        }
    }

关于java - Project Euler 9 Solution没有给出正确的结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30330847/

相关文章:

java - 循环算法Java实现

算法 - 从必须按顺序选择的项目生成所有组合

java - 在应用程序运行之前保持 mysql 连接打开

java - 如何在 Spring + Thymeleaf 上添加弹出窗口

algorithm - 哈希表索引如何工作?

python - 如何加快我的 Python 扑克手与手牌赢率计算器

python - 生成所有唯一对排列

java - 使用Java和JSP按行迭代表时丢失数据

java - JUnit测试自定义对象类型的getter方法

algorithm - 什么是最好的图像缩小算法(质量方面)?