找到由兩個3位數字的產品製成的最大回文

Question

package testing.project; 

public class PalindromeThreeDigits { 

    public static void main(String[] args) { 
     int value = 0; 
     for(int i = 100;i <=999;i++) 
     { 
      for(int j = i;j <=999;j++) 
      { 
       int value1 = i * j; 
       StringBuilder sb1 = new StringBuilder(""+value1); 
       String sb2 = ""+value1; 
       sb1.reverse(); 
       if(sb2.equals(sb1.toString()) && value<value1) { 
        value = value1; 

       } 

      } 
     } 

     System.out.println(value); 
    } 
} 

這是我在Java中編寫的代碼...除此之外是否有任何有效的方法..我們可以優化此代碼嗎？ ？

Answer 1

我們假設下面的最大的此類迴文將有六位數字鼠她比5，因爲143 * 777 = 111111是迴文。

如其他地方所指出的，一個6位數的10迴文abccba是11的倍數。這是真的，因爲* 100001 + b * 010010 + c * 001100等於11 * a * 9091 + 11 * b * 910 + 11 * c * 100。因此，在我們的內部循環中，如果m不是11的倍數，我們可以將n減少11步。

我們正試圖找到百萬以下的最大回文數，它是兩個3位數字的乘積。要找到一個大的結果，我們首先嚐試大的除數：

• 我們從999向下邁1，
• 從999減1（如果11除m或9％的時間）或從990減11（如果11不除m，或91％的時間），則運行n。

我們跟蹤變量q中迄今爲止發現的最大回文。假設q = r·s，其中r < = s。我們通常有< = < = s。我們需要m·n> q或n> = q/m。當發現更大的迴文，n的範圍受到更多限制，原因有兩個：q變大，m變小。

附加程序的內部循環只執行506次，而使用天真程序的時間是〜810000次。

#include <stdlib.h> 
#include <stdio.h> 
int main(void) { 
    enum { A=100000, B=10000, C=1000, c=100, b=10, a=1, T=10 }; 
    int m, n, p, q=111111, r=143, s=777; 
    int nDel, nLo, nHi, inner=0, n11=(999/11)*11; 

    for (m=999; m>99; --m) { 
    nHi = n11; nDel = 11; 
    if (m%11==0) { 
     nHi = 999; nDel = 1; 
    } 
    nLo = q/m-1; 
    if (nLo < m) nLo = m-1; 

    for (n=nHi; n>nLo; n -= nDel) { 
     ++inner; 
     // Check if p = product is a palindrome 
     p = m * n; 
     if (p%T==p/A && (p/B)%T==(p/b)%T && (p/C)%T==(p/c)%T) { 
     q=p; r=m; s=n; 
     printf ("%d at %d * %d\n", q, r, s); 
     break;  // We're done with this value of m 
     } 
    } 
    } 
    printf ("Final result: %d at %d * %d inner=%d\n", q, r, s, inner); 
    return 0; 
} 

請注意，該程序是在C中，但相同的技術將在Java中工作。

Answer 2

我會怎麼做：

1. 開始在999，向後工作我的方式，以998，997，等
2. 創建我目前的數字迴文。
3. 確定此數字的素數因子分解（如果您有預先生成的素數列表，則並非全部昂貴）
4. 通過此素數因子分解列表來確定是否可以使用這些因子的組合來製作2 3位數

一些代碼：。

int[] primes = new int[] {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71, 
73,79,83,89,97,101,103,107,109,113,,127,131,137,139,149,151,157,163,167,173, 
179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281, 
283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409, 
419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541, 
547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659, 
661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809, 
811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941, 
947,953,967,971,977,983,991,997}; 

for(int i = 999; i >= 100; i--) { 

    String palstr = String.valueOf(i) + (new StringBuilder().append(i).reverse()); 
    int pal = Integer.parseInt(pal); 
    int[] factors = new int[20]; // cannot have more than 20 factors 
    int remainder = pal; 
    int facpos = 0; 
    primeloop: 
    for(int p = 0; p < primes.length; i++) { 
     while(remainder % p == 0) { 
      factors[facpos++] = p; 
      remainder /= p; 
      if(remainder < p) break primeloop; 
     } 
    } 
    // now to do the combinations here 
} 

Answer 3

您可以使用一個事實，即11迴文以減少搜索空間的倍數，我們可以得到這樣的，因爲我們可以假設迴文將是6位數字和> = 111111.

例如（從歐拉計劃;））

P= xyzzyx = 100000x + 10000y + 1000z + 100z + 10y +x 
P=100001x+10010y+1100z 
P=11(9091x+910y+100z) 

檢查是否爲i mod 11 = 0，則j循環可通過11中減去（990開始），因爲這兩個中的至少一個必須是整除11.

！

Answer 4

你可以嘗試它打印

999 * 979 * 989 = 967262769 
largest palindrome= 967262769 took 0.015 

---

public static void main(String... args) throws IOException, ParseException { 
    long start = System.nanoTime(); 
    int largestPalindrome = 0; 
    for (int i = 999; i > 100; i--) { 
    LOOP: 
    for (int j = i; j > 100; j--) { 
     for (int k = j; k > 100; k++) { 
     int n = i * j * k; 
     if (n < largestPalindrome) continue LOOP; 
     if (isPalindrome(n)) { 
      System.out.println(i + " * " + j + " * " + k + " = " + n); 
      largestPalindrome = n; 
     } 
     } 
    } 
    } 
    long time = System.nanoTime() - start; 
    System.out.printf("largest palindrome= %d took %.3f seconds%n", largestPalindrome, time/1e9); 
} 

private static boolean isPalindrome(int n) { 
    if (n >= 100 * 1000 * 1000) { 
    // 9 digits 
    return n % 10 == n/(100 * 1000 * 1000) 
     && (n/10 % 10) == (n/(10 * 1000 * 1000) % 10) 
     && (n/100 % 10) == (n/(1000 * 1000) % 10) 
     && (n/1000 % 10) == (n/(100 * 1000) % 10); 
    } else if (n >= 10 * 1000 * 1000) { 
    // 8 digits 
    return n % 10 == n/(10 * 1000 * 1000) 
     && (n/10 % 10) == (n/(1000 * 1000) % 10) 
     && (n/100 % 10) == (n/(100 * 1000) % 10) 
     && (n/1000 % 10) == (n/(10 * 1000) % 10); 
    } else if (n >= 1000 * 1000) { 
    // 7 digits 
    return n % 10 == n/(1000 * 1000) 
     && (n/10 % 10) == (n/(100 * 1000) % 10) 
     && (n/100 % 10) == (n/(10 * 1000) % 10); 
    } else throw new AssertionError(); 
} 

Answer 5

我們可以將任務翻譯成數學語言。

對於短的啓動，我們使用字符數字：

abc * xyz = n 

abc is a 3-digit number, and we deconstruct it as 100*a+10*b+c 
xyz is a 3-digit number, and we deconstruct it as 100*x+10*y+z 

現在，我們有兩個數學表達式，並且可以定義A，B，C，X，Y，Z如€的{0 .. 9}。
從{1..9}而不是{0..9}中定義a和x是更精確的元素，因爲097並不是真正的3位數字，是嗎？

好的。

如果我們想要產生一個大數字，我們應該嘗試達到9 ......-數字，並且由於它是迴文的，所以它必須是模式9 .... 9。如果最後一位數字是9，然後從

(100*a + 10*b + c) * (100*x + 10*y + z) 

遵循Z * c具有導致一個數字，在數字9結尾 - 所有其他計算不感染的最後一位。因爲（1 * 9 = 9,9 * 1 = 9,3 * 3 = 9,7 * 7 = 49），所以c和z必須來自（1,3,7,9）。現在

一些代碼（斯卡拉）：

val n = (0 to 9) 
val m = n.tail // 1 to 9 
val niners = Seq (1, 3, 7, 9) 
val highs = for (a <- m; 
    b <- n; 
    c <- niners; 
    x <- m; 
    y <- n; 
    z <- niners) yield ((100*a + 10*b + c) * (100*x + 10*y + z)) 

那我就按大小排序，並與最大的一個開始，測試它們是迴文。所以我會忽略測試回覆的小數字，因爲這可能並不便宜。爲了美學上的原因，我不會採用（toString.reverse == toString）方法，而是遞歸分割和模解決方案，但是在今天的機器上，它沒有太大區別，是嗎？

// Make a list of digits from a number: 
def digitize (z: Int, nums : List[Int] = Nil) : List[Int] = 
    if (z == 0) nums else digitize (z/10, z%10 :: nums) 

/* for 342243, test 3...==...3 and then 4224. 
    Fails early for 123329 */ 
def palindromic (nums : List[Int]) : Boolean = nums match { 
    case Nil   => true 
    case x :: Nil  => true 
    case x :: y :: Nil => x == y 
    case x :: xs  => x == xs.last && palindromic (xs.init) } 

def palindrom (z: Int) = palindromic (digitize (z)) 

對於嚴重的性能考慮，我會根據toString/reverse/equals方法進行測試。也許情況更糟。它會提前失敗，但是分割和模不知道是最快的操作，我用它們來從Int中創建一個List。它適用於BigInt或Long，只需很少的重新聲明，並且與Java很好地協作;可以用Java實現，但在那裏看起來不同。

好了，把東西放在一起：

highs.filter (_ > 900000) .sortWith (_ > _) find (palindrom) 
res45: Option[Int] = Some(906609) 

其中有835號左> 900000，並返回相當快，但我想更暴力破解是不是要慢得多。

也許有更聰明的方法來構建最高的迴文，而不是搜索它。

的一個問題是：我不知道之前，有一個解決辦法> 900000.

---

一個非常不同的方法是，以生產大回文，並解構他們的因素。

Answer 6

i did this my way , but m not sure if this is the most efficient way of doing this . 

package problems; 
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 


    public class P_4 { 

/** 
* @param args 
* @throws IOException 
*/ 
static int[] arry = new int[6]; 
static int[] arry2 = new int[6]; 

public static boolean chk() 
{ 
    for(int a=0;a<arry.length;a++) 
     if(arry[a]!=arry2[a]) 
      return false; 

return true; 

} 

public static void main(String[] args) throws IOException { 
    // TODO Auto-generated method stub 

    InputStreamReader ir = new InputStreamReader(System.in); 
    BufferedReader br = new BufferedReader(ir); 
    int temp,z,i; 

for(int x=999;x>100;x--) 
    for(int y=999;y>100;y--) 
     { 
     i=0; 
      z=x*y; 
      while(z>0) 
       { 
        temp=z%10; 
        z=z/10; 
        arry[i]=temp; 
        i++; 
       } 

      for(int k = arry.length;k>0;k--) 
         arry2[arry.length- k]=arry[k-1]; 

    if(chk()) 
    { 
     System.out.print("pelindrome = "); 

for(int l=0;l<arry2.length;l++) 
System.out.print(arry2[l]); 
System.out.println(x); 
System.out.println(y); 
} 

    } 
} 
} 

Answer 7

package ex; 

    public class Main { 

     public static void main(String[] args) { 
      int i = 0, j = 0, k = 0, l = 0, m = 0, n = 0, flag = 0; 

      for (i = 999; i >= 100; i--) { 
       for (j = i; j >= 100; j--) { 
        k = i * j; 

        // System.out.println(k); 
        m = 0; 
        n = k; 

        while (n > 0) { 
         l = n % 10; 
         m = m * 10 + l; 
         n = n/10; 
        } 

        if (m == k) { 
         System.out.println("pal " + k + " of " + i + " and" + j); 
         flag = 1; 
         break; 
        } 
       } 

       if (flag == 1) { 
        // System.out.println(k); 
        break; 
       } 
      } 
     } 
    } 

Answer 8

這是C，一點點長碼，但能夠完成任務。:)

#include <stdio.h> 
#include <stdlib.h> 
/* 
A palindromic number reads the same both ways. The largest palindrome made from the         product of two 
2-digit numbers is 9009 = 91 99. 

Find the largest palindrome made from the product of two 3-digit numbers.*/ 

int palndr(int b) 
{ 
int *x,*y,i=0,j=0,br=0; 
int n; 
n=b; 
while(b!=0) 
{ 
    br++; 
    b/=10; 
} 
x=(int *)malloc(br*sizeof(int)); 
y=(int *)malloc(br*sizeof(int)); 

int br1=br; 

while(n!=0) 
{ 
    x[i++]=y[--br]=n%10; 
    n/=10; 
} 

int ind = 1; 
for(i=0;i<br1;i++) 
if(x[i]!=y[i]) 
ind=0; 
free(x); 
free(y); 
return ind; 
} 

int main() 
{ 
    int i,cek,cekmax=1; 
    int j; 
    for(i=100;i<=999;i++) 
    { 
     for(j=i;j<=999;j++) 
     { 
     cek=i*j; 

     if(palndr(cek)) 
     { 
      if(pp>cekmax) 
      cekmax=cek; 
     } 
     } 
    } 

    printf("The largest palindrome is: %d\n\a",cekmax); 
} 

Answer 9

實際上，你可以使用Python做到這一點，很容易只看看：

actualProduct = 0 
highestPalindrome = 0 

# Setting the numbers. In case it's two digit 10 and 99, in case is three digit 100 and 999, etc. 
num1 = 100 
num2 = 999 

def isPalindrome(number): 
     number = str(number) 
     reversed = number[::-1] 
     if number==reversed: 
       return True 
     else: 
       return False 

a = 0 
b = 0 

for i in range(num1,num2+1): 
     for j in range(num1,num2+1): 
       actualProduct = i * j 
       if (isPalindrome(actualProduct) and (highestPalindrome < actualProduct)): 
         highestPalindrome = actualProduct 
         a = i 
         b = j 


print "Largest palindrome made from the product of two %d-digit numbers is [ %d ] made of %d * %d" % (len(str(num1)), highestPalindrome, a, b) 

Answer 10

public class Pin 
{ 
    public static boolean isPalin(int num) 
    { 
     char[] val = (""+num).toCharArray(); 
     for(int i=0;i<val.length;i++) 
     { 
      if(val[i] != val[val.length - i - 1]) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 

    public static void main(String[] args) 
    { 
     for(int i=999;i>100;i--) 
      for(int j=999;j>100;j--) 
      { 
       int mul = j*i; 
       if(isPalin(mul)) 
       { 
        System.out.printf("%d * %d = %d",i,j,mul); 
        return; 
       } 
      } 
    } 
} 

Answer 11

因爲我們沒有同時循環兩個迭代器（num1和num2），所以我們找到的第一個迴文數將是最大的。我們不需要測試我們發現的迴文是否最大。這大大縮短了計算時間。

package testing.project; 
public class PalindromeThreeDigits { 
    public static void main(String[] args) { 

    int limit = 99; 
    int max = 999; 
    int num1 = max, num2, prod; 

    while(num1 > limit) 
    { 
     num2 = num1; 
     while(num2 > limit) 
     { 
      total = num1 * num2; 
      StringBuilder sb1 = new StringBuilder(""+prod); 
      String sb2 = ""+prod; 
      sb1.reverse(); 
      if(sb2.equals(sb1.toString())) { //optimized here 
       //print and exit 
      } 
      num2--; 
     } 
     num1--; 
    } 

}//end of main 
}//end of class PalindromeThreeDigits 

Answer 12

我試圖通過託賓的喜悅和vickyhacks且二者的解決方案產生的結果580085這是錯誤的，這裏是我的解決方案，雖然很笨拙：

import java.util.*; 
class ProjEu4 
{ 

public static void main(String [] args) throws Exception 
{ 
    int n=997; 
    ArrayList<Integer> al=new ArrayList<Integer>(); 
    outerloop: 
    while(n>100){ 
    int k=reverse(n); 
    int fin=n*1000+k; 
      al=findfactors(fin); 
    if(al.size()>=2) 
     { 
      for(int i=0;i<al.size();i++) 
      { 
       if(al.contains(fin/al.get(i))){ 
        System.out.println(fin+" factors are:"+al.get(i)+","+fin/al.get(i)); 
        break outerloop;} 
      } 

     } 
     n--; 
    } 
} 
private static ArrayList<Integer> findfactors(int fin) 
{ 
    ArrayList<Integer> al=new ArrayList<Integer>(); 
    for(int i=100;i<=999;i++) 
    { 
     if(fin%i==0) 
      al.add(i); 
    } 
    return al; 
} 
private static int reverse(int number) 
{ 
    int reverse = 0; 
    while(number != 0){ 
     reverse = (reverse*10)+(number%10); 
     number = number/10; 
    } 
    return reverse; 
} 
} 

Answer 13

極有可能是一個複製的的另一種解決方案，但由於python化代碼，它看起來很簡單，即使它有點蠻力。

def largest_palindrome(): 
    largest_palindrome = 0; 
    for i in reversed(range(1,1000,1)): 
     for j in reversed(range(1, i+1, 1)): 
      num = i*j 
      if check_palindrome(str(num)) and num > largest_palindrome : 
       largest_palindrome = num 
    print "largest palindrome ", largest_palindrome 

def check_palindrome(term): 
    rev_term = term[::-1] 
    return rev_term == term 

Answer 14

什麼：在Python

>>> for i in range((999*999),(100*100), -1): 
...  if str(i) == str(i)[::-1]: 
...   print i 
...   break 
... 
997799 
>>> 

Answer 15

我相信這是一個簡單的方法：檢查迴文從兩個三位數的最大的產品降，兩度三位數的因素，選擇第一回文。

這裏是Ruby代碼：

require './palindrome_range' 
require './prime' 

def get_3_digit_factors(n) 
    prime_factors = Prime.factors(n) 

    rf = [prime_factors.pop] 
    rf << prime_factors.shift while rf.inject(:*) < 100 || prime_factors.inject(:*) > 999 

    lf = prime_factors.inject(:*) 
    rf = rf.inject(:*) 

    lf < 100 || lf > 999 || rf < 100 || rf > 999 ? [] : [lf, rf] 
end 

def has_3_digit_factors(n) 
    return !get_3_digit_factors(n).empty? 
end 

pr = PalindromeRange.new(0, 999 * 999) 
n = pr.downto.find {|n| has_3_digit_factors(n)} 
puts "Found #{n} - Factors #{get_3_digit_factors(n).inspect}, #{Prime.factors(n).inspect}" 

prime.rb：

class Prime 

    class<<self 

    # Collect all prime factors 
    # -- Primes greater than 3 follow the form of (6n +/- 1) 
    # Being of the form 6n +/- 1 does not mean it is prime, but all primes have that form 
    # See http://primes.utm.edu/notes/faq/six.html 
    # -- The algorithm works because, while it will attempt non-prime values (e.g., (6 *4) + 1 == 25), 
    # they will fail since the earlier repeated division (e.g., by 5) means the non-prime will fail. 
    # Put another way, after repeatedly dividing by a known prime, the remainder is itself a prime 
    # factor or a multiple of a prime factor not yet tried (e.g., greater than 5). 
    def factors(n) 
     square_root = Math.sqrt(n).ceil 
     factors = [] 

     while n % 2 == 0 
     factors << 2 
     n /= 2 
     end 

     while n % 3 == 0 
     factors << 3 
     n /= 3 
     end 

     i = 6 
     while i < square_root 
     [(i - 1), (i + 1)].each do |f| 
      while n % f == 0 
      factors << f 
      n /= f 
      end 
     end 

     i += 6 
     end 

     factors << n unless n == 1 
     factors 
    end 

    end 

end 

palindrome_range.rb：

class PalindromeRange 

    FIXNUM_MAX = (2**(0.size * 8 -2) -1) 

    def initialize(min = 0, max = FIXNUM_MAX) 
    @min = min 
    @max = max 
    end 

    def downto 
    return enum_for(:downto) unless block_given? 

    n = @max 
    while n >= @min 
     yield n if is_palindrome(n) 
     n -= 1 
    end 
    nil 
    end 

    def each 
    return upto 
    end 

    def upto 
    return enum_for(:downto) unless block_given? 

    n = @min 
    while n <= @max 
     yield n if is_palindrome(n) 
     n += 1 
    end 
    nil 
    end 

    private 

    def is_palindrome(n) 
    s = n.to_s 
    i = 0 
    j = s.length - 1 
    while i <= j 
     break if s[i] != s[j] 
     i += 1 
     j -= 1 
    end 
    i > j 
    end 

end 

Answer 16

一個稍微不同的方法，可以很容易地計算出最大的迴文號碼由最多兩個6位數字的產品組成。

第一部分是創建一個迴文數字生成器。所以不需要檢查一個數字是否是迴文，第二部分是一個簡單的循環。

#include <memory> 
#include <iostream> 
#include <cmath> 

using namespace std; 
template <int N> 
class PalindromeGenerator { 
    unique_ptr <int []> m_data; 
    bool m_hasnext; 
public : 
    PalindromeGenerator():m_data(new int[N]) 
    { 
     for(auto i=0;i<N;i++) 
     m_data[i]=9; 
     m_hasnext=true; 
    } 
    bool hasNext() const {return m_hasnext;} 

long long int getnext() 
{ 
    long long int v=0; 
    long long int b=1; 
    for(int i=0;i<N;i++){ 
     v+=m_data[i]*b; 
     b*=10; 
    } 
    for(int i=N-1;i>=0;i--){ 
     v+=m_data[i]*b; 
     b*=10; 
    } 

    auto i=N-1; 
    while (i>=0) 
    { 
     if(m_data[i]>=1) { 
      m_data[i]--; 
      return v; 
     } 
     else 
     { 
      m_data[i]=9; 
      i--; 
     } 
    } 

    m_hasnext=false; 
    return v; 
} 


}; 

template<int N> 
void findmaxPalindrome() 
{ 
    PalindromeGenerator<N> gen; 
    decltype(gen.getnext()) minv=static_cast<decltype(gen.getnext())> (pow(10,N-1)); 
    decltype(gen.getnext()) maxv=static_cast<decltype(gen.getnext())> (pow(10,N)-1); 
    decltype(gen.getnext()) start=11*(maxv/11); 
    while(gen.hasNext()) 
    { 
     auto v=gen.getnext(); 
     for (decltype(gen.getnext()) i=start;i>minv;i-=11) 
     { 
      if (v%i==0) 
      { 
       auto r=v/i; 
       if (r>minv && r<maxv){ 
        cout<<"done:"<<v<<" "<<i<< "," <<r <<endl; 
        return ; 
       } 
      } 

     } 
    } 

return ; 
} 
int main(int argc, char* argv[]) 
{ 
    findmaxPalindrome<6>(); 
    return 0; 
} 

Answer 17

public class ProjectEuler4 { 

public static void main(String[] args) { 

    int x = 999; // largest 3-digit number 
    int largestProduct = 0; 

    for(int y=x; y>99; y--){ 
     int product = x*y; 

     if(isPalindormic(x*y)){ 
      if(product>largestProduct){ 
       largestProduct = product; 
       System.out.println("3-digit numbers product palindormic number : " + x + " * " + y + " : " + product); 
      } 
     } 

     if(y==100 || product < largestProduct){y=x;x--;} 
    } 


} 

public static boolean isPalindormic(int n){ 

    int palindormic = n; 
    int reverse = 0; 

    while(n>9){ 
     reverse = (reverse*10) + n%10; 
     n=n/10; 
    } 
    reverse = (reverse*10) + n;  
    return (reverse == palindormic); 
} 
}