您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q30: 插线板连接方式

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

1. 问题描述

本题来自《程序员的算法趣题》中的第30题。

假设有双插口和三插口两种插线板。墙壁上只有一个插座能使用。而需要用电的电器有N台,试考虑如何分配插线板。举个例子,当N=4时,共有4种插线板连接方式(使用同一个插线板,不考虑插口位置的差异,只考虑插线板的连接方法)。另外,要是所有插线板上最后没有多余的插口。N=4时的连接方式如下图所示。

图1 N=4时的连接情况示例(共4种)

求N=20时,插线板的插线连接方式有多少种(不考虑电源功率限制的问题)?

2. 递归表达式

令f(N)表示要用电的电器为N台时的插线连线方式数。

很显然,f(1) = 1,此时直接将设备插在墙壁的插孔上就可以了。

当N>=2时,必须使用插线板来扩容。

第1级插线板有两种情况,即双口插线板或者三口插线板。

Case1: 考虑第1级插线板用双口插线板,假设双口插线板的两个插口下的子网络分别提供k1和k2个有效插口数(插线板自身也要消耗插口数,不算在有效插口数内)。则k1和k2必须满足以下条件:

第一个条件源自于“不能有多余的插口”这一限制条件。进一步,由于“使用同一个插线板,不考虑插口位置的差异,只考虑插线板的连接方法”,即{插口1的子网络提供k1个有效插口数,插口2的子网络提供k2个有效插口数}的连接方法与{插口1的子网络提供k2个有效插口数,插口2的子网络提供k1个有效插口数}视为相同的方案,不重复计算。因此可以不失一般性地假定

由此可以得到递归表达式:

Case2: 考虑第1级插线板用三口插线板,假设三口插线板的三个插口下的子网络分别提供k1、k2和k3个有效插口数(插线板自身也要消耗插口数,不算在有效插口数内)。则k1、k2和k3必须满足以下条件:

同理可得递归表达式:

最后,N个电器时的总的插线连接方式数为:

以下为几种简单情况的手算结果(可以用于调试参考):

3. 去重(repetition removal)

但是按照上一节的递归表达式编程计算得到结果(74801991)与原书给出的结果(63877262)不一致!原因在于以上递归计算中漏掉了一些重复的情况。比如说,当一个双口插线板的两个插口分配了相同的负载(即k1=k2)时,这个时候存在一些对称的配置,根据题设要求不能重复计算,需要排除掉。以下分双口插线板和三口插线板两种情况来分别考虑如何去重。

3.1 双口插线板的去重

待追加

3.2 三口插线板的去重

待追加

4. 代码和测试

# -*- coding: utf-8 -*-
"""
Created on Tue Aug 17 13:21:23 2021

@author: chenxy
"""

import time

class Solution:

    def patchPanelConnect(self, num):

        memo = dict()

        def recur(num): # Recursive core
            if num == 0:
                print('patchPanelConnectFast(): invalid input parameter')
            if num == 1:
                #print('patchPanelConnect({0}) = {1}'.format(num,1))
                return 1

            if num in memo:
                return memo[num]
                        
            # using two-port patch panel as the first stage
            sum2 = 0
            for n1 in range(1, num//2+1): 
                for n2 in range(n1, num-n1+1): 
                    if n2 == (num - n1):
                        if n2 == n1:                        
                            sum2 = sum2 + recur(n1) * (recur(n1)+1)/2
                        else:
                            sum2 = sum2 + recur(n1) * recur(n2)
                            
            
            # using three-port patch panel as the first stage
            sum3 = 0
            for n1 in range(1, (num//3+1)): # 
                for n2 in range(n1,(num-n1)//2+1): # 
                    for n3 in range(n2,(num-n1-n2+1)):# n3 = n2,n2+1,...num-n1-n2
                        if n3 == (num - (n1 + n2)):
                            if n1 == n2 and n2 == n3:                            
                                sum3 = sum3 + recur(n1) * (recur(n1)+1) * (recur(n1)+2)/6
                            elif n1 == n2:
                                sum3 = sum3 + recur(n1) * (recur(n1)+1) * recur(n3)/2
                            elif n1 == n3:
                                sum3 = sum3 + recur(n1) * recur(n2) * (recur(n1)+1)/2
                            elif n2 == n3:    
                                sum3 = sum3 + recur(n1) * recur(n2) * (recur(n2)+1)/2                                
                            else:
                                sum3 = sum3 + recur(n1) * recur(n2) * recur(n3)
    
            #print('patchPanelConnect({0}) = {1}'.format(num,(sum2+sum3)))
            memo[num] = (sum2 + sum3)
            return (sum2 + sum3)

        return recur(num)

测试如下:

if __name__ == '__main__':

    sln   = Solution()

    # print('num = 7, ans = ', sln.patchPanelConnect(7))    
    # print('num = 10, ans = ', sln.patchPanelConnect(10))
    
    # Testcase1    
    for num in range(4,21,4):
        tStart = time.time()    
        numOfConnect = sln.patchPanelConnect(num)
        tElapsed = time.time() - tStart        
        print('num = {0:2.0f}, connect methods = {1:8.0f}, tCost = {2:6.3f}(sec)'.format(num, numOfConnect,tElapsed))

运行结果:

num = 4, connect methods = 4, tCost = 0.000(sec)

num = 8, connect methods = 156, tCost = 0.000(sec)

num = 12, connect methods = 9802, tCost = 0.000(sec)

num = 16, connect methods = 750908, tCost = 0.000(sec)

num = 20, connect methods = 63877262, tCost = 0.000(sec)

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