项目欧拉45

Question

项目欧拉45

3

我虽然不是一名熟练的程序员，但我认为这是一个有趣的问题，我想试着解决一下。

三角形数、五边形数和六边形数由以下公式生成:

三角形数 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");
                }
            }

            }

    }
}

我知道这可能是一段非常缓慢和低效的代码，但目前我并不太关心这个问题，我只关心找到下一个数字，即使这需要我的计算机花费数年时间。

- Peter

4个回答

1

另一种解决方案，耗时2毫秒：

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;
    }

}

改进：

您已经指定六边形数是三角形数，但我会添加一个简短的证明：k*(2*k-1)可以写成以下形式i*(i+1)/2，如果i=2*k-1。
在这种情况下，isTriangle可以被移除。
性能将是类似的，因为该函数很少被调用（仅当数字是五边形时才被调用）。

- ROMANIA_engineer

谢谢，这很有帮助。同样适用于Project Euler或Hackerrank的项目。 - Kangkan

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秒内产生了所需的答案。

- Blastfurnace

好的，谢谢大家。不知道为什么我的电脑不会显示结果 :) 但是还是很高兴听到它并没有完全失效。 - Peter

@Peter：我已经检查过了，你在计算 p 时可能存在整数溢出。请注意我在表达式 p = i * ((3 * i - 1) / 2) 中添加的额外括号。如果我去掉这些括号，我的代码会进入无限循环。 - Blastfurnace

如果 i 是偶数，那么 3*i-1 就是奇数，并且由于整数运算，((3 * i - 1) / 2) 会向下舍入0.5。你刚好在最终答案中得到了奇数，这只是你的运气而已。 - moinudin

@marcog：感谢您的纠正，我会去修复我的代码。 - Blastfurnace

嗯，这可能就是它不起作用的原因。但显然正如你所说，它在C++中可以工作，那么这只是Java有这个问题吗？ - Peter

0

数学

关键在于：

ti = hi*2 - 1

其中 ti 和 hi 分别是 T 和 H 的索引。

这意味着对于任何的 H(hi)，总会有一个对应的 T(ti)。
因此只需要找到 P(pi) = H(hi)，并且可以通过线性求解来实现。

代码（`go`）

解决方案：

package p45

// 参考：https://projecteuler.net/problem=45

func NextAllEqual(startHi, startPi int32) (v int64, hi, pi int32) {
    start := calculateH(startHi)
    h, p := nextH(start, startHi), nextP(start, startPi)
    hi, pi = startHi+1, startPi+1

    for h != p {
        if hi <= 0 || pi <= 0 { // 超出范围，
            return -1, -1, -1
        }

        if h < p {
            h = nextH(h, hi)
            hi++
        } else {
            p = nextP(p, pi)
            pi++
        }
    }

    return h, hi, pi
}

// h(i) = i * (2*i - 1)
func calculateH(i int32) int64 {
    return int64(i) * (int64(i)<<1 - 1)
}

// h(i+1) = h(i) + (4*i + 1)
func nextH(h int64, i int32) int64 {
    return h + (int64(i)<<2 + 1)
}

// p(i+1) = p(i) + (3*i + 1)
func nextP(p int64, i int32) int64 {
    return p + (3*int64(i) + 1)
}

// ti = 2*hi- 1
func TQiFromHi(hi int32) int32 {
    return hi<<1 - 1
}

测试用例：

package p45

import (
    "fmt"
    "testing"
)

const (
    zeroHi, zeroPi   = int32(1), int32(1)
    firstHi, firstPi = 143, 165
)

func TestNextAllEqual_first(t *testing.T) {
    // runOnce_NextAllEqual(t, zeroHi, zeroPi)
    runOnce_NextAllEqual(t, firstHi, firstPi)
}

func runOnce_NextAllEqual(t *testing.T, preHi, prePi int32) (v int64, hi, pi int32) {
    v, hi, pi = NextAllEqual(preHi, prePi)
    if v > 0 {
        ti := TQiFromHi(hi)
        fmt.Printf("v = %d, indices:\n\tti = %d, pi = %d, hi = %d\n\n", v, ti, pi, hi)

    } else {
        fmt.Println("完成，索引超出 int32 范围")
    }

    return v, hi, pi
}

// 查找所有索引在 int32 范围内的值，
func TestNextAllEqual_all_int32_indices(t *testing.T) {
    hi, pi := zeroHi, zeroPi
    var v int64
    for seq := 1; ; seq++ {
        fmt.Printf("[%d]\t", seq)
        v, hi, pi = runOnce_NextAllEqual(t, hi, pi)
        if v <= 0 {
            break
        }
    }
}

结果

(在一台旧笔记本电脑上运行)

对于问题44：
它花费了约2ms。

=== RUN   TestNextAllEqual_first
v = 1533776805, indices:
    ti = 55385, pi = 31977, hi = 27693

--- PASS: TestNextAllEqual_first (0.00s)

要在有符号32位范围内找到所有这样的索引。
它花费了约5.4s，有4个这样的值，不包括起始值(1,1,1)。

=== RUN   TestNextAllEqual_all_int32_indices
[1] v = 40755, indices:
    ti = 285, pi = 165, hi = 143

[2] v = 1533776805, indices:
    ti = 55385, pi = 31977, hi = 27693

[3] v = 57722156241751, indices:
    ti = 10744501, pi = 6203341, hi = 5372251

[4] v = 2172315626468283465, indices:
    ti = 2084377905, pi = 1203416145, hi = 1042188953

[5] Done, index out of range of int32
--- PASS: TestNextAllEqual_all_int32_indices (5.33s)

- Eric

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- moinudin · Accepted Answer

我们知道T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755。我们从 nt=286, np=166, 和 nh=144 开始，并计算出对应的三角形数、五边形数和六边形数。然后，将结果最小的那个数字的 n 值增加1。继续这样做，直到所有数字相等，你就得到了答案。

在我的电脑上，这个算法的Python实现运行时间为0.1秒。

你的代码有溢出问题。尽管答案适合32位的 int，但临时值 i * (3 * i - 1) 在达到答案之前就会溢出。使用64位的 long 值可以解决你的代码问题。

项目欧拉45

数学

代码（go）

结果

代码（`go`）