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

目錄

1. 問題描述

2. 解題分析

3. 代碼及測試

1. 問題描述

        用繩子連接配接紙杯制作“紙杯電話”——這應該勾起了很多人對理科實驗的回憶。如果把繩子拉直，對着一邊的紙杯講話，聲音就可以從另一邊的紙杯傳出。

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

        舉個例子，如果有 6 個小朋友，則隻要如下圖一樣結對，

        就可以順利用紙杯電話通話。也就是說，6 個人的時候，有 5 種結對方式。

        求：有 16 個小朋友的時候，一共有多少種結對方式？

2. 解題分析

        以f(N)表示當有N個小朋友時的結對組合方式數可以推導出以下遞推關系式：

        遞推過程以及筆算的結果如下所示： 

3. 代碼及測試

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

# -*- coding: utf-8 -*-
"""
Created on Wed Sep  8 07:41:50 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

def 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))   
           

運作結果：

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

        下一篇：Q23: 二十一點通吃

https://blog.csdn.net/chenxy_bwave/article/details/120234925

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