2025年3月16日 星期日 甲辰(龙)年 月十五 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

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

时间:12-28来源:作者:点击数:44

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

运行结果:

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门