注:所谓回文数就是正序和倒序相等的数字,好比9009的倒序还是9009
在题目中,我们已经知道了这个回文数是2个三位数的乘积, 那我们可以很轻松的写出代码。
#定义数字倒转函数
def reverse(num):
strnum = str(num)[::-1]
return int(strnum)
max = None
for a in range(100, 1000):
for b in range(100, 1000):
rs = a * b
if rs == reverse(rs) and rs > max:
max = rs
print max
用这个方法我们是可以得到结果,但是效率好像不尽人意。 现在我们来分析下还可以怎么优化我们的程序:
1. 上述程序中,a和b的乘积会反复出现吗? 比如当a=132,b=528同a=528, b=132的结果是一样的,那我们通过设置b小于或大于a,是不是可以避免这样的情况。
2. 题目要求我们找的最大的乘积, 那2个三位数肯定也是很大, 我们用从大到小查询,是不是会比从小到大查询快很多呢,当我们找到的后一个回文数没有前一个大,那程序就可以终止了。
3. 两个三位数的乘积肯定是一个六位数, 而这个六位回文数数P我们可以用xyzzyx的形式表示,那我们可以得到下面的公式:
P = 100000x + 10000y + 1000z + 100z + 10y + x
P = 100001x + 10010y + 1100z
P = 11(9091x + 910y + 100z)
在这个公式中我们发现回文数是11的倍数,而11是质数,这也就表示不是a可以被11整除,就是b可以被11整除。那我们合理的利用11作为递进数是不是要比原来的1更效率呢?
通过上述分析,我们来重写代码:
#定义数字倒转函数
def reverse(num):
strnum = str(num)[::-1]
return int(strnum)
max = None
for a in range(999, 99, -1):
db = -1
start = 999
if a % 11 != 0:
start = 990
db = -11
for b in range(start, 99, db):
rs = a * b
if rs == reverse(rs):
if rs > max:
max = rs
else:
break
print max
经测试,原来的程序需要810000次循环,而优化后的程序只需要71533次循环, 性能提高了10倍多。
分享到:
相关推荐
将一个整数分解为两个数的积-comdiv.m 本程序可以将一个整数分解为两个整数的积,这两个整数同时是这个整数的最大因子,如250=25*10,255=17*15;
三位数乘两位数最大乘积.doc
问题描述:设n是一个正整数,将n分解为若干互不相同的自然数之和,且使这些自然数的乘积最大。 本讲义提供该问题的正确算法的自然语言描述及其严格证明。
两位数逆序乘积式,找出AB*CD=BA*DC,例如12*63=21*36
给出一个正整数a,要求分解成若干个正整数的乘积,即a = a1 * a2 * a3 * ... * an,并且1 ,问这样的分解的种数有多少。注意到a = a也是一种分解。 Input 第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1...
实现一多位十进制数和一个一位十进制数的乘法,被乘数和乘数均以ASCII码形式存放在内存中,结果以十进制数形式显示在屏幕上。
最大K乘积问题: 设I是一个n位十进制整数。如果将I划分为k段,则可得到k个整数。...试设计一个算法,对于给定的I和k,求出I的最大k乘积。 编程任务: 对于给定的I 和k,编程计算I 的最大k 乘积。
如果数组中有正数有负数,则最大乘积既可能是三个最大正数的乘积,也可能是两个最小负数(即绝对值最大)与最大正数的乘积。综上,我们在给数组排序后,分别求出三个最大正
实现算法: 给定两个整数u和v,它们分别有m和n位数字,且m≤n。用通常的乘法求uv的值需要O(mn)时间。我们可以将u和v均看作是有n位数字的大整数。用分治法在O(nlog3)时间内计算uv的值。当m时,此法效率不高。...
hutc-乘积最大 参考代码hutc-乘积最大 参考代码hutc-乘积最大 参考代码
乘积最大的拆分.zip
大整数分解问题:给定两个n位长二进制数x和y,求这两个数的乘积。时间复杂性控制在Θ(n1.6)
输入:三个整数,第一个n表示S的位数,第二个m表示分割的段数,第三个数为需要被分段的n位十进制数S。 n、m和S三个数中间空格相连,这里1,n,即S、S的最大m乘积、S的最小m和这三个数都用int型即可, 虽然,输出的数...
对称正定矩阵分解成正定矩阵乘积1
试编写程序,求各种分解方法中各加数乘积的最大值。 题目 2:有 n 个人参加一个马拉松接力游戏,游戏规定每个人可以根据自己的情况随时终止 游戏并由下一个人继续接力。由于每个人的情况不同,即使同一个人也不可能...
4.对存储乘积累加和得数组进行十进制个位化,即数组每位存的数值不超过9,即利用对10取模取余的方法,余数留在本位,模就当是进位就往上一位累加。 5对规范化的数值倒序输出就是得到大整型数乘积的结果。
分解质因数 分解质因数 分解质因数 分解质因数 分解质因数
# 给你一个正整数列表 L, 判断列表内所有数字乘积的最后一个非零数字的奇偶性。如果为奇数输出1,偶数则输出0。 # 输入示例 # 输入:L=[2,8,3,50] # 输出示例 # 输出:0 # 解析 # 在上题的基础上的改造题, 这里直接...
设n是一个正整数,现在要将n分解为若干个互不相同的自然数的和,且使这些数的乘积最大。