30桁の最大の積

Question

私は1000文字の文字列を与えられた友達からプログラミングの質問を受けました。タスクは、30桁の連続した数字の最大の製品を見つけることです。

私のコードは正しいように見えますが、答えは本当に低くなるようですが、これはなぜですか？

この問題の関連コードを以下に示します。

static String s = "2389748943892"; //... This number is actually 1000 characters. 

    public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int largest = 0; 
    for(int i = 0; i < 970; i ) { 
     String cur = s.substring(i, i 30); 
     int cur_val = 0; 
     for(int x = 0; x < 30; x ) { 
     if(x == 0) { 
      System.out.println(Integer.parseInt(cur.substring(0, 1))); 
      cur_val = Integer.parseInt(cur.substring(x, 1)); 
     } else { 
      cur_val = cur_val * Integer.parseInt(cur.substring(x, x 1)); 
     } 

     } 
     if(cur_val > largest) { 
     largest = cur_val; 
     } 
     System.out.println("Largest: " largest); 
     // should be 8876473335152640000 but is 2013265920 

    } 
    } 

Answer 1

編集：Arrgh、私は「遅い」の代わりに「ロー」に読み... OK、パフォーマンスの問題を忘れて、私はあなたが話していたと思いました。

Howverは、ln（9^30）/ ln（2）を計算しても95を少し上回るので、96桁が必要です。 Math.BigIntegerを試してみてください！

---

これは、部分文字列が過剰に使用されたためです（結果的に、新しいStringオブジェクトが常に作成され、破棄されるためです）。あなたは単一の文字だけに興味があるので、s.charAt（n）の方がいいです。解析も簡単です：このようにして得られたcharから '0'を減算するだけです。だから、あなたが得る：

for(int i = 0; i < 970; ++i) 
{ 
    int cur_val = 0; 
    for(int x = i; x < i + 30; ++x) 
    { 
     cur_val *= s.charAt(x) - '0'; 
    } 
} 
/* rest as you had already */ 

は（OK、私は部分文字列を印刷して左）。

また、あなたが投稿コードで、いくつかの構文エラーは、（明らかに「+」が不足している、substring i, i 30）があるとこのは、あまりにも、あなたのコードであなたを起こった場合には、（カウンタ変数をインクリメントしませんでした無限ループで終わってしまっただろう - しかし、あなたは遅い結果を得ていないだろう、あなたは全く得られなかったであろう）。

外部ループに「0」がある場合、次の30回の反復の結果が0になり、これらをスキップして別のスピードアップが得られることが分かります。