程序員的算法趣題Q22: 不纏繞的紙杯電話

MoAir 發(fā)布于2021-09-09 09:33 / 1989人閱讀

摘要：假設(shè)有幾個(gè)小朋友以相同間隔圍成圓周，要結(jié)對用紙杯電話相互通話。如果繩子交叉，很有可能會纏繞起來，所以結(jié)對的原則是不能讓繩子交叉。如下所示運(yùn)行結(jié)果上一篇異或楊輝三角形下一篇禁止右轉(zhuǎn)本系列總目錄參見程序員的算法趣題詳細(xì)分析和全解

1. 問題描述

2. 解題分析

3. 代碼及測試

1. 問題描述

????????用繩子連接紙杯制作“紙杯電話”——這應(yīng)該勾起了很多人對理科實(shí)驗(yàn)的回憶。如果把繩子拉直，對著一邊的紙杯講話，聲音就可以從另一邊的紙杯傳出。

????????假設(shè)有幾個(gè)小朋友以相同間隔圍成圓周，要結(jié)對用紙杯電話相互通話。如果繩子交叉，很有可能會纏繞起來，所以結(jié)對的原則是不能讓繩子交叉。

????????舉個(gè)例子，如果有 6 個(gè)小朋友，則只要如下圖一樣結(jié)對，

????????就可以順利用紙杯電話通話。也就是說，6 個(gè)人的時(shí)候，有 5 種結(jié)對方式。

????????求：有 16 個(gè)小朋友的時(shí)候，一共有多少種結(jié)對方式？

2. 解題分析

????????以f(N)表示當(dāng)有N個(gè)小朋友時(shí)的結(jié)對組合方式數(shù)可以推導(dǎo)出以下遞推關(guān)系式：

????????遞推過程以及筆算的結(jié)果如下所示：?

3. 代碼及測試

????????基于以上遞推關(guān)系，代碼就顯得微不足道了。如下所示：

# -*- coding: utf-8 -*-"""Created on Wed Sep  8 07:41:50 2021@author: chenxy"""import sysimport timeimport datetimeimport math# import randomfrom   typing import List# from   queue import Queue# from   collections import dequeimport itertools as itdef paringGame(N:int)->int:    memo = dict()    memo[0] = 1        for n in range(2,N+1,2):                nums = 0        for m in range((n//2)):            # print(n,m)            nums += memo[2*m] * memo[n-2-2*m]        memo[n] = nums            return memo[N]if __name__ == "__main__":            for N in range(16,30,4):                    tStart = time.time()            nums = paringGame(N)                tCost  = time.time() - tStart        print("Pairing combination numbers for {0} = {1}, tCost = {2:6.3f}(sec)".format(N,nums,tCost))

運(yùn)行結(jié)果：

? ? ? ? 上一篇：Q21: 異或楊輝三角形

? ? ? ? 下一篇：Q27: 禁止右轉(zhuǎn)

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