怎么用Python写算法题
这篇文章给大家介绍怎么用Python写算法题，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。
题目
题目描述
给你n根火柴棍，你可以拼出多少个形如"A+B=C"的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是00）。用火柴棍拼数字0-90−9的拼法如图所示：
注意：
加号与等号各自需要两根火柴棍
如果A≠B，则A+B=C与B+A=C视为不同的等式(A,B,C>=0)
n根火柴棍必须全部用上
输入格式
一个整数n(n<=24)。
输出格式
一个整数，能拼成的不同等式的数目。
输入输出样例
样例1:
输入14输出2
样例2
输入18输出9
解法
方法1:打表法
因为n的最大值只有24，那么可以直接提前把答案穷举出来。
# 0-9需要多少根火柴棒num =[6, 2, 5, 5, 4, 5, 6, 3, 7, 6]# 输入一个数，计算需要多少火柴棒def count(x): if x == 0: return 6 c = 0 while x > 0: digit = x % 10 c += num[digit] x = x // 10 return cresult = [0] * 24for n in range(10, 25): #10根火柴以下都是0，很明显 print("caculate ", n) for i in range(0, 10000): #假设单个数字最大值为10000 for j in range(0, 10000): if count(i) + count(j) + count(i+j) == n - 4: result[n-1] += 1print(result)上述代码在我的电脑上跑半天也出不来，最大值改成2000就可以。同样的代码，用Java很快就出结果了，足以说明Python并不适合这一类的题目。
public class Test { public static void main(String[] args) { int[] result = new int[24]; for(int i = 10; i <= 24; i++) { for(int j = 0; j < 10000; j++) { for(int k = 0; k < 10000; k++) { if(count(j) + count(k) + count(j+k) == i - 4) { result[i] += 1; } } } } for(int i = 0; i < 24; i++) { System.out.println(result[i]); } } public static int[] num = {6,2,5,5,4,5,6,3,7,6}; public static int count(int x) { if(x == 0) { return 6; } int c = 0; while (x > 0) { int digit = x % 10; c += num[digit]; x = x / 10; } return c; }}最后结果是{0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,8,9,6,9,29,39,38,65,88,128}。
但是虽然是穷举，但是上面代码有个问题，每次都要重复调用count，提前把count存起来就行了，虽然用Python还是很慢，但是能够在可接受时间内出结果。
# 0-9需要多少根火柴棒num =[6, 2, 5, 5, 4, 5, 6, 3, 7, 6]# 输入一个数，计算需要多少火柴棒def count(x): if x == 0: return 6 c = 0 while x > 0: digit = x % 10 c += num[digit] x = x // 10 return cCOUNT = [0] * 20000for i in range(0, 20000): COUNT[i] = count(i)result = [0] * 24for n in range(10, 25): print("caculate ", n) for i in range(0, 10000): for j in range(0, 10000): if COUNT[i] + COUNT[j] + COUNT[i+j] == n - 4: result[n-1] += 1print(result)方法2:优化上述方法
没有什么更好的方法，我们可以尽量减少循环次数，另外，如果能知道单个数的最大值，那就更好办了。
要想用最少的火柴棒拼出最大的数，那优先得拼出最大的数字个数，因为999肯定要比1111小，因为一个数字至少2个火柴，所以对于偶数个火柴，肯定是用拼成11111这样的最大，例如10根火柴，能拼出的最大数是11111，20个火柴，能拼出的最大数是1111111111。
假设最大值超过10000，那至少需要10根，能拼出11111，剩下10根分成8+2根，两个凑起来不可能超过10000，所以最大值不超过10000。
假设最大值可能位于[9000,10000)，至少需要12根，能拼出9111，剩下8根不可能加起来等于这个数。
假设最大值可能位于[8000,9000)，至少需要13根，更不可能。
假设最大值可能位于[7000,8000)，至少需要9根，也就是7111，剩下11根，，如果分成9+2，2根只能是1，所以9根必须拼成7110，不够数。
假设最大值可能位于[6000,7000)，至少需要12根，剩下8根也不行。
假设最大值可能位于[5000,6000)，至少需要11根，剩下9根能拼出的最大4位数是7xxx或者1xxx，加起来不可能是5000。对于[2000,5000)也一样。
假设最大值可能位于[1900,2000]，那么最少需要12根，1911，剩下的没法相加为1911。
依次分析，我们发现最大数不可能大于1111。通过程序结果来看，最大值为712。
改进之后，不用打表也能AC。
# 0-9需要多少根火柴棒num =[6, 2, 5, 5, 4, 5, 6, 3, 7, 6]# 输入一个数，计算需要多少火柴棒def count(x): if x == 0: return 6 c = 0 while x > 0: digit = x % 10 c += num[digit] x = x // 10 return cCOUNT = [0] * 713for i in range(0, 713): COUNT[i] = count(i)result = 0n = int(input())for i in range(0, 712): for j in range(0, 712): if i + j > 712: continue if COUNT[i] + COUNT[j] + COUNT[i+j] == n - 4: result += 1print(result)
关于怎么用Python写算法题就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
