2025年3月15日 星期六 甲辰(龙)年 月十四 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

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

时间:12-30来源:作者:点击数:55

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. 后记

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

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门