資訊專欄INFORMATION COLUMN
摘要：且聽下回分解基于動態(tài)規(guī)劃策略的優(yōu)化解法參見程序員的算法趣題偷懶的算盤上一篇程序員的算法趣題同數(shù)包夾程序員的算法趣題同數(shù)包夾本系列總目錄參見程序員的算法趣題詳細(xì)分析和全解程序員的算法趣題詳細(xì)分析和全解
目錄
????????剛看到這道題目一臉懵逼，印象中小時候并沒有學(xué)過算盤，沒想到啊。。。居然連這個都躲不過^-^??
????????關(guān)鍵點(diǎn)在于把算盤上算珠的擺放位置看作是數(shù)字的一種表達(dá)方式。算盤分上下段，在每個數(shù)位上，上段一個算珠表示5，下段一個算珠表示1。因此每個數(shù)位上的數(shù)在算盤上的表示可以用兩個數(shù)字來表示：(x//5, x%5), for x=0,1,2, ... ,9. 第1個數(shù)表示上段的表示，第2個數(shù)表示下段的表示。比如說8，用上段一個算珠表示5，用下段3個算珠表示3。（參見上面的圖例）。
????????本題要求計(jì)算的是1到10的和，總和只有55，所以只需要考慮兩位數(shù)，因此總共可以由4個數(shù)字來表示它在算盤上的表示：(x//50, (x%50)//10, (x%10)//5, (x%10)%5).
????????基于以上考慮，進(jìn)行一次加法所需要的算珠移動次數(shù)就是比較加法執(zhí)行前后算盤上的兩個數(shù)的表示的差分，即比較4個位置上的算珠個數(shù)的差異，對這些差異進(jìn)行求和即得所需要移動的算珠的總次數(shù)。
????????這里的關(guān)鍵是不要被神秘的算珠劃拉的動作所迷惑。。。我剛看到這道題目時腦海中模糊顯現(xiàn)的就是手指在算盤上靈活而詭異的劃拉動作。不用關(guān)心算珠劃拉的過程，只要關(guān)心算珠起始位置和最終位置即可！
# -*- 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: """ 當(dāng)前算盤上值為cursm時，再加上y需要移動算珠的個數(shù) 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))????????運(yùn)行結(jié)果：moves=26, tCost = 32.127(sec)?
? ? ? ? 太慢了！總共有10!=3628800種排列，所以暴力搜索需要非常長的時間。需要考慮優(yōu)化策略。
? ? ? ? 比如說動態(tài)規(guī)劃策略。。。一時還沒有想清楚。。。且聽下回分解^-^
? ? ? ? [2021-10-13]基于動態(tài)規(guī)劃策略的優(yōu)化解法參見：
????????程序員的算法趣題Q54: 偷懶的算盤(2)
? ? ? ? 上一篇：程序員的算法趣題Q53: 同數(shù)包夾
????????本系列總目錄參見：程序員的算法趣題：詳細(xì)分析和Python全解
????????
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/122545.html
摘要：目錄前言前言遞推關(guān)系遞推關(guān)系代碼及測試代碼及測試后記后記前言參見程序員的算法趣題偷懶的算盤上一篇中給出的初始方案是暴力破解或者說全量搜索的方式，總共需要搜索種情況，因此非常耗時。 目錄 1. 前言 2. 遞推關(guān)系 3. 代碼及測試 4. 后記 1. 前言 ????????參見程序員的算法趣...
摘要：假設(shè)有幾個小朋友以相同間隔圍成圓周，要結(jié)對用紙杯電話相互通話。如果繩子交叉，很有可能會纏繞起來，所以結(jié)對的原則是不能讓繩子交叉。如下所示運(yùn)行結(jié)果上一篇異或楊輝三角形下一篇禁止右轉(zhuǎn)本系列總目錄參見程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 1. 問...
摘要：可以在遍歷所有矩陣時，對各種出現(xiàn)的次數(shù)進(jìn)行計(jì)數(shù)，最后計(jì)數(shù)值為的個數(shù)即為所求結(jié)果。上一篇排序交換次數(shù)的最少化排序交換次數(shù)的最少化本系列總目錄參見程序員的算法趣題詳細(xì)分析和全解程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 1. 問題描述 ...
摘要：能以最少交換次數(shù)到達(dá)升序有序排列記為的數(shù)列記為就等價于從代表的節(jié)點(diǎn)在這張圖中到達(dá)對應(yīng)的節(jié)點(diǎn)的最短路徑長度。上一篇質(zhì)數(shù)矩陣質(zhì)數(shù)矩陣下一篇唯一的序列本系列總目錄參見程序員的算法趣題詳細(xì)分析和全解程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 ...
閱讀 3276·2021-11-22 14:44
閱讀 1122·2021-11-16 11:53
閱讀 1272·2021-11-12 10:36
閱讀 710·2021-10-14 09:43
閱讀 3702·2019-08-30 15:55
閱讀 3406·2019-08-30 14:14
閱讀 1746·2019-08-26 18:37
閱讀 3419·2019-08-26 12:12
