(循环嵌套思路详解 | 一个“在盒子里过家家”的算法 -- 以冒泡排序与打印菱形为例)一:https://developer.aliyun.com/article/1518296?spm=a2c6h.13148508.setting.16.16ee4f0efBeqrc
2. 如何运用该思路详解引例?
来看题。
我们用“行”来代替上述“盒子”的概念,走一走这道题。以盒子为思考单位,在本题中,是以“行”为思考单位。
我们知道,本题首先要找出规律:每一行打印几个空格几个"*"
规律
我们以行为思考单位,思考每一行需要做什么。这些东西,到时候都是直接填充的外层for循环中的东西。
如图示代码,我们先将其分层,确定结构。重点看循环嵌套部分。它的构造思路:
1. 确定行数,即外层for循环的参数 i
2. 确定每一行里面要做什么(思路:先……再……然后……最后)
- 先(n+1-i)个空格,要打印这么多,自然而然地使用for循环
- 再打印"*",因为是等到空格打印完了才打印"*",所以关于"*"的部分要排在空格后面,讲究先来后到
- 最后换行,因为是每一行行末,图案打印完了才要换行,所以这句话排在最后。(有的人会误写到外层for循环外面……以行为单位思考,行里不就没有换行了嘛?)
代码实现
#include<iostream> using namespace std; int main() { // i是行数 // n=5的时候 // 第1行 2个空格 1个* // 第2行 1个空格 3个* // 第3行 0个空格 5个* // // 第i行 n+1-i个空格 2*i-1个* int input_line; int i,j,k; //遍历用的变量 cout << "please input a number:> "<< endl << endl; cin >> input_line; // n是行数的一半 n+1是中间行 int n = (input_line-1)/2; // 输出上半段 for(i=1; i<=n+1; i++){ //一行里面 先输出n+1-i个空格 for(j=1;j<=n+1-i;j++){ cout << " "; } //再输出2*i-1个* for(k=1;k<=2*i-1;k++){ cout << "*"; } //再换行 cout << endl; } // 输出下半段-- 和上面完全一样,就是行数要少一行 for(i=n;i>=1;i--){ //先输出n+1-i 个空格 for(j=1;j<=n+1-i;j++){ cout << " "; } //再输出2*i-1个* for(k=1;k<=2*i-1;k++){ cout << "*"; } cout << endl; } return 0; }
三、思路应用 -- 冒泡排序
找了两张图,看哪张都一样。有人觉得冒泡排序复杂,但用盒子思路,其实很好理解。我们以这两张图来讲解冒泡排序的盒子思路。
自己画的示意图
网上截取的示意图
以盒子为思考单位——这里的盒子——最大最宏观的循环,可以从图中一眼看出:冒泡的趟数。
每一趟里面,具体干了什么呢? 交换逆序元素位置。
所以每一趟要完成:比较相邻两个数的大小并换好位子。
还不够具体。具体怎么比?
1. 比较第1个数和第2个数大小,判断要不要换位子(假设从小到大排),要是原来后一个数比前一个数小(逆序了) ---> 要换位子
2. 比较第2个数和第3个数大小,判断要不要换位子
3. 比较第3个数和第4个数大小,判断要不要换位子
……
第n-1步: 比较第(n-1)个数和第 n 个数大小,判断要不要换位子
好像是循环欸,那就写成循环吧!i 已经用过了,那就用 j 吧!注意,每一趟并不是完全相同的。毕竟前面排好序的数,嫌累的话后面就没必要再排一遍了。
加个 for(j = 0; j < size - 1 - i; j++),是很自然的事情。本题中,外层 i 便是排序的趟数,里面的 j 则是每趟里面要两两交换的次数。代码如下:
//升序排序 for(i=0;i<ARR_SIZE-1;i++){ //每一趟要干什么? for(j=0;j<ARR_SIZE-1-i;j++){ //每次交换要干什么? int tmp; if(a[j]>a[j+1]){ tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp; } } }
当然,这不是完整的冒泡代码。因为它还能优化:如果中途某一趟发现这些数刚好已经有序了,那不就提前下班不用再干活了吗?因而我们加一个每趟开始对这趟数是否有序的判断:
//升序排序 int xch; for(i=0;i<ARR_SIZE-1;i++){ xch = 0; for(j=0;j<ARR_SIZE-1-i;j++){ int tmp; if(a[j]>a[j+1]){ tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp; xch = 1; } } if(!xch){ break; } }
就是这样了,利用盒子思路自然而然地思考和运用双层循环。
四、思路应用 -- 菱形打印的代码优化
代码如下,该代码是上面常规代码的优化版本。在此留给感兴趣的朋友们思考研究,不作过多解释了。
#include<iostream> using namespace std; int main() { int i,n,j; cout<<"请输入一个数字:"<<endl; cin>>n; for(i=-n;i<=n;i++) { for(j=1;j<=abs(i);j++) cout<<" "; for(j=1;j<=n-2*abs(i);j++) cout<<"*"; cout<<endl; } return 0; }
当然,菱形还可以是空心的,同样的思维模式,改动一下实心菱形代码即可:
空心菱形
#include <iostream> using namespace std; int main() { // i是行数 // n是中间行 int i,j,n,input; cout << "please input a number:> "<< endl << endl; cin>>input; n = input/2; //第一行 n个空格 1个* for(i=1;i<=n;i++){ cout<<" "; } cout<<"*"<<endl; //2到n行 for(i=1; i<=n; i++){ //一行里面先输出n-i个空格 for(j=1; j<=n-i; j++){ cout<<" "; } //然后输出1个* for(j=1; j<=2; j++){ cout<<"*"; for(j=1; j<=2*i-1; j++)//*+空格+*的长度 { cout<<" "; } cout<<"*"; } cout<<endl; } //下半部分 for(i=n-1; i>=1; i--){ for(j=1; j<=n-i; j++){ cout<<" "; } for(j=1; j<=2; j++){ cout<<"*"; for(j=1; j<=2*i-1; j++){ cout<<" "; } cout<<"*"; } cout<<endl; } //最后一行 和第一行一样 for(i=1;i<=n;i++) cout<<" "; cout<<"*"<<endl; return 0; }
五、总结
- 有意识地弱化“双层循环”这个概念——以盒子为单位思考问题!不要过于紧张所谓几个循环嵌套。对二维数组有一定的了解更好,它们的理解和学习可以是相辅相成的。
- 就像输入输出一样,自然而然用到了就写,而不要一上来就刻意地想:噢!这题我要用双层循环了,怎么凑才好呢?事实上不要对任何东西刻意,用心理解而不要刻意去背。
- 分析不同题目的“盒子”是什么,尝试迁移。
- 多做题找感觉永不过时!
- 码字不易,感谢支持!