Java 最大的回文产品——欧拉项目
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/24772179/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Largest palindrome product - euler project
提问by Praveen Kumar
I was trying to solve project Euler problem 4which is:
我试图解决项目欧拉问题 4，即：
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.
回文数的读法是一样的。两个两位数的乘积构成的最大回文数是 9009 = 91 × 99。求两个 3 位数的乘积构成的最大回文数。
Here is my solution , it's output is 997799 , however that's not the correct answer ,I wonder where is the problem:
这是我的解决方案，它的输出是 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;
}
}
回答by Sanjeev Kumar
You are decrementing i sequentially from 999*999 to 100 *100. It does not necessarily mean that the first palindrome you are finding is a product of two 3 digit numbers.
您正在将 i 从 999*999 依次递减到 100 *100。这并不一定意味着您找到的第一个回文是两个 3 位数的乘积。
The palindrome 997799 has 11 and 90709 as prime factors which is not a product of two 3 digit numbers.
回文 997799 有 11 和 90709 作为质因数，它不是两个 3 位数的乘积。
回答by Robby Cornelissen
The for loop runs for ifrom 998001 down to 100000. Nowhere in your program are you checking that ican actually be the product of two 3-digit numbers.
for 循环i从 998001运行到 100000。在您的程序中没有任何地方检查它i实际上可以是两个 3 位数的乘积。
回答by Yagnesh Agola
You are iterating for loop with number from 998001 to 10000 in that some number may not be a product two 3-digit number.
You for should multiply two 3-digit number and than compare it if that number is palindrome or not.
您正在使用从 998001 到 10000 的数字迭代 for 循环，因为某些数字可能不是两个 3 位数字的乘积。
您应该将两个 3 位数字相乘，然后比较该数字是否为回文数。
Your for loop code should be :
您的 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;
}
}
This will gives you largest palindrome number of which is product of two 3-digit number.
Output is :
这将为您提供最大的回文数，其中最大的回文数是两个 3 位数的乘积。
输出是：
palindrum number 289982
Product of : 539 * 538
This will true if both number is different while you multiply.
If you want to include same number product to check that is palindrome or not than there may be little change in above code.
For that code should be :
如果乘法时两个数字不同，这将是正确的。
如果你想包含相同数量的产品来检查是否是回文，那么上面的代码可能几乎没有变化。
对于该代码应该是：
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;
}
}
}
Which give you output like :
这给你的输出如下：
palindrum number 698896
Product of : 836 * 836
I think this is what you need to do.
我认为这是你需要做的。
回答by ROMANIA_engineer
Here is a solution that doesn't iterate through all the 6-digit numbers:
这是一个不遍历所有 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");
}
Edit:
编辑：
An improvedsolution for the mainmethod ( according to Peter Schuetze ) could be:
该方法的改进解决方案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");
}
For this particular example, the time is about 2 times better, but if you have bigger numbers, the improvement will be more significant.
对于这个特定的例子，时间大约要好 2 倍，但如果你有更大的数字，改进会更显着。
Output:
输出：
906609
回答by Saif Al Falah
You are also assuming that the first palindrome you'll find will be the largest. The first palindrome you'll find is 580085 which isn't the right answer.
您还假设您找到的第一个回文将是最大的。您会发现的第一个回文是 580085，这不是正确答案。
You are also assuming that the first palindrome you'll find is the product of two 3 digit numbers. You should also use two different numbers instead of multiplying 999 with 999 and iterating down to 100 * 100.
您还假设您会找到的第一个回文是两个 3 位数的乘积。您还应该使用两个不同的数字，而不是将 999 乘以 999 并向下迭代到 100 * 100。
回答by SOLID
None of the above seemed to have given the right answer. (I think the logic may be correct but the right answer is 906609). Since you are not aware that the number is 6 digit or 5 digit, you want to check which both. Below is a simple code to do same.
以上似乎都没有给出正确的答案。（我认为逻辑可能是正确的，但正确的答案是 906609）。由于您不知道该数字是 6 位数还是 5 位数，因此您想检查两者。下面是一个简单的代码来做同样的事情。
The multiplication is called once to often, I know...
乘法经常被调用一次，我知道......
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)
回答by codewhywhat
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;
}
回答by Vikas Tawniya
Well I am seeing a lot of things wrong here.
好吧，我在这里看到了很多错误。
- First of all you are using multiplication of 2 highest 3 digit numbers and then decrementing it to find palindrome. What you need to do according to question is to use variables having highest 3 digit no.s and then decrement them to check there resultant product.
- Second for checking if the no. is palindrome you used an array to store it then used a loop to check it, I find it incorrect, as you could simply store the resultant no. in another integer variable by using the simple approach.(reverseNum * 10 + (num % 10) )
- 首先，您使用 2 个最高的 3 位数字的乘法，然后将其递减以找到回文。根据问题，您需要做的是使用具有最高 3 位数编号的变量，然后将它们递减以检查结果产品。
- 其次检查是否没有。是回文你用一个数组来存储它然后用一个循环来检查它，我发现它不正确，因为你可以简单地存储结果号。在另一个整数变量中使用简单的方法。(reverseNum * 10 + (num % 10) )
And I am seeing a correct code already posted by a user (ROMANIA)
我看到一个用户已经发布了正确的代码（罗马尼亚）
回答by Dhaval Mistry
Done in C. This might help you.
用 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);
}
回答by Tesfay K. Aregay
/* Find the largest palindrome made from the product of two n-digit numbers. Since the result could be very large, you should return the largest palindrome mod 1337. Example: Input: 2 Output: 987 Explanation: 99 x 91 = 9009, 9009 % 1337 = 987 Note: The range of n is [1,8]. */
/* 找出由两个 n 位数字的乘积构成的最大回文数。由于结果可能非常大，您应该返回最大的回文mod 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));
}
}
