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