首页 > 代码库 > 初学者编程编程实战指南 (3)- 性能优化
初学者编程编程实战指南 (3)- 性能优化
百马百担问题
题目描述
百马百担问题。有100匹马，驮100担货，大马驮3担，中马驮2担，两匹小马1担，编程计算所有可能的驮法？
输入
无
输出
输出所有可能的驮法。
每行输出一种驮法，每种驮法依次输出：
大马数，中马数，小马数
如2,30,68
表示大马数为2，中马数为30，小马数为68
样例输入
样例输出
2,30,68
5,25,70
8,20,72
11,15,74
14,10,76
17,5,78
20,0,80
下面的初学者容易写出的代码，而且最常犯错的地方就是忘记 z % 2 == 0
1 #include <stdio.h> 2 3 int main(void) 4 { 5 int x, y, z; 6 for(x = 0; x <= 33; x++) 7 for(y = 0; y <= 50; y++) 8 for(z = 0; z <= 100; z++) { 9 if(x + y + z == 100 && 3 * x + 2 * y + z / 2 == 100 && z % 2 == 0)10 printf("%d,%d,%d\n", x, y, z);11 }12 13 return 0;14 }
能不能去掉z % 2 == 0这个条件呢？ 一种思路就是将 3 * x + 2 * y + z / 2 == 100两边都乘以2，等式成为6*x+4*y+z==200。 更好的做法是修改循环变量的步长
1 #include <stdio.h> 2 3 int main(void) 4 { 5 int x, y, z; 6 for(x = 0; x <= 33; x++) 7 for(y = 0; y <= 50; y++) 8 for(z = 0; z <= 100; z += 2) { 9 if(x + y + z == 100 && 3 * x + 2 * y + z / 2 == 100)10 printf("%d,%d,%d\n", x, y, z);11 }12 13 return 0;14 }
如果进一步观察，发现第8行的枚举z是没有必要的，因为z必然是100-x-y，这样会节省不少开销。
1 #include <stdio.h> 2 3 int main(void) 4 { 5 int x, y, z; 6 for(x = 0; x <= 33; x++) 7 for(y = 0; y <= 50; y++) { 8 z = 100 - x - y; 9 if(z % 2 == 0 && 3 * x + 2 * y + z / 2 == 100)10 printf("%d,%d,%d\n", x, y, z);11 }12 13 return 0;14 }
变化一下判断条件，可以用100-x-y代替z，从而抹去z的痕迹。 6x+4y+z = 100+5x+3y，有下面第8行的判等式（该式实际一开始就可以推出），这个式子是推导的结果，绝非一眼所能看出。
1 #include <stdio.h> 2 3 int main(void) 4 { 5 int x, y; 6 for(x = 0; x <= 33; x++) 7 for(y = 0; y <= 50; y++) { 8 if(5 * x + 3 * y == 100) 9 printf("%d,%d,%d\n", x, y, 100 - x - y);10 }11 12 return 0;13 }
有了第8行，可看出x不超过20，而且y也不必枚举了。程序只剩一层循环，得到了极大的优化。
1 #include <stdio.h> 2 3 int main(void) 4 { 5 int x, y; 6 for(x = 0; x <= 20; x++){ 7 y = 100 - 5 * x; 8 if(y % 3 == 0){ 9 y /= 3;10 printf("%d,%d,%d\n", x, y, 100 - x - y);11 }12 }13 14 return 0;15 }
在本例中，我们通过步步优化，从三层循环简化到一层循环，执行效率是提高了，但是代码的可读性却是大大下降了。对于小程序来讲，可读性更重要一些。但是在一些性能关键的地方，优化是必不可少的。
初学者编程编程实战指南 (3)- 性能优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。