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

wangzy2019 發布于2021-10-14 09:43 / 698人閱讀

摘要：且聽下回分解基于動態規劃策略的優化解法參見程序員的算法趣題偷懶的算盤上一篇程序員的算法趣題同數包夾程序員的算法趣題同數包夾本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解

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 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:    """    當前算盤上值為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 = 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))

????????運行結果：moves=26, tCost = 32.127(sec)?

4. 后記

? ? ? ? 太慢了！總共有10!=3628800種排列，所以暴力搜索需要非常長的時間。需要考慮優化策略。

? ? ? ? 比如說動態規劃策略。。。一時還沒有想清楚。。。且聽下回分解^-^

? ? ? ? [2021-10-13]基于動態規劃策略的優化解法參見：

????????程序員的算法趣題Q54: 偷懶的算盤(2)

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

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

????????

GPU云服務器云服務器最短路算法的程序最復雜的程序算法最厲害的算法想法程序偷懶

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/122545.html

程序員的算法趣題Q54: 偷懶的算盤(2)

摘要：目錄前言前言遞推關系遞推關系代碼及測試代碼及測試后記后記前言參見程序員的算法趣題偷懶的算盤上一篇中給出的初始方案是暴力破解或者說全量搜索的方式，總共需要搜索種情況，因此非常耗時。目錄 1. 前言 2. 遞推關系 3. 代碼及測試 4. 后記 1. 前言 ????????參見程序員的算法趣...

daydream 2021-10-14 09:43 評論0 收藏0
程序員的算法趣題Q22: 不纏繞的紙杯電話

摘要：假設有幾個小朋友以相同間隔圍成圓周，要結對用紙杯電話相互通話。如果繩子交叉，很有可能會纏繞起來，所以結對的原則是不能讓繩子交叉。如下所示運行結果上一篇異或楊輝三角形下一篇禁止右轉本系列總目錄參見程序員的算法趣題詳細分析和全解目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 1. 問...

MoAir 2021-09-09 09:33 評論0 收藏0
程序員的算法趣題Q46: 唯一的OX序列

摘要：可以在遍歷所有矩陣時，對各種出現的次數進行計數，最后計數值為的個數即為所求結果。上一篇排序交換次數的最少化排序交換次數的最少化本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 1. 問題描述 ...

y1chuan 2021-09-30 09:47 評論0 收藏0
程序員的算法趣題Q45: 排序交換次數的最少化

摘要：能以最少交換次數到達升序有序排列記為的數列記為就等價于從代表的節點在這張圖中到達對應的節點的最短路徑長度。上一篇質數矩陣質數矩陣下一篇唯一的序列本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 ...

flybywind 2021-09-29 09:35 評論0 收藏0