Re: [問題] 排序

[loveme00835 (高髮箍)]

※ 引述《Quietlake (ekalteiuQ)》之銘言：
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: Code::Blocks 10.05
: 問題(Question)：
: http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b021
: 最後一個測資沒通過
: 錯誤結果(Wrong Output)：
: *** 第 5 點 (20%)：WA
: 與正確輸出不相符(line:46)
: 您的答案為: 2
: 正確答案為: 70
: 程式碼(Code)：(請善用置底文網頁, 記得排版)
: http://codepad.org/fx5NBBe9
: 補充說明(Supplement)：
: 使用insertion sort。
: 找不出問題，上來請求各位的協助。
: 另外想問，大家都怎麼產生極端測資作測試？我每次都只是試幾個，過了就送程式
: 通常結果都不是很好……

通常貼文問問題的時候會把程式碼簡化成 20~ 40 行以便閱讀, 而且
程式碼本身要能和問題做一個良好的對應, 而不是依賴註解, 因為看
的人有可能被誤導. 如何做好對應? 首先要從設計著手.

一開始給定一個結構, 對應輸入的每一行:

    struct student {
        int id; // optional
        int total; // optional
        int chinese;
        int english;
        int math;
        int physics;
        int chemistry;
    };

再來就是給定兩個學生 a、b 定義什麼叫做 a 的分數比 b 的分數高:

    // return 1 if a > b, return 0 otherwise
    int greater_than( const struct student * a,
                      const struct student * b ) {

        if ( a->total > b->total ) {
            return 1;
        } else if ( a->total == b->total ) {
            return ( a->math > b->math ? 1 : 0 );
        }

        return 0;
    }

再來排序變成對一維陣列做了, 沒有複雜的 signature:

    void insertionSort( struct student * students, int size );

在 insertionSort 裡呼叫 greater_than 就能做到比較的效果, 不需
要跟它講從哪邊開始排序, 傳遞位移過的指標當第一個引數即可. 這
樣的好處就是不必考慮索引計算的問題.

-

經過上述的對應, 你只要會排整數, 你就會做這一題.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.121.197.115
※ 編輯: loveme00835     來自: 140.121.197.115      (01/29 12:15)
推 Quietlake:感謝指導，以後我會注意您提到的點。
推 DarkPrincex:怎麼有一種在call C語言內建qsort的感覺...好恐怖
→ DarkPrincex:如果我要這樣做大概會偷懶直接用operator <來做@@
→ loveme00835:operator< 應該視為最後的解決方案, 因為當code寫成
→ loveme00835:a < b 的形式, 編譯器首先會在物件所在的 scope 下找
→ loveme00835:尋可用的呼叫, 當然在你呼叫的地方也同樣找尋候選函式
→ loveme00835:造成模稜兩可的呼叫, 所以才有 <functional> 內的函式
→ loveme00835:物件出現, 並且成為associate container預設比較準則