【算法趣题】Q02 数列的四则运算

前言

【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。

问题描述

组合的方法是在各个数字之间插入四则运算的运算符组成算式，然后计算算式的结果（某些数位之间可以没有运算符，但至少要插入1个运算符）

例） 1234 → 1+2×3-4=3

假设这里的条件是，组合算式的计算结果为“将原数字各个数位上的数逆序排序得到的数”，并且算式的运算按照四则运算的顺序进行（先乘除，后加减），那么位于100~999，符合条件的有以下几种情况。
351 → 3×51 = 153
621 → 6×21 = 126
886 → 8×86 = 688

求位于1000~9999，满足上述条件的数。

思考

根据组合方法的提示，各个数字之间的操作符可以有“”（无运算符），“+”（加法），“-”（减法），“*”（乘法），“/”（除法），即

operator = ['','+','-','*','/']

对于上例中的351，将351拆分为各个数的序列，有

a= 351

strList = list(str(a))

strList

['3', '5', '1']

将序列组合成3*51的算式，

formulaStr = strList[0]+'*'+strList[1]+''+strList[2]

formulaStr

'3*51'

计算算式的结果，

eval(formulaStr)

153

再深入思考，

• 位于1000~9999的数是个四位数，“将原数字各个数位上的数逆序排列得到的数”也应该是四位数，即末尾不等于“0”，否则倒序后的数不足4位。
  

• 如果用了“+”，最大的值只有999+9=1008，逆序排列如要得到原始值，原始最后位只能为1,而999+1=1000，也逆序排列后也得不到原始值，当然，“-”和“/”都不可能使结果达到4位。

• 如果用了“*”，其后面的数字肯定不能为“0”，否则计算结果肯定不足4位。

代码及结果

现在可以写代码了。附上python代码，及结果。

operator = ['','*']

for i in range(1000,10000):

    # 末尾数字不为0

    if(i % 10 == 0): continue

    # 将四位数转为各个数字的序列

    numList = list(str(i))

    for l in range(len(operator)):

        for m in range(len(operator)):

            for r in range(len(operator)):

                # 如果操作符不为''，其后的数字不为'0'

                if(operator[l]!='' and numList[1]=='0') or\

                (operator[m]!='' and numList[2]=='0'):

                    continue

                # 组合算式

                formulaStr = numList[0]+operator[l]+numList[1]+operator[m]\

                +numList[2]+operator[r]+numList[3]

                if(len(formulaStr)>4):# 一定要插入1个运算符

                    # 如果算式结果等于逆序排列后的数，输出结果

                    if(eval(formulaStr)==int(str(i)[::-1])):

                        print(str(i)+" ---> "+formulaStr+"="+str(i)[::-1]) 

结果为：

5931 ---> 5*9*31=1395