C++第八课一维数组

一维数组第8课怎样用以学过知识解决以下问题输入N个数,要求反向输出这N个数.例如:输入545391输出19354分析在解决这个问题时，要把很多数据保存下来，如果用以前的方法定义变量很麻烦，我们可以批量定义变量。最常用的方法是定义数组来解决。

inta[10];a是数组名，10表示有10个变量，分别是a[0]、a[1]、……a[9],且每个值取整型。例1:输入N(N<10)个数,要求反向输出这N个数.例如:输入545391输出1935400000A[0]A[1]A[2]A[3]A[4]00000A[5]A[6]A[7]A[8]A[9]定义数组:inta[10];输入:cin>>n;for(i=0;i<n;i++)cin>>a[i];45391输出:for(i=n-1;i>=0;i--)cout<<a[i];一维数组的初始化在定义数组时对数组元素赋以初值。

例如：inta[10]={0,1,2,3,4,5,6,7,8,9};可以只给一局部元素赋初值。

例如：inta[10]={0,1,2,3,4};在对全部数组元素赋初值时，可以不指定数组长度。

例如：inta[]={1,2,3,4,5}两个数组转存，要用循环一一导入，不能直接赋值。for(i=0;i<n;i++)a[i]=b[i];例2求不达均分的人数〔P1057〕输入n个(n<=10)学生的成绩，统计有多少人的分数低于平均分。样例：输入：4{n=4,表示有4个人的成绩}80884490输出：1{只有1个人的分数低于平均分}1、先定义数组a[i]用来存放n个人的分数。存入总分、均分的变量。2、输入局部：在输入的过程中可以顺便统计一下总分。3、计算均分4、统计低于均分的人数。5、输出。P1072陶陶摘苹果第一个应用：进制转换[例3]将一个十进制整数转化为二进制数.分析:例如将十进制数12转化为二进制数,方法如下:把十进制数除以2,用一个数组a来存放余数,将商作为新的数继续除以2,反复进行,一直除到商为0时停止。输出：将a组数反向输出cin>>x;k=0;while(){k=k+1;//K是数组的下标指针a[k]=x%2;x=x/2;}for()cout<<a[i];P1098十六进制中10用A表示，11用B…….P1099第二个应用：选择排序

例4：选择排序:将n个整数按由小到大的顺序输出。

样例：输入：6{表示有6个数}

574386

输出:345678假设6个数据是：a[]=574386，我们把1号位放最小数，就从2号位开始，一一与1号位比较，如果比它小，那么交换，这样做到6号位，就使得1号位存放一个最小的数，下面再把2号位放次小的数，从3号位开始比较，以此类推，直至n-1号位。如：a[1]a[2]a[3]a[4]a[5]a[6]574386574386{a[1]与a[2]比较，不交换}574386{a[1]与a[3]比较，交换}475386{a[1]与a[4]比较，交换}375486{a[1]与a[5]比较，不交换}{a[1]与a[6]比较，不交换}这时，a[1]就是最小的一个数，下面再进行确定a[2]，方法同样，最后确定a[5]，a[6]不必确定。参考程序如下:cin>>n;inta[n+5];//多定义几个for(i=1;i<=n;i++)

cin>>a[i];

for(i=1;i<=n-1;i++)for(j=i+1;j<=n;j++)if(a[i]>a[j])swap(a[i],a[j]);for(i=1;i<=n;i++)cout<<a[i]<<““;使用swap交换函数必须使用头文件#include<algorithm>使用sortmaxmincount函数也要使用这个头文件。直接用sort函数排序如果数组a[0]---a[n-1]sort(a,a+n)如果数组a[1]---a[n]sort(a+1,a+n+1)sort(a+1,a+n+1)排序练习P1102排序默认的是由小到大排序，查名次的时候应该从后往前。

for(i=n;i>=1;i--)if(a[i]==x)break;cout<<??;P1124最好不使用sort排序，选择排序比较的时候要注意两种情况都交换：a数组存编号b数组存值，比较的时候：if(b[i]<b[j]||b[i]==b[j]&&a[i]>a[j])输出的时候，每行要输出三个数。基数排序例7：将n个小于100的不同的正整数进行从小到大排序。样例：输入：543561

输出：13456采用选择排序的运算次数是n2，可以采用另外一种方法：cin>>n;for(i=1;i<=n;i++){cin>>x;a[x]=1;}for(i=1;i<=100;i++)if(a[i]>0)cout<<i<<““;

如果有相同的，那么做一些改动：a[x]++;在输出的时候当a[i]>1的时候，必须全部输出。优点：时间复杂度O(n)。弱点：必须要知道数据的范围，且是整数。[练习]P1097明明的随机数分析：如果采用一般的模拟方法来做，很麻烦，直接使用基数排序法。P1096用上述类似的方法。数组的值开始都是0；移走的，将数组的值变成1。最后统计还有多少个值是0。基数排序的运用P1101P1096数组定义在函数外，默认值为0读一对数，将数组中的这一局部变为1最后统计数组中还有多少个数是0.P1129十个数的操作a[]x输入三种情况：(1)输出NO:if(x<=a[1]||x>=a[10])……else{for(i=1;i<=11;i++)//找一下这个数有没有if(a[i]>=x)break;//第i位数有可能等于或大于if(a[i]==x){第〔2〕种情况}else{第〔3〕种情况}}第〔2〕种情况：将第i位删除方法：从i位到n-1位，前面一位取后面一位的值。for(j=i;j<=n-1;j++)a[j]=a[j+1];for(i=1;i<=9;i++)cout<<a[i]<<‘‘;第〔3〕种情况：在第i位插入X方法：从后面第n+1位到第i+1位，取前面一位的值。for(j=n+1;j>=i+1;j--)a[j]=a[j-1];for(i=1;i<=11;i++)cout<<a[i]<<‘‘;约瑟夫问题：设有N个人依次围成一圈,从第1个人起开始报数,报到M的人出列,下一个人再从1起报数,报到M的人出列,下一个人再从1起报数,如此继续,直到所有人均出列为止.设N个人的编号为1,2,...,N,打印出出列的次序。例如：输入：N=6，M=3，那么输出出列的顺序是：364251inti=0;a[i]初始化为1；//a[i]=1表示i在圈上。for(j=1;j<=n;j++){p=0;do{i=i+1;if(i>n)i=1;p=p+a[i];}while(p!=m);//报一轮的模拟a[i]=0;cout<<i<<““;//输出，同时将这个人出圈}P1125高精度算法P1870a[100]=1;b[100]=1；{a数组作为1！，b数组存放和}for(i=2;i<=n;i++){

求i的阶乘:a[]*i,结果用a数组存放；求a[]+b[]，结果用b数组存放；}输出：b数组的结果。

[1][2][3]……[95][96][97][98][99][100]000456789a000000321b+

0111

111

111

7

70010加法过程

g=0;{进率初始为0}for(i=maxn;i>=1;i--){s=a[i]+b[i]+g;a[i]=s%10;g=s/10;}

5

50

4

4asg输出局部：i=1;while〔a[i]==0&&i<maxn)i++;//防止和是０for(j=i;j<=maxn;j++)cout<<a[j];高精度*单精度输入时的第一个数用数组存放，而第二个数直接用一个整型变量存放。

[1][2][97][98][99][100]006789ab*S乘法过程

g=0;{进率初始为0}for(i=maxn;i>=1;i--){s=a[i]*b+g;a[i]=s%