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