用C语言求解查找假币问题
时间: 2024-05-02 11:20:22 浏览: 80
C# 用分治法算假币问题
3星 · 编辑精心推荐
假币问题是指有一堆硬币,其中有一枚是假币,假币比真币轻,现在要用天平来称出假币,请用C语言编写程序解决此问题。
思路:
1. 将硬币分成三堆,每一堆数量相等。
2. 将其中两堆放在天平两端,比较重量。
3. 如果两边重量相等,说明假币在第三堆中。
4. 如果天平左边轻,则假币在左边,否则在右边。
5. 对第三堆重复上述步骤,直到找到假币。
代码实现如下:
```c
#include <stdio.h>
#define COINS 27 // 硬币总数
#define FAKE 9 // 假币位置
int main() {
int coins[COINS]; // 存放硬币的数组
int i, j, k; // 循环计数器
int left, right; // 天平左右两端的重量
// 初始化硬币数组
for (i = 0; i < COINS; i++) {
coins[i] = 1;
}
coins[FAKE] = 0; // 将假币置为轻
// 查找假币
i = j = k = 0;
while (1) {
left = right = 0;
for (i = j; i < j + COINS/3; i++) {
left += coins[i];
}
for (i = j + COINS/3; i < j + 2*COINS/3; i++) {
right += coins[i];
}
if (left == right) {
j = k + 2*COINS/3;
} else if (left < right) {
k = j + COINS/3;
j = k - COINS/3;
} else {
k = j + COINS/3;
j = k + COINS/3;
}
if (j == FAKE) {
printf("假币在第 %d 个位置\n", j+1);
break;
}
}
return 0;
}
```
代码说明:
1. 定义了宏常量`COINS`表示硬币总数,`FAKE`表示假币位置。
2. 定义了一个长度为`COINS`的数组`coins`来存放硬币,其中1表示真币,0表示假币。
3. 初始化硬币数组,将假币置为0。
4. 使用三个循环计数器`i`、`j`、`k`来分别表示三堆硬币的起始位置。
5. 使用`while`循环不断地查找假币,直到找到为止。
6. 在循环中,首先将天平左右两端的重量`left`、`right`初始化为0。
7. 然后分别计算出两堆硬币的重量。
8. 如果两边重量相等,则假币在第三堆中。
9. 如果天平左边轻,则假币在左边,否则在右边。
10. 根据假币的位置调整三个计数器的值,继续查找假币。
11. 如果找到假币,则输出其位置,并退出循环。
12. 注意数组下标从0开始,需要把假币位置加1才是实际位置。
测试样例:
假币在第10个位置,共有27个硬币。
程序输出:
假币在第 10 个位置
阅读全文