循环结构

循环结构

数组(应需要产生)

循环+数组-->数据结构初步

例. 数4987.输出个位.十位.百位.千位

数组+循环

一维二维三维

离散-->线性（一对一）{链表栈队列}-->树形（一对多）-->图（多对多）

链表（线性最基础）：创建追加插入删除查找累加求和升序降序
New:删除查找累加求和升序降序

查找：查找x表示在链表中查找x第一次出现的位置

线性查找（O(n)）最少查找次数为1
如果N很大 (1+n)/2=N

二分查找：二分法树状数组
链表两个元素 a和len

数组a[101]
len变量

1 #include<iostream>
2 using namespace std;
3 int main(){
4   for(int i=起始值;i<=终了值; i++){
5     循环内容
6   }
7   return 0;
8 }

次数=终了值-起始值+1

找七练习(循环+分支)

从1到100之间输出7的倍数或者个位是7 十位是7的数

1 for(范围内){
2     if(按条件挑出){
3     
4     }
5 } //过筛子结构  范围内  按条件挑出 发起

用for循环结构从1-->100循环，条件为 i/10==7 || i%10==7 || i%7==0

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4 
 5   for(int i=0;i<=100;i++){
 6         if( i/10==7 || i%10==7 || i%7==0){
 7           cout<<i<<" ";//空格
 8       }
 9   }
10   return 0;
11 }

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   int x,f=1;
 5   cin>>x;
 6   if(x==2){cout<<"yes
";return 0;}
 7   for(int i=2;i<=x-1;i++){
 8       if(x%i==0){
 9          f=0;
10          break;//强制退出循环 
11       }
12   }
13   if(f==1){cout<<"yes
";}else{cout<<"no
";}
14   return 0;
15 }

优化:n-1 sqrt(n) 开平方

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 int main(){
 5   int x,f=1;//入口 
 6   cin>>x;
 7   if(x==2){cout<<"yes
"; return 0;} //越特殊的越往上写 
 8   if(x%2==0){cout<<"no
"; return 0;} 
 9   for(int i=2;i<=sqrt(x);i++){
10       if(x%1==0){
11          f=0;
12          break;
13       }
14   }
15   if(f==1){cout<<"yes
";}else{cout<<"no
";}
16   return 0;//出口 可以有多个 
17 }

break:强制结束循环

continue:结束本次继续下一次循环

输入100以内既是3的倍数又是5的倍数

1 #include<iostream>
2 using namespace std;
3 int main(){
4   for(int i=1;i<=6;i++){
5     cout<<i*15<<" "; 
6   }
7 
8   return 0;
9 }

二重循环

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   for(int i=1;i<=10;i++){
 5     for(int j=1;j<=12;i++){
 6       cout<<"0";
 7     }
 8     cout<<"
";
 9   }
10   return 0;
11 }

1 for(){
2     for(){
3     
4     } 
5 }//多重循环  穷举

九九乘法表

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   int n;
 5   cin>>n; 
 6   for(int i=1;i<=n;i++){
 7     for(int j=1;j<=n;j++){
 8     cout<<j<<"X"<<i<<"="<<i*j<<" ";
 9     }
10     cout<<"
";
11   }
12   return 0;
13 }

输出三角形

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   int n;
 5   cin>>n;
 6   for(int i=1;i<=n;i++){
 7     for(int j=1;j<=n-i;j++){
 8       cout<<" ";
 9     }
10     for(int j=1;j<=2*i-1;j++){
11       cout<<"*";
12     }
13     cout<<"
";
14   }
15   return 0;
16 }

*
**
***
****
*****
******

i " " "*"
————
1 0 1
2 1 2
3 2 3
i i-1 i

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   int n;
 5   cin>>n;
 6   for(int i=1;i<=n;i++){
 7     for(int j=1;j<=i-1;j++){cout<<" ";}
 8     for(int j=1;j<=i;j++){cout<<"*";}
 9     cout<<"
";
10   }
11   return 0;
12 }

***********
*********
*******
*****
***
*

i " " "*"
-------------------------------
1 0 11
2 1 9
3 2 7
4 3 5
i i-1 (2*n)-(2*i-1)

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   int n;
 5   cin>>n;
 6   for(int i=1;i<=n;i++){
 7     for(int j=1;j<=i-1;j++){
 8       cout<<" ";
 9     }
10     for(int j=1;j<=(2*n)-(2*i-1);j++){
11       cout<<"*";
12     }
13     cout<<"
";
14   }
15   return 0;
16 }

输出菱形

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   int n;
 5   cin>>n;
 6   for(int i=1;i<=n;i++){
 7     for(int j=1;j<=n-i;j++){cout<<" ";}
 8     for(int j=1;j<=2*i-1;j++){
 9       if(j==1 || j==2*i-1){
10         cout<<"*";
11       }else{
12         cout<<" ";
13       }
14    }   
15    cout<<"
";
16  }
17   for(int i=1;i<=n;i++){
18     for(int j=1;j<=i;j++){cout<<" ";}
19     for(int j=1;j<=(2*n)-(2*i+1);j++){
20       if(j==1 || j==(2*n)-(2*i+1)){
21      cout<<"*";
22       }else{
23          cout<<" ";
24       } 
25    }    
26    cout<<"
";
27   } 
28   return 0;
29 }

*
***
*****
*******
*********
*******
*****
***
*

i " " "*"
—————
1 4 1
2 3 3
3 2 5
i n-i 2*i-1

1 1 7
2 2 5
3 3 3
i i (2*n)-(2*i-1)

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4  int n;
 5  cin>>n;
 6  for(int i=1;i<=n;i++){
 7    for(int j=1;j<=n-i;j++){cout<<" ";}
 8    for(int j=1;j<=2*i-1;j++){cout<<"*";}
 9    cout<<"
";
10  }
11   for(int i=1;i<=n;i++){
12     for(int j=1;j<=i;j++){cout<<" ";}
13     for(int j=1;j<=(2*n)-(2*i+1);j++){cout<<"*";}
14     cout<<"
";
15   }
16   return 0;
17 }

多重循环

对于多重循环而言，外层循环执行一次，内层循环将执行若干次，知道内层循环的条件不成立，外层循环才去执行下一次操作。

在多重循环中，内层循环必须在内层结束，不能出现内外循环交叉的情况 (来源:CCF程序设计P146)

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4  for(int i=1;i<=7;i++){
 5    for(int j=1;j<=7;j++){
 6      for(int k=1;k<=7;k++){
 7        cout<<i<<j<<k<<"
";
 8      }
 9    }
10  } 
11   return 0;
12 }

输出所有1~7组合三位数的所有不重复的结果及总个数

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   int s=0;
 5   for(int i=1;i<=7;i++){
 6     for(int j=1;j<=7;j++){
 7          if(j!=1){
 8              for(int k=1;k<=7;k++){
 9                 if(k!=i&&k!=j){
10                   cout<<i<<j<<k<<"
";
11                   s++;
12                 }
13             }
14         }
15     }    
16    }
17   cout<<s;
18 }

输出100以内的所有质数

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   int f;
 5   for(int i=2;i<=100;i++){
 6       f=1;
 7       if(i==2){cout<<i<<" ";continue;}
 8       for(int j=2;j<=i-1;j++){
 9           if(i%j==0){
10              f=0;
11              break;
12               }
13       }
14       if(f==1){cout<<i<<" ";}
15   }
16   return 0;
17 }

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 int main(){
 5   int x,f;
 6   for(int i=2;i<=100;i++){  //冲突 
 7     f=1;
 8     x=i;
 9     if(x==2){cout<<x<<" ";continue;} 
10     if(x%2==0){continue;} 
11     for(int j=2;j<=sqrt(x);j++){
12         if(x%j==0){
13            f=0;
14            break;
15     }
16     }
17     if(f==1){cout<<x<<" ";}
18   }
19   
20   return 0; 
21 }

穷举枚举列举
分书方案(现在):五个人选五本书不是随机每本书只有一本
分书方案(复杂):n个人选n本书

1 1 1 0 1 //范围选择全部但排除三
1 1 0 1 1
0 1 1 0 1
1 1 0 1 0
0 0 1 1 1
行表示人
列表示书
1 表示喜欢
0 表示不喜欢
12345
21345
24513
31245
35241
15324
14325

维度:描述对象样本特征的个数
为每一个人描述他能选择的书

1 1 1 0 1
1 1 0 1 1
0 1 1 0 1
1 1 0 1 0
0 0 1 1 1

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   int ans=0;
 5   for(int i=1;i<=5;i++){
 6     if(i!=4){
 7       for(int j=1;j<=5;j++){
 8         if(j!=3 && j!=i){
 9           for(int k=1;k<=5;k++){
10             if(k!=1 && k!=4 && k!=i && k!=j){
11               for(int m=1;m<=5;m++){
12                 if(m!=3 && m!=5 && m!=i && m!=j && m!=k){
13                   for(int w=1;w<=5;w++){
14                     if(w!=1 && w!=2 && w!=i && w!=j && w!=k && w!=m){
15                        cout<<i<<j<<k<<m<<w<<"
"; 
16                        ans++;
17                     }
18                   }
19                 }
20               }
21             }
22           }
23         }
24       }
25     }
26   }
27   cout<<ans<<"
";
28   return 0;
29 }

谁是小偷

有ABCD四个嫌疑人只有一个小偷
A:"我不是小偷" i
B:"C是小偷 j
C;"小偷肯定是D" k
D;"C在冤枉好人" w
有一人在说谎三人说的是实话问谁是小偷
维度还是人

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   for(int i=0;i<=1;i++){
 5     for(int j=0;j<=1;j++){
 6       for(int k=0;k<=1;k++){
 7         for(int w=0;w<=1;w++){
 8           if(i+j+k+w==1 && (i!=1)+(k==1)+(w==1)+(w!=1)==3){
 9             cout<<i<<j<<k<<w<<"
";
10           }
11         }
12       }
13     }
14   }
15 
16   return 0;
17 }

在循环结构中的位运算

数据在计算机中采用二进制形式存储，一个0或者一个1称为一个二进制位，简称位。

& 按位与对应二进制位均为为1时结果为1 否则为0

| 按位或对应的二进制有一个为1则为1

^ 按位异或对应的二进制位数字不同时为1 否则为0

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4   int x=3,y=5;
//给定x y的值 经过下面三步之后可以将x y的值发生交换
 5   x^=y;
 6   y^=x;
 7   x^=y;
 8   cout<<x<<y;
 9   return 0;
10 }
运行结果为 5,3

~取反把运算数的各个二进制位按位求反

<<左移 m<<n 把m对应的二进制数的各个二进制位向左移n位高位丢弃低位0补齐

>>右移 m>>n 把m对应的二进制数的各个二进制位向右移n位低位丢弃高位0补齐

1 #include<iostream>
2 using namespace std;
3 int main(){
4   int x,y;
5   cin>>x>>y;
6   cout<<(x&y)+( (x^y)>>1 );
7   return 0;
8 }

模拟步骤//以3 5为例

①将x y转化成二进制数即 011 101

②x&y=011&101=001

③x^y=011^101=110

④(x^y)>>1=(110)>>1=11

⑤(x&y)+( (x^y)>>1 )=001+11=001+011=100

⑥输出二进制数100对应的十进制数4