除了最“笨”的暴力搜索以外,没有找到什么头绪。
这个问题涉及到几个维度的搜索:
这种多个维度的搜索问题,维度的搜索顺序很重要。错误的维度搜索顺序可能会导致额外的时间甚至导致陷入死循环。比如说,本题如果以选择哪个数字为第一搜索维度的话,有些数字可能会不管用多少个都无法构成符合条件的表达式,因此就会陷入无限循环。
本题的最关键的一点是要用最少个数的数字。因此应该以个数为第一搜索维度。
算法流程如下:
有几个细节需要注意:
构造好表达式后,如何评估表达式的值。可以自写代码实现但是比较麻烦。Python中有eval()实现了这一功能,本题的焦点不在于表达式的值如何评估,所以在本题解中就偷懒使用eval()了。对于如何自写代码评估感兴趣的话,可以参考Q2的题解:https://www.cdsy.xyz/computer/programme/algorithm/221220/cd38838.html
- # -*- 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))
只想到了暴力搜索的方法,好在运行时间似乎还在可以接受的范围。至于是否还有更好的解法,在“偷看”答案之前,(反正已经有了一个解)还是让“思考”再飞一会儿^-^.