程序员的算法趣题Q41: 用1个数表达1234

1. 问题描述

2. 解题分析

除了最“笨”的暴力搜索以外，没有找到什么头绪。

这个问题涉及到几个维度的搜索：

1. 用哪个数字
2. 用几个
3. 如何构成表达式

这种多个维度的搜索问题，维度的搜索顺序很重要。错误的维度搜索顺序可能会导致额外的时间甚至导致陷入死循环。比如说，本题如果以选择哪个数字为第一搜索维度的话，有些数字可能会不管用多少个都无法构成符合条件的表达式，因此就会陷入无限循环。

本题的最关键的一点是要用最少个数的数字。因此应该以个数为第一搜索维度。

算法流程如下：

有几个细节需要注意：

1. 关于除法是采用整数除法，在python中有“//”表示整数除法，可以方便使用
2. 允许多位数的存在。包括多位数的遍历有不同的方法，本题中采用的方式，假设另有一个空的运算符‘’，如果两个数字之间插入一个空运算符‘’就表示构成了两位数。构造多位数的话则一次类推。这样做的好处是空操作符‘’和其他4个有效运算符可以统一对待，因此由k个n构成的表达式时就相当于在k个n的(k-1)个位置上任意插入不同的运算符，处理起来非常方便。这一构造方法最先用于Q2的解答，请参考。

构造好表达式后，如何评估表达式的值。可以自写代码实现但是比较麻烦。Python中有eval()实现了这一功能，本题的焦点不在于表达式的值如何评估，所以在本题解中就偷懒使用eval()了。对于如何自写代码评估感兴趣的话，可以参考Q2的题解：https://www.cdsy.xyz/computer/programme/algorithm/221220/cd38838.html

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Sun Sep 26 08:08:54 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
from   collections import deque
import itertools as it
import numpy as np

def expr_gen_eval(n,k,target):    
    op  = ['+', '-', '*', '//','']    
    for ops in it.product(op,repeat = k-1):
        # print(ops)
        exprlist = (2*k-1) * [str(n)]
        for i in range(k-1):
            exprlist[2*i+1] = ops[i]
        exprstr = ''.join(exprlist)
        # print(exprstr)
        rslt = eval(exprstr)
        if rslt == target:
            return True,exprstr
    return False,''

target = 1234
k      = 1
isFound= False
tStart = time.perf_counter()
while 1:
    print('k = {0}'.format(k))
    for n in range(1,10):
        # Forming math expression with k n's and {+,-,*,/,''}
        isFound,exprstr = expr_gen_eval(n, k, target)
        if isFound == True:
            break
    if isFound == True:
        break
    k = k + 1
tCost  = time.perf_counter() - tStart
print('(n,k)=({0},{1}, exprstr={2}, tCost = {3:6.3f}(sec))'.format(n,k,exprstr,tCost))
    
    

运行结果：(n,k)=(9,7, exprstr=99999//9//9, tCost = 1.303(sec))

4. 后记

只想到了暴力搜索的方法，好在运行时间似乎还在可以接受的范围。至于是否还有更好的解法，在“偷看”答案之前，（反正已经有了一个解）还是让“思考”再飞一会儿^-^.