【CS50x(2022)】ProblemSet3 - Tideman 題解(Selection sort) - RitaChien's Blog

[utterances-bot]

【CS50x(2022)】ProblemSet3 - Tideman 題解(Selection sort) - RitaChien's Blog

這是目前在 CS50x 課程中遇到的最難的題目了，如果不把思考邏輯好好整理一遍，下次再回顧應該還是要花很多時間理解一遍。

https://ritachien.github.io/posts/ab8ef72d/

[lushan1688]

感谢作者！能看到中文的解释太开心了！谢谢你

[ritachien]

沒想到真的會有人來看，謝謝你的回饋~ p.s. 回來看的時候才發現我把 bubble sort 和 selection sort 的解法貼反了 😅

[Fred-Zi]

感谢作者！自己英文水平还不够高，看你的博客更容易理解很多！

[Yuan104]

关于这题一直有一个问题，想请教作者。在一些情况下，出现小循环，例如a>b>c>a，并不影响d大于a、b、c，在这时d仍然符合题目中关于获胜者"source"的定义（the winner of the election should be the “source” of the graph (i.e. the candidate that has no arrow pointing at them)。而在作者提供的思路下是杜绝了“小循环”的产生，而且网上基本上都是跟作者一样的思路。不知道是我对题目的理解有问题还是有其他说法呢？希望能得到帮助，谢谢！

[ritachien]

Hi, @Yuan104 不知道我有沒有正確理解你的問題: 假設已經確定 d>a、d>b、d>c，是否還有確認 abc 之間存在小循環的意義?

如果你的問題是上面這樣，那杜絕小循環產生的原因是因為題目針對 Tideman voting 的定義有 3 個步驟: Tally → Sort → Lock，其中 Lock 步驟要杜絕小循環產生(原文: so long as locking in that pair does not create a cycle in the graph)。最後 Once the graph is complete, the source of the graph (the one with no edges pointing towards it) is the winner!

投票的 winner 要在投票意向圖畫完後才能決定(所以我不能中途決定 d 贏了，要跑完整個流程)，而畫圖的過程要杜絕循環產生。

希望有回答到你的問題。如果沒有，也歡迎你提供更多資訊或範例說明!! 💖

[Yuan104]

第一次在GitHub上提问，非常感谢作者及时又认真的回复！！！我理解您的解答，这对我理解题目有了帮助，我终于知道为什么大家都是这样写代码的了。💖

但我想补充一下，我并不是在中途决定d赢了的，而是画完所有图后根据”source“的定义去确定它获胜的。如果我们假设画图的过程中不去杜绝小循环的产生，只防止大循环的产生（我知道这不符合题目"so long as locking in that pair does not create a cycle in the graph"的要求），那么在我的例子中d是符合获胜规则的。

所以我想进一步讨论tideman，是不是题目本身有一些问题，如果我们为了保证最后获胜者“source”的产生，其实不一定非要杜绝所有的小循环，就像我举例的那样，在有小循环产生的情况下仍然出现了获胜者，其实我们只需要去防止大循环的产生即可。

不知道作者是否理解我纠结的地方了，我也许有些钻牛角尖了，毕竟重点是学习recursion这个知识点💖。

[ritachien]

我覺得題目設計杜絕所有循環的原因是因為畫圖的順序是 Sort 步驟依照力度決定的，這會牽涉到幾個問題:

1. 你是什麼時候知道 d > 其他所有候選人?
2. 循環出現的當下怎麼確定是大循環還是小循環?
   

舉幾個例子來討論，如果 sort 如下:

1. Sort = [ a>b, b>c, c>a, d>a, d>b, d>c ] → 你舉的例子。即使忽略 abc 的循環也不影響結果，可以確實得出 d 是 winner。(這種情況 abc 產生的是小循環)
2. Sort = [ a>b, b>c, c>a ] → 很不剛好票數產生 a=d, b=d, c=d 的狀況，你發現 d 不影響選舉結果，但是你需要回頭處理前面的循環。(這種情況 abc 產生的是大循環)
   

要注意到 a=d, b=d, c=d 的狀況是有可能發生的，因為這種選舉方式的邏輯就是倆倆比較，所以在 add_pairs 步驟 d 會被忽略，d 完全不會出現在 Sort 結果裡面。

第二個例子的情況下，在遍歷完一次陣列後才發現 abc 是大循環，需要回頭重新處理 abc 之間的關係，也就是為了得出結果，你需要遍歷同一個陣列兩次。這是一個比較不好的邏輯處理方式。另外就是，abcd 的例子候選人很少，如果更多候選人也能產生很多循環互相交錯的狀況，為了讓後續的邏輯趨向簡單，一開始就杜絕循環會是比較有效率的做法。

以上是我的看法。

[Yuan104]

理解了！非常感谢！

我最近的学习卡在cs50tideman了，准备按照大家的逻辑先完成这个作业。如果以后我写出了符合我逻辑的代码一定来和大家分享。

再次感谢作者的解答！！！

[rinevard]

感谢作者的分享~看完以后思路也清晰了不少。😊