摘要：且听下回分解基于动态规划策略的优化解法参见程序员的算法趣题偷懒的算盘上一篇程序员的算法趣题同数包夹程序员的算法趣题同数包夹本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解
目录
刚看到这道题目一脸懵逼，印象中小时候并没有学过算盘，没想到啊。。。居然连这个都躲不过^-^
关键点在于把算盘上算珠的摆放位置看作是数字的一种表达方式。算盘分上下段，在每个数位上，上段一个算珠表示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个位置上的算珠个数的差异，对这些差异进行求和即得所需要移动的算珠的总次数。
这里的关键是不要被神秘的算珠划拉的动作所迷惑。。。我刚看到这道题目时脑海中模糊显现的就是手指在算盘上灵活而诡异的划拉动作。不用关心算珠划拉的过程，只要关心算珠起始位置和最终位置即可！
# -*- coding: utf-8 -*-"""Created on Tue Oct 12 07:43:10 2021@author: chenxy"""# import sysimport time# import datetime# import math# import random# from typing import List# from queue import Queue# from collections import dequeimport itertools as itimport 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%5 return z, abs(a1-b1)+abs(a2-b2)+abs(a3-b3)+abs(a4-b4)tStart = time.perf_counter()minMoves = 100for 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 = movestCost = time.perf_counter() - tStartprint("moves={0}, tCost = {1:6.3f}(sec)".format(minMoves,tCost))运行结果：moves=26, tCost = 32.127(sec)
太慢了！总共有10!=3628800种排列，所以暴力搜索需要非常长的时间。需要考虑优化策略。
比如说动态规划策略。。。一时还没有想清楚。。。且听下回分解^-^
[2021-10-13]基于动态规划策略的优化解法参见：
本系列总目录参见：程序员的算法趣题：详细分析和Python全解
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/122545.html
摘要：目录前言前言递推关系递推关系代码及测试代码及测试后记后记前言参见程序员的算法趣题偷懒的算盘上一篇中给出的初始方案是暴力破解或者说全量搜索的方式，总共需要搜索种情况，因此非常耗时。 目录 1. 前言 2. 递推关系 3. 代码及测试 4. 后记 1. 前言 参见程序员的算法趣...
摘要：假设有几个小朋友以相同间隔围成圆周，要结对用纸杯电话相互通话。如果绳子交叉，很有可能会缠绕起来，所以结对的原则是不能让绳子交叉。如下所示运行结果上一篇异或杨辉三角形下一篇禁止右转本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问...
摘要：可以在遍历所有矩阵时，对各种出现的次数进行计数，最后计数值为的个数即为所求结果。上一篇排序交换次数的最少化排序交换次数的最少化本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...
摘要：能以最少交换次数到达升序有序排列记为的数列记为就等价于从代表的节点在这张图中到达对应的节点的最短路径长度。上一篇质数矩阵质数矩阵下一篇唯一的序列本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 ...
阅读 3122·2021-11-22 14:44
阅读 949·2021-11-16 11:53
阅读 1045·2021-11-12 10:36
阅读 503·2021-10-14 09:43
阅读 3447·2019-08-30 15:55
阅读 3238·2019-08-30 14:14
阅读 1575·2019-08-26 18:37
阅读 3246·2019-08-26 12:12
