菱形打印程序——谈如何学习算法.doc

菱形打印程序谈如何学习算法菱形打印很多人，打印菱形在控制台的思路是，把菱形上下拆分，分两段很接近的代码来打印，其实这样代码很不好看，并且不好阅读我们知道，要打印的图案是这种： * * * *满足上下对称，左右对称，那么，你能不能也弄一个二重循环，同样是对称的？很简单，首先我们要抛开习惯性思维，for循环不一定要在0开始或者0结束我们可以让循环从 -c 到 c ，这样不就轻松产生一个对称的吗？（只要取个绝对值）我们把菱形的中心看成是坐标0,0，那么，会输出星号的坐标，是 |x| + |y| = c 的点由此可得#include #define IABS(x) ( (x) = 0 ? (x) : -(x) ) /定义一个计算绝对值的宏void print(int size) / size是这个菱形的半径，直径会是size * 2 + 1int x, y;for (y = -size; y = size; y+)for (x = -size; x = size; x+)if ( IABS(x) + IABS(y) = size ) /x和y各自的绝对值的和，即 |x| + |y| = sizeputchar(*);elseputchar( );putchar(n);int main()print(5); /输出一个半径为5的菱形getchar();return 0;如果我需要得到空心菱形呢？非常非常简单，因为菱形边界上的点，满足的是|x| + |y| = c所以，我们只要把那个if里的小于等于号，改成双等于号 = 就可以了再类似地，如果我不要*号，我要最外层是字母A，然后里一层是B这样呢？即： A ABAABCBA ABA A那么，我们只要在putchar那里做一个字符计算：void print(int size) / size是这个菱形的半径，直径会是size * 2 + 1int x, y;for (y = -size; y = size; y+)for (x = -size; x = size; x+)if ( IABS(x) + IABS(y) = size ) /x和y各自的绝对值的和，即 |x| + |y| size，所以前面输出了三个 ，然而由于|x|渐渐减小，之后输出了一个*，由于|x|又渐渐增大，又输出了三个 ，这样就巧妙地完成了左右的对称。又由于下一次循环|y|比这次循环小1，所以就“更容易”输出*，由于|y|也有对称的特性，所以完成了上下的对称。至此，我们大概就对为什么可以上下左右对称有了一个感性的认识，不过恐怕更多的是对这些代码的惊叹：为什么这样写就能巧妙地做到这些？IABS(x) + IABS(y) = size这个表达式也太神奇了！其实我们上来看程序的运行过程，只是为了从运行过程中试着找到入口去探索这个算法的本质是什么，这是一个从现象到本质的过程，而不能被现象吓到了。我们把菱形的中心看成是坐标0,0，那么，会输出星号的坐标，是 |x| + |y| = c 的点那么程序的原理实际上就是通过枚举(x,y), |x| = size, |y| = size, x, y Z中的点（即下图中红色部分，包括边界），再通过一个式子来确认合法点，如果合法，就输出*，反之输出 ：那么我们又有疑问了，为什么是|x| + |y| = c？我们来证明一下上面右上角的红色三角区域（包括边界）的所有点(x,y)（x，yN），x+y=size（自己先试试看）：通过观察，我们可以发现y的取值范围随着x在改变，至于“怎么改变”则与size有关，那么我们可以想一下，如果我们把其中的y用size和x表示，这个不等式不就容易得证了吗？那么我们可以得知y0, size-x（xsize），取两边分别讨论，当y=0时，x+y=x=size，当y=size-x时，x+y=x+size- x=size，当y(0, size-x)（xsize）时，x+ysize。综上所述，x+y=size，证毕。其实即使你不会证明，也可以当作公式默认下来，这都无关紧要。于是我们就能自己写出|x| + |y| = c这个式子了，也就知道了这个算法的本质，现在一切都掌握在我们手中，甚至我们可以对原程序做一点改动：由于是枚举(x,y)(x,y), |x| = size, |y| = size, x, y Z，而且有绝对值的对称做保障，那么无论x、y谁在外面只要全枚举到就行了，所以也可以把x放在外层循环：for (x = -size; x = size; x+)for (y = -size; y = size; y+)if (IABS(x) + IABS(y) = size) /x和y各自的绝对值的和，即 |x| + |y| = sizeputchar(*);elseputchar( );putchar(n);观察原程序的输出，我们可以发现由于对称的缘故，程序输出的右侧多输出了我们看不见的空格，我们也可以不输出它：if (IABS(x) + IABS(y) = size ) /x和y各自的绝对值的和，即 |x| +