目錄

1. 前言

2. 遞推關(guān)系

3. 代碼及測試

4. 后記

1. 前言

????????參見程序員的算法趣題Q54: 偷懶的算盤

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

? ? ? ? 本篇給出基于動態(tài)規(guī)劃思想的題解。

2. 遞推關(guān)系

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

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

????????其中，unvisited表示一個集合，“unvisited-k”則表示從unvisited中刪除一個元素k的操作。

?????? 基于以上遞推關(guān)系，可以以正向的標(biāo)準(zhǔn)的動態(tài)規(guī)劃的方式實現(xiàn)，也可以以遞歸加Memoization的方式實現(xiàn)，鑒于后者代碼顯得更加簡潔，以下代碼采用后者。

?????? 因為10個數(shù)每個只能用一次，所以實際上visited或者unvisited（以下代碼中是用visited）可以用10比特的二進(jìn)制數(shù)來表示。?

3. 代碼及測試

# -*- 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)#3. Recursion + Memoizationmemo = dict()minMoves = 100def 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<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< (moves + cur_move):                minMoves = (moves + cur_move)                    memo[bit10] = minMoves    return minMoves    tStart = time.perf_counter()minMoves = search2(0)tCost  = time.perf_counter() - tStartprint("moves={0}, tCost = {1:6.3f}(sec)".format(minMoves,tCost))

運行結(jié)果：

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

4. 后記

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

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

? ? ? ? search1()將到目前visited為止的算珠移動次數(shù)通過函數(shù)接口傳遞，然后在到達(dá)目標(biāo)（即所有數(shù)都運算完的狀態(tài)）進(jìn)行最小算珠移動次數(shù)判斷，并且以{visited, moves}作為狀態(tài)表示用于memo記憶。而Search2()則只計算從visited往后的最小算珠移動次數(shù)，因此只需要基于visited進(jìn)行memo記憶。

????????很顯然，search1()所需要考慮的{visited, moves}所表示的狀態(tài)數(shù)會遠(yuǎn)遠(yuǎn)大于search2()的僅由visited所表示的狀態(tài)數(shù)?；蛟S這就是兩者運算速度相差4倍的原因吧。

? ? ? ? 上一篇：程序員的算法趣題Q53: 同數(shù)包夾

????????本系列總目錄參見：程序員的算法趣題：詳細(xì)分析和Python全解

?