Project Euler＃4最大のPalindromeプロダクト

Question

2つの3桁の数字を掛け合わせて生成される最大の回文番号を探しています。回文番号は、両側から同じものを読み取る番号です（例：12345654321または単に9009）。 次のコードは正しくコンパイルされますが、出力が906609のときに出力が749947になるため、論理エラーが発生していることがはっきりしています。

boolean valid = false; 
for (int i = 999*999; i > 100*100; i--) { 
    if (i/100000 == i % 10 && 
     i/10000 % 10 == i/10 % 10 && 
     i/1000 % 10 == i/100 % 10) { 
     int buffer = i; 
     int total = 1; 
     for (int k = 2; k < buffer; k++) { 
      if (buffer % k == 0) { 
      buffer /= k; 
      total *=k; 
      } 
     } 
     if (buffer >= 100 && buffer < 1000 && total >=100 && total < 1000) { 
      System.out.println(i); 
      System.out.println(total); 
      System.out.println(buffer); 
      break; 
     } 
    } 
    } 
    } 
} 

Answer 1

906609 = 3 * 11 * 83 * 331 = 2739 * 331 = 913 * 993 = ... 

あなたのコードは、あなたのif文が失敗したbuffer = 331, total = 2739に解決します。代わりに10000 998001からすべての数字をチェックし、掛けた数になる3桁の値は、3桁の数字の重forループを使用しても最大の製品を見つける探してみるの：提案

パリンドローム。

Answer 2

このアプローチは従うのが簡単で、機能します。

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 

public class Palindrome 
{ 
    private static List<Integer> palindromes = new ArrayList<Integer>(); 

    public static void main(String[] args) 
    { 
    for (int i = 999; i > 99; i--) 
    { 
     for (int j = 999; j > 99; j--) 
     { 
     if (isPalendrome(i * j)) 
     { 
      palindromes.add(i * j); 
     } 
     } 
    } 
    if (!palindromes.isEmpty()) 
    { 
     Collections.sort(palindromes); 
     System.out.println(palindromes.get(palindromes.size() - 1)); 
    } 
    } 

    private static boolean isPalendrome(int number) 
    { 
    char[] word = String.valueOf(number).toCharArray(); 
    int i1 = 0; 
    int i2 = word.length - 1; 
    while (i2 > i1) 
    { 
     if (word[i1] != word[i2]) 
     { 
     return false; 
     } 
     ++i1; 
     --i2; 
    } 
    return true; 
    } 
} 

Answer 3

まあ、あなたがコードを書いた説明しやすくなっているはずですが、我々はその中の推論に戻って行かなければなりません。外側のループは、回文的なアプローチをとり、回文パターンのすべての数値をチェックしてから、内側のテストを適用します。

その内部テストは、物事がうまくいかないところです。それは賢明にしようとしているが、論理エラーを引き起こしている。私がしようとしているのは、見つかった番号をbufferとtotalに分解し、2桁の3桁の数字にすることです。ただし、後で3桁の数字しかチェックしません。このルールには関係なく計算されます。

kは、bufferからtotalに転送する潜在的要因として使用されます。各数値は1回チェックされ、正方形またはそれ以上の力率を持つ数値は除外されます。さらに重要なことに、この場合は、totalがbufferよりも小さくなくなるまで、低から高にチェックされます。では906609はどうなりますか？

(%i1) factor(906609); 
(%o1) 3 11 83 331 

アルゴリズムは、3 * 11 * 83 * 331で解決されますが、3 * 11 * 83 = 2739は誤った桁数に設定されます。求められる答えには、3 * 331 * 11 * 83という異なる因子の分割が使用されます。因数分解アプローチは実行可能ですが、3桁の積を生成する要因のグループ化を確認する必要があります。