1. 项目背景与意义
"71百鸡百钱.c"这个文件名就散发着浓浓的年代感——典型的DOS时代命名风格。这种上世纪90年代遗留下来的C代码,在如今的开发环境中运行时往往会遇到各种兼容性问题。我最近在整理旧硬盘时发现了这个经典案例,决定通过修复和解析这个"百鸡百钱"问题的实现代码,带大家重温早期编程的独特魅力。
百鸡百钱是中国古代著名的数学问题,出自《张丘建算经》:"今有鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一。凡百钱买百鸡,问鸡翁、鸡母、鸡雏各几何?"这个问题的C语言实现版本在上世纪90年代非常流行,是许多人的编程启蒙案例。
2. 原始代码解析
2.1 代码结构与风格分析
原始"71百鸡百钱.c"的代码风格具有鲜明的时代特征:
c复制#include<stdio.h>
main()
{
int x,y,z;
for(x=0;x<=20;x++)
for(y=0;y<=33;y++) {
z=100-x-y;
if(5*x+3*y+z/3==100 && z%3==0)
printf("cock=%d,hen=%d,chick=%d\n",x,y,z);
}
}
几个明显的时代特征:
main()函数没有返回值类型声明(默认为int)- 变量命名极其简短(x,y,z)
- 缩进风格不统一(混用空格和Tab)
- 没有现代C语言常见的代码块大括号
- 使用原始的printf格式输出
2.2 算法逻辑解析
这段代码采用暴力枚举法求解:
- 外层循环枚举公鸡数量x(0-20,因为5*20=100)
- 内层循环枚举母鸡数量y(0-33,因为3*33=99)
- 小鸡数量z通过z=100-x-y计算得出
- 检查是否满足5x+3y+z/3=100且z能被3整除
这个算法时间复杂度为O(n²),对于这个特定问题完全够用,体现了早期程序员对计算效率的朴素理解。
3. 代码现代化改造
3.1 基础语法更新
首先我们需要让代码符合现代C标准(C11/C17):
c复制#include <stdio.h>
#include <stdbool.h>
int main(void)
{
int cock, hen, chick;
bool found = false;
for(cock = 0; cock <= 20; cock++) {
for(hen = 0; hen <= 33; hen++) {
chick = 100 - cock - hen;
if(5 * cock + 3 * hen + chick / 3 == 100
&& chick % 3 == 0) {
printf("公鸡: %d, 母鸡: %d, 小鸡: %d\n",
cock, hen, chick);
found = true;
}
}
}
if(!found) {
printf("未找到符合条件的解\n");
}
return 0;
}
主要改进:
- 添加了
#include <stdbool.h>头文件 - 明确main函数返回类型和参数
int main(void) - 使用更有意义的变量名(cock,hen,chick)
- 添加了解决方案存在性检查
- 统一了代码缩进风格(4空格)
- 增加了返回语句
return 0
3.2 防御性编程增强
原始代码缺乏基本的输入验证和错误处理。我们添加以下防御性措施:
c复制#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAX_PRICE 1000
bool validate_input(int total_money, int total_chickens) {
return total_money > 0 && total_chickens > 0
&& total_money <= MAX_PRICE;
}
void solve_chicken_problem(int total_money, int total_chickens) {
int cock, hen, chick;
bool found = false;
for(cock = 0; cock <= total_money/5; cock++) {
for(hen = 0; hen <= total_money/3; hen++) {
chick = total_chickens - cock - hen;
if(chick < 0) continue;
if(5 * cock + 3 * hen + chick / 3 == total_money
&& chick % 3 == 0) {
printf("公鸡: %d, 母鸡: %d, 小鸡: %d\n",
cock, hen, chick);
found = true;
}
}
}
if(!found) {
printf("未找到符合条件的解\n");
}
}
int main(void) {
int total_money = 100;
int total_chickens = 100;
if(!validate_input(total_money, total_chickens)) {
fprintf(stderr, "错误: 输入参数无效\n");
return EXIT_FAILURE;
}
solve_chicken_problem(total_money, total_chickens);
return EXIT_SUCCESS;
}
改进亮点:
- 添加了输入验证函数
- 定义了价格上限常量
- 将核心算法提取为独立函数
- 使用标准退出码EXIT_SUCCESS/FAILURE
- 添加了错误输出到stderr
- 增加了负数检查(chick < 0)
3.3 性能优化版本
虽然原始问题的规模很小,但我们可以探索更高效的算法:
c复制#include <stdio.h>
#include <stdbool.h>
void optimized_solution(int total_money, int total_chickens) {
int cock, hen, chick;
bool found = false;
// 数学推导优化:减少循环次数
for(cock = 0; cock <= total_money/5; cock++) {
hen = (total_money - 7 * cock) / 4;
chick = total_chickens - cock - hen;
if(hen >= 0 && chick >= 0
&& 5*cock + 3*hen + chick/3 == total_money
&& chick % 3 == 0) {
printf("公鸡: %d, 母鸡: %d, 小鸡: %d\n",
cock, hen, chick);
found = true;
}
}
if(!found) {
printf("未找到符合条件的解\n");
}
}
这个版本通过数学推导将O(n²)复杂度降为O(n):
- 由方程5x+3y+z/3=100和x+y+z=100推导出y=(100-7x)/4
- 只需单层循环枚举x值即可
- 计算出的y和z需要验证非负和整除条件
4. 跨平台兼容性处理
4.1 编译器兼容问题
原始代码在现代编译器上可能遇到以下问题:
-
隐式函数声明:老式C允许隐式声明函数,现代编译器会报错
- 修复:明确包含所有需要的头文件
-
main函数格式:现代标准要求明确返回类型
- 修复:使用
int main(void)形式
- 修复:使用
-
变量声明位置:C99前变量必须在块开头声明
- 修复:保持变量声明在作用域起始处
4.2 构建系统现代化
为方便现代开发环境使用,添加Makefile:
makefile复制CC = gcc
CFLAGS = -Wall -Wextra -std=c11
TARGET = hundred_chickens
all: $(TARGET)
$(TARGET): hundred_chickens.c
$(CC) $(CFLAGS) -o $@ $^
clean:
rm -f $(TARGET)
.PHONY: all clean
关键构建选项:
-Wall -Wextra:启用更多警告-std=c11:使用C11标准- 分离编译和清理目标
5. 测试与验证
5.1 单元测试框架
添加简单的测试验证:
c复制#include <stdio.h>
#include <stdbool.h>
void test_solutions() {
struct TestCase {
int money;
int chickens;
int expected;
} cases[] = {
{100, 100, 3}, // 经典问题应有3解
{50, 50, 0}, // 无解情况
{0, 0, 0}, // 边界情况
};
for(size_t i = 0; i < sizeof(cases)/sizeof(cases[0]); i++) {
printf("测试用例 %zu: money=%d, chickens=%d\n",
i+1, cases[i].money, cases[i].chickens);
solve_chicken_problem(cases[i].money, cases[i].chickens);
printf("\n");
}
}
5.2 性能对比测试
比较原始算法与优化算法的效率:
c复制#include <time.h>
void performance_test() {
clock_t start, end;
double cpu_time_used;
start = clock();
for(int i = 0; i < 10000; i++) {
original_solution(100, 100);
}
end = clock();
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("原始算法耗时: %.5f 秒\n", cpu_time_used);
start = clock();
for(int i = 0; i < 10000; i++) {
optimized_solution(100, 100);
}
end = clock();
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("优化算法耗时: %.5f 秒\n", cpu_time_used);
}
6. 代码风格与文档
6.1 添加Doxygen文档
c复制/**
* @file hundred_chickens.c
* @brief 解决百鸡百钱问题的实现
* @version 1.1
* @date 2023-05-20
*/
/**
* @brief 验证输入参数的有效性
* @param total_money 总钱数
* @param total_chickens 总鸡数
* @return true 输入有效
* @return false 输入无效
*/
bool validate_input(int total_money, int total_chickens) {
return total_money > 0 && total_chickens > 0
&& total_money <= MAX_PRICE;
}
6.2 现代代码格式化
使用clang-format配置:
yaml复制BasedOnStyle: LLVM
IndentWidth: 4
BreakBeforeBraces: Allman
ColumnLimit: 80
PointerAlignment: Right
7. 扩展思考
7.1 数学建模视角
百鸡百钱问题可以表示为线性方程组:
code复制5x + 3y + z/3 = 100
x + y + z = 100
x, y, z ∈ ℕ
这是一个不定方程,有多个整数解。通过代数方法可以推导出:
code复制x = 4k
y = 25 - 7k
z = 75 + 3k
其中k=0,1,2,3
7.2 现代C++实现对比
作为对比,展示现代C++20的实现:
cpp复制#include <iostream>
#include <tuple>
#include <vector>
auto solve_chicken_problem(int total_money, int total_chickens) {
std::vector<std::tuple<int,int,int>> solutions;
for(int cock = 0; cock <= total_money/5; ++cock) {
for(int hen = 0; hen <= total_money/3; ++hen) {
int chick = total_chickens - cock - hen;
if(chick >= 0 &&
5*cock + 3*hen + chick/3 == total_money &&
chick % 3 == 0) {
solutions.emplace_back(cock, hen, chick);
}
}
}
return solutions;
}
现代C++特性带来的改进:
- 使用tuple和vector组织数据
- 结构化返回类型
- emplace_back避免临时对象
- 更严格的类型检查
8. 项目总结与收获
通过这个复古代码修复项目,我深刻体会到:
-
代码可读性的重要性:原始代码虽然简洁,但缺乏描述性命名和注释,增加了理解成本
-
防御性编程的价值:现代编程实践中输入验证和错误处理不可或缺
-
算法优化的思维:从暴力枚举到数学推导的优化过程展示了算法思维的演进
-
代码风格的演进:30年间C语言的编码规范发生了显著变化,更强调可维护性
-
文档和测试的必要性:完善的文档和测试用例是专业项目的标志
这个看似简单的百鸡百钱问题,实际上包含了编程实践的诸多核心要素。修复这样的复古代码,不仅是对编程历史的致敬,更是对现代软件开发最佳实践的生动演练。