Akuna Capital Quant Dev #1 - 2018 (Python)

第一题跟m没有关系吧

我猜八成是没看懂你程序

paris1129 发表于 2018-8-28 07:40
请问楼主，第一题怎么解？

补充内容 (2018-8-28 07:40):

不好意思，很长一段时间没上论坛了。这是我的代码（最后那个probability是主程序），是纯数学的方法，当时所有case都是正确的。不建议采用，正确的方法应该是动态规划吧，但是我确实不会。

1. """
   
2. 有 m
   
3. 个多边形，每个多边形有 n 条边，每条边可以有 k 中染色方式，求从多边形中取出两
   
4. 个多边形，染色相同的概率，另如果 rotate 之后染色相同也算相同，但不能翻折
   
5. """
   
6. def numbertolist(num,n,k):
   
7.     l=[0]*n
   
8.     i=n-1
   
9.     while num:
   
10.         l[i]=num%k
    
11.         num=num//k
    
12.         i-=1
    
13.     return l
    
14. 
    
15. def rotate(l,i):
    
16.     return l[i::]+l[0:i]
    
17.    
    
18. 
    
19. def check(l1,l2):
    
20.     for i in range(1,len(l1)):
    
21.         if l1==rotate(l2,i):
    
22.             return True
    
23.     return False
    
24. 
    
25. def category(n,k):
    
26.     dic={}
    
27.     for num in range(k**n):
    
28.         lis=numbertolist(num,n,k)
    
29.         flag=0
    
30.         for i in range(len(dic)):
    
31.             if check(lis,dic[i][0]):
    
32.                 dic[i].append(lis)
    
33.                 flag=1
    
34.                 break
    
35.         if flag==0:
    
36.             dic[len(dic)]=[lis]
    
37.     return [len(dic[key]) for key in dic]
    
38. 
    
39. def probability(n,k):
    
40.     return sum([x**2 for x in category(n,k)])

复制代码

翻出了一个考完之后重写的带comments的代码。

多边形染色问题（第一题）解析解（一行代码）。 O(1) 时间/空间复杂度。

您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

求解思路可参考：
https://math.stackexchange.com/questions/449292/coloring-sides-of-a-polygon
问题不完全一样，但顺着这个思路不难自己推出来