本题来自《程序员的算法趣题》中的第30题。
假设有双插口和三插口两种插线板。墙壁上只有一个插座能使用。而需要用电的电器有N台,试考虑如何分配插线板。举个例子,当N=4时,共有4种插线板连接方式(使用同一个插线板,不考虑插口位置的差异,只考虑插线板的连接方法)。另外,要是所有插线板上最后没有多余的插口。N=4时的连接方式如下图所示。
图1 N=4时的连接情况示例(共4种)
求N=20时,插线板的插线连接方式有多少种(不考虑电源功率限制的问题)?
令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个电器时的总的插线连接方式数为:
以下为几种简单情况的手算结果(可以用于调试参考):
但是按照上一节的递归表达式编程计算得到结果(74801991)与原书给出的结果(63877262)不一致!原因在于以上递归计算中漏掉了一些重复的情况。比如说,当一个双口插线板的两个插口分配了相同的负载(即k1=k2)时,这个时候存在一些对称的配置,根据题设要求不能重复计算,需要排除掉。以下分双口插线板和三口插线板两种情况来分别考虑如何去重。
待追加
待追加
- # -*- 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)