2014-07-16 55 views
0

我試圖解決項目歐拉problem 4是:最大回文產品 - 歐拉項目

迴文數讀取相同的兩種方式。由兩個2位數字產品製成的最大回文是9009 = 91×99. 找到由兩個3位數字產品製成的最大回文。

這裏是我的解決方案,它的產量是997799,然而,這不是正確的答案,我不知道問題出在哪裏:

package projecteuler; 

public class Pro4 { 

    public static void main(String[] args) { 

     for(int i=999*999;i>=100*100;i--){ 
      if(isPalindrome(i)==true){ 
       System.out.println(i); 
       break; 
      } 
     } 
    } 

    static boolean isPalindrome(int x){ 
     int[] bits = new int[7]; 
     int index=1; 
     while(x>0){ 
      bits[index]=x%10; 
      index++; 
      x/=10; 
     } 
     for(int i=1;i<=index/2;i++){ 
      if(bits[i]!=bits[index-i]){ 
       return false; 
      } 
     } 
     return true; 
    } 

} 
+0

你有沒有檢查它通過一個調試器?坦率地說,有很多可能會出錯的地方 - 用一步調試器檢查它將是找出問題的好的第一步。 – Makoto

回答

2

您正在遞減我按順序從999 * 999到100 * 100 。這並不一定意味着你找到的第一個迴文是兩個3位數字的乘積。

迴文997799有11和90709作爲主要因素,它不是兩個3位數字的乘積。

+0

問題是兩個3位數字的最大回文產品。 – az89

1

for循環運行i從998001降到100000.您的程序中沒有任何地方檢查i實際上可能是兩個3位數字的乘積。

+0

他的循環實際上是從999 * 999運行的,即從998001降到100000;) –

+0

@PeterSchuetze謝謝。糾正。 –

0

您正在循環使用數字從998001到10000的循環,因爲某些數字可能不是產品兩個3位數字。
你應該乘以兩個3位數的數字,並比較它,如果這個數字是迴文。

您的循環代碼應該是:

for(int i=999;i>=100;i--) 
    { 
     int k = i-1; 
     int product = i * k; 
     System.out.println(i+" * "+k+" = "+product); 

     if(isPalindrome(product)==true){ 
      System.out.println("palindrum number "+product); 
      System.out.println("Product of : "+i+" * "+k); 
      break; 
     } 
    } 

這將會給你最大的迴文數目爲兩個3位數字的產品。
輸出是:

palindrum number 289982 
Product of : 539 * 538 

這將真,如果當你乘兩個數是不同的。
如果要包含相同數字的產品以檢查迴文是否比上面的代碼中可能沒有什麼變化。
對於代碼應該是:

for(int i=999;i>=100;i--){ 
     int k = i; 
     int product = i * k; 
     System.out.println(i+" * "+k+" = "+product); 

     if(isPalindrome(product)==true){ 
      System.out.println("palindrum number "+product); 
      System.out.println("Product of : "+i+" * "+k); 
      break; 
     } 
     else{ 
      k = i - 1; 
      product = i * k; 
      System.out.println(i+" * "+k+" = "+product); 
      if(isPalindrome(product)==true){ 
       System.out.println("palindrum number "+product); 
       System.out.println("Product of : "+i+" * "+k); 
       break; 
      } 
     } 
    } 

,給你喜歡的輸出:

palindrum number 698896 
Product of : 836 * 836 

我覺得這是你需要做什麼。

+2

你的答案很好,但錯了。你只是比較'i *(i-1)'的乘積。我發現的最大的是913 * 993 = 906609 –

4

這裏是不通過所有的6位數字迭代的溶液:

public static boolean isPalindrome(int nr) { 
    int rev = 0;     // the reversed number 
    int x = nr;      // store the default value (it will be changed) 
    while (x > 0) { 
     rev = 10 * rev + x % 10; 
     x /= 10; 
    } 
    return nr == rev;    // returns true if the number is palindrome 
} 

public static void main(String[] args) { 

    int max = 100001; 

    for (int i = 999 ; i >= 100 ; i--) { 
     for (int j = 999 ; j >= 100 ; j--) { 
      int p = i * j; 
      if (max < p && isPalindrome(p)) { 
       max = p; 
      } 
     } 
    } 
    System.out.println(max); 
} 

編輯:

一種改善了main方法溶液(根據彼得Schuetze )可以是:

public static void main(String[] args) { 

    int max = 100001; 

    for (int i = 999 ; i >= 100 ; i--) { 
     if (max >= i*999) { 
      break; 
     } 
     for (int j = 999 ; j >= i ; j--) {    
      int p = i * j; 
      if (max < p && isPalindrome(p)) { 
       max = p; 
      } 
     } 
    }  
    System.out.println(max); 
} 

對於這個特定的例子時間是6倍,但如果你有更多的數字,改善將更加顯着。

+3

+1,因爲這是迄今爲止最好的解決方案。我也喜歡在確定它是否是迴文之前,先將其與max進行比較。這種便宜的操作可能會節省一些時間。但是,還有優化的空間。 1)你幾乎計算所有產品兩次,因爲'i * j = j * i'你只需要計算所有'j> = i'的乘積。 2)對於小'i',沒有'j <1000'產生大於'max'的產品。所以加入if(max/i> 1000){i = 99}'將有效縮短計算最大回文數的時間到當前時間的1/10或更少。 –

+0

非常好的建議。我更新了我的帖子。謝謝。 –

0

你也假設你會發現第一個迴文是最大的迴文。你會發現第一個迴文是580085,這不是正確的答案。

你也假設你會發現第一個迴文是兩個3位數字的乘積。您還應該使用兩個不同的數字,而不是將999與999相乘,然後迭代到100 * 100.

0

以上都沒有給出正確的答案。 (我認爲邏輯可能是正確的,但正確的答案是906609)。由於您不知道數字是6位數還是5位數,因此您需要檢查哪兩個數字。下面是一個簡單的代碼來做同樣的事情。

乘法被稱爲一次的時候,我知道...

i = 999 
for u in range (100,1000): 
    for y in range (100,1000): 
     if len(str(u*y)) == 5 and str(u*y)[0]==str(u*y)[4]and str(u*y)[1]==str(u*y)[3] and u*y>i: 
     i=u*y 
     print ('the product of ', u, ' and ',y,' is: ',u*y) 
    elif len(str(u*y)) == 6 and str(u*y)[0]==str(u*y)[5]and str(u*y)[1]==str(u*y)[4]and str(u*y)[2]==str(u*y)[3]and u*y>i: 
     i=u*y 
     print ('the product of ', u, ' and ',y,' is: ',u*y) 
0
public class LargestPalindromProduct { 

    public static void main(String args[]) { 
     LargestPalindromProduct obj = new LargestPalindromProduct(); 
     System.out.println("The largest palindrome for product of two 3-digit numbers is " + obj.getLargestPalindromeProduct(3)); 
    } 

/* 
* @param digits 
* @return 
*/ 
private int getLargestPalindromeProduct(int digits) { 
    int largestPalindromeProduct = -1; 
    int startNum = (int)Math.pow(10, digits) - 1; 
    int endNum = (int)Math.pow(10, digits-1) - 1; 

    for (int i = startNum; i > endNum; i--) { 
     for (int j = startNum; j > endNum; j--) { 
      if (isPalindrome(i * j)) { 
       largestPalindromeProduct = Math.max(largestPalindromeProduct, i * j); 
      } 
     } 
    } 
    return largestPalindromeProduct; 
} 

private boolean isPalindrome(int number) { 
    String s = String.valueOf(number); 
    for (int i = 0, j = s.length() -1; i < j;i++, j--) { 
     if (s.charAt(i) != s.charAt(j)) { 
      return false; 
     } 
    } 
    return true; 
} 
0

好吧,我看到了很多事情錯在這裏。

  • 首先,您使用2個最高3位數的乘法,然後遞減找到迴文。根據問題你需要做的是使用具有最高3位數字的變量,然後減少它們以檢查產生的結果。
  • 第二個用於檢查否。是迴文,你使用了一個數組來存儲它,然後用一個循環來檢查它,我發現它不正確,因爲你可以簡單地存儲結果no。通過使用簡單的方法另一整型變量。(reverseNum * 10 +(NUM%10))

而且我看到已經發布的

0

完成C中的用戶(羅馬尼亞)正確的代碼 這可能會幫助你。

#include<stdio.h> 
int calculate(int n) 
{ 
    int temp = 0,m = 0; 
    m = n; 
    while(n != 0) 
    { 
     temp = temp * 10; 
     temp = temp + n % 10; 
     n = n/10; 
    } 
    if(m == temp) 
    { 
     printf(" %d \n",temp); 
     return temp; 
    } 
    else 
    { 
     return 0; 
    } 
} 
int main() 
{ 
    int i,j,temp = 0,count=0,temp1 = 0; 
    for(i = 100;i < 1000;i++) 
    { 
     for(j = 100;j < 1000;j++) 
     { 
      temp1 = i * j; 
      temp = calculate(temp1); 

      if(temp > count) 
      { 
       count = temp; 
      } 
     } 
    } 
    printf(" The Largest Palindrome number is : %d \n",count); 
} 
0

/* 查找兩個n位數的乘積的最大回文。 因爲其結果可能是非常大的,你應該返回的最大回文國防部1337 舉例: 輸入:2 輸出:987 說明:99 X 91 = 9009,9009%,1337 = 987 注: 範圍n是[1,8]。 */

public class LargestPalindromeProduct { 
    public int largestPalindrome(int n) { 
     if(n<1 || n>8) 
      throw new IllegalArgumentException("n should be in the range [1,8]"); 

     int start = (int)Math.pow(10, n-1); // n = 1, start 1, end = 10 -1. n = 2, start = 10, end = 99; 
     if(start == 1) start = 0 ; // n = 3, start = 100, end == 999 
     int end = (int)Math.pow(10, n) - 1; 

     long product = 0; 
     long maxPalindrome = 0; 

     for(int i = end ; i >= start ; i--) 
     { 
      for(int j = i ; j >= start ; j--) 
      { 
       product = i * j ; 
       // if one of the number is modulo 10, product can never be palindrome, e.g 100 * 200 = 200000, or 240*123 = 29520. this is because the product will always end with zero but it can never begin with zero except one/both of them numbers is zero. 
       if(product % 10 == 0) 
        continue; 
       if(isPalindrome(product) && product > maxPalindrome) 
        maxPalindrome = product;      
      } 
     } 
     return (int)(maxPalindrome % 1337); 
    } 
    public static boolean isPalindrome(long n){ 
     StringBuffer sb = new StringBuffer().append(Long.toString(n)).reverse(); 
     if(sb.toString().equals(Long.toString(n))) 
      return true; 
     return false; 
    } 
    public static void main(String[] args){ 
     System.out.println(new LargestPalindromeProduct().largestPalindrome(2)); 
    } 

} 
0

既然沒有人在R.這一個解決方案,給出了這個問題的答案一樣。

歐拉項目問題4

迴文數字讀取相同的方式。由兩個2位數字產品製成的最大回文是9009 = 91×99.

查找由兩個3位數字產品製成的最大回文。 R沒有內置函數來檢查迴文,所以我創建了 一個,儘管可以使用'rev':)。此外,代碼未針對主要用於提高可讀性的速度進行優化。

 reverse <- function(x){ 
     Args: 
     x : object whose elements are to be reversed, can be of type 
     'character' or 'vector' of length = 1 
     Returns: 
      x : The object's elements are reversed e.g boy becomes yob and 23 
     becomes 32 
     Error Handling: 
     if (is.vector(x) == TRUE & length(x) > 1){ 
     stop("Object whose length > 1 cannot be used with reverse(x) 
     consider vector.reverse(x)") 
      } 
     Function Execution 
     if (is.character(x) == TRUE){ 
      v <- unlist(strsplit(x, '')) 
      N <- length(v) 
      rev.v <- v 
      for (i in 0:(N - 1)){ 
     rev.v[i + 1] <- v[N - i] 
     } 
     rev.v <- paste0(rev.v, collapse = '') 
      return(rev.v) 
     } else { 
      x <- as.character(x) 
     v <- unlist(strsplit(x, '')) 
      rev.v <- v 
      N <- length(v) 
for (i in 0:(N - 1)){ 
    rev.v[i + 1] <- v[N - i] 
} 
rev.v <- paste0(rev.v, collapse = '') 
rev.v <- as.numeric(rev.v) 
    return(rev.v) 
    } 
} 

    the function vector.reverse() has been deleted to reduce the length of 
    this code 

    is.palindrome <- function(x){ 
    Args: 
    x : vector whose elements will be tested for palindromicity, can be of 
length >= 1 
    Returns: 
    TRUE : if an element in x or x is palindromic 
    FALSE: if an element in x or x is not palindromic 

    Function Execution: 
    if (is.vector(x) == TRUE & length(x) > 1){ 
    x.prime <- vector(length = length(x)) 
    for (i in 1:length(x)){ 
     x.prime [i] <- reverse(x [i]) 
} 
    return(x.prime == x) 
} else { 
ifelse(reverse(x) == x, return(TRUE), return(FALSE)) 
    } 
    } 

    palindromes between 10000 and 999*999 
Palin <- (100*100):(999*999) 
Palin <- Palin [is.palindrome(Palin) == 1] 
i.s <- vector('numeric', length = length(Palin)) 
j.s <- vector('numeric', length = length(Palin)) 

    Factoring each of the palindromes 
    for (i in 100:999){ 
    for (j in 100:999){ 
     if (sum(i * j == Palin) == 1){ 
     i.s[i-99] <- i 
     j.s[i-99] <- j 

     } 
    } 
    } 
product <- i.s * j.s 
which(i.s * j.s == max(product)) -> Ans 
paste(i.s[Ans[1]], "and", j.s[Ans[1]], "give the largest two 3-digit 
    palindrome") 



ANSWER 
    993 * 913 = 906609 

享受!

0

C#編寫的

private static void Main(string[] args) 
     { 
      var maxi = 0; 
      var maxj = 0; 
      var maxProd = 0; 
      for (var i = 999; i > 100; i--) 
      for (var j = 999; j > 100; j--) 
      { 
       var product = i * j; 
       if (IsPalindrome(product)) 
        if (product > maxProd) 
        { 
         maxi = i; 
         maxj = j; 
         maxProd = product; 
        } 
      } 
      Console.WriteLine(
       "The highest Palindrome number made from the product of two 3-digit numbers is {0}*{1}={2}", maxi, maxj, 
       maxProd); 
      Console.ReadKey(); 
     } 

     public static bool IsPalindrome(int number) 
     { 
      var numberString = number.ToString(); 
      var reverseString = string.Empty; 
      for (var i = numberString.Length - 1; i >= 0; --i) 
       reverseString += numberString[i]; 
      return numberString == reverseString; 
     } 
0

另一種簡單的解決方案本方法比以前的方法顯著更快。 它開始通過評估999 * 999這是在Puzzled over palindromic product problem提出的方法的實現

我們想以前更小的產品,試圖更大的產品,所以接下來嘗試998 * 998,與外循環的每一次減少1 。在內部循環中, 採用外部極限數來創建(n + y)(n-y)(總是小於n^2),迭代y直到其中一個因素太大或太小。

https://pthree.org/2007/09/15/largest-palindromic-number-in-python/,的因素 一個必須是11 檢查的倍數,以查看是否的因素之一是11的倍數,並且,該產品是比以前發現(或初始)迴文數量。

一旦這些測試得到滿足,看看產品是迴文。

一旦找到了迴文,我們可以將外環的極限提高到迴文的平方根,因爲這是可能是答案的最小值。

該算法僅在475個比較中找到答案。這遠遠好於簡單方法提出的810,000,甚至405450.

任何人都可以提出更快的方法嗎?

Longest palindromes: 
Max factor Max Palindrome 
9999   99000099 
99999  9966006699 
999999  999000000999 
9999999  99956644665999 
99999999  9999000000009999 
999999999 999900665566009999 

public class LargestPalindromicNumberInRange { 
    private final long lowerLimit; 
    private final long upperLimit; 
    private long largestPalindrome; 
    private long largestFirstFactor; 
    private long largestSecondFactor; 
    private long loopCount; 
    private long answerCount; 

public static void main(String[] args) { 
    long lowerLimit = 1000; 
    long upperLimit = 9999; 
    LargestPalindromicNumberInRange palindromicNumbers = 
      new LargestPalindromicNumberInRange(lowerLimit, upperLimit); 
    palindromicNumbers.TopDown(); 
} 

private LargestPalindromicNumberInRange(long lowerLimit, long upperLimit){ 
    this.lowerLimit = lowerLimit; 
    this.upperLimit = upperLimit; 
} 
private void TopDown() { 
    loopCount = 0; 
    answerCount = 0; 
    largestPalindrome = lowerLimit * lowerLimit; 
    long initialLargestPalindrome = largestPalindrome; 
    long lowerFactorLimit = lowerLimit; 
    for (long limit = upperLimit; limit > lowerFactorLimit; limit--){ 
     for (long firstFactorValue = limit; firstFactorValue >= limit - 1; firstFactorValue--) { 
      long firstFactor = firstFactorValue; 
      long secondFactor = limit; 
      while(secondFactor <= upperLimit && firstFactor >= lowerLimit){ 
       if (firstFactor % 11 == 0 || secondFactor % 11 == 0) { 
        long product = firstFactor * secondFactor; 
        if (product < largestPalindrome) { break; } 
        loopCount++; 
        if (IsPalindromic(product)) { 
//     System.out.print("Answer: " + product + "\n"); 
         answerCount++; 
         largestPalindrome = product; 
         largestFirstFactor = firstFactor; 
         largestSecondFactor = secondFactor; 
         lowerFactorLimit = (long) Math.sqrt(largestPalindrome); 
         break; 
        } 
       } 
       firstFactor--; 
       secondFactor++; 
      } 
     } 
     System.out.print("Answer: " + largestPalindrome + "\n"); 
     System.out.print("Factor1: " + largestFirstFactor + "\n"); 
     System.out.print("Factor2: " + largestSecondFactor + "\n"); 
     System.out.print("Loop count: " + loopCount + "\n"); 
     System.out.print("Answer count: " + answerCount + "\n"); 
    } 
private boolean IsPalindromic(Long x) { 
    String forwardString = x.toString(); 

    StringBuilder builder = new StringBuilder(); 
    builder.append(forwardString); 
    builder = builder.reverse(); 
    String reverseString = builder.toString(); 

    return forwardString.equals(reverseString); 
} 

}