Re: [问卦] 这段code要怎么打?

楼主: a1919979 (狐狸精婊子)   2018-04-17 01:09:17
原题其实可以很简单的简化为几何的全等来说明。但是考量要以程式码实作我们还是从相对
轻松的集合来下手吧!
在比较{2,3,4},{4,5,6},{1,2,6}这三个集合是否几何排序上相似,最简单的方式就是作归
一化(?)后再比较。
这里的归一化函数F()很简单,将集合中某个元素借由平移摆到1的位子即可。而平移的作法
也只是简单将集合内各元素作同减运算罢了。
即我们可借由
F(2,3,4)={2-1,3-1,4-1}={1,2,3}

F(4,5,6)={4-3,5-3,6-3}={1,2,3}
两者归一化后结果相同来简单的判定两集合相似!
不过针对{1,2,6}呢?
很显然{1,2,3}!={1,2,6}
然而这是我们忽视掉可以平移到位子1的不仅仅是编号最小的元素这点。若我们针对位子6去
作平移,可以得到F(6,1,2)={1,-4,-3}这种怪怪的集合。
实际上这又是忽视了位子1往回平移一格在这种情形下并不是跑到不存在的位子0而是位子6
的事实。考量至此实际上F(6,1,2)={1,6-4=2,6-3=3}={1,2,3}。
总结来说要判断{a,b,c},{x,y,z}是否相似
等同于只要判断
F(a,b,c)==F(x,y,z)
or F(a,b,c)==F(y,z,x)
or F(a,b,c)==F(z,x,y)
的真假值即可
至于F()怎么写?自己的作业自己作啊!
作者: zzzz8931 (肥宅)   2017-04-17 01:09:00
这串居然活到半夜...
作者: chchan1111 (123)   2018-04-17 01:11:00
没人要看啦 阿宅滚
作者: p72910 (总是有刁民想害朕)   2018-04-17 01:13:00
你这时间复杂度是n平方,不优想个O(n)的再来吧,这题大概算法期中考考题拿来八卦版问乡民

Links booklink

Contact Us: admin [ a t ] ucptt.com