3 
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编写的代码...除了这个之外还有什么有效的方法..我们可以进一步优化这段代码吗？

4

17 回答 17

11

我们假设最大的回文数将有六位数而不是五位数，因为 143*777 = 111111 是一个回文数。

如其他地方所述，6 位以 10 为底的回文 abccba 是 11 的倍数。这是正确的，因为 a*100001 + b*010010 + c*001100 等于 11*a*9091 + 11*b*910 + 11 *c*100。因此，在我们的内部循环中，如果 m 不是 11 的倍数，我们可以将 n 递减 11。

我们正试图找到一百万以下的最大回文数，它是两个 3 位数字的乘积。为了找到一个大的结果，我们首先尝试大除数：

  • 我们将 m 从 999 向下移动 1；
  • n 从 999 向下运行 1（如果 11 除 m，或 9% 的时间）或从 990 除以 11（如果 11 不除 m，或 91% 的时间）。

我们跟踪迄今为止在变量 q 中发现的最大回文数。假设 q = r·s 且 r <= s。我们通常有 m < r <= 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。

于 2011-08-25T22:57:56.773 回答
3

我会做什么：

  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 
}
于 2011-08-25T00:59:57.010 回答
3

我们可以将任务翻译成数学语言。

作为一个简短的开始，我们使用字符作为数字：

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} 的 €。
将 a 和 x 定义为 {1..9} 中的元素而不是 {0..9} 更精确，因为 097 并不是真正的 3 位数字，是吗？

行。

如果我们想产生一个大数字，我们应该尝试达到一个 9......- 数字，因为它是回文，它必须是 9....9 的模式。如果最后一个数字是 9，那么从

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

遵循 z*c 必须导致一个数字，以数字 9 结尾 - 所有其他计算都不会影响最后一个数字。

所以 c 和 z 必须来自 (1,3,7,9)，因为 (1*9=9, 9*1=9, 3*3=9, 7*7=49)。

现在一些代码（Scala）：

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. 它适用于 BigInt 或 Long，几乎不需要重新声明，并且适用于 Java；可以用 Java 实现，但在那里看起来不同。

好的，把东西放在一起：

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

那里有 835 个数字 > 900000，它返回的速度非常快，但我想更多的暴力破解也不会慢很多。

也许有一种更聪明的方法来构建最高回文，而不是寻找它。

一个问题是：我以前不知道，有一个解决方案 > 900000。

一个非常不同的方法是，产生大回文，并解构它们的因素。

于 2011-08-26T06:41:53.370 回答
2 
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;
                }
            }
    }
}
于 2013-04-18T16:25:10.140 回答
1 
 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;
                }
            }
        }
    }
于 2012-10-20T12:44:15.030 回答
1

一种稍微不同的方法，可以轻松计算由最多两个 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;
}
于 2015-03-04T01:37:55.653 回答
0

您可以使用 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 整除。

于 2011-08-25T01:20:43.677 回答
0

您可以尝试以下打印

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();
}
于 2011-08-25T08:35:49.890 回答
0 
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);
}

    }
}
}
于 2012-05-15T14:34:30.377 回答
0

这是 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);
}
于 2013-01-20T23:55:11.753 回答
0

你实际上可以用 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)
于 2013-02-01T08:59:34.067 回答
0

由于我们没有同时循环两个迭代器（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
于 2013-07-30T15:43:32.717 回答
0

我尝试了 Tobin joy 和 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;
}
}
于 2013-12-04T22:01:26.273 回答
0

很可能它是另一个解决方案之一的复制，但由于 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
于 2013-12-26T09:55:15.087 回答
0

怎么样：在python中

>>> for i in range((999*999),(100*100), -1):
...     if str(i) == str(i)[::-1]:
...         print i
...         break
...
997799
>>>
于 2013-12-27T13:57:40.740 回答
0

我相信有一个更简单的方法：检查从两个三位数的最大乘积下降的回文，选择具有两个三位数因子的第一个回文。

这是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}"

素数.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

回文范围.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
于 2014-06-16T19:51:46.587 回答
0 
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);
}
}
于 2017-03-19T11:19:38.437 回答