用c语言实现田忌赛马（贪心算法）

*田忌赛马的故事大家一定都听过，为了是田忌赢尽可能多的钱，就应该尽可能使田忌的好马对齐王的好马，田忌的劣马尽可能多的消耗齐王更好的马，这就是贪心的本质。本题到底应该如何贪心？

*让双方最差的马比：

1.如果田忌赢齐王 ，赢一局

2.如果田忌输齐王， 让田忌最劣的马和齐王最好的马比 ，输一局（消耗了齐王最 好的一匹马，稳稳的贪心）

3.如果平局的话 就先不管它

让双方的两匹最好的马相比

1.如果田忌赢齐王 赢一局

2.否则，在双方最差的马平局的情况下，田忌最好的马小于或等于齐王最好的马，用田忌最差的马和齐王最好的比，如果田忌的最差的马赢齐王最好的马，赢一局

如果田忌的最差的马输 则输一局，否则平局

**

本题大概如此贪心，明白大概算法思路之后，就是如何书写代码，为了得到最好的马和最差的马分别是哪位，我们应该对马速进行排序，排序方法很多，冒泡，选择等想必大家都已经非常熟悉，在此，笔者介绍一下qsort函数进行排序处理。

qsort函数

定义：快速排序任意类型数据库函数。

头文件：

qsort函数原型：

void qsort(void *base,size_t num,size_t width,int (*compare)(const void *,const void *))

各参数含义:

(1)base是待排序数组首元素地址；

(2)num是数组大小

(3)width是各元素占用空间大小；

(4)函数指针（回调函数）

最后一个函数指针（回调函数），代码如下

int compare(const void *a, const void *b)
{return *(int*)a - *(int*)b; //由小到大排序//return *(int *)b - *(int *)a; 由大到小排序
}

显而易见可以进行正序倒序排序，此处便不再多言

接下来再具体演示一下qsort引用的方法

qsort(a, 1000, sizeof(int), compare);

至此，大体思路就已经整理完毕清楚，然后就是文件处理，如何从文件中引入数据，输出数据到文件，至此，话不多说，直接上代码，代码的标注应该可以完全理解文件操作，如果文件操作不是很熟悉，建议稍微学习一下，文件操作应该不算很难。

#include
#include
/* 定义comp以实现快排函数qsort，从大到小排序*/ 
int comp(const void* a, const void* b)
{return *(int*)b - *(int*)a;
}
int main()
{FILE* in;	FILE* out;/*定义文件指针*/int num;in = fopen(".\\读入与输出文件\\data.in.txt", "r+");/*打开data.in文件*/if (in == 0)/*文件打开错误*/{printf("file error\n");exit(1);}else{out = fopen(".\\读入与输出文件\\answer.out.txt", "r+");/*打开answer.out文件*/if (out == 0)/*文件打开失败*/{printf("file error\n");exit(1);}else{fscanf(in, "%d", &num);/*读取data.in文件，获取马匹数*/if (num == 0)/*防止上来就给个0*/fprintf(out, "没马怎么比？");else{do{int tj[1001], qw[1001];for (int i = 0; i < num; i++){fscanf(in, "%d ", &tj[i]);/*获取田忌马速*/}for (int j = 0; j < num; j++){fscanf(in, "%d ", &qw[j]);/*获取齐王马速*/}/*接下来是贪心算法的内容*/ qsort(tj, num, sizeof(tj[0]), comp);//对田忌马速排序 qsort(qw, num, sizeof(qw[0]), comp);//对齐王马速排序 int a = 0;int b = 0;int m = num - 1;int n = num - 1;int t = 0;while (a <= m)//开始比试 {if (tj[m] > qw[n])//如果田忌的劣马胜过齐王劣马，赢一次 {m--;n--;t++;}else if (tj[m] < qw[n])//如果劣马略逊一筹，则消耗齐王一匹好马，输一局 {m--;b++;t--;}else if (tj[a] > qw[b])//如果田忌好马胜过齐王好马，赢一次 {a++;b++;t++;}else//田忌劣马换掉齐王好马，绝对贪心 {if (tj[m] > qw[b])//田忌最劣马换掉齐王好马，赢一次 {b++;m--;t++;}else if (tj[m] < qw[b])// 田忌最劣马换掉齐王好马，输一次 {b++;m--;t--;}else// 平局，不比了 {b++;m--;}}}fprintf(out, "%d\n", 200 * t);/*将结果输出至answer.out文件*/fscanf(in, "%d", &num);/*读取下一组数据的马匹数*/}while (num != 0);/*判断全部数据是否结束*/}}fclose(out);/*关闭answer.out文件*/}fclose(in);/*关闭data.in文件*/return 0;
}

为了使程序运行，只需在和程序相同的文件夹中，创建文档分别名为“data.in”和".out"的文件，在"data.in"中输入数据运行，便可在“.out”中找到田忌赚到的钱啦！

*操作说明：

1.打开文件夹“读入与输出文件"

2.打开“data.in”文件，在里面输入待测数据（输入完数据之后务必别忘了0！）

3.保存并关闭后，运行程序

4.程序运行结束后，打开“.out”文件，里面有你想要的数据。

（在运行第二次之前，请一定要把上一次写入“.out”文件中的数据清空）