找到由两个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编写的代码……除此之外是否有任何有效的方法..我们可以更优化这些代码吗？
我们假设最大的这样的回文将有六位而不是五位，因为143 * 777 = 111111是回文。
如其他地方所述，6位数的10-palindrome abccba是11的倍数。这是正确的，因为* 100001 + b * 010010 + c * 001100等于11 * a * 9091 + 11 * b * 910 + 11 * C * 100。 因此，在我们的内循环中，如果m不是11的倍数，我们可以将n减少11步。
我们正试图找到百万以下最大的回文，它是两个3位数字的乘积。 为了找到一个大的结果，我们首先尝试大的除数：
- 我们从999开始，从1开始向下移动;
- 将n从999向下运行1（如果11除以m，或9％的时间）或从990除以11（如果11不除m，或91％的时间）。
我们跟踪到目前为止变量q中发现的最大回文。 假设q = r·s，r <= s。 我们通常有m
附加程序的内循环仅执行506次，相比之下使用的朴素程序的~810000倍。
#include #include 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中工作。
我会怎么做：
- 从999开始，向后退到998,997等
- 为我当前的号码创建回文。
- 确定此数字的素数分解（如果您有预先生成的素数列表，则不是那么昂贵）。
- 通过这个素数分解列表来确定我是否可以使用这些因子的组合来产生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 }
我们可以将任务翻译成数学语言。
首先，我们使用字符作为数字：
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}的€。
从{1..9}定义a和x作为元素更精确，而不是{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创建一个List。 它适用于BigInt或Long，几乎没有重新声明，并且适用于Java; 可以用Java实现，但在那里看起来不同。
好吧，把事情放在一起：
highs.filter (_ > 900000) .sortWith (_ > _) find (palindrom) res45: Option[Int] = Some(906609)
那里有835个数字> 900000，它返回的速度相当快，但我想更强大的蛮力也不会慢得多。
也许有一种更聪明的方法来构建最高的palindrom，而不是搜索它。
一个问题是：我以前不知道，有一个解决方案> 900000。
一种非常不同的方法是产生大的回文，并解构它们的因素。
public class Pin { public static boolean isPalin(int num) { char[] val = (""+num).toCharArray(); for(int i=0;i100;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; } } } }
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; } } } }
一种稍微不同的方法，可以很容易地计算出由最多两个6位数字的乘积产生的最大回文数。
第一部分是创建回文数的发生器。 所以没有必要检查一个数字是否是回文，第二部分是一个简单的循环。
#include #include #include using namespace std; template class PalindromeGenerator { unique_ptr m_data; bool m_hasnext; public : PalindromeGenerator():m_data(new int[N]) { for(auto i=0;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 void findmaxPalindrome() { PalindromeGenerator gen; decltype(gen.getnext()) minv=static_cast (pow(10,N-1)); decltype(gen.getnext()) maxv=static_cast (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(); return 0; }
您可以使用11是回文的倍数来减少搜索空间的事实。 我们可以得到这个，因为我们可以假设回文将是6位数并且> = 111111。
例如（来自projecteuler;））
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整除。
您可以尝试以下打印
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(); }
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;a100;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
这是C中的代码，有点长，但是完成了工作。:)
#include #include /* 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;icekmax) cekmax=cek; } } } printf("The largest palindrome is: %d\n\a",cekmax); }
你可以用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)
由于我们没有同时循环下两个迭代器（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
我尝试了Tobin joy和vickyhacks的解决方案，他们两个都产生了结果580085这是错的，这是我的解决方案，虽然非常笨拙：
import java.util.*; class ProjEu4 { public static void main(String [] args) throws Exception { int n=997; ArrayList al=new ArrayList (); 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 findfactors(int fin) { ArrayList al=new ArrayList (); 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; } }
最有可能的是复制其他解决方案之一但由于pythonified代码它看起来很简单，即使它有点蛮力。
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
怎么样：在python中
>>> for i in range((999*999),(100*100), -1): ... if str(i) == str(i)[::-1]: ... print i ... break ... 997799 >>>
我相信有一种更简单的方法：检查从两个三位数的最大乘积下降的回文，选择具有两个三位数因子的第一个回文。
这是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<
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
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); } }