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

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

Мы предполагаем, что самый большой такой палиндром будет иметь шесть цифр, а не пять, потому что палиндром - 143 * 777 = 111111.

Как уже отмечалось в другом месте, 6-значное основание-10 палиндрома abccba кратно11. Это верно, потому что a * 100001 + b * 010010 + c * 001100 равно 11 * a * 9091 + 11 * b * 910 + 11 * c * 100.Таким образом, в нашем внутреннем цикле мы можем уменьшить n с шагом 11, если m не кратно 11.

Мы пытаемся найти самый большой палиндром под миллион, который является произведением двух трехзначных чисел,Чтобы найти большой результат, сначала мы пробуем большие делители:

• Мы спускаемся на м вниз с 999 на 1;
• Снизьте n с 999 на 1 (если 11 делит м, или 9% времени) или с 990 на 11 (если 11 не делит м, или 91% времени).

Мы отслеживаем самый большой палиндром, найденный до сих пор в переменной q.Предположим, что q = r · s с r <= s.У нас обычно есть m <r <= s.Нам нужно m · n> q или n> = q / m.При обнаружении более крупных палиндромов диапазон n становится более ограниченным по двум причинам: q увеличивается, m уменьшается.

Внутренний цикл присоединенной программы выполняется только 506 раз, против ~ 8 10000 раз наивногоИспользуемая программа.

#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.

Answer 2

Мы можем перевести задачу на язык математики.

Для краткого начала мы используем символы в качестве цифр:

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 на самом деле не является трехзначным числом,это?

Хорошо.

Если мы хотим произвести большое число, мы должны попытаться достичь 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.

---

Совсем другой подход: производить большие палиндромы и деконструировать их факторы.

Answer 3

Что бы я сделал:

1. Начиная с 999, возвращаясь к 998, 997 и т. Д.
2. Создайте палиндром для моего текущего номера.
3. Определите простую факторизацию этого числа (не так уж и дорого, если у вас есть предварительно сгенерированный список простых чисел.
4. Проработайте этот простой список факторизации, чтобы определить, могу ли я использовать комбинацию факторов, чтобы сделать 2Трехзначные числа.

Некоторые коды:

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 
}

Answer 4

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

Answer 5

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

Answer 6

Немного другой подход, который может легко вычислить наибольшее число палиндромов, полученное из произведения до двух 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;
}

Answer 7

Я полагаю, что существует более простой подход: исследовать палиндромы, спускающиеся из наибольшего произведения из двух трехзначных чисел, выбирая первый палиндром с двумя трехзначными множителями.

Вот код 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}"

prime.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

palindrome_range.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

Answer 8

А как же: в питоне

>>> for i in range((999*999),(100*100), -1):
...     if str(i) == str(i)[::-1]:
...         print i
...         break
...
997799
>>>

Answer 9

Скорее всего, это репликация одного из других решений, но благодаря питонизированному коду оно выглядит просто, даже если оно немного грубое.

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

Answer 10

Я попробовал решение от Тобина радости и Викихакса, и оба они дали результат 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;
}
}