演算法實驗課回顧
田忌賽馬
問題描述：
你一定聽說過田忌賽馬的故事吧？如果3匹馬變成n匹（n<=100），齊王仍然讓他的馬按照優到劣的順序初賽，田忌可以按任意順序選擇他的賽馬出賽，贏一局，田忌可以得到200兩銀子；輸一局，田忌就要輸掉200兩銀子，已知道國王和田忌的所有馬的奔跑速度，并且所有馬的奔跑速度均不相同，現已經對兩人的馬分別從快到慢排好序，請設計一個演算法，幫助田忌贏得最多的銀子，
要求：
輸入：第一行一個整數n，表示雙方各有n匹馬；
第二行n個整數分別表示田忌的n匹馬的速度；
第三行n個整數分別表示齊王的n匹馬的速度，
輸出：若通過聰明的你精心安排，如果能贏得比賽（贏的次數大于比賽總次數的一半），那么輸出“YES”， 否則輸出“NO”，并輸出一個整數，代表田忌最多能贏多少兩黃金，
-
如果田忌最快的馬比齊王最快的馬快，則比之
-
如果田忌最快的馬比齊王最快的馬慢，則用田最慢的馬跟齊最快的馬比
// 這是貪心的第一步
-
如果田忌最快的馬的速度與齊威王最快的馬速度相等
-
如果田忌最慢的比齊威王最慢的快，則比之
// 這是貪心的第二步
-
如果田忌最慢的比齊威王最慢的慢，田忌慢VS齊王快
-
田忌最慢的與齊威王最慢的相等，田忌慢VS齊王快
-
代碼 C++實作
#include <iostream>
#include <cstdlib>
using namespace std;
// 快排
void Quick(int a[], int begin, int end) {
if (begin >= end)
return;
int t = a[begin];
int i = begin;
int j = end;
while (i < j)
{
while (i<j && a[j] < t)
j--;
a[i] = a[j];
while (i < j && a[i] >= t)
i++;
a[j] = a[i];
}
a[i] = t;
Quick(a, begin, i - 1);
Quick(a, i + 1, end);
}
// 田忌賽馬演算法
int tianRac(int Tian[], int King[], int n) {
int money = 0; // 田忌贏的錢
int tianh = 0, tiane = n-1, kingh = 0, kinge = n-1; // 分別標記田忌馬隊和齊王馬隊的最快和最慢的馬
// 共有 n 次比賽，每進行一次，就換下一匹馬（田姥爺就位，開始賽馬秀）
for (int i = 0; i < n; i++) {
// 田忌快馬比齊王快馬快時，那就和他一較高下（賭怪，必贏）
if (Tian[tianh] > King[kingh]) {
money += 200;
tianh++; // 下一個
kingh++; // 下一個
}
// 田忌快馬比齊王快馬慢時，用最慢的馬跟他最快的比（埋伏他一手，這匹馬不用搶，他死定了，反手一個超級加倍，悶聲發大財）
else if (Tian[tianh] < King[kingh]) {
money -= 200;
tiane--;
kingh++;
}
// 田忌的快馬和齊王的快馬一樣快時（他也一樣快？不過不用怕，他的馬贏不了我）
else {
// 田忌的慢馬比齊王的慢馬快時（很牛逼這個馬）
if (Tian[tiane] > King[kinge]) {
money += 200;
tiane--;
kinge--;
}
// 田忌的慢馬比齊王的慢馬一樣快和慢時，就用慢馬和他快馬比（如果將這個慢馬換成快馬我的馬將絕殺，可惜換不得）
else {
money -= 200;
tiane--;
kingh++;
}
}
}
// 回傳田忌贏的錢（飛機~）
return money;
}
int main() {
int n; // 比賽雙方馬的數量
cout << "公等馬幾何" << endl;
cin >> n;
int* Tian = new int[n];
int* King = new int[n];
cout << "將軍 馬之疾" << endl;
for (int i = 0; i < n; i++) {
cin >> *(Tian + i);
}
cout << "王 馬之疾" << endl;
for (int i = 0; i < n; i++){
cin >> *(King + i);
}
// 排序，降序排
Quick(Tian, 0, n-1);
Quick(King, 0, n - 1);
// 呼叫“就算佛祖來了，田姥爺也難輸”演算法
int result = tianRac(Tian, King, n);
if (result > 0) {
cout << "將軍 勝" << endl;
cout << "贏 " << result << "金" << endl;
}
else if (result == 0)
{
cout << "和" << endl;
}
else {
cout << "王 勝" << endl;
cout << "贏 " << -result << "金" << endl;
}
return 0;
}
測驗資料：
95 92 80 85 98 86 81 83
88 89 97 99 82 85 90 91
80 79 90 95 78 85 68 91
95 92 99 85 98 86 85 96
結果截圖：
ps: 這個演算法對田姥爺太難輸了…
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/235268.html
標籤：其他