田忌赛马贪心算法c语言
时间: 2023-07-04 13:17:22 浏览: 310
田忌赛马问题是一个经典的贪心算法问题。下面是一个使用C语言实现的简单示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define NUM_HORSES 10
int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int main() {
int ti[NUM_HORSES] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 田忌的马
int qi[NUM_HORSES] = {8, 9, 10, 1, 2, 3, 4, 5, 6, 7}; // 齐王的马
int ti_win = 0, qi_win = 0; // 记录胜利次数
int ti_idx = 0, qi_idx = 0; // 田忌和齐王当前选手的位置
qsort(ti, NUM_HORSES, sizeof(int), cmp);
qsort(qi, NUM_HORSES, sizeof(int), cmp);
while (ti_idx < NUM_HORSES && qi_idx < NUM_HORSES) {
if (ti[ti_idx] > qi[qi_idx]) { // 田忌的马跑得快
ti_win++;
ti_idx++;
qi_idx++;
} else { // 齐王的马跑得快
qi_win++;
ti_idx++;
qi_idx++;
}
}
printf("田忌赢了%d场,齐王赢了%d场\n", ti_win, qi_win);
return 0;
}
```
在这个示例代码中,我们先定义了田忌和齐王的马的速度,并将它们分别按照速度从小到大排序。然后,我们使用两个指针 ti_idx 和 qi_idx 来记录当前选手的位置,同时使用 ti_win 和 qi_win 来记录胜利场次。接着,我们在一个 while 循环中,不断比较当前两个选手的马的速度,以此来确定谁胜谁负。最后,输出田忌和齐王的胜利场次即可。
阅读全文