プロジェクトオイラー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言語だけを知っているので、ネット上のソリューションを見つけるのが難しいです。とにかく誰かが助けることを願う。ここで私はそれはおそらく非常に遅く、ineffecientコードだが、それは私が唯一、それは私のコンピュータの数年かかる場合でも、次の番号を見つけることを気にし、この時点ではあまり私には関係しません実現私のコード

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

我々はT = P = Hが = 40755.我々はnt=286、np=166とnh=144で開始し、それぞれの三角形、五角形、六角形番号を動作することを知っています。どちらの数字が最も小さいかは、nという値にバンプします。すべての数字が等しく、あなたの答えが出るまでこれを続けます。

このアルゴリズムのPython実装は、コンピュータ上で0.1秒で実行されます。

コードの問題はオーバーフローです。答えは32ビットのintに適合しますが、回答に達する前に一時的な値i * (3 * i - 1)がオーバーフローします。 64ビットのlongの値を使用すると、コードが修正されます。

Answer 2

あなたのコードは、正解をかなり早く生成するようです。

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++ソリューションの内部ループのように見えるループが終了した後、あなただけの結果を印刷する場合はwhileループを簡略化することができます。それは私のマシンで約0.002秒で望ましい答えを出しました。

Answer 3

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 = 2*k-1の場合は、次の形式のi*(i+1)/2で記入してください。
• この場合、isTriangleは削除できます。
• この関数はめったに呼ばれなかった（数字が五角形の場合にのみ呼び出されたため）、パフォーマンスは同様です。