资源描述
一维数组 怎样用以学过知识解决下列问题 输入 N个数 ,要求反向输出这 N个数 . 例如 :输入 5 4 5 3 9 1 输出 1 9 3 5 4 分析 在解决这个问题时，要把很多数据保存下 来，如果用以前的方法定义变量很麻烦，我 们可以批量定义变量。最常用的方法是定义 数组来解决。 int a10; a是数组名， 10表示有 10个变量，分别是 a0、 a1、 a9,且每个值取整型。 例 1:输入 N(Nn; for (i=0;iai; 4 5 3 9 1 输出 : for (i=n-1;i=0;i-) coutai; 一维数组的初始化 在定义数组时对数组元素赋以初值。 例如： int a10=0,1,2,3,4,5,6,7,8,9; 可以只给一部分元素赋初值。 例如： int a10=0,1,2,3,4; 在对全部数组元素赋初值时，可以不指定数组长度。 例如： int a=1,2,3,4,5 两个数组转存，要用循环一一导入，不能直接赋值。 for (i=0;in;i+) ai=bi; 例 2求不达均分的人数 （ P1057） 输入 n个 (nx; k=0; while ( ) k=k+1; /K是数组的下标指针 ak=x% 2; x=x / 2; for ( ) coutn; int an+5; /多定义几个 for (i=1;iai; for (i=1;i=n-1;i+) for (j=i+1; jaj) swap(ai,aj); for (i=1; i=n;i+) coutai“ “; 使用 swap交换函数必须 使用头文件 #include 使用 sort max min count 函数也要使用这个头文件。 直接用 sort 函数排序 如果数组 a0-an-1 sort(a,a+n) 如果数组 a1-an sort(a+1,a+n+1) sort(a+1,a+n+1) 排序练习 P1102 排序默认的是由小到大排序，查名次的 时候应该从后往前。 for (i=n;i=1;i-) if (ai=x) break; cout?; P1124 最好不使用 sort 排序，选择排序比较的时候要注意两种情况 都交换： a数组存编号 b数组存值，比较的时候： if (biaj) 输出的时候，每行要输出三个数。 基数排序 例 7：将 n个小于 100的不同的正整数进行从小到大排序。 样例：输入： 5 4 3 5 6 1 输出： 1 3 4 5 6 采用选择排序的运算次数是 n2，可以采用另外一种方法： cinn; for (i=1;ix; ax=1; for (i=1;i0) couti1 的时 候，必须全部输出。 优点：时间复杂度 O(n)。 弱点：必须要知道数据的范围，且是 整数。 练习 P1097 明明的随机数 分析：如果采用一般的模拟方法来做，很麻烦，直接使用基 数排序法。 P1096 用上述类似的方法。 数组的值开始都是 0； 移走的，将数组的值变成 1。 最后统计还有多少个值是 0。 基数排序的运用 P1101 P1096 数组定义在函数外，默认值为 0 读一对数，将数组中的这一部分变为 1 最后统计数组中还有多少个数是 0. P1129 十个数的操作 a x输入 三种情况： (1)输出 NO: if (x=a10) else for (i=1;i=x) break; /第 i位数有可能等于或大于 if (ai=x) 第（ 2）种情况 else 第（ 3）种情况 第（ 2）种情况： 将第 i位删除 方法：从 i位到 n-1位，前面一位取后面一位的值。 for (j=i;j=n-1;j+) aj=aj+1; for (i=1;i=9;i+) coutai=i+1;j-) aj=aj-1; for (i=1;i=11;i+) coutai ; 约瑟夫问题：设有 N个人依次围成一圈 , 从第 1个人起开始报数 , 报到 M的人出列 ,下一个人再从 1起报数 ,报到 M的人出列 , 下一个人 再从 1起报数 ,如此继续 , 直到所有人均出列为止 . 设 N个人的编号 为 1,2,.,N, 打印出出列的次序。例如：输入： N=6， M=3，则输 出出列的顺序是： 3 6 4 2 5 1 int i=0; ai初始化为 1； /ai=1表示 i在圈上。 for (j=1;jn) i=1; p=p+ai; while (p!=m); /报一轮的模拟 ai=0; couti“ “; /输出，同时将这个人出圈 P1125 高精度算法 P1870 a100=1; b100=1； a数组作为 1！， b数组存放和 for (i=2; i=1;i-) s=ai+bi+g; ai=s % 10; g=s / 10; 5 5 0 4 4 a s g 输出部分： i=1; while （ ai=0 /防止和是 for (j=i; j=maxn;j+) cout=1;i-) s=ai*b+g; ai=s % 10; g=s /10; a数组存放被减数， b数组存放减数 ,结果仍用 a数组存放。 for (i=maxn; i=1;i-) if (aibi) ai-1=ai-1-1; ai=ai+10; ai=ai-bi; 高精度减法
展开阅读全文