目錄
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
# from typing import List
# from queue import Queue
# from collections import deque
import itertools as it
import numpy as np
def 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 = 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全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/310518.html
標籤：其他