while循环

【while详解】

while循环在很多场合用起来是十分方便的，现再次对其作更加详细的介绍。

1.程序的测试数据有多组，假如测试数据一共有N组，N从键盘输入。

用for循环可以这样做：

int N;

cin>>N;

for (int i=1;i<=N;i++)

{

cin>>测试数据；

…

}

用while循环我们这样做：

int N;

cin>>N;

while （N--） //即先判断N的值，只要N不为0就执行循环；然后N的值自减1；这样循环次数为N

{

cin>>测试数据；

…

}

2. while后面的条件可为多个条件，多个条件可用逻辑运算符计算整个条件表达式的值。

如上节课中遇到的求m和n这两个正整数的最大公约数问题。采用传统算法的思路是：先找出m和n中的较小者min(m,n)，那么这两个数的最大公约数gcd必定满足“min(m,n)>=gcd>=1”；我们让gcd的值从min(m,n)开始循环递减，每循环一次减1，直到找到第一个同时满足m% gcd==0和n%gcd==0的gcd的值为止，这个值就是m和n的最大公约数。

用while循环我们可以写出这样的程序：

#include <iostream>

using namespace std;

int main()

{

         int m,n;

         cin>>m>>n;

         int gcd;

         if (n>m)           //将m和n中较小的那个放在gcd中

             gcd=m;

     else

         gcd=n;

         while (m%gcd!=0||n%gcd!=0)     //不能满足同时整除时，继续循环

         {

                   gcd--;

         }

         cout<<gcd;

         return 0;

}

3.无限循环

while （1）   //无限循环

括号中的条件表达式写为“1”表示值恒为真，那么循环会一直进行下去，永不停止。要想从循环中退出来，可以在循环体里面加入满足某种情况下的break或者return 0语句。

4.从键盘无限制读入数据

例如：输入一些数，求它们的和。

这里输入的一些数并没有限定数的数量，也没有要求事先从键盘上输入即将输入数字的个数，意思就是你想输入多少个就多少个。我们可以这样写程序：

#include <bits/stdc++.h>

using namespace std;

int main()

{

         int x,sums=0;

         while(cin>>x)   //只要读到了数字，就继续循环

             sums+=x;

         cout<<sums;

         return 0;

}

那么，程序怎么知道我已经不想输入数字了，而要求最终输出结果呢？

如果你已经决定输入完毕了，可以先按Enter键，再按Ctrl+Z键，最后再按Enter键，即可结束输入。

【再谈素数/质数】

数学王国里正在召开只有素数才能参加的机密会议，这时又来了几个数字要求进入会场，请你帮助门卫统计一下，其中有多少个是素数。

输入：第一行，整数n；第二行，n 个正整数。

输出：素数的个数。

输入样例：

5

2 6 9 7 10

输出样例：

2

#include <bits/stdc++.h>

using namespace std;

int main()

{

     int n,x,ans=0;

     cin>>n;

     for (int i=1;i<=n;i++)

     {

         cin>>x;

         bool book=0;      //bool型数据类型的值只有真和假，即1和0两种情况

         for (int j=2;j<=sqrt(x);j++)

         {

              if (x%j==0)

              {

                   book=1;

                   break;

              }

         }

         if (x>1&&book==0) ans++;    //这里非常关键，想想为什么？

     }

     cout<<ans;

     return 0;

}

上周大家所写的程序实际上是有一些问题的，上周没有提出来，现在来讨论一下：

①      上面程序中加粗的if判断那条语句，如果不加“x>1”，这个程序就是有问题的，因为如果输入的正整数是1，会被判为素数，但1不是素数。2和3都是素数，上述程序又是否解决了这个问题呢？当输入的x值为2或者3时，j<=sqrt(x)一定不成立，程序不会进入内层循环，book的值为0，2和3都会被判为素数，没有问题。

②      为什么只判到j<=sqrt(x)就可以了，而不用写成j<x？因为在等式M*N=K中，如果M>sqrt(K)，那么N<sqrt(K)一定成立，所以根本没有必要到大于sqrt(x)的范围内去找因子。

③      注意sqrt(x)的结果可为整数或小数，有同学这样写程序：

int kk=0;

for (int j=2;j<=sqrt(x);j++)

{

     if (x%j==0)

     {

              book=1;

          break;

     }

else kk++;

     }

if (kk== sqrt(x)-1) cout<<x;     //即使x是素数，这里的等式多半也是不成立的

所以上面这样写也是不能正确输出素数的，当然我们可以int(sqrt(x))来解决小数这个问题，不过要注意int（）这个函数是向下取整的。另外如果输入的正整数是1、2、3，那么这种写法也是不能解决问题的，需要单独处理。

【欧几里得算法】

再谈求两个正整数的最大公约数欧几里得算法：

实现程序如下：

#include <iostream>

using namespace std;

int main()

{

     int n,m,r;

     cin>>m>>n;   //这里的m和n谁大谁小，根本就没关系，经过一轮循环它们的大小顺序始终会正常 

     r=m%n;

     while (r!=0)

     {

         m=n;

         n=r;

         r=m%n;

     }

     cout<<n;

     return 0;

}

那么这个算法为何是正确的呢？现在我们来证明一下，要特别注意的是证明的思路（下面证明过程中用到的数均为整数）。

先正向推：假如m和n的最大公约数是d，r=m%n，那么d也是n和r的最大公约数。

如果m和n的最大公约数是d，那么m和n 可表示为：m=k1*d，n=k2*d；r=m%n有m=k3*n+r，r=m-k3*n=k1*d-k3*k2*d=d*(k1-k2*k3)，这足可以证明d也是n和r的公约数。那么如何证明d一定是n和r的最大公约数呢？我们可以采用反证法。假如存在d2>d并且d2是n和r的最大公约数，那么r=d2*x，n=d2*y；m=k3*n+r=k3*d2*y+d2*x=d2*(k3*y+x)，这样d2也一定是m 和n的公约数，并且这个d2还要大于d，这与最开始的假设“m和n的最大公约数是d”矛盾，所以假设不成立，d一定是n和r的最大公约数，正向得证。

反向证明：假如n和r的最大公约数是d，r=m%n，那么d也是m和n的最大公约数。思路同上面完全一样，自己可以试一试，这里免证。

【拆分数字】

输入一个不超过整型范围的正整数，依次拆分出这个数每位上的数字并输出，每个数之间用一个空格隔开。如输入356809，输出为：3 5 6 8 0 9。

【分解质因数】

把一个合数分解成若干个质因数乘积的形式（即求质因数的过程）叫做分解质因数。分解质因数（也称分解素因数）只针对合数。

输入一个正整数n，将n分解成质因数乘积的形式。

如输入：36

输出：36=2*2*3*3