程序员的算法趣题|程序员的算法趣题Q54: 偷懒的算盘算法趣题|python|算法

目录

1. 问题描述
2. 解题分析
3. 代码及测试
4. 后记
1. 问题描述
文章图片

刚看到这道题目一脸懵逼，印象中小时候并没有学过算盘，没想到啊。。。居然连这个都躲不过^-^
2. 解题分析关键点在于把算盘上算珠的摆放位置看作是数字的一种表达方式。算盘分上下段，在每个数位上，上段一个算珠表示5，下段一个算珠表示1。因此每个数位上的数在算盘上的表示可以用两个数字来表示：(x//5, x%5), for x=0,1,2, ... ,9. 第1个数表示上段的表示，第2个数表示下段的表示。比如说8，用上段一个算珠表示5，用下段3个算珠表示3。（参见上面的图例）。
本题要求计算的是1到10的和，总和只有55，所以只需要考虑两位数，因此总共可以由4个数字来表示它在算盘上的表示：(x//50, (x%50)//10, (x%10)//5, (x%10)%5).
基于以上考虑，进行一次加法所需要的算珠移动次数就是比较加法执行前后算盘上的两个数的表示的差分，即比较4个位置上的算珠个数的差异，对这些差异进行求和即得所需要移动的算珠的总次数。
这里的关键是不要被神秘的算珠划拉的动作所迷惑。。。我刚看到这道题目时脑海中模糊显现的就是手指在算盘上灵活而诡异的划拉动作。不用关心算珠划拉的过程，只要关心算珠起始位置和最终位置即可！
3. 代码及测试

# -*- coding: utf-8 -*- """ Created on Tue Oct 12 07:43:10 2021@author: chenxy """# import sys import time # import datetime # import math # import random # fromtyping import List # fromqueue import Queue # fromcollections import deque import itertools as it import numpy as npdef move(x: int, y: int)->int: ''' 当前算盘上值为cursm时，再加上y需要移动算珠的个数Parameters ---------- x : int The current number in abacus. y : int The number to be added.Returns ------- int The number of abacus-stone being moved in the above operation.''' # The representation of x a1 = 1 if x>=50 else 0 a2 = (x%50) // 10 a3 = 1 if (x%10)>=5 else 0 a4 = x%5# The representation of x+y z= x + y b1 = 1 if z>=50 else 0 b2 = (z%50) // 10 b3 = 1 if (z%10)>=5 else 0 b4 = z%5return z, abs(a1-b1)+abs(a2-b2)+abs(a3-b3)+abs(a4-b4)tStart = time.perf_counter() minMoves = 100 for p in it.permutations(range(1,11)): cursum = 0 moves= 0 for k in range(10): cursum, move_tmp = move(cursum,p[k]) moves = moves + move_tmp if minMoves > moves: minMoves = moves tCost= time.perf_counter() - tStart print('moves={0}, tCost = {1:6.3f}(sec)'.format(minMoves,tCost))

运行结果：moves=26, tCost = 32.127(sec)

4. 后记太慢了！总共有10!=3628800种排列，所以暴力搜索需要非常长的时间。需要考虑优化策略。
比如说动态规划策略。。。一时还没有想清楚。。。且听下回分解^-^

上一篇：程序员的算法趣题Q53: 同数包夹
本系列总目录参见：程序员的算法趣题：详细分析和Python全解
【程序员的算法趣题|程序员的算法趣题Q54: 偷懒的算盘】