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

MoAir 發布于2021-09-09 09:33 / 2005人閱讀

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

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

運行結果：

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

? ? ? ? 下一篇：Q27: 禁止右轉

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

GPU云服務器云服務器最短路算法的程序最復雜的程序算法最厲害的算法想法程序不需要數據庫的博客程序

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

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

一篇文章搞定前端面試

摘要：客戶端發送包到服務器，并進入狀態，等待服務器確認。再進一步接收到客戶端的就進入狀態。通常情況下連接就是連接，因此連接一旦建立通訊雙方開始互發數據進行通信，直到其中一方或雙方斷開連接為止。統一資源定位符。本文旨在用最通俗的語言講述最枯燥的基本知識面試過前端的老鐵都知道，對于前端，面試官喜歡一開始先問些HTML5新增元素啊特性啊，或者是js閉包啊原型啊，或者是css垂直水平居中怎么實現...

ISherry 2019-08-02 11:39 評論0 收藏0
一篇文章搞定前端面試

摘要：客戶端發送包到服務器，并進入狀態，等待服務器確認。再進一步接收到客戶端的就進入狀態。通常情況下連接就是連接，因此連接一旦建立通訊雙方開始互發數據進行通信，直到其中一方或雙方斷開連接為止。統一資源定位符。本文旨在用最通俗的語言講述最枯燥的基本知識面試過前端的老鐵都知道，對于前端，面試官喜歡一開始先問些HTML5新增元素啊特性啊，或者是js閉包啊原型啊，或者是css垂直水平居中怎么實現...

Airmusic 2019-08-30 15:54 評論0 收藏0
一篇文章搞定前端面試

摘要：客戶端發送包到服務器，并進入狀態，等待服務器確認。再進一步接收到客戶端的就進入狀態。通常情況下連接就是連接，因此連接一旦建立通訊雙方開始互發數據進行通信，直到其中一方或雙方斷開連接為止。統一資源定位符。本文旨在用最通俗的語言講述最枯燥的基本知識面試過前端的老鐵都知道，對于前端，面試官喜歡一開始先問些HTML5新增元素啊特性啊，或者是js閉包啊原型啊，或者是css垂直水平居中怎么實現...

lavnFan 2019-08-23 12:13 評論0 收藏0
程序員的算法趣題Q54: 偷懶的算盤

摘要：且聽下回分解基于動態規劃策略的優化解法參見程序員的算法趣題偷懶的算盤上一篇程序員的算法趣題同數包夾程序員的算法趣題同數包夾本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 1. 問題描述 ??...

wangzy2019 2021-10-14 09:43 評論0 收藏0
程序員的算法趣題Q45: 排序交換次數的最少化

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

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