问题描述:

你一定听说过田忌赛马的故事吧?如果3匹马变成n匹(n<=100),齐王仍然让他的马按照优到劣的顺序初赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子;输一局,田忌就要输掉200两银子。已知道国王和田忌的所有马的奔跑速度,并且所有马的奔跑速度均不相同,现已经对两人的马分别从快到慢排好序。请设计一个算法,帮助田忌赢得最多的银子。

要求:
(1)写出伪码。
(2)利用C或C++代码,编程实现上述算法。
输入:第一行一个整数n,表示双方各有n匹马;第二行n个整数分别表示田忌的n匹马的速度;第三行n个整数分别表示齐王的n匹马的速度。
输出:若通过聪明的你精心安排,如果能赢得比赛(赢的次数大于比赛总次数的一半),那么输出“YES”。
否则输出“NO”。并输出一个整数,代表田忌最多能赢多少两黄金。

实验原理:

如果田忌最快的马比齐王最快的马快,则比之
如果田忌最快的马比齐王最快的马慢,则用田最慢的马跟齐最快的马比
// 这是贪心的第一步
如果田忌最快的马的速度与齐威王最快的马速度相等
如果田忌最慢的比齐威王最慢的快,则比之
// 这是贪心的第二步
如果田忌最慢的比齐威王最慢的慢,田忌慢VS齐王快
田忌最慢的与齐威王最慢的相等,田忌慢VS齐王快

实验程序:

#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; }
实验测试:

复杂度分析:
将tj的马匹速度与king的马匹速度从小到大进行排序,然后对马匹分三种情况进行比较,时间复杂度为o(N)

技术
©2019-2020 Toolsou All rights reserved,
程序员的520,送给女友的几行漂亮的代码(python版)基于stm32控制四轮小车电机驱动(一)linux查看磁盘空间命令实验四 自动化测试工具-软件测试axios拦截器封装与使用C语言——qsort函数opencv-python傅里叶变换以及逆变换在算法研究过程中如何进行算法创新nc的安装和简单操作C语言做一个简易的登陆验证(功能)界面