我正在研究介紹演算法和資料結構課程的自動作業。學生提交代碼，我對他們進行提升測驗，通過測驗的數量給出一個等級，很容易。但我想評估排序演算法，例如“實施冒泡排序、插入排序、選擇排序和合并排序”。有沒有一種聰明的方法來測驗每個人的實作，以知道他們確實實作了所請求的演算法？
顯然我可以檢查他們對輸入的排序。但我真正想要的不僅僅是比較各種輸入的時間以檢查復雜性。
uj5u.com熱心網友回復：
有沒有一種聰明的方法來測驗每個人的實作，以知道他們確實實作了所請求的演算法？
讓他們撰寫一個對（比如說） a 進行排序的通用排序，std::vector<T>然后在您的單元測驗中提供一個類，您可以在其中多載排序演算法使用的比較運算子來記錄它正在排序的物件。最后，您的測驗可以檢查該日志并確定是否以正確的順序將正確的事物相互比較。
一種排序演算法與另一種排序演算法的區別最終在于比較元素的順序。
編輯：這是一個示例實作。不是世界上最干凈或最漂亮的東西，但足以作為單元測驗中使用的一次性類。
struct S
{
static std::vector<std::pair<int, int>> * comparisonLog;
int x;
S(int t_x) : x(t_x) { }
bool operator <(const S & t_other) const
{
comparisonLog->push_back({x, t_other.x});
return x < t_other.x;
}
};
std::vector<std::pair<int, int>> * S::comparisonLog;
單元測驗中的示例用法：
std::vector<std::pair<int, int>> referenceComparisons, studentComparisons;
const std::vector<S> values = { 1, 5, 4, 3, 2 };
S::comparisonLog = &referenceComparisons;
{
auto toSort = values;
std::sort(toSort.begin(), toSort.end());
}
S::comparisonLog = &studentComparisons;
{
auto toSort = values;
studentSort(toSort);
assert(std::is_sorted(toSort.begin(), toSort.end()));
}
assert(referenceComparisons == studentComparisons);
這將檢查是否studentSort實作與 相同的排序演算法std::sort。（當然，它不檢查的是studentSort不只是轉發到std::sort......）
編輯添加：另一種可能更好地概括除排序演算法以外的事物的替代方法是讓他們撰寫一個通用排序，采用特定型別的開始和結束迭代器，并為您手頭的迭代器檢測指標算術和取消參考運算子他們。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/472143.html