程序员的算法趣题Q54: 偷懒的算盘

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种排列，所以暴力搜索需要非常长的时间。需要考虑优化策略。

比如说动态规划策略。。。一时还没有想清楚。。。且听下回分解^-^

[2021-10-13]基于动态规划策略的优化解法参见：

程序员的算法趣题Q54: 偷懒的算盘(2)