Найти самый большой палиндром из двух трехзначных чисел

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

Поскольку мы не выключаем оба итератора (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 2

Вы можете использовать тот факт, что 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 3

Это код на 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 4

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 5

Вы можете попробовать следующее, что печатает

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 6

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

Answer 7

Вы можете сделать это с помощью 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)