目錄
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: 異或楊輝三角形
下一篇：Q27: 禁止右轉
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298612.html
標籤：其他