编程：对一个数组进行Shell排序的程序

1、南 京 邮 电 大 学编程实践报告 学号： 姓名： 指导老师：周文数理学院信息与计算科学2014年5月一、 第016E题1 问题描述。设计对一个数组进行Shell排序的程序。2 问题分析。对于此问题要注意两个方面，一个是数组的输入、输出，另一个则是如何实现shell排序。对于数组的输入、输出，要注意申请动态数组空间，并且最后要释放；对于实现shell排序，要注意利用循环结构实现步长变化时，数组元素的处理。3 设计思路。模块化设计：1) input模块：通过循环结构及数组实现数列的输入2) Shellsort模块：实现对数组的shell排序 3) output模块：实现对排序后数组的输出4) 主

2、函数模块：实现各模块函数功能4 流程图。系统整体流程Main主函数input函数output函数shellsort函数5 源程序。#include<iostream.h>void input(int a,int n)int i=0;cout<<"-请输入要排序的数-"<<endl;docin>>ai;i+;while(i<n);/输入void ShellSort(int a,int n)int d=n;while(d>1)d=(d+1)/2;/开始步长for(int i=0;i<n-d;i+)if(ai+d&

3、lt;ai)int temp;temp=ai;ai=ai+d;ai+d=temp;/互换/shell排序void output(int a,int n)for(int k=0;k<n;k+)cout<<ak<<' 'cout<<endl;/输出int main()int m;cout<<"-请输入要排序多少数-"<<endl;cin>>m;int *a;a=new intm;/申请动态数组空间input(a,m);ShellSort(a,m);cout<<"-

4、经shell排序后-"<<endl;output(a,m);return 0;6测试：包括测试数据、测试结果、结果分析测试数据：（1）8 29 34 5 2 6 （2）355 744 62 6 7 26 7 26 测试结果：结果分析：按照人工排序可验证排序结果正确7 心得。1. 学习了第一次接触的shell排序2. 学习了如何对程序进行模块化设计，并了解c+程序的重要性二、 第008M题1. 问题描述。编写一个子程序NewTon（float x0，float eps，float x1）。它的功能是用牛顿迭代法求 f(x)=在x=0附近的一个实根。牛顿迭代公式为： 迭代收敛

5、判据为：（eps为指定的迭代精度，例如1e-6）。若迭代成功，则返回非零值；否则，返回0。2. 问题分析。对于子程序牛顿迭代，我们在主函数中用迭代的方法实现，应用循环结构，当达到所需精度时循环截止。3. 设计思路。（1）计算f，(x) （2）代入x0，计算x1（3）计算f(x1)（4）判断|f(x1)|是否小于eps（4）如果小于eps，输出x1；如果大于eps，令x0等于x1，重复（2）-（4）步4. 流程图计算f，(x) 代入x0，计算x1计算f(x1)判断|f(x1)|是否小于eps输出x1x0=x1 |f(x1)|>eps |f(x1)|<eps5. 源程序。#includ

6、e <stdio.h>#include <conio.h>#include <math.h>float function(float x);float d2function(float x);int NewTon(float x0,float eps,float *x1);/函数声明int main() int n=0;float x0=0; /*初值*/ float xold,xnew; float eps=1e-6; /*精度*/ int NewTon(float x0,float eps,float *x1); xold=x0; while (!New

7、Ton(xold,eps,&xnew)xold=xnew; printf("输出根为:n");printf("x=%ft",xnew);getch(); return 0;float function(float x) return x*x*x-2*x*x+4*x+1;float d2function(float x) return 3*x*x-4*x+4;int NewTon(float x0,float eps,float *x1) *x1=x0-function(x0)/d2function(x0); if (fabs(function(*

8、x1)<eps) return 1; else return 0;6 测试：包括测试数据、测试结果、结果分析测试结果结果分析：当我们用printf("x=%ftf=%ft",xnew,function(xnew);替换printf("x=%ft",xnew);时，输出f,若f=0.000000，则结果正确：7. 心得1. 加深对牛顿迭代的理解2. 掌握对函数声明与函数定义3. 解决难点：如何利用循环结构进行迭代三、 第019M题1. 问题描述。设有n个人围坐在圆桌周围，从某个位置开始用自然数进行编号为1，2，n。然后从编号为k的人从1开始报数，数到

9、m的人便出列；下一个人(第m十1个)又从1开始报数，数到m的人便是第二个出列的人。如此继续下去，直到最后一个人出列为止。要求输出这个出列的顺序。 这个问题称为雅瑟夫(Josephu)问题。 具体要求如下： (1)n、m、k由键盘输入，输入前要有提示。 (2)在输入n后，动态建立方法说明中所需要建立的数组空间；程序运行结束时释放该存储空间。 (3)分别用n8，m4，k1以及n10，m12，k = 4调试运行你的程序。2. 问题分析。这是一个删除数组元素的问题，关键在于把握删除的数组下标；可以通过循环结构顺序删除。3. 设计思路。1) 建立一个长度为n的整型数组a,顺序存储1到n，表示n个人。2)

10、 从第k个人开始报数。3) 用i=k-1表示数组元素下标，假设从i“指向”的数组元素开始数，数到m，相当于i值增加m-1。如果在数的过程中遇到数组最后一个元素，则要从数组第一个元素继续数，即将数组想象成一个“环”，为此要用到求余运算，综合起来，被删除元素的下表计算公式为：i=(i+m-1)%n如果删除的正好是数组最后一个元素，那么下一轮要从数组第一个元素开始数。4) 重复执行步骤(3),直到n等于1。开始输入n,m,k顺序存储1至nn>0从k开始报数进行数组元素删除并输出n-结束4. 流程图否是 5. 源程序。#include<iostream.h>#include<s

11、tdlib.h>int main()int i,j,m,n,k,*pa;cout<<"input n and m"<<endl;cin>>n>>m;cout<<"input k"<<endl;docin>>k;while(k>n-1);/保证k符合要求pa=new intn;if(pa=NULL)cout<<"allocation failure"exit(1);for(i=0;i<n;i+)pai=i+1;i=k-1;c

12、out<<"出列顺序为："<<endl;while(n>0)i=(i+m-1)%n;cout<<pai<<" "for(j=i+1;j<n;j+)paj-1=paj;n-;if(i=n)i=0;cout<<endl;delete pa;/满足题目要求二return 0;6. 测试：包括测试数据、测试结果、结果分析n8，m4，k1n10，m12，k = 47. 心得1. 切记动态数组空间申请后要释放2. 学习如何应用循环结构对数组元素的删除四、 第018H题1. 问题描述。由n2个方块

13、排成n行n列的正方形称为“n元棋盘”。如果两个皇后位于n元棋盘上的同一行或同一列或同一对角线上，则称它们为互相攻击。要求输出使n无棋盘上的n个皇后互不攻击的所有布局。 具体要求如下； (1)n可由键盘输入。 (2)在输入n后，动态建立方法说明中所需要建立的数组空间；程序运行结束时释放该存储空间。 (3)分别用n4，5，6运行你的程序。2问题分析。皇后不能相互攻击，也就是不能处于同一条直线上，所以每一行只能有一个皇后，也不能处于同一列或斜线上。解决问题最直接的办法，就是在逐次在每一行每一个位置上尝试放一个皇后，并且在放后必须与前面放置的不能互相攻击。只要能够保证n个皇后都能找到正确的位置就是成功

14、。3设计思路。（1）输入皇后的总数（2）在第一行上一次的下一列放置皇后（3）在第下一行寻找不与前面相互攻击的位置（4）重复第（3）步n次（4）如果成功，输出皇后的排列输入皇后的总数在第一行上一次的下一列放置皇后在第下一行寻找不与前面相互攻击的位置输出皇后的排列结束开始（5）重复24步n次（6）结束4流程图。5源程序。#include <iostream>#include <math.h>using namespace std;int *position; /放置的位置int queen; /皇后数目int count=0; /第N种可能性/判断第n行放置皇后是否合法bo

15、ol SignPoint(int n)for (int i=0;i<n;i+) if(*(position+i)=*(position+n)|abs(*(position+i)-*(position+n)=abs(i-n) return false; return true;/设置皇后void SetQueen(int n=0)if(queen=n) printf("NO.%d: ",+count); printf("n");for(int i=0;i<queen;i+) for (int j=0;j<queen;j+)if(j=pos

16、itioni)printf("* ");else printf("0 "); printf("n");printf("n");/ return;elsefor(int i=0;i<queen;i+)positionn = i;if(SignPoint(n)SetQueen(n+1);/如果该位置放置皇后正确的话,则到下一行int main()cout<<"请输入皇后的总数:"<<endl;cin>>queen;position = new int100;

17、SetQueen();cout<<"摆放完毕"<<endl;return 0;6测试：包括测试数据、测试结果、结果分析测试数据分别为：n4，5，6测试结果：n=4当n=5时，情况为10种；n=67 心得。对于程序本身，学会使用模块函数；而函数主要包括位置的摆放和对位置摆放是否合理的判断。课程总结 一周，一个团队，四个程序，我们收获颇多，也感触颇多。 从所做程序来看，我们主要还是运用了所学习的c、c+语言，但与大一所做的程序设计不同的是，我们现在对于这几种编程语言算是得心应手了，并不会像大一时那么害怕。从程序中运用的知识来看，我们整体上还是学会采用了模块化的设计，学会如何对于函数声明，函数定义的使用，从而使得程序更加清晰。并且了解到循环语句是各个程序的重点和难点。另外，对于“约瑟夫环问题”和“n元棋盘问题”我们更多的是学会如何去分析问题、解决问题。例如对于“约瑟夫环”，我们首先考虑这是一个删除问题，而我们选择