程序员的算法趣题Q22: 不缠绕的纸杯电话

MoAir 发布于2021-09-09 09:33 / 1907人阅读

摘要：假设有几个小朋友以相同间隔围成圆周，要结对用纸杯电话相互通话。如果绳子交叉，很有可能会缠绕起来，所以结对的原则是不能让绳子交叉。如下所示运行结果上一篇异或杨辉三角形下一篇禁止右转本系列总目录参见程序员的算法趣题详细分析和全解

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云服务器最短路算法的程序最复杂的程序算法最厉害的算法想法程序不需要数据库的博客程序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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