<style> .reveal { color: #ebb362; } </style> # 110-2數學校定必修/跑步勝利方程式 第六組 分配題目:第二、六題 --- ## 一、摘要 ---- - 動機 - 問題描述 - 困難 - 解法 - 結果 --- ## 二、動機 ---- - 雖然操場在整修無法使用，但是我們可以用數學架構起想像的比賽，以邏輯推導如何分配各跑者的圈數及次數，以最少的秒數，拿下接力賽的勝利 --- ## 三、問題描述 ---- 繞圈賽要完成n圈，每班派m人參加以接力賽的方式進行。每個人的圈數自訂。每人至少都要跑1圈，如何分配可使總共所花的時間最少？ ---- ### 背景條件 ---- 繞圈賽派出相應人數跑完指定圈數，可自由分配每人跑的圈數，且每人最少跑一圈，可分幾次完成 設一人第k次跑第m圈所花的時間為 <span style="font-size: .7em">(1.2)^(k-1)^(1.1)^(m-1)^</span>，求如何分配使時間最少 ---- ### 問題二 ---- 若A跑一圈需要40秒，B跑一圈需要44秒，C跑一圈需要60秒，3人要合力跑完20圈，這3人如何分配每人的跑步的圈數，讓完成20圈時間最少? ---- ### 問題五 ---- 若A跑一圈需要40秒，B跑一圈需要42秒，C跑一圈需要44秒，D跑一圈需要46秒，E跑一圈需要46秒，這5人如何分配每人的跑步的圈數，讓完成20圈時間最少? --- ## 四、困難 ---- - 發現:其中一個例題三人所花時間成等差 - 驗證結果:特例 - 結論:找不出通則 --- ## 五、解法 ---- - 工人智慧：excel大法-輸入方程式，讓電腦跑出數據，再人力一一排名  - 程式窮舉：將人力比對使用的邏輯交給電腦來執行 ---- <!-- .slide: style="font-size: .4em;" --> ### 甲選手 | 趟數\\圈數 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |-|-|-|-|-|-|-|-| | 1 | 1 | 1.1 | 1.21 | 1.331 | 1.4641 | 1.61051 | 1.771561 | | 2 | 1.2 | 1.32 | 1.452 | 1.5972 | 1.75692 | 1.932612 | 2.1258732 | | 3 | 1.44 | 1.584 | 1.7424 | 1.91664 | 2.108304 | 2.3191344 | 2.55104784 | | 4 | 1.728 | 1.9008 | 2.09088 | 2.299968 | 2.5299648 | 2.78296128 | 3.061257408 | | 5 | 2.0736 | 2.28096 | 2.509056 | 2.7599616 | 3.03595776 | 3.339553536 | 3.67350889 | ---- <!-- .slide: style="font-size: .4em;" --> ### 乙選手 | 趟數\\圈數 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |-|-|-|-|-|-|-|-| | 1 | 1.1 | 1.21 | 1.331 | 1.4641 | 1.61051 | 1.771561 | 1.9487171 | | 2 | 1.32 | 1.452 | 1.5972 | 1.75692 | 1.932612 | 2.1258732 | 2.33846052 | | 3 | 1.584 | 1.7424 | 1.91664 | 2.108304 | 2.3191344 | 2.55104784 | 2.806152624 | | 4 | 1.9008 | 2.09088 | 2.299968 | 2.5299648 | 2.78296128 | 3.061257408 | 3.367383149 | | 5 | 2.28096 | 2.509056 | 2.7599616 | 3.03595776 | 3.339553536 | 3.67350889 | 4.040859779 | ---- <!-- .slide: style="font-size: .4em;" --> ### 丙選手 | 趟數\\圈數 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |-|-|-|-|-|-|-|-| | 1 | 1.5 | 1.65 | 1.815 | 1.9965 | 2.19615 | 2.415765 | 2.6573415 | | 2 | 1.8 | 1.98 | 2.178 | 2.3958 | 2.63538 | 2.898918 | 3.1888098 | | 3 | 2.16 | 2.376 | 2.6136 | 2.87496 | 3.162456 | 3.4787016 | 3.82657176 | | 4 | 2.592 | 2.8512 | 3.13632 | 3.449952 | 3.7949472 | 4.17444192 | 4.591886112 | | 5 | 3.1104 | 3.42144 | 3.763584 | 4.1399424 | 4.55393664 | 5.009330304 | 5.510263334 | ---- ### 各圈排名 ---- <!-- .slide: style="font-size: .4em;" --> ### 甲選手 | 趟數\\圈數 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |-|-|-|-|-|-|-|-| | 1 | 1 | 2 | 5 | 9 | 14 | 21 | 29 | | 2 | 4 | 7 | 12 | 19 | 28 | 37 | 47 | | 3 | 11 | 17 | 25 | 35 | 46 | 56 | 66 | | 4 | 24 | 33 | 43 | 54 | 65 | 74 | 82 | | 5 | 42 | 52 | 62 | 72 | 81 | 88 | 94 | <!-- ---- --> ### 乙選手 | 趟數\\圈數 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |-|-|-|-|-|-|-|-| | 1 | 2 | 5 | 9 | 14 | 21 | 29 | 39 | | 2 | 7 | 12 | 19 | 27 | 37 | 47 | 58 | | 3 | 17 | 25 | 35 | 45 | 56 | 66 | 76 | | 4 | 33 | 43 | 55 | 64 | 74 | 82 | 90 | | 5 | 52 | 62 | 73 | 80 | 88 | 94 | 99 | <!-- ---- --> ### 丙選手 | 趟數\\圈數 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |-|-|-|-|-|-|-|-| | 1 | 16 | 23 | 32 | 41 | 51 | 61 | 71 | | 2 | 31 | 40 | 50 | 60 | 70 | 79 | 87 | | 3 | 49 | 59 | 69 | 78 | 86 | 93 | 98 | | 4 | 68 | 77 | 85 | 92 | 97 | 101 | 103 | | 5 | 84 | 91 | 96 | 100 | 102 | 104 | 105 | ---- ## 程式邏輯概述 ---- - 輸入甲、乙、丙、目標圈數後，程式會： 1. 將各選手的各圈相關資訊(該圈秒數、選手代號、是第幾趟&圈)打包好後，一個個全部存入一維容器A中 ---- 3. 將容器中的每圈資料依照**該圈秒數**進行遞增排序 4. 窮舉出所有選手的**趟數分配**，共會有$n-人數+1$種可能（例如傳接棒：甲->乙->丙和甲->乙->甲->乙便是其中兩種可能） ---- 6. 依照各個趟數條件，在容器中找尋符合條件的前n個，就可以得出該趟數分配下的最短秒數及甲乙丙分別跑的圈數，打包並存入另一個一維容器B 7. 將B中的$n-人數+1$個內容物，以所花秒數進行遞增排序 8. 印出B中前五項的秒數及甲乙丙的各圈&趟分配 ----  --- ## 六、結果 ---- - 利用excel可應對多種不同的問題，只要修改數據即可 - 未找到通式 - 可設計程式輸入背景數據，讓程式跑出最短秒數 ---- ### 答案 ---- - 第二題、甲(5, 3, 2)乙(4, 3, 1)丙(1, 1) -> 1098.376秒 - 第五題、甲(4, 2)乙(3, 2)丙(2, 1)丁(2, 1)戊(2) --- ## 七、感想&展望 ---- - 工欲善其事，必先利其器 - 並非所有問題均有通則 --- ## 八、小組分工 ---- 楊軒輊：簡報製作、討論問題、試算表操作 蕭名凱：程式撰寫、簡報格式設定＆製作、討論問題、試算表操作 黃俞華、林品辰、鄭力文、林貽建：分享意見、討論問題 --- ## 附錄：程式原始碼 ---- ```c++=1 #include <iostream> #include <cmath> #include <vector> #include <utility> #include <algorithm> #include <iomanip> using namespace std; using vec = vector<pair<double,vector<int>>>; using mypair = pair<double,vector<int>>; vec create_player(int id, int sec, int n){ vec v; for(int i = 0; i < (n/3+1); i++){ for(int j = 0; j < (n/3+1); j++){ mypair cell; cell.first = (sec*pow(1.2, i)*pow(1.1, j)); // cout << cell.first << endl; cell.second = {id, i+1, j+1}; v.push_back(cell); } } return v; } template <class T> bool sort_function(T i, T j){return (i.first < j.first); } template <class T> void print_vector(T a){ for(auto it = a.begin(); it!= a.end(); ++it){ cout << it->first << " (" << it->second[0] << ", " << it->second[1] << ", " << it->second[2] << ")\n"; } } template <class T> void print_anss(T a){ for(auto it = a.begin(); it!= a.begin()+5; ++it){ cout<< it->first << "s => {"; for(auto it2 = it->second.begin(); it2!= it->second.end(); ++it2){ cout << "("; for(int i = 0; i < (*it2).size(); i++){ cout<< (*it2)[i]; if (i == ((*it2).size()-1))break; cout << ", "; } if(it2 == (it->second.end()-1)){ cout << ")"; break; }; cout << "), "; } cout << "}\n"; } } template <class T> vec merge_and_sort(T p1, T p2, T p3){ vec all; all.insert(all.end(), p1.begin(), p1.end()); all.insert(all.end(), p2.begin(), p2.end()); all.insert(all.end(), p3.begin(), p3.end()); sort(all.begin(), all.end(), sort_function<pair<double, vector<int>>>); // print_vector<vec>(all); //測試用 return all; } vector<pair<double,vector<vector<int>>>> brute_force(int goal, vec sorted_data){ int p1t, p2t, p3t; p1t = p2t = p3t = 1; vector<pair<double,vector<vector<int>>>> v; int _cycle = 1; while(p1t+p2t+p3t <= goal){ int count = p1t+p2t+p3t; double total = 0; pair<double,vector<vector<int>>> p; p.second.push_back(vector<int>(p1t, 1)); p.second.push_back(vector<int>(p2t, 1)); p.second.push_back(vector<int>(p3t, 1)); for(auto it = sorted_data.begin(); it != sorted_data.end(); ++it){ if(it->second[0] == 1 && (it->second)[1] <= p1t && it->second[2] == 1){ total += it->first; } else if(it->second[0] == 2 && (it->second)[1] <= p2t && it->second[2] == 1){ total += it->first; } else if(it->second[0] == 3 && (it->second)[1] <= p3t && it->second[2] == 1){ total += it->first; } } if(count == goal){ p.first = total; v.push_back(p); break; } for(auto it = sorted_data.begin(); it != sorted_data.end(); ++it){ if(it->second[2] == 1)continue; if(it->second[0] == 1 && (it->second)[1] <= p1t){ count++; total += it->first; p.second[0][it->second[1]-1]++; } else if(it->second[0] == 2 && (it->second)[1] <= p2t){ count++; total += it->first; p.second[1][it->second[1]-1]++; } else if(it->second[0] == 3 && (it->second)[1] <= p3t){ count++; total += it->first; p.second[2][it->second[1]-1]++; } if(count == goal){ p.first = total; v.push_back(p); break; } if(_cycle == 1){ p1t++; _cycle++; } else if(_cycle == 2){ p2t++; _cycle++; } else if (_cycle == 3){ p3t++; _cycle = 1; } } sort(v.begin(), v.end(), sort_function<pair<double,vector<vector<int>>>>); return v; } int main(){ cout << fixed; // cout << "(請依序輸入:p1初始一圈所花時間 p2的 p3的 要跑的總圈數)\n"; cout << "input format: p1 p2 p3 n\n"; int p1, p2, p3, n; while(cin){ cin >> p1 >> p2 >> p3 >> n; vec p1vec = create_player(1, p1, n); vec p2vec = create_player(2, p2, n); vec p3vec = create_player(3, p3, n); vec all = merge_and_sort<vec>(p1vec, p2vec, p3vec); vector<pair<double,vector<vector<int>>>> anss = brute_force(n, all); print_anss<vector<pair<double,vector<vector<int>>>>>(anss); //測試用 // cout << (*a)[n]->first << " " << (*a)[n]->second[0] << (*a)[n]->second[1]; // cout << all[n].first << " (" << all[n].second[0] << ", " << a[n].second[1] // << ", " << all[n].second[2] << ")\n"; } return 0; }