题目4：找出由两个三位数乘积构成的回文,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

776667 发表于 2016-10-2 00:00:31

本帖最后由 776667 于 2016-10-2 00:03 编辑

def euler(x,y):
return max(])

if __name__ == '__main__':
print(euler(100,1000))

镜中人31 发表于 2016-10-6 20:25:04

final = 0
for i in range(100,1000):
for j in range(100,1000):
   num = i * j
   num2 = num
   s = str()
   while True:
         s = s + str(num2%10)
         num2 = num2//10
         if num2 == 0:
            break
   if int(s) == num:
         if num > final:
            final = num
            x = i
            y = j
print(x,y,final)

答案：913*993 = 906609

镜中人31 发表于 2016-10-6 20:28:03

镜中人31 发表于 2016-10-6 20:25
final = 0
for i in range(100,1000):
for j in range(100,1000):

我判断回文的方法是：
将乘积的最后一位数字以字符串的形式从后往前相加，然后再判断其整型和原乘积是否相等来确定是否为回文数，我使用的是python

jerryxjr1220 发表于 2016-10-10 10:05:35

906609

一行代码：
print max(])

梦想绘制者 发表于 2016-11-2 21:04:26

# Python 3.5实现最大的由两个三位数乘积构成的回文数
#
# 未来尽可能的提高效率，避免前后两数重复相乘的情况
# 例如：123 * 456 与 456 * 123
# 设置限制条件使得输出结果均为第一个数小于第二个数
# 当不满足条件时使用continue语句快速跳过
#
def maxPalindromeProduct(digitNum):
result = []
first = []
second = []
limit0 = 10 ** (digitNum - 1)
limit1 = 10 ** digitNum

for i in range(limit0 + 1,limit1):
   for j in range(limit0 + 1,limit1):
         if i > j:
            continue
         else:
            product = i * j
            if isPalindrome(product):
               result.append(product)
               first.append(i)
               second.append(j)

maxResult = max(result)
lenResult = len(result)
for k in range(lenResult):
   if result == maxResult:
         max_index = k
         break

return maxResult,first,second

def isPalindrome(n):
strN = str(n)
lenN = len(strN)
half = lenN //2

for i in range(half):
   if strN != strN[-i - 1]: # 等同于strN != strN.pop():
         return False
return True

print('最大的由两个三位数乘积构成的回文数为：',end = '')
maxPP = maxPalindromeProduct(3)
print('%d = %d×%d'%(maxPP,maxPP,maxPP))

>>>
最大的由两个三位数乘积构成的回文数为：906609 = 913×993

梦想绘制者 发表于 2016-11-2 21:10:41

jerryxjr1220 发表于 2016-10-10 10:05

很简洁，但是没有取得两个因数的值。{:9_237:}

jerryxjr1220 发表于 2016-11-2 23:11:23

梦想绘制者发表于 2016-11-2 21:10
很简洁，但是没有取得两个因数的值。

题目只是要乘积啊，并没有要显示2个乘数

tsembrace 发表于 2016-11-7 21:37:39

"""
一个回文数是指从左向右和从右向左都一样的数字。
最大的由两个两位数乘积构成的回文数9009=91*99；
找出最大的由两个三位数乘积构成的回文数。
"""
import copy
import time

start=time.clock()
#先定义一个判断回文数的函数
def isPalindrome(n):
m=n
list=[]
#把n的各位倒序插入列表
while m!=0:
   list.append(m%10)
   m=int(m/10)
#下一句不能简单的用listx=list代替
#这样无法真正生成一个新列表赋给listx,而是把list的引用赋给了listx
#如果修改list或者修改listx，其实都是修改的引用指向的内容
#会同时影响listx和list
listx=copy.deepcopy(list)
list.reverse()
if list==listx:
   return True
else:
   return False

list=[]
for i in range(100,1000):
for j in range(i,1000):
   s=i*j
   if isPalindrome(s):
         list.append(s)
print(list)
list.sort()
print(list[-1])
end=time.clock()
print("总耗时："+str(end-start)+"seconds")

lyciam 发表于 2016-11-16 18:36:36

def euler04(figures=3):
"""
一个回文数指的是从左向右和从右向左读都一样的数字。最大的由两个两位数乘积构成的回文数是9009=91*99.
找出最大的有由三个数乘积构成的回文数。
"""
snum = int('1' + '0' * (figures-1) )
enum = int('9' * figures)

result = {}
items = range(snum, enum+1)
count = 0
for n in items:
   for m in items[ count: ]:
         if list(str(n*m)) == list ( reversed ( str(n*m) ) ):
            result.update( {m*n : [ m , n ] } )
   count += 1
return result

numdict = euler04(3)
key = max( numdict.keys() )
print('{}:{} * {}'.format(key,numdict,numdict))

figures = 3 运行结果：906609:993 * 913
figures = 4 运行结果：99000099:9999 * 9901 （四位数效率就开始慢啦……）

〃陌殇、怀素 发表于 2016-11-20 21:28:14

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

int main()
{
int i,j;                //三位数乘数
int m,n,t;
int max=0;

for(i=100;i<1000;i++)
{
   for(j=100;j<1000;j++)
   {
         m =0;
         n=i*j;
         t = n;
         while(t!=0)       //倒转一个数
         {
            m=m*10+t%10;
            t=t/10;
            if(n == m)       //判断是否回文数
            {
               if(n > max)
                     max = m;
            }
         }
   }

}
printf("三位数乘积所得的最大回文数为： %d \n",max);
return 0;

}

joker11111 发表于 2016-11-20 22:13:24

本帖最后由 joker11111 于 2016-11-21 13:23 编辑

//-------------------------------------------
//04--找出最大的由3位数构成的回文数
//一个回文数是指从左读或者从右读都是一样的数
//如9009 = 91 * 99为最大的由两位数乘积构成的回文数
//-------------------------------------------
#include <windows.h>
#include <iostream>
#include <time.h>
#include <math.h>

using namespace std;

long int PalNum(int& m);
bool JuPalNum(long int& m);
int main()
{
clock_t start, finish;
double totaltime;
start = clock();

int m = 3;
cout << "最大的由" << m << "位数乘积构成的回文数为：" << PalNum(m) << endl;

finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
cout << "此程序的运行时间为" << totaltime << endl;
system("pause");
return 0;
}

/**********************************
功能：返回最大的由m位数乘积构成的回文数
***********************************/
long int PalNum(int& m)
{
int p, q, p1, q1;
long int s,max_s = 0;

for (p = pow(10, m - 1); p < pow(10, m); p++)
{
for (q = pow(10, m - 1); q < pow(10, m); q++)
{
s = p * q;
if (JuPalNum(s) && s > max_s)
{
max_s = s;
p1 = p;
q1 = q;
}
}
}
cout << p1 << "*" << q1 << "=" << max_s << endl;
return max_s;
}

/**********************************
功能：判断这个数是否为回文数
***********************************/
bool JuPalNum(long int& m)
{
int l = 0; //l为传入m的位数
long int n = 0, p = m, q;
while (p)
{
p /= 10;
l++;
}
p = m;
while (l)
{
q = p%10;
p /= 10;
n += q * pow(10,l-1);
l--;
}
if (n == m)
return true;
else
return false;
}

913*993 = 906609

style丶焚寂 发表于 2016-11-24 20:00:45

def huiwen():
res = []
res1=[]
for i in range(100,1000):
for j in range(100,1000):
k=i*j
listk=list(str(k))
relistk=listk[:]
relistk.reverse()
if listk==relistk:
res.append(k)
res1.append((i,j))

return res,res1

a,b=huiwen()
max_huiwen = max(a)
max_a,max_b=b

最大为906609，913*993
但是运行比较慢，没有优化，就是最简单的方法，平方级的复杂度

芒果加黄桃 发表于 2017-1-6 22:34:47

def isPalindromic(n):
t1 = list(str(n))
t2 = t1.copy()
t2.reverse()
if t1 == t2:
   return True
else:
   return False

start = time()
for number in range(999999,10001,-1):
if isPalindromic(number):
   for m in range(999,100,-1):
         if number // m > m:
            break
         if number % m == 0:
            n = number / m
            if n >= 100:
               print('回文数 %d 由三位数：%d 和三位数 %d 相乘获得' % (number ,m ,n ))
               break
print('cost %.3f sec' % (time()-start))

marmot 发表于 2017-1-10 16:47:59

import time
start=time.time()
i=1
for x in range(1000,101,-1):          #反着跳效率高
for y in range(1000,101,-1):
   num= x*y
   list1=str(num)
   if list1[:] == list1[::-1]:
         if num > i :          #取出最大数和构成它的因数
            i = num
            m= x
            n=y
         print(i,m,n)
print('用时%.5f' %(time.time()-start))

————————————————————————————————————
结果
906609 993 913
用时0.53135

marmot 发表于 2017-1-10 16:49:15

import time
start=time.time()
i=1
for x in range(100,1000):          #反着跳效率高
for y in range(100,1000):
   num= x*y
   list1=str(num)
   if list1[:] == list1[::-1]:
         if num > i :          #取出最大数和构成它的因数
            i = num
            m= x
            n=y
         print(i,m,n)
print('用时%.5f' %(time.time()-start))

——————————————————————
906609 913 993
用时0.50133

为什么正着跳效率还高点0.0

渡风发表于 2017-1-12 20:52:44

本帖最后由渡风于 2017-1-12 20:58 编辑

此代码使用matlab编程
Problem4所用时间为3.1214秒
Problem4的答案为906609
% 题目4：找出由两个三位数乘积构成的回文
function Output=Problem4(Input)
if nargin==0
Input=999;
Sum=Input*2;
end
tic
Flag=0;
for kk=Sum:-1:100+100
for ii=999:-1:100
   for jj=999:-1:100
         if ii+jj==kk&&ii<=jj
            Str=num2str(ii*jj);
            Other=Str(end:-1:1);
            if Str==Other
               Output=ii*jj;
               Flag=1;%用来跳出多重循环
               break
            end
         end
   end
   if Flag==1
         break
   end
end
   if Flag==1
         break
   end
end
toc
disp('此代码使用matlab编程')
disp(['Problem4所用时间为',num2str(toc)])
disp(['Problem4的答案为',num2str(Output)])
end

shinningpika 发表于 2017-1-23 18:17:10

a=[]
def check(d):
d=str(d)
e=d[::-1]
e=int(e)
d=int(d)
if (e+d)==d*2:
   a.append(d)
for i in range(100,999):
for each in range(150,200):
   d=i*each
   check(d)
print(a[:-1])

研究半天。。尴尬

FlySelf 发表于 2017-2-2 11:07:56

import time

def is_palindromic(number=100):
'判断是否为回文数'
flag = True
list_number = []

while number != 0:
   list_number.append(number % 10)
   number //= 10

length = len(list_number)
for n in range(0, length // 2):
   if list_number != list_number:
         flag = False
return flag

start = time.clock()
max_palindromic = 0
for i in range(100, 1000):
for j in range(100, 1000):
   if is_palindromic(i * j):
         if max_palindromic < (i * j):
            max_palindromic = i * j
         print('%d x %d = %d' %(i, j, i * j))
         break
print('最大的由两个三位数乘积构成的回文数为%d' %max_palindromic)
end = time.clock()
print('程序执行了%fs。' %(end - start))

执行结果：
993 X 913 = 906609
最大的由两个三位数乘积构成的回文数为906609
程序执行了1.310824s。

0mrli0 发表于 2017-2-20 18:33:46

本帖最后由 0mrli0 于 2017-2-20 18:34 编辑

/*找出最大的由两个三位数乘积构成的回文
分析：先判断一个六位数是否是回文，是然后判断能否找到两个三位数因子*/

#include <stdio.h>

int IsPalindrome(int n)//判断是不是回文
{
int i = 6;
int a = {0};
while(i)
{
   i--;
   a = n % 10;
   n = n / 10;
}
return (a==a && a==a && a==a) ? 1 : 0;
}

int Isfactoring(int n)//判断能否分解为两个三位数相乘
{
int i = 1000, test;
int flag = 0;
while(i > 100)
{
   i--;
   if(n%i == 0)
   {
         test = n / i;
         if(test>=100 && test<1000)
         {
            flag = 1;
            break;
         }
   }
}
return flag;
}
int main()
{
int i = 1000000, max = 0;
while(i>100000)
{
   i--;
   //max = (IsPalindrome(i) && Isfactoring(i)) ? i : max;
   if(IsPalindrome(i))
   {
         if(Isfactoring(i))
         {
            max = i;
            break;
         }
   }
}
printf("max palindrome = %d\n", max);
return 0;
}

max palindrome = 906609

Process returned 0 (0x0) execution time : 0.018 s

没有输出因子。。。

0mrli0 发表于 2017-2-20 20:16:51

/*题目：2520是最小的能被1-10中的每个数字整除的正整数。
   最小的能被1-20中的每个整数整除的正整数是多少。
分析：1.简单粗暴的是直接一个一个找。
   3.原来可以两个两个求公倍数*/
#include <stdio.h>
#include <stdlib.h>

int gcd(int a, int b)
{
int t;
if(b == 0)
{
t = a;
}
else
{
   t = gcd(b, a % b);
}
return t;
}
/*最小公倍数*/
int lcm(int a, int b)
{
int t;
t = a * b /gcd(a, b);
return t;
}
int main()
{
int i, t = 1;
for(i=2; i<=19; i++)
{
   t = lcm(t, i);
}
printf("t = %d",t);
return 0;
}
t = 232792560
Process returned 0 (0x0) execution time : 0.014 s

页: 1 [2] 3 4 5 6 7

鱼C论坛's Archiver