论坛 › 欧拉计划（Project Euler） › 题目4：找出由两个三位数乘积构成的回文

欧拉计划 发表于 2015-4-20 23:41:09

题目4：找出由两个三位数乘积构成的回文

本帖最后由 欧拉计划 于 2017-1-14 17:43 编辑

Largest palindrome product

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。

找出最大的有由个三位数乘积构成的回文数。

翅膀团 发表于 2015-6-29 19:49:58

本帖最后由 永恒的蓝色梦想 于 2020-6-30 18:05 编辑

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    int a,b,c,i,p,q,max=0,x,y;
    char num;
    for(a=999;a!=100;a--)
    {
      for(b=999;b!=100;b--)
      {
            c = a * b;
            itoa (c,num,10);
            p = strlen(num);
            q = p/2;
            for(i=0;i<q;i++)
            {
            if(num != num)
            {
            goto z;
            }
            }
            if(c > max)
            {
            max = c;
            x = a;
            y = b;
            }
z:         c = 0;
       }
    }
    printf("%d * %d=%d\n",x,y,max);

}

如果有错误希望指出

无名侠 发表于 2015-7-9 14:41:46

难点应该就是判断是否为回文了。
我用的方法有些歪门邪道，利用字符串来判断，不过效率还行。
然后就是三位数的枚举。
A * B = B * A
所以我用了两层循环。 第一层循环从500向下递减，第二层循环是从1000向下递减。
从最大向下递减的好处：找到的第一个回文数就是最大的:lol:

输出结果：
499 * 737 =367763
def deDec(x):
        str1 = str(x)
        str3 = ""
        x2 = len(str1)
        x2-=1
        while x2>=0:
                str3=str3+str1
                x2-=1
        return str3==str1

def pdr():
        x1=500
        x2=1000
        while x1>0:
                while x2>=500:
                        y=x1*x2
                        if deDec(y):
                                print(str(x1)+" * "+str(x2)+" = ",y)
                                return
                        x2-=1
                x2=1000
                x1-=1
如果有错误，还望各位大神们指出。

牡丹花下死做鬼 发表于 2015-7-19 22:07:14

#include<stdio.h>
#include<windows.h>
int main()
{
        int i, j = 0,k,ys;
        for(i = 998001;i>10000;--i) /*从最大的三位数乘积999*999的值998001--最小的100*100的值10000开始遍历*/
        {
                k = i;
                while(k != 0) /*将i倒置*/
                {
                        ys = k % 10;
                        k = k / 10;
                        j = j * 10 + ys;
                }
                if(i == j) /*判断i是否为回文数*/
                {
                        for(k = 100;k<999;++k) /*判断该数是否能由两三位数相乘得到 将该数除以一三位数（100-999）*/
                        {
                                if(i%k==0) /*判断该数是否能由一三位数于其他数相乘得到*/
                                {
                                        if(i/k >= 100 && i/k <1000) /*判断该数是否为三位数*/
                                        {
                                                goto s;
                                        }
                                        else if(i/k<100) /*若以为二位数说明已不符合退出循环*/
                                        {
                                                break;
                                        }
                                        else /*若为四位数继续加大k的值继续循环不做任何动作*/
                                        {
                                                ;
                                        }
                                }
                        }
                }
                else
                {
                        j = 0;
                }
        }
s:printf("The best is:%d = %d * %d\n",j,k,j/k);
system("pause");
return 0;
}

wyc1gg 发表于 2015-10-8 17:38:53

本帖最后由 永恒的蓝色梦想 于 2020-6-30 18:06 编辑

def int_reverse(x):
    '求一个数的反转：1234得到4321'
    x1 = str(x)
    x1 = list(x1)
    x1.reverse()
    x1 = ''.join(x1)
    x1 = int(x1)
    return x1
      
def last_pal(digt):
   
    '两个digt位数乘积得到的最大回文'
   
    x = range(10**(digt-1),10**digt)
    y = range(10**(digt-1),10**digt)
    pal = {}
    for i in x:
      for j in y:
            s = i * j
            s1 = int_reverse(s)
            if s == s1:
                pal = (i,j)
            
    last_pal = max(pal.keys())
    print(last_pal)      
    print(pal)

last_pal(3)
==================================
结果：906609(993, 913)
但是感觉循环的使用，是的程序比较慢

maoguy 发表于 2015-11-2 14:06:42

/*题目4：找出由两个三位数乘积构成的回文*/

#include <iostream>
using namespace std;

int main()
{
        int a; //乘积
        int max = 0;//最大回文数
       
        int i,j;//两个三位数

        for (i = 100;i <= 999;i ++)
        {
                for (j = 100;j <= 999;j ++)
                {
                        a = i * j;
                       
                        if (a / 100000 > 0) //判断a是否六位数
                        {
                                if (a / 100000 == a%10 && \
                                        (a % 100000) / 10000 == (a % 100) / 10 && \
                                        (a % 10000) / 1000 == (a % 1000) / 100)
                                {
                                        cout<<"回文数为："<<a<<endl;

                                        if (a > max)
                                        {
                                                max = a;
                                        }
                                }
                                       
                        }

                        else
                        {
                                if (a / 10000 == a % 10 && \
                                        (a % 10000) / 1000 == (a % 100) / 10)
                                {
                                       
                                        cout<<"回文数为："<<a<<endl;

                                        if (a > max)
                                        {
                                                max = a;
                                        }
                                }
                        }

                }
        }

        cout<<"最大回文数为"<<max<<endl;

        return 0;
}

输出：最大回文数为906609

ianv 发表于 2016-3-16 17:42:43

#include<stdio.h>
#include<time.h>
int ispalindrome(int num)//仅对于这道题
{
        int a;
        for (int i=0;i<6;i++)
        {
                a=num%10;
                num/=10;
        }
        if((a==a)&&(a==a)&&(a==a))
                return 1;
        else
                return 0;
}

int checkfactor(int num)
{
        int i=100;
        for(i;i<1000;i++)
        {
                if(num%i==0)
                {

                        if(((num/i)>=100)&&((num/i)<1000))
                        return i;
                }
        }
        return 0;
}

int main()
{
        int i=997800;
        int factor1,factor2;
        double start, finish;
        start = clock();//取开始时间
        for(i;i>10000;i--)
        {
                if((ispalindrome(i))&&(checkfactor(i)))
                        break;
        }
        finish = clock();//取结束时间
        printf( "\n%f seconds\n",(finish - start) / CLOCKS_PER_SEC);//以秒为单位显示之
        factor1=checkfactor(i);
        factor2=i/factor1;
        printf("%d=%d*%d",i,factor1,factor2);
        getchar();
}

0.011s

张无忌 发表于 2016-5-1 23:40:54

# -*- coding: utf-8 -*-
"""
Palindromic number.
Find lagest palindrome made from the prod of two 3-digit numbers.
"""

def is_palindrome(num):
    if str(num) == str(num)[::-1]:
      return True
    return False

def find_palindrome(min_num=100, max_num=999):
    for m in reversed(range(min_num, max_num + 1)):
      for n in reversed(range(min_num, max_num + 1)):
            if is_palindrome(m*n):
                yield m*n

print(max(find_palindrome()))

Liu_xy 发表于 2016-5-4 22:43:37

list1 = []
for i in range(100,1000):
    for j in range(100, 1000):
      ret = i*j
      str_ret = list(str(ret))
      str_ret2 = str_ret[:]
      str_ret2.reverse()
      if str_ret == str_ret2:
            list1.append(ret)
print(max(list1))

飘飞的白杨 发表于 2016-6-10 18:29:01

def a():
      n = 999
      while n>100:#6位回文数
                m = n*1000+n%10*100+n//10%10*10+n//100
                for i in range(999,99,-1):
                        j = m//i
                        if m%i==0 and j>=100 and j<=999:
                              return(m,i,j)
                n-=1
      n = 999
      while n>100:#5位的回文数
                m = n*100+n//10%10*10+n//100
                for i in range(999,99,-1):
                        j = m//i
                        if m%i==0 and j>=100 and j<=999:
                              return(m,i,j)
                n-=1
               
print(a())

huomqh 发表于 2016-6-13 14:06:35

xx=0
for i in range(100,1000):
    for j in range(i,1000):
      x=i*j
      if x>xx:
            list1=list(str(x))
            l=len(list1)
            p=1
            for z in range((l+1)//2):
                if list1 != list1.pop():
                  p=0
                  break
            if p:
                xx=x
                a,b=i,j
print(xx)

答案906609=913*993

neilyoone 发表于 2016-6-14 23:56:12

想了下，没测试，是否可以设置，先算出乘积，字符串中s=“123456”，那么s[::-1]就==”654321”，直接这样判断，很多有reverse方法，或者reversed函数～不知对否

冷钟天 发表于 2016-7-4 18:32:06

本帖最后由 永恒的蓝色梦想 于 2020-6-30 18:06 编辑

>>> c=0
>>> for i in range(999,100,-1):
        for j in range(999,100,-1):
                a=str(i*j)
                b=a[::-1]
                if b==a:
                        if c<int(a):
                                c=int(a)
                                d=


>>> print('最大的回文数是',c,'乘数',d,'*',d)



为什么我发不错跟楼上一样的格式。。。。

幻世伽蓝 发表于 2016-7-5 16:00:57

def palindrome(n):
    a = []
    b = []
    while(n):
      result = n % 10
      a.append(result)
      n //= 10
    b = a.copy()
    b.reverse()
    if b == a:
      return 1
    else:
      return 0

number = []

for x in range(100, 1000):
    for y in range(100, 1000):
      i = x * y
      num = palindrome(i)
      if num:
            number.append(i)

print(max(number))


906609

#include <stdio.h>
int palindrome(int x)
{
    int num = 0,temp = x;
    while(x)
    {
       num = x % 10 + num *10;
       x /= 10;
    }
    if (num == temp)
      return 1;
    else
      return 0;
}

int max(int a)
{
    int n = 0,temp;
    while(a)
    {
      if(a > a)
      {
            a = a;
      }
      n++;
    }
    return a;
}

int main()
{
    int x, y, z, n = 0;
    int a;
    for(x = 100; x <= 999; x++)
    {
      for(y = 100; y <= 999; y++)
      {
            z = x * y;
            if(palindrome(z))
            {
                a = z;
                n++;
            }
      }
    }
    printf("%d",max(a));
    return 0;
}

c的代码运行程序总是停止运行，有没有大神指点一下吖{:5_92:}

幻世伽蓝 发表于 2016-7-5 16:04:00

冷钟天 发表于 2016-7-4 18:32
>>> c=0
>>> for i in range(999,100,-1):
        for j in range(999,100,-1):


表情左边有个“<>”样子的东西，这是专门发代码的{:5_91:}

冷钟天 发表于 2016-7-5 17:28:46

幻世伽蓝 发表于 2016-7-5 16:04
表情左边有个“”样子的东西，这是专门发代码的

好的，谢谢

gzt1993828 发表于 2016-7-26 18:39:14

本帖最后由 永恒的蓝色梦想 于 2020-6-30 18:06 编辑

def palin(n):
    if 100000<n<1000000:
      result=str(n)
      if result[:3]==result+result+result:
            return True
      else:
            return -1
    else:
      print('输入错误')
      return -1
Sum=[]   
for i in range(500,1000):
    for j in range(500,1000):
      if palin(i*j) is True:
            Sum.append(i*j)

Sum.sort()
Sum.reverse()
print(Sum)

始终 发表于 2016-8-12 02:42:35

def is_palin(s):
    n = len(s)
    i = 0
    while i < n / 2:
      if s != s[-(i + 1)]:
            return False
      i += 1
    return True


def findpalin(m, n):
    x = n * n
    y = (m - 1) * (m - 1)
    while y > x:
      if is_palin(str(y)):
            i = n
            while i < m:
                if y % i == 0 and y / i >= n and y / i < m:
                  return i, int(y / i), y
                i += 1
      y -= 1
    return None
print(findpalin(1000, 100))

(913, 993, 906609)

Plusenxue 发表于 2016-8-26 12:45:13

def ishuiwen(m):
    a = list(str(m))
    b = a.copy()
    a.reverse()
    if a == b:
      return True
    else:
      return False

result = []
for i in range(999,0,-1):
    for j in range(999,i-1,-1):
      k = i*j
      if ishuiwen(k):
            result.append(k)
            break
max(result)

toBeNot 发表于 2016-9-28 10:18:01

public class LargestPalindromeProduct
{
      // 判断整数n是不是回文数
      public static boolean isPalindrome(int n)
      {
                String s = String.valueOf(n);
                return new StringBuffer(s).reverse().toString().equals(s);
      }
      
      public static void main(String[] args)
      {
                int num = 0;   //保存回文数
                int x = 0;         //保存构成回文数的两个三位数因子
                int y = 0;
                for(int i = 999;i >= 100;i--)
                {
                        for(int j = 999;j >= 100;j--)
                        {
                              if(isPalindrome(i*j) && (i*j) > num)
                              {
                                        num = i * j;
                                        x = i;
                                        y = j;
                              }                        
                        }
                }
               
                System.out.println("两个三位数的乘积得到的回文数是：" + num + " = " + x + " * " + y);
      }
}

查看完整版本: 题目4：找出由两个三位数乘积构成的回文