euler项目45

Question

我还不是一个熟练的程序员，但我认为这是一个有趣的问题，我想我可以试一试。

三角形、五角数和六角形数由下列公式生成：

• 三角T_(n)=n(n+1)/2 1，3，6，10，15，.
• 五角P_(n)=n(3n−1)/2 1，5，12，22，35，.
• 六角形H_(n)=n(2n−1) 1，6，15，28，45，.

可以证明T_(285) = P_(165) = H_(143) = 40755。

查找下一个也是五角和六角的三角形数。

是任务描述。

我知道六角形数字是三角形数字的子集，这意味着你只需要找到一个Hn=Pn的数字。但我似乎无法让我的代码起作用。我只知道java语言，这就是为什么我很难在网络上找到解决方案的原因。不管怎样，希望有人能帮上忙。这是我的密码

public class NextNumber {

    public NextNumber() {
    next();
    }

    public void next() {


int n = 144;
int i = 165;
int p = i * (3 * i - 1) / 2;
int h = n * (2 * n - 1);
        while(p!=h) {
            n++;
           h = n * (2 * n - 1);

            if (h == p) {
                System.out.println("the next triangular number is" + h);
            } else {
                while (h > p) {
                    i++;
                    p = i * (3 * i - 1) / 2;
                }
                if (h == p) {
                    System.out.println("the next triangular number is" + h); break;
                    }
                 else if (p > h) {
                    System.out.println("bummer");
                }
            }

            }

    }
}

我意识到这可能是一个非常缓慢和无效的代码，但在这一点上我不太关心，我只关心找到下一个数字，即使它需要我的计算机数年。

Answer 1

您的代码看起来会很快产生正确的答案。如果只在循环结束后打印结果，则可以简化while循环：

while (p != h) {
    n++;
    h = n * (2 * n - 1);
    while (h > p) {
        i++;
        p = i * ((3 * i - 1) / 2);
    }
}
System.out.println("the next triangular number is" + h);

注意:您的内环看起来非常像我的C++解决方案的内环。在我的机器上，它在大约0.002秒内得到了想要的答案。

Answer 2

另一种采用2 ms的解决方案

public class P45 {

    public static void main(String[] args) {
        long H = 0;
        long i = 144;
        while(true) {
            H = i*((i<<1)-1);
            if ( isPentagonal(H) && isTriangle(H) ) {
                break;
            }
            i++;
        }
        System.out.println(H);
    }

    private static boolean isPentagonal(long x) {
        double n = (1 + Math.sqrt(24*x+1)) / 6;
        return n == (long)n;
    }

    private static boolean isTriangle(long x) {
        double n = (-1 + Math.sqrt((x<<3)+1)) / 2;
        return n == (long)n;
    }

}

改进的

您已经指定:六角形数字是三角形数字，但我补充了一个简短的证明:如果i = 2*k-1.

• In (这里是isTriangle )可以删除isTriangle，则k*(2*k-1)可以用以下形式写成i*(i+1)/2。

• 性能相似，因为该函数很少被调用(只有在该数字为pentagonal).

时才调用它。