目錄

1. 前言

2. 遞推關系

3. 代碼及測驗

4. 后記

1. 前言

參見程式員的演算法趣題Q54: 偷懶的算盤

上一篇中給出的初始方案是暴力破解（或者說全量搜索）的方式，總共需要搜索10!=3628800種情況，因此非常耗時，

本篇給出基于動態規劃思想的題解，

2. 遞推關系

由于10個數每個只用計算一次，考慮已經執行了若干個數的運算（它們構成visited集合）,此時算盤上的計算結果為curSum，完成之后剩余的運算所需要的最少算珠移動數與之前若干個數的運算順序（以及相應的算珠移動數）是無關的，僅與curSum有關，由此可以得到本問題的子問題分解結構，如下所述，

令f(unvisited)表示（在當前已經求得的和—即visited中的數的和—的基礎上）執行剩余的unvisited的數的運算所需要的最少算珠移動數，注意，unvisited與visited是互補的，或者說一一對應的，則有以下遞推關系成立：

其中，unvisited表示一個集合，“unvisited-k”則表示從unvisited中洗掉一個元素k的操作，

基于以上遞推關系，可以以正向的標準的動態規劃的方式實作，也可以以遞回加Memoization的方式實作，鑒于后者代碼顯得更加簡潔，以下代碼采用后者，

因為10個數每個只能用一次，所以實際上visited或者unvisited（以下代碼中是用visited）可以用10位元的二進制數來表示，

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)

#3. Recursion + Memoization
memo = dict()
minMoves = 100
def search1(bit10, moves)->int:
    '''   
    Parameters
    ----------
    bit10 : int
        10 bits to represent whether each one of [1,2,...,10] is used.
        bit[0]:1; bit[1]:2; ...; bit[9]:10; 
    moves : number of moves up to now.
    Returns
    -------
        The minimum number of moves needed for the current condition.
    '''
    # print(bit10,moves)
    global minMoves
    if bit10 == 0b11_1111_1111:
        if minMoves > moves:
            minMoves = moves
            return    
        
    if (bit10, moves) in memo:        
        # Already visited, no need to continue.
        return    
    
    cur_sum = 0
    for k in range(10):
        if bit10>>k & 0x1 == 1:
            cur_sum = cur_sum + (k+1)
            
    for k in range(10):
        if bit10>>k & 0x1 == 0:                            
            _,cur_move = move(cur_sum, k+1)            
            search1(bit10|(0x1<<k),cur_move+moves)
    memo[(bit10, moves)] = minMoves
    
tStart = time.perf_counter()
search1(0,0)
tCost  = time.perf_counter() - tStart
print('moves={0}, tCost = {1:6.3f}(sec)'.format(minMoves,tCost))

#4. Recursion + Memoization
memo = dict()
def search2(bit10)->int:
    '''   
    Parameters
    ----------
    bit10 : int
        10 bits to represent whether each one of [1,2,...,10] is used.
        bit[0]:1; bit[1]:2; ...; bit[9]:10; 
    Returns
    -------
        The minimum number of moves needed for the current condition.
    '''
    # print(bit10)
    if bit10 == 0b11_1111_1111:
        return 0   
        
    if bit10 in memo:        
        # Already visited, no need to continue.
        return memo[bit10]   
    
    cur_sum = 0
    for k in range(10):
        if bit10>>k & 0x1 == 1:
            cur_sum = cur_sum + (k+1)
    minMoves = 100            
    for k in range(10):
        if bit10>>k & 0x1 == 0:                            
            _,cur_move = move(cur_sum, k+1)            
            moves = search2(bit10|(0x1<<k))
            if minMoves > (moves + cur_move):
                minMoves = (moves + cur_move)                
    memo[bit10] = minMoves
    return minMoves
    
tStart = time.perf_counter()
minMoves = search2(0)
tCost  = time.perf_counter() - tStart
print('moves={0}, tCost = {1:6.3f}(sec)'.format(minMoves,tCost))

運行結果：

moves=26, tCost = 0.028(sec)
moves=26, tCost = 0.007(sec)

4. 后記

以上包含兩種同為“Recursion+Memoization”策略的實作方式，后一種又比前一種還要再快4倍，相比原始的暴力破解方案則快了三個數量級，

search1()與search2()為什么會有4倍的速度差異呢？

search1()將到目前visited為止的算珠移動次數通過函式介面傳遞，然后在到達目標（即所有數都運算完的狀態）進行最小算珠移動次數判斷，并且以{visited, moves}作為狀態表示用于memo記憶，而Search2()則只計算從visited往后的最小算珠移動次數，因此只需要基于visited進行memo記憶，

很顯然，search1()所需要考慮的{visited, moves}所表示的狀態數會遠遠大于search2()的僅由visited所表示的狀態數，或許這就是兩者運算速度相差4倍的原因吧，

上一篇：程式員的演算法趣題Q53: 同數包夾

本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解