最大的回文产品 – 欧拉项目

我试图解决项目Euler 问题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; } } 

Answer 1

这是一个不会遍历所有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 = -1; 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 > -1? max : "No palindrome found"); } 

编辑：

main方法的改进解决方案（根据Peter Schuetze）可以是：

 public static void main(String[] args) { int max = -1; 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 > -1? max : "No palindrome found"); } 

对于这个特殊的例子，时间大约是2倍，但是如果你的数字更大，那么改进将更加显着。

输出 ：

 906609 

Answer 2

你按顺序从999 * 999递减到100 * 100。 这并不一定意味着您找到的第一个回文是两个3位数字的乘积。

回文997799有11和90709作为主要因素，它不是两个3位数的乘积。

Answer 3

for循环运行i从998001下降到100000.在你的程序中没有任何地方你检查i实际上可以是两个3位数字的乘积。

Answer 4

您正在迭代for循环，其编号从998001到10000，因为某些数字可能不是产品两个3位数字。
您应该乘以两个3位数字，然后比较它，如果该数字是回文或不是。

你的for循环代码应该是：

  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 

我想这就是你需要做的。

Answer 5

你也假设你会发现第一个最大的回文。 你会发现第一个回文是580085，这不是正确的答案。

您还假设您找到的第一个回文是两个3位数字的乘积。 您还应该使用两个不同的数字，而不是将999乘以999并迭代到100 * 100。

Answer 6

以上都没有给出正确的答案。 （我认为逻辑可能是正确的，但正确的答案是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) 

Answer 7

 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; } 

Answer 8

好吧，我在这里看到很多错误。

• 首先，您使用2个最高3位数的乘法，然后递减它以找到回文。 根据问题，您需要做的是使用具有最高3位数no.s的变量，然后递减它们以检查最终产品。
• 第二，检查是否。 是palindrome你使用一个数组来存储它然后用一个循环来检查它，我发现它不正确，因为你可以简单地存储结果否。 在另一个整数变量中使用简单的方法。（reverseNum * 10 +（num％10））

我看到用户已经发布了正确的代码（ROMANIA）

Answer 9

用C完成。这可能会对你有所帮助。

 #include 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); } 

Answer 10

/ *找到由两个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, eg 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)); } } 

Answer 11

因为在R中没有人这样做。这个解决方案给出了问题的答案。

项目欧拉问题4

回文数字读取两种方式相同。 由两个2位数字的乘积制成的最大回文是9009 = 91×99。

找到由两个3位数字的乘积制成的最大回文。 R没有内置function来检查回文，所以我创建了一个虽然可以使用’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 eg 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] is <- vector('numeric', length = length(Palin)) js <- 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){ is[i-99] <- i js[i-99] <- j } } } product <- is * js which(is * js == max(product)) -> Ans paste(is[Ans[1]], "and", js[Ans[1]], "give the largest two 3-digit palindrome") ANSWER 993 * 913 = 906609 

请享用！

Answer 12

用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; } 

Answer 13

此方法比以前的方法快得多。 它首先评估999 * 999.它是在困惑的回文产品问题中提出的方法的实现

我们想在较小的产品之前尝试更大的产品，所以接下来尝试998 * 998，外循环每次减少一个。 在内部循环中，取外部限制数来创建（n + y）（ny）（总是小于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); } 

}

Answer 14

这是c ++中的代码

 #include  using namespace std; int reverse(int a){ int reverse=0; for(int i=0;i<6;i++){ reverse = reverse*10+a%10; a/=10; } return reverse; } int main(){ int a=999,max=1,rev;; int b=999; for(a=999;a>100;a--){ for(b=999;b>100;b--){ int p = a*b; rev = reverse(p); if (p==rev) { if(max 

Answer 15

这是Project_Euler-4问题的Python代码。

我们必须找到最大的回文数，它是两个三位数的乘积

 import math def isPal(x): x=str(x) t=x[::-1] if(x==t): return True else: return False max=0 for i in range(999,99,-1): for j in range(999,99,-1): if(isPal(i*j)): if((i*j)>max): max=(i*j) print(max) 

答案是906609