Akuna Capital Quant Dev #1 - 2018 (Python)

先说说题目吧，3题，120分钟。

1. 你的包里有m个正n边形，一共有k种颜色，每条边任意染色，染每个颜色的概率是相同的。然后你从这m个多边形里任取两个，求它们恰好是相同染色的概率，这里“相同”是指通过旋转能够重合，但是不能翻折。已知n=2*p，p是质数。

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

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

其中1,2题是把函数写出来就可以了，不用写input那部分，但是第3题需要写input部分，就是input().strip()那些。

我通过了所有的test case，但是还是挂了，表示不服。其中第一题用了一种自己认为很牛逼的方法，code也就差不多20行，复杂度很小，几乎都可以手算。comments写了很多，因为本人数学专业，用了抽象代数里群在集合上的作用的知识（轨道稳定化子定理），所以不知道考官能不能看懂，尽管我已经尽力解释地很通俗易懂了。如果考官是因为看不懂我的程序挂我，有点不甘心；如果是因为程序格式的问题，我心服口服，毕竟数学专业，代码写得不是那么规范。

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

复制代码

多边形染色问题（第一题）解析解（一行代码）。 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
问题不完全一样，但顺着这个思路不难自己推出来

谢谢。 楼主是应用数学博士今年毕业么?

咋觉得全部都是数学题而不是编程题啊

daizhenli94 发表于 2018-3-10 09:16
谢谢。 楼主是应用数学博士今年毕业么?

明年毕业

多谢楼主

楼主你们这个是金工类型吧

楼主，第一题怎么解啊？