利用数组处理批量数据
　　1．用筛选法求100之内的素数。
　　【解】 所谓“筛选法”指的是“埃拉托色尼（Eratosthenes）筛选法”。他是古希腊的著名数学家。他采取的方法是：在一张纸上写上1～1000的全部整数，然后逐个判断它们是否为素数，找出一个非素数，就把它挖掉，最后剩下的就是素数，见图5.1。

图  5.1
　　具体做法如下：
　　（1）先将1挖掉（因为1不是素数）。
　　（2）用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。
　　（3）用3去除它后面各数，把3的倍数挖掉。
　　（4）分别用4，5…各数作为除数去除这些数以后的各数。这个过程一直进行到除数后面的数已全被挖掉为止。例如在图5.1中找1～50的素数，要一直进行到除数为47为止（事实上，可以简化，如果需要找1～n的素数表，只须进行到除数为（取其整数）即可。例如对1～50，只须进行到将7()作为除数即可。请读者思考为什么）。
　　上面的算法可表示为：
　　（1）挖去1；
　　（2）用下一个未被挖去的数p去除p后面各数，把p的倍数挖掉；
　　（3）检查p是否小于n的整数部分（如果n=1000，则检查p＜31?），如果是，则返回（2）继续执行，否则就结束；
　　（4）纸上剩下的数就是素数。
　　用计算机解此题，可以定义一个数组a，a[1]～a[n] 分别代表1～n这n个数，如果检查出数组a的某一元素的值是素数，就使它变为0，最后剩下不为0的就是素数。
　　程序如下：
     
     #include <iostream>
     #include <iomanip>
     using namespace std;
     #include <cmath>
     int main( )
      {int i,j,n,a[101];	//定义a数组包含101个元素
       for (i=1;i<=100;i++)	//a[0]不用, 只用a[1]~a[100]
         a[i]=i;	//使a[1]~a[100]的值为1~100
       a[1]=0;	//先“挖掉”a[1]
       for (i=2;i<sqrt(100);i++)
         for (j=i+1;j<=100;j++)
           {if (a[i]!=0 && a[j]!=0)
             if (a[j]%a[i]==0)
              a[j]=0;  }	//把非素数“挖掉”
         cout << endl;
         for (i=1,n=0;i<=100;i++)
          {if (a[i]!=0)	//选出值不为0的数组元素, 即素数
            {cout << setw(5) << a[i] << " ";	//输出素数, 宽度为5列
             n++;}	//累计本行已输出的数据个数
           if(n==10)	//输出10个数后换行
             {cout << endl;
              n=0;}
           }
          cout << endl;
          return 0;
        } 
     
　　运行结果：
     
      2    3    5    7   11   13   17   19   23   29
     31   37   41   43   47   53   59   61   67   71
     73   79   83   89   97
     
　　2．用选择法对10个整数排序。
　　【解】 选择排序的思路如下：
　　设有10个元素a[1]～a[10]，将a[1]与a[2]～a[10]比较，若a[1]比a[2]～a[10]都小，则不进行交换，即无任何操作。若a[2]～a[10]中有一个以上比a[1]小，则将其中最小的一个（假设为a[i]）与a[1]交换，此时a[1]中存放了10个中最小的数。第二轮将a[2]与a[3]～a[10]比较，将剩下9个数中的最小者a[i]与a[2]对换，此时a[2]中存放的是10个中第2小的数。以此类推，共进行9轮比较，a[1]～a[10] 就已按由小到大顺序存放。
　　程序如下：
     
     #include <iostream>
     using namespace std;
     int main( )
       {int i,j,min,temp,a[11];
        cout << "enter data:" << endl;
        for (i=1;i<=10;i++)
          {cout << "a[" << i << "]=";
           cin >> a[i];	//输入10个数 
          }
        cout << endl << "The original numbers:" << endl;
        for (i=1;i<=10;i++)
          cout << a[i] << " ";	//输出这10个数 
        cout << endl;
        for (i=1;i<=9;i++)	//以下8行是对10个数排序 
          {min=i;
           for (j=i+1;j<=10;j++)
             if (a[min]>a[j])  min=j;
             temp=a[i];	//以下3行将a[i+1]~a[10]中最小者与a[i]对换
             a[i]=a[min];
             a[min]=temp;
           }
        cout << endl << "The sorted numbers:" << endl;
        for (i=1;i<=10;i++)	//输出已排好序的10个数 
          cout << a[i] << " ";
        cout << endl;
        return 0;  
     }  
     
　　运行结果：
     
     enter data:
     a[1]=36 ↙
     a[2]=?– 9↙
     a[3]=5↙
     a[4]=6↙
     a[5]=?–1↙
     a[6]=35↙
     a[7]=34↙
     a[8]=738↙
     a[9]=18↙
     a[10]=11↙
     
     The original numbers:
     36 –9 5 6 –1 35 34 738 18 11 
     The sorted numbers:
     –9 –1 5 6 11 18 34 35 36 738
     
　　说明：定义a数组有11个元素，即a[0]～a[10]，但实际上只对a[1]～a[10]这10个元素输入值并排序。a[0]未用到，这样符合人们的习惯。
　　3．求一个3×3矩阵对角线元素之和。
　　【解】 
     
     #include <iostream>
     using namespace std;
     int main( )
      {int a[3][3],sum=0;
       int i,j;
       cout << "enter data:" << endl;
       for (i=0;i<3;i++)
          for (j=0;j<3;j++)
            cin >> a[i][j];
       for (i=0;i<3;i++)
          sum=sum+a[i][i];
       cout << "sum=" << sum << endl;
       return 0;
       }
     
　　运行结果：
     
      enter ata：
      1 3 5 7 9 11 13 15 17↙
      sum=27
     
　　此程序中用的是整型数组，运行结果是正确的。如果用的是实型数组，只须将程序第4行的int改为float或double即可，在输入数据时可输入单精度或双精度的数。
　　4．有一个已排好序的数组，输入一个数，要求按原来排序的规律将它插入数组中。
　　【解】 假设数组a有n个元素，而且已按升序排列，在插入一数时按下面的方法处理：
　　（1）如果插入的数num比a数组最后一个数大，则将插入的数放在a数组末尾。
　　（2）如果插入的数num不比a数组最后一个数大，则将它依次和a[0]～a[n–1]比较，直到出现a[i]>num为止，这时表示a[0]～a[i–1] 各元素的值比num小，a[i]～a[n–1] 各元素的值比num大。num理应插到a[i–1]之后、a[i]之前。怎样才能实现此目的呢？将a[i]～a[n–1]各元素向后移一个位置（即a[i]变成a[i+1]，…，a[n–1]变成a[n]）。然后将num放在a[i]中。
　　按此思路编写程序如下：
     
     #include <iostream>
     using namespace std;
     int main( )
      {int a[11]={ 1 6 13 17 28 40 56 78 89 100};
       int num,i,j;
       cout << "array a:" << endl;
       for (i=0;i<10;i++)
        cout << a[i] << " ";
        cout << endl;
        cout << "insert data:";
        cin >> num;
        if (num>a[9])
          a[10]=num;
        else
         {for (i=0;i<10;i++)
          {if (a[i]>num)
            {for (j=9;j>=i;j– –)
              a[j+1]=a[j];
             a[i]=num;
             break;
            }
           }
          }
         cout << "Now, array a:" << endl;
         for (i=0;i<11;i++)
           cout << a[i] << " ";
         cout << endl;
         return 0;
      } 
     
　　运行结果：
     
     array a:
     1 6 13 17 28 40 56 78 89 100
     insert data:15↙
     Now,array a:
     1 6 13 15 17 28 40 56 78 89 100
     
　　5．将一个数组中的值按逆序重新存放。例如，原来顺序为8，6，5，4，1。要求改为1，4，5，6，8。
　　【解】 解此题的思路是：以中间的元素为中心，将其两侧对称的元素的值互换即可。例如将8和1互换，将6和4互换。程序如下：
     
     #include <iostream>
     using namespace std;
     int main( )
     { const int n=5;
       int a[n],i,temp;
       cout << "enter array a:" << endl; 
       for (i=0;i<n;i++)
         cin >> a[i];
       cout << "array a:" << endl;
       for (i=0;i<n;i++)
        cout << a[i] << " ";
       for (i=0;i<n/2;i++)            //循环的作用是将对称的元素的值互换
         { temp=a[i];
           a[i]=a[n–i–1];
           a[n–i–1]=temp;
          }
       cout << endl << "Now,array a:" << endl;
       for (i=0;i<n;i++)
         cout << a[i] << " ";
       cout << endl;
       return 0;
     }   
     
　　运行结果：
     
     enter array a:
     9 8 7 6 5↙
     array a:
     9 8 7 6 5
     Now, array a:
     5 6 7 8 9
     
　　如果数组的大小改变，只须修改程序第4行即可。
　　6．打印出以下的杨辉三角形（要求打印出10行）。
     
     1
     1   1
     1   2   1
     1   3   3   1
     1   4   6   4  1
     1   5  10  10  5  1
     (    (   (   (   ( ?? (
     
　　【解】 杨辉三角形是展开后各项的系数。例如：
　　(a?+?b)0展开后为  1	系数为1
　　(a?+?b)1展开后为  a+b，	系数为1，1
　　(a?+?b)2展开后为  a2+2ab+b2	系数为1，2，1
　　(a?+?b)3展开后为  a3+3a2b+3ab2+b3	系数为1，3，3，1
　　(a?+?b)4展开后为  a4+4a3b+6a2b2+4ab3+b4	系数为1，4，6，4，1
　　以上就是杨辉三角形的前5行。杨辉三角形各行的系数有以下规律：
　　（1）各行第一个数都是1。
　　（2）各行最后一个数都是1。
　　（3）从第3行起，除上面指出的第一个数和最后一个数外，其余各数是上一行中的同列和前一列两个数之和。例如第4行第2个数（3）是第3行第2个数（2）和第3行第1个数（1）之和。可以这样表示：a[i][j]=a[i–1][j]+a[i–1][j–1]。其中，i为行数，j为列数。
　　算法如下：
　　（1）使二维数组a第1列和对角线元素的值为1；
　　（2）数组其他各元素的值为a[i][j]=a[i–1][i–1]+a[i–1][i]；
　　（3）输出数组各元素的值。
　　程序如下：
     
     #include <iostream>
     #include <iomanip>
     using namespace std;
     int main( )
      {const int n=11;
       int i,j,a[n][n];	//数组为11行11列, 0行0列不用
       for (i=1;i<n;i++)
         {a[i][1]=1;	//使第1列元素的值为1
          a[i][i]=1;	//使对角线元素的值为1
         }
       for (i=3;i<n;i++)	//从第3行开始处理
         for (j=2;j<=i–1;j++)
            a[i][j]=a[i–1][j–1]+a[i–1][j];
       for (i=1;i<n;i++)	//输出数组各元素的值
         {for (j=1;j<=i;j++)
            cout << setw(6) << a[i][j] << " ";
          cout << endl;
         }
       cout << endl;
       return 0;
     }
     
　　运行结果：
     
     1
     1     1
     1     2     1
     1     3     3     1
     1     4     6     4     1
     1     5    10    10     5     1
     1     6    15    20    15     6     1
     1     7    21    35    35    21     7     1
     1     8    28    56    70    56    28     8     1
     1     9    36    84   126   126    84    36     9     1
     
　　7．找出一个二维数组中的鞍点，即该位置上的元素在该行上最大，在该列上最小（也可能没有鞍点）。
　　【解】 一个二维数组最多有一个鞍点，也可能没有。解题思路是：先找出一行中值最大的元素，然后检查它是否为该列中的最小值，如果是，则是鞍点（不需要再找别的鞍点），输出该鞍点；如果不是，则再找下一行的最大数……如果每一行的最大数都不是鞍点，则此数组无鞍点。
　　程序如下：
     
     #include <iostream>
     using namespace std;
     int main( )
     { const int n=4,m=5;				//假设数组为4行5列     
       int i,j,a[n][m],max,maxj;
       bool flag;
       for (i=0;i<n;i++)				//输入数组
          for (j=0;j<m;j++)
            cin >> a[i][j];
       for (i=0;i<n;i++)         
        {max=a[i][0]; maxj=0;			//开始时假设a[i][0]最大, 将列号(0)赋给maxj保存
         for (j=0;j<m;j++)				//找出第i行中的最大数
           if (a[i][j]>max)
            {max=a[i][j];				//将本行的最大数存放在max中
             maxj=j;				//将最大数所在的列号存放在maxj中
            }
         flag=true;					//先假设是鞍点, 用flag为真来代表
         for (int k=0;k<n;k++)
           if (max>a[k][maxj])			//将最大数和其同列元素相比
             {flag=false;				//如果max不是同列最小, 表示不是鞍点, 令flag为假
              continue;}
         if(flag)					//如果flag为真, 表示是鞍点
           {cout << "a[" << i << "][" << "[" << maxj << "]=" << max << endl;
     //输出鞍点的值和所在行列号
            break;
           }
         }
       if(!flag)						//如果flag为假表示鞍点不存在
         cout << "It does not exist!" << endl;
        return 0;
     } 
     
　　运行结果：
     
     ① 1 2 3 4 5↙					（输入4行5列数据）
        2 4 6 8 10↙
        3 6 9 12 15↙
        4 8 12 16 20↙
        a[0][4]=5					（0行4列元素是鞍点, 其值为5）
     ② 1 12 3 4 5↙					（输入4行5列数据)
        2 4 16 8 10↙
        3 6 9 12 15↙
        4 8 12 16 20↙
        It does not exist!				（无鞍点）
     
　　8．有15个数按由大到小的顺序存放在一个数组中，输入一个数，要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中，则打印出“无此数”。
　　【解】 从一维数组中查一个数最简单的方法是从第1个数开始顺序查找，将要找的数与数组中的数一一比较，直到找到为止（如果数组中无此数，则应找到最后一个数，然后判定“找不到”）。
　　但这种“顺序查找法” 效率低，如果表列中有1000个数，且要找的数恰恰是第1000个数，则要进行999次比较才能得到结果。平均比较次数为500次。
　　折半查找法是效率较高的一种方法。基本思路如下：
　　假如有已按由小到大排好序的9个数，a[1]～a[9]，其值分别为
1，3，5，7，9，11，13，15，17
　　若想查3是否在此数组中，可以先找出表列中居中的数，即a[5]，将要找的数3与a[5]比较，a[5]的值是9，发现a[5]>3，显然3应当在a[1]～a[5]，而不会在a[6]～a[9]。这样就可以缩小查找范围，甩掉a[6]～a[9]这一部分，即将查找范围缩小为一半。再找a[1]～a[5]的居中的数，即a[3]，将要找的数3与a[3]比较，a[3]的值是5，发现a[3]>3，显然3应当在a[1]～a[3]。这样又将查找范围缩小一半。再将3与a[1]～a[3]的居中的数a[2]比较，发现要找的数3等于a[2]，查找结束。一共比较了3次。如果表列中有n个数，则最多比较的次数为 int(log2n)+1。
　　程序如下：
     
     #include <iostream>
     using namespace std;
     int main( )
     { const int n=7;
       int i,number,top,bott,mid,loca,a[n];
       bool flag=true,sign;
       char c;
       cout << "enter data:" << endl;
       cin >> a[0];
       i=1;
       while(i<n)
        {cin >> a[i];
         if (a[i]>=a[i–1])
           i++;
         else
           cout << "enter this data again:";
        }
       cout << endl;
       for (i=0;i<n;i++)
         cout << a[i] << " ";
       cout << endl;
       while(flag)
         {cout << "input number to look for:"; 
          cin >> number;
          sign=false;	//sign为假表示尚未找到
          top=0;	//top是查找区间的起始位置
          bott=n–1;	//bott是查找区间的最末位置
          if ((number<a[0])||(number>a[n–1]))	//要查的数不在查找区间内
            loca = –1;	//表示要查找的数不在正常范围内
          while ((!sign) && (top<=bott))
            {mid=(bott+top)/2;	//找出中间元素的下标
             if (number==a[mid])	//如果要查找的数正好等于中间元素
              {loca=mid;	//记下该下标
               cout << "Find " << number << ", its position is " << loca+1 << endl;
                     //由于下标从0算起, 而人们习惯从1算起, 因此输出数的位置时要加1
               sign=true;	//表示找到了
               }
             else if (number<a[mid])	//如果要查找的数小于中间元素的值
               bott=mid–1;	//只须从下标为0~mid–1的范围中找
             else	//如果要查找的数不小于中间元素的值
               top=mid+1;	//只须从下标为mid+1~bott的范围中找
            }
           if(!sign || loca == –1)	//sign为假或loca等于–1, 意味着找不到
             cout << number << " has not found." << endl;;
           cout << "continue or not(Y/N)?";
           cin >> c;
           if (c=='N' || c=='n')
            flag=false;	//flag为开关变量, 控制程序是否结束运行
            }
        return 0;
      }
     
　　运行结果：
     
     enter data:	（输入数据）
     6 8 12 10↙	（数据未按由小到大顺序输入）
     enter this data again:	（要求重新输入)
     23 34 44 45 56 57 58↙