线性方程组的数值算法C语言实现(附代码)

线性方程组AX=B 的数值计算方法实验

一、 实验描述：

随着科学技术的发展，线性代数作为高等数学的一个重要组成部分，在

科学实践中得到广泛的应用。本实验的通过C 语言的算法设计以及编程，来实现高斯消元法、三角分解法和解线性方程组的迭代法（雅可比迭代法和高斯-赛德尔迭代法），对指定方程组进行求解。

二、 实验原理：

1、高斯消去法：

运用高斯消去法解方程组，通常会用到初等变换，以此来得到与原系数矩阵等价的系数矩阵，达到消元的目的。初等变换有三种：(a)、(交换变换)对调方程组两行；(b)、用非零常数乘以方程组的某一行；(c)、将方程组的某一行乘以一个非零常数，再加到另一行。

通常利用(c)，即用一个方程乘以一个常数，再减去另一个方程来置换另一个方程。在方程组的增广矩阵中用类似的变换，可以化简系数矩阵，求出其中一个解，然后利用回代法，就可以解出所有的解。 2、选主元：

若在解方程组过程中，系数矩阵上的对角元素为零的话，会导致解出的结果不正确。所以在解方程组过程中要避免此种情况的出现，这就需要选择行的判定条件。经过行变换，使矩阵对角元素均不为零。这个过程称为选主元。选主元分平凡选主元和偏序选主元两种。平凡选主元：

如果()0p pp a ≠，不交换行；如果()0p pp a =，寻找第p 行下满足()0p pp a ≠的第

一行，设行数为k ，然后交换第k 行和第p 行。这样新主元就是非零主元。偏序选主元：为了减小误差的传播，偏序选主元策略首先检查位于主对角线或主对角线下方第p 列的所有元素，确定行k ，它的元素绝对值最大。然后如果k p >，则交换第k 行和第p 行。通常用偏序选主元，可以减小计算误差。 3、三角分解法：

由于求解上三角或下三角线性方程组很容易所以在解线性方程组时，可将系数矩阵分解为下三角矩阵和上三角矩阵。其中下三角矩阵的主对角线为1，上三角矩阵的对角线元素非零。有如下定理：

如果非奇异矩阵A 可表示为下三角矩阵L 和上三角矩阵U 的乘积：

A LU = (1)

则A 存在一个三角分解。而且，L 的对角线元素为1，U 的对角线元素非零。得到L 和U 后，可通过以下步骤得到X ：

(1)、利用前向替换法对方程组LY B =求解Y 。 (2)、利用回代法对方程组UX Y =求解X 。

4、雅可比迭代：

考察一般形式的线性方程组：

,

1,2,3,N

ij j

i j

a x

b i N ==∑ (2)

设从(2)中分离变出变量i X 将它改写成：

111,2,3,N

i i ij j

j ii

j i x b a x i N a =≠?? ?

=

-= ? ???

∑ (3)

据此建立雅可比迭代公式：

(k 1)

(k)111,2,3,N i i ij j

j ii j i x b a x i N a +=≠?? ?=-= ? ???

∑ (4)

5、高斯-赛德尔迭代：

通过对雅可比迭代的观察，由于通常1k x +被认为是比k x 更好的x 的近

似值，所以在计算1k y +时用1k x +来替换k x 是合理的。所以对雅可比迭代进行了改进，得到了高斯-赛德尔迭代，其收敛速度更快。它的迭代公式为：

(k 1)

(k 1)11

1,2,3,N

i i ij j

j ii

j i x b a x i N a ++=≠?? ?

=-= ? ???

∑ (5)

三、 实验内容：

1、许多科学应用包含的矩阵带有很多零。在实际情况中很重要的三角形线

性方程组有如下形式:

111211122232

2233343

221111

11N N N N N N N N N N N N

d x c x b a x d x c x b a x d x c x b a x d x c x b a x d x b --------+=++=++=++=+=

(6)

构造一个程序求解三角形线性方程组。可假定不需要行变换，而且可用第k 行消去第k+1行的k x 。

2、使用C 语言编写一个程序求解线性方程组AX B =，其中：

1357213500252631A -????-?

?=????---??1234B ????

??=??????

3、使用2中的程序求解线性方程组AX B =，其中=1

j ij N N

A a i -???==?? ；而且1

ij N B b ???=??，11b N =当2i ≥时，1(i 1)/(i 1)N

i b =--。对3,7,11N =的情况分别求解。精确解为[]1111X '= 。对得到的结果与精确解的差异进行解释。

4、修改2中的程序，使得它可以通过重复求解N 个线性方程组

J J AC E = 其中1,2,,J N = (7)

来得到1A - ，

则

1212[C C C ][E E E ]N N A = (8)

而且

112[C C C ]N A -= (9)

5、设有如下三角线性方程组，而且系数矩阵具有严格的对角优势：

111211122232

2233343

221111

11N N N N N N N N N N N N

d x c x b a x d x c x b a x d x c x b a x d x c x b a x d x b --------+=++=++=++=+=

(10)

（1）、根据解线性方程组的迭代法原理，设计一个算法来求解上述方程

组，算法必须有效利用系数矩阵的稀疏性。

(2)、用（1）中的程序解下列的三角线性方程组：

(a)121232

3

43

454849

50

49

5043+43+43

+

434343

m m m m m m m m m m m m m m m m +=+=+=+=++

=+= (b)121232

3

43

4

54849

50

49

50

41+42+41+

424142

m m m m m m m m m m m m m m m m +=+=+=+=++

=+=

6、利用高斯-赛德尔迭代法求解下列带状方程：

12312341234523

4

5646

47

48495047

48

495048

49

50

12252122521225212521225212252125x x x x x x x x x x x x x x x x x x x x x x x x x x x x x -+=-+-+=-+-+=-+-

+

=

-+-+=-+-=-+=

四、计算结果及分析：

1、此题由于没有提供具体的实例计算，所以,以《数值方法(MATLAB 版)》(第四版)第107页的11、12题为例，进行代码的计算验证。此题以高斯消去法作为算法的核心，并依此来进行程序的编写。 实例：

第11题:求解下列线性方程组。

1212

32

3

43

4

27239

423102412

x x x x x x x x x x +=+-=++=-=

第12题:求解下列线性方程组。

121232

3

43

4

5259

34219262

x x x x x x x x x x +=-

+=--+=+= 第11题的正确解为:[]1322x '=- 第12题的正确解为:[]2321x '=-

精确的结果。

2、此题以带选主元的三角分解法作为算法的核心，以此进行程序的编写。

验算:将x 代入AX B =中，算出[]1.0000 2.0001 3.0000 4.0000B

'= 与实际的B 进行比较，此算法在保留四位小数的时候，得出的解比较的正确。

3

经过程序计算可看出，在3,7N =时得出的结果比较的精确，与所给

的答案一致。但在11N =时，得出的结果与实际的结果相差很大。可能由于计算时迭代次数较多，机器误差累计造成。

4、此题由于没有提供具体的实例计算，所以,以《数值方法(MATLAB 版)》

(第四版)第119页的第4(b)题为例，进行代码的计算验证。J 1-27A =42125-2??

????

????

1E 11J ????=??????

经验算，可推出[]1012A C C C -=。

5、此题用高斯-赛德尔迭代法作为算法的核心，以此编写程序。通过对给出的两个实例的计算：

6、用5中的程序，通过高斯-赛德尔迭代求解此带状方程解为：

五、实验结论：

经过C程序计算的得出的数据，经验算后，都比较好的符合了计算的要求，这同时也证明了算法的正确性。通过本次实验，了解科学计算中的解线性方程组的一些基本方法，通过亲自设计算法，对这些科学的方法有了更加深刻的认识。对以后的学习有很大帮助。

附件：

一、(高斯消去法)：

#include

#include//头文件声明//

float main()

{

float *a,*b,*c,*d,*x,**A;

FILE *fp;//定义指向文件的指针//

float temp,sum;

int i,j,N;

fopen_s(&fp,"D:\\vs程序\\3.4.6-1.12.txt","w" );//确定文件指针的指向// printf("请输入此方程组的元的个数：\n");

scanf_s("%d",&N);

a=(float *)malloc((N-1)*sizeof(float));//动态定义一维数组，下同//

b=(float *)malloc(N*sizeof(float));

c=(float *)malloc((N-1)*sizeof(float));

d=(float *)malloc(N*sizeof(float));

x=(float *)malloc(N*sizeof(float));

A=(float **)malloc(N*sizeof(float *));//动态定义二维数组//

for (i=0;i

A[i]=(float *)malloc(N*sizeof(float));

for(i=0;i

{

for(j=0;j

A[i][j]=0;//先使系数矩阵为一个0矩阵//

}

printf("请输入对角系数d[i]:\n");

for(i=0;i

{

scanf_s("%f",&d[i]);//输入对角元素的值//

}

printf("请输入系数a[i]:\n");

for(i=0;i

{

scanf_s("%f",&a[i]);//输入对角线下的元素系数//

}

printf("请输入系数c[i]:\n");

for(i=0;i

{

scanf_s("%f",&c[i]);//输入对角线下的元素系数//

}

for(i=0;i

{

A[i][i]=d[i];//给系数矩阵的对角元素重新赋值//

}

for(i=0;i

{

A[i+1][i]=a[i];

A[i][i+1]=c[i];

}//给系数矩阵重新赋值，使之成为三角形线性方程组//

printf("请输入系数b[i]:\n");

for(i=0;i

{

scanf_s("%f",&b[i]);//输入题中的b矩阵//

}

for(i=0;i

{

temp=(*(A[i+1]+i))/(*(A[i]+i));//对角元素所在列的下一行元素比上此对角元素，求出其比例关系//

b[i+1]=b[i+1]-b[i]*temp;//根据上条指令求出的比例关系，进行行变换//

for(j=0;j

A[i+1][j]=A[i+1][j]-A[i][j]*temp;//进行行变换，已达到消元的目的// }

x[N-1]=b[N-1]/A[N-1][N-1];//经过上面的行变换，求出只有一个未知数的那一行的未知数大小//

for(i=2;i<=N;i++)

{

sum=0;

sum+=A[N-i][N+1-i]*x[N+1-i];

x[N-i]=(b[N-i]-sum)/A[N-i][N-i];

}//此循环根据书上的回代公式和上面求出的未知数的值，求出输入的方程组的解//

if (fp!=NULL)

{

fprintf(fp,"此方程组的解为：");

for(i=0;i

fprintf(fp,"\nx[%d]=%9.4f",i,x[i]);//将计算结果，输出到文件指针所指向的文件中去//

fclose(fp);//关闭文件//

}

free(a);//释放动态定义指针所指向的空间，便于下次使用。下同//

free(b);

free(c);

free(d);

free(x);

for(i=0; i

{

free(A[i]);

}

free(A);

return 0;

}

二、(三角分解法)：

#include

#define N 11

float x[N],y[N];//定义外部变量，便于函数间的传递//

/*偏序选主元函数*/

void select(float(*X)[N],float Y[N])

{

float max,c[N],b;

int i,j,k,n;

for(i=0;i

{

max=X[i][i];

for(j=i+1;j

{

if(X[j][i]>=max)

{

max=X[j][i];

n=j;

}

}//此循环用于比较出一列中最大的那个元素，并把其所在的列数赋给n//

b=Y[i];

Y[i]=Y[n];

Y[n]=b;//Y矩阵跟随X矩阵的行变换，相当于增广矩阵的变换//

for(k=0;k

{

c[k]=X[i][k];

X[i][k]=X[n][k];

X[n][k]=c[k];//根据上面的n值，对X进行行变换，选出最大主元作为对角元素//

}

}

for(i=0;i

{

if(X[i][i]==0)

max=X[i][i];

for(j=0;j

{

if(X[j][i]>=max)

{

max=X[j][i];

n=j;

}

}

b=Y[i];

Y[i]=Y[n];

Y[n]=b;

for(k=0;k

{

c[k]=X[i][k];

X[i][k]=X[n][k];

X[n][k]=c[k];

}

}

}

/*行变换函数*/

void ShiftRow(float(*X)[N])

{

float m[N];

int k,i,j;

for(k=0;k

{

for(i=k;i

{

m[i]=X[i+1][k]/X[k][k];//将对角元素以下所在列的的元素与其比较，并求出其比较值//

X[i+1][k]=m[i];//将以上比较出的值赋给与对角元素所比的元素//

for(j=k;j

X[i+1][j+1]=X[i+1][j+1]-X[k][j+1]*m[i];//经过以上的变换，进行行变换// }

}

}

/*求L矩阵和Y矩阵函数*/

float* Low(float(*X)[N],float Y[N])

{

float L[N][N]={0},sum;//先定义L矩阵为零矩阵//

int i,j;

for(i=0;i

L[i][i]=1;//定义对角元素为1//

for(j=0;j

{

for(i=j+1;i

L[i][j]=X[i][j];//将上面变换后的矩阵的对应值赋给L矩阵// }

y[0]=Y[0];//求出y矩阵的首元素//

for(i=1;i

{

sum=0;

for(j=0;j

sum+=L[i][j]*y[j];

y[i]=Y[i]-sum;

}//根据已知的首元素，利用回代法求出Y矩阵//

return (y);

}

/*求U矩阵和X矩阵函数*/

float* Up(float(*X)[N],float Y[N])

{

float U[N][N]={0},sum;//先定义U矩阵为零矩阵//

int i,j;

for(i=0;i

{

for(j=i;j

U[i][j]=X[i][j];//将经变换后的X矩阵的对应值赋给U矩阵// }

x[N-1]=Y[N-1]/U[N-1][N-1];

for(i=N-2;i>=0;i--)

{

sum=0;

for(j=N-1;j>i;j--)

sum+=U[i][j]*x[j];

x[i]=(Y[i]-sum)/U[i][i];

}//利用回代法求出x的值//

return(x);

}

float main()

{

float A[N][N],B[N],*Y,*X;

int i,j;

FILE *fp;//定义文件指针//

fopen_s(&fp,"D:\\vs程序\\3.5.8--2.3.txt","w" );//定义文件指针所指位置//

printf("请输入所求方程组的系数矩阵：\n");

for(i=0;i

for(j=0;j

scanf_s("%f",&A[i][j]);//输入所求方程组的系数矩阵//

printf("请输入系数B[i]：\n");

for(i=0;i

scanf_s("%f",&B[i]);

select(A,(float*)B);//调用偏序选主元函数，进行主元选取//

ShiftRow(A);//对经过选主元后的系数矩阵进行行变换//

Y=Low(A,(float*)B);//计算Y矩阵//

X=Up(A,(float*)Y);//求出x的值，并返回//

if (fp!=NULL)

{

fprintf(fp,"此方程组的解为：");

for(i=0;i

fprintf(fp,"\nx[%d]=%9.4f",i,X[i]);//将结果输出到文件指针所指的文件里// fclose(fp);//关闭文件//

}

return 0;

}

三、(高斯-赛德尔迭代)

#include

#include

#include//头文件声明//

#define nMax 100//最大迭代次数//

#define eps 0.00000000001//所需的精度//

#define N 50

double x[N];

/*高斯-赛德尔迭代函数*/

double* GaussSeidel(double (*ax)[N],double *by,double *xpre)

{

double err,temp;

int i,j,k;

for(i=0;i

{

for(k=0;k

{

err=0;//在每次循环中将误差定义为零，便于下面的误差计算//

for(j=0;j

{

temp=0;

for(i=0;i

{

if(i==j)//根据迭代公式，不计算i=j这一项的值//

continue;

temp+=ax[j][i]*xpre[i];//根据迭代公式，先求出其和//

}

x[j]=(by[j]-temp)/ax[j][j];//高斯-赛德尔迭代公式//

err+=fabs(xpre[j]-x[j]);//对误差项进行计算//

xpre[j]=x[j];//将当前x值作为前一个x的值，代入进行迭代// }

if(err

break;

}

x[i]=x[j];//将每次符合条件的x值赋到另一个数组里//

}

printf("%d\n",k);

return(x);//返回符合条件的x值//

}

void main()

{

double a[N][N],b[N],xp[N],*X;

int i,j;

FILE *fp;//定义指向文件的指针//

fopen_s(&fp,"D:\\vs程序\\test.txt","w" );//定义文件指针所指位置//

for(i=0;i

{

for(j=0;j

{

a[i][j]=0;

if(i==j)

a[i][j]=4;

}

}

for(i=1;i

a[i][i-1]=a[i-1][i]=1;//与上一个for循环一起，根据题意给系数矩阵赋值// for(i=0;i

b[i]=3;

for(i=0;i

xp[i]=1;//自定义初始迭代值//

X=GaussSeidel(a,b,xp);//调用GaussSeidel函数，计算x的值//

if (fp!=NULL)

{

fprintf(fp,"此方程组的解为：\n");

for(i=0;i

{

fprintf(fp," x[%d]=%12.10f",i,X[i]);//将结果输出到文件指针所指的文件里//

if(i%3==0)//每行输出三个值//

fprintf(fp,"\n");

}

fclose(fp);//关闭文件//

}

}

数据结构与算法C语言版期末复习题

《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

C语言几种常见的排序方法

C语言几种常见的排序方法 2009-04-2219:55 插入排序是这样实现的： 首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。 从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。 重复2号步骤，直至原数列为空。 插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的： 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。 重复2号步骤，直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。 选择排序 选择排序是这样实现的： 设数组内存放了n个待排数字，数组下标从1开始，到n结束。 i=1 从数组的第i个元素开始到第n个元素，寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n－1算法结束，否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同，它是这样的： 首先新建一个空列表，作用与插入排序中的"有序列表"相同。 找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。 重复2号步骤，直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。

非常全的C语言常用算法

一、基本算法 1．交换（两量交换借助第三者） 例1、任意读入两个整数，将二者的值交换后输出。 main() {int a,b,t; scanf("%d%d",&a,&b); printf("%d,%d\n",a,b); t=a; a=b; b=t; printf("%d,%d\n",a,b);} 【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。 假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。 其中t为中间变量，起到“空杯子”的作用。 注意：三句赋值语句赋值号左右的各量之间的关系！ 【应用】 例2、任意读入三个整数，然后按从小到大的顺序输出。 main() {int a,b,c,t; scanf("%d%d%d",&a,&b,&c); /*以下两个if语句使得a中存放的数最小*/ if(a>b){ t=a; a=b; b=t; } if(a>c){ t=a; a=c; c=t; } /*以下if语句使得b中存放的数次小*/ if(b>c) { t=b; b=c; c=t; } printf("%d,%d,%d\n",a,b,c);} 2．累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。例1、求1+2+3+……+100的和。 main() {int i,s; s=0; i=1; while(i<=100) {s=s+i; /*累加式*/ i=i+1; /*特殊的累加式*/ } printf("1+2+3+...+100=%d\n",s);} 【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。

C语言9种常用排序法

C语言9种常用排序法 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.带哨兵的直接插入排序 9.基数排序 例子：乱序输入n个数，输出从小到大排序后的结果1.冒泡排序 #include int main() { int i, j, n, a[100], temp; while(scanf("%d",&n)!=EOF) { for(i=0;i

for(i=0;ia[j+1]) //比较a[j]与a[j+1],使a[j+1]大于a[j] { temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; } } } for(i=0;i int main() {

int i, j, n, a[100], t, temp; while(scanf("%d",&n)!=EOF) { for(i=0;ia[j]) t = j; } temp = a[i]; a[i] = a[t]; a[t] = temp; } for(i=0;i

C语言经典算法100例(1---30)

2008-02-18 18:48 【程序1】 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】 题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高 于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提 成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000)

几种排序算法的分析与比较--C语言

一、设计思想 插入排序：首先，我们定义我们需要排序的数组，得到数组的长度。如果数组只有一个数字，那么我们直接认为它已经是排好序的，就不需要再进行调整，直接就得到了我们的结果。否则，我们从数组中的第二个元素开始遍历。然后，启动主索引，我们用curr当做我们遍历的主索引，每次主索引的开始，我们都使得要插入的位置（insertIndex）等于-1，即我们认为主索引之前的元素没有比主索引指向的元素值大的元素，那么自然主索引位置的元素不需要挪动位置。然后，开始副索引，副索引遍历所有主索引之前的排好的元素，当发现主索引之前的某个元素比主索引指向的元素的值大时，我们就将要插入的位置（insertIndex）记为第一个比主索引指向元素的位置，跳出副索引；否则，等待副索引自然完成。副索引遍历结束后，我们判断当前要插入的位置（insertIndex）是否等于-1，如果等于-1，说明主索引之前元素的值没有一个比主索引指向的元素的值大，那么主索引位置的元素不要挪动位置，回到主索引，主索引向后走一位，进行下一次主索引的遍历；否则，说明主索引之前insertIndex位置元素的值比主索引指向的元素的值大，那么，我们记录当前主索引指向的元素的值，然后将主索引之前从insertIndex位置开始的所有元素依次向后挪一位，这里注意，要从后向前一位一位挪，否则，会使得数组成为一串相同的数字。最后，将记录下的当前索引指向的元素的值放在要插入的位置（insertIndex）处，进行下一次主索引的遍历。继续上面的工作，最终我们就可以得到我们的排序结果。插入排序的特点在于，我们每次遍历，主索引之前的元素都是已经排好序的，我们找到比主索引指向元素的值大的第一个元素的位置，然后将主索引指向位置的元素插入到该位置，将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法，使得挪动的次数相对较多，如果对于排序数据量较大，挪动成本较高的情况时，这种排序算法显然成本较高，时间复杂度相对较差，是初等通用排序算法中的一种。 选择排序：选择排序相对插入排序，是插入排序的一个优化，优化的前提是我们认为数据是比较大的，挪动数据的代价比数据比较的代价大很多，所以我们选择排序是追求少挪动，以比较次数换取挪动次数。首先，我们定义我们需要排序的数组，得到数组的长度，定义一个结果数组，用来存放排好序的数组，定义一个最小值，定义一个最小值的位置。然后，进入我们的遍历，每次进入遍历的时候我们都使得当前的最小值为9999，即认为每次最小值都是最大的数，用来进行和其他元素比较得到最小值，每次认为最小值的位置都是0，用来重新记录最小值的位置。然后，进入第二层循环，进行数值的比较，如果数组中的某个元素的值比最小值小，那么将当前的最小值设为元素的值，然后记录下来元素的位置，这样，当跳出循环体的时候，我们会得到要排序数组中的最小值，然后将最小值位置的数值设置为9999，即我们得到了最小值之后，就让数组中的这个数成为最大值，然后将结果数组result[]第主索引值位置上的元素赋值为最小值，进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result[]。选择排序的优势在于，我们挪动元素的次数很少，只是每次对要排序的数组进行整体遍历，找到其中的最小的元素，然后将改元素的值放到一个新的结果数组中去，这样大大减少了挪动的次序，即我们要排序的数组有多少元素，我们就挪动多少次，而因为每次都要对数组的所有元素进行遍历，那么比较的次数就比较多，达到了n2次，所以，我们使用选择排序的前提是，认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序，他的比较次数大于插入排序的次数，而挪动次数就很少，元素有多少个，挪动次数就是多少个。 希尔排序：首先，我们定义一个要排序的数组，然后定义一个步长的数组，该步长数组是由一组特定的数字组成的，步长数组具体得到过程我们不去考虑，是由科学家经过很长时间计算得到的，已经根据时间复杂度的要求，得到了最适合希尔排序的一组步长值以及计算

C语言常用算法集合

1.定积分近似计算： /*梯形法*/ double integral(double a,double b,long n) { long i;double s,h,x; h=(b-a)/n; s=h*(f(a)+f(b))/2; x=a; for(i=1;i

} 3.素数的判断： /*方法一*/ for (t=1,i=2;i0;n/=10) k=10*k+n%10; return k; } /*求回文数*/ int f(long n) { long k,m=n; for(k=0;n>0;n/=10) k=10*k+n%10; if(m==k) return 1; return 0; } /*求整数位数*/ int f(long n) { int count; for(count=0;n>0;n/=10) count++; return count; }

数据结构经典算法 C语言版

//插入排序法 void InsertSort() { int s[100]; int n,m,j,i=0,temp1,temp2; printf("请输入待排序的元素个数："); scanf("%d",&n); printf("请输入原序列："); for (i=0; is[n-1]); s[n]=m; for (i=0; im) { temp1=s[i]; s[i]=m; for (j=i+1; j

//堆排序 static a[8] = {0,25,4,36,1,60,10,58,}; int count=1; void adjust(int i,int n) { int j,k,r,done=0; k = r = a[i]; j = 2*i; while((j<=n)&&(done==0)) { if(j=a[j]) done = 1; else { a[j/2] = a[j]; j = 2* j; } } a[j/2] = r; } void heap(int n) { int i,j,t; for(i =n/2;i>0;i--) adjust(i,n); printf("\n初始化成堆===> "); for(i = 1;i < 8;i++) printf("%5d",a[i]); for(i = n-1;i>0;i--) { t = a[i+1]; a[i+1] = a[1]; a[1] = t; adjust(1,i); printf("\n第%2d步操作结果===>",count++); for(j = 1;j<8;j++) printf("%5d",a[j]); } }

最新C语言常用算法集合汇总

C语言常用算法集合

1.定积分近似计算： /*梯形法*/ double integral(double a,double b,long n) { long i;double s,h,x; h=(b-a)/n; s=h*(f(a)+f(b))/2; x=a; for(i=1;i

if(n==1||n==2) *s=1; else{ fib(n-1,&f1); fib(n-2,&f2); *s=f1+f2; } } 3.素数的判断： /*方法一*/ for (t=1,i=2;i0;n/=10) k=10*k+n%10; return k; } /*求回文数*/

基于C语言的多种排序方法的实现

基于C语言地多种排序方法地实现 1 引言 1.1 课题背景 排序问题源远流长，一直是数学地重要组成部分.随着各种信息地快速更新，排序问题也走进了其他领域以及我们地日常生活.如何高效地排序一直困扰着我们. 1.2 课程设计目地 排序是数学地重要组成部分，工作量大是其存在地问题.如何高效地排序？本程序就是解决这个问题而设计.程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题.本软件开发地平台为最新地微软公司出版地市面最新系统Windows 2000，而且可以作为自身地运行平台非常广泛，包括 Windows 98/2000/XP/Vista等等. 1.3课程设计内容 本程序把对数列地排序转化为对数组元素地排序，用户可以根据自己地实际问题选择系统提供地七种排序方法地任意一种进行排序.程序通过自身地判断以及处理实现排序.程序最后输出每趟排序及初始排序结果. 2 系统分析与设计方案 2.1 系统分析 设计一个排序信息管理系统，使之能够操作实现以下功能： 1) 显示需要输入地排序长度及其各个关键字 2) 初始化输入地排序序列 3) 显示可供选择地操作菜单

4) 显示输出操作后地移动次数和比较次数 5) 显示操作后地新序列 5) 可实现循环继续操 2.2 设计思路 通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入地元素进行相应地处理. [2] 2.3 设计方案 设计方案如图2.1所示 图2.1 设计方案 具体流程见图2.2

图 2.2 程序流程图

3功能设计 3.1 SqList顺序表 其中包括顺序表长度，以及顺序表.源代码如下：[1] typedef struct { KeyType key。 //关键字项 InfoType otherinfo。 //其他数据项 }RedType。 typedef struct { RedType r[MaxSize+1]。 //r[0]作为监视哨 int length。 //顺序表长度 }SqList。 3.2 直接插入排序 直接插入排序是将一个记录插入到已排好序地有序表中，从而得到一个新地、记录数增1地有序表 图3.1 直接插入排序示意图 将第i个记录地关键字r[i].key顺序地与前面记录地关键字r[i-1].key,r[i-2].key,……，r[1].key进行比较，把所有关键字大于r[i].key地记录依次后移一位，直到关键字小于或者等于r[i].key地记录

C语言常用排序算法

/* ===================================================================== ======== 相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）： 1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就 说这种排序方法是稳定的。反之，就是非稳定的。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4, a2,a3,a5就不是稳定的了。 2、内排序和外排序 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ===================================================================== =========== */ /* ================================================ 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述：

快速排序法(C语言)

#include #include #include #include #define randx(x) (rand()%x) typedef int KeyType; typedef int DataType; typedef struct { KeyType key;/*排序码字段*/ DataType info; /*记录的其它字段*/ }RecordNode; typedef struct { int n; /*文件中的记录个数,可以视为常量*/ RecordNode *record; }SortObject; void creatsort(SortObject * pvector, int &l, int &r)//新建二叉排序树{ int i; int k; printf("您即将要创建一个序列\n");

printf("\n请输入该序列元素的个数\n"); scanf("%d", &pvector->n); pvector->record = (RecordNode*)malloc((sizeof(RecordNode))*(pvector->n)); printf("\n你要以什么方式创建序列？\n方式1：自动创建请输入1，方式2：手动创建请输入0\n"); scanf("%d", &k); if (k) { srand((int)time(0)); for (i = 0; i < pvector->n; i++) { if(pvector->n<100) pvector->record[i].key = randx(100); else if((pvector->n<1000)) pvector->record[i].key = randx(1000); else pvector->record[i].key = randx(pvector->n); } } else { printf("\n请输入%d个大小不一样的整数\n", pvector->n);

c语言经典算法100例

60.题目:古典问题:有一对兔子,从出生后第3个月 起每个月都生一对兔子,小兔 子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总 数 为多少? _________________________________________________________________ _ 程序分析:兔子的规律为数列1,1,2,3,5,8,13,21.... _________________________________________________________________ __ 程序源代码: main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出,每行四个*/

f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理,you try! 61.题目:判断101-200之间有多少个素数,并输出所有素数。 _________________________________________________________________ _ 1 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被 整 除,则表明此数不是素数,反之是素数。 _________________________________________________________________ __ 程序源代码: #include "math.h" main() { int m,i,k,h=0,leap=1;

C语言常用排序算法

1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。 2、内排序和外排序在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ================================================ 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ==================================================== 算法思想简单描述： 在要排序的一组数中，选出最小的一个数与第一个位置的数交换； 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环 到倒数第二个数和最后一个数比较为止。 选择排序是不稳定的。算法复杂度O(n2)--[n的平方] ===================================================== void select_sort(int*x,int n) { int i,j,min,t; for(i=0;i

基于C语言的多种排序方法的实现

基于C语言的多种排序方法的实现

《基于C 语言的多种排序方法的实现》第 1 页共30页基于C语言的多种排序方法的实现 1 引言 1.1 课题背景 排序问题源远流长，一直是数学地重要组成部分。随着各种信息的快速更新，排序问题也走进了其他领域以及我们地日常生活。如何高效地排序一直困扰着我们。 1.2 课程设计目的 排序是数学的重要组成部分，工作量大是其存在的问题。如何高效地排序？本程序就是解决这个问题而设计。程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题。本软件开发的平台为最新的微软公司出版的市面最新系统Windows 2000，而且可以作为自身的运行平台非常广泛，包括Windows 98/2000/XP/Vista等等。 1.3课程设计内容 本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的七种排序方法的任意一种进行排序。程序通过自身的判断以及处理实现排序。程序最后输出每趟排序及初始排序结果。

2 系统分析与设计方案 2.1 系统分析 设计一个排序信息管理系统，使之能够操作实现以下功能： 1) 显示需要输入的排序长度及其各个关键字 2) 初始化输入的排序序列 3) 显示可供选择的操作菜单 4) 显示输出操作后的移动次数和比较次数 5) 显示操作后的新序列 5) 可实现循环继续操 2.2 设计思路 通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入的元素进行相应的处理。[2] 2.3设计方案 设计方案如图2.1所示 图2.1 设计方案

具体流程见图2.2

最新C语言常用算法归纳

C语言常用算法归纳 应当掌握的一般算法 一、基本算法： 交换、累加、累乘 二、非数值计算常用经典算法： 穷举、排序（冒泡，选择）、查找（顺序即线性） 三、数值计算常用经典算法： 级数计算（直接、简接即递推）、一元非线性方程求根（牛顿迭代法、二分法）、定积分计算（矩形法、梯形法） 四、其他： 迭代、进制转换、矩阵转置、字符处理（统计、数字串、字母大小写转换、加密等）、整数各数位上数字的获取、辗转相除法求最大公约数（最小公倍数）、求最值、判断素数（各种变形）、数组元素的插入（删除）、二维数组的其他典型问题（方阵的特点、杨辉三角形） 详细讲解 一、基本算法 1．交换（两量交换借助第三者） 例1、任意读入两个整数，将二者的值交换后输出。 main() { int a,b,t; scanf("%d%d",&a,&b); printf("%d,%d\n",a,b); t=a; a=b; b=t; printf("%d,%d\n",a,b); }

【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。 假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。 其中t为中间变量，起到“空杯子”的作用。 注意：三句赋值语句赋值号左右的各量之间的关系！ 【应用】 例2、任意读入三个整数，然后按从小到大的顺序输出。 main() { int a,b,c,t; scanf("%d%d%d",&a,&b,&c); /*以下两个if语句使得a中存放的数最小*/ if(a>b){ t=a; a=b; b=t; } if(a>c){ t=a; a=c; c=t; } /*以下if语句使得b中存放的数次小*/ if(b>c) { t=b; b=c; c=t; } printf("%d,%d,%d\n",a,b,c); } 2．累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。 例1、求1+2+3+……+100的和。 main() { int i,s; s=0; i=1; while(i<=100) { s=s+i; /*累加式*/ i=i+1; /*特殊的累加式*/ } printf("1+2+3+...+100=%d\n",s); } 【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。 3．累乘

十大经典排序算法-C语言

十大经典排序算法（动图演示，收藏好文） 0、算法概述 0.1 算法分类 十种常见排序算法可以分为两大类： 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。 0.2 算法复杂度 0.3 相关概念 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n 的函数。 1、冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 1.1 算法描述 ?比较相邻的元素。如果第一个比第二个大，就交换它们两个； ?对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； ?针对所有的元素重复以上的步骤，除了最后一个； ?重复步骤1~3，直到排序完成。 1.2 动图演示

1.3 代码实现 function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len - 1; i++) { for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { // 相邻元素两两对比var temp = arr[j+1]; // 元素交换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; }

C语言常用算法程序汇总

C程序设计的常用算法 算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。 一、简单数值类算法 此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。 1、求阶乘：n!=1*2*384…..*n; n!= n*(n-1)!= 下列程序用于求n的阶乘.在累乘之前,一定要将用于存放乘积的变量的值初始化为1. long func(int n) { int i; long t=1; for(i=2;i<=n;i++) t*=i; return t; }

printf("\n"); } main() { int n; scanf("%d", &n); printf("n!=%ld\n", fac(n)); } 2、整数拆分问题：把一个整数各个位上的数字存到数组中 #define N 4 /* N代表整数位数*/ viod split(int n, int a[ ]） /* 1478: a[ 3]=8, a[2 ]=7, a[1 ]=4…*/ {int i; for(i=N-1;i!=0; i--) { a[i]=n%10; n=n/10; } } main() {int i,m=1478,b[N-1]; split(m, b）; for(i=0;i<4; i++) printf(“%5d”, b[i]);

(整理)C语言常用算法.

八、常用算法 （一）考核知识要点 1．交换、累加、累乘、求最大（小）值 2．穷举 3．排序（冒泡、插入、选择） 4．查找（顺序、折半） 5．级数计算（递推法） 6．一元方程求解（牛顿迭代法、二分法） 7．矩阵（转置） 8．定积分计算（矩形法、梯形法） 9．辗转相除法求最大公约数、判断素数 10．数制转换 （二）重点、难点精解 教材中给出的算法就不再赘述了。 1．基本操作：交换、累加、累乘 1）交换 交换算法的要领是“借助第三者”（如同交换两个杯子里的饮料，必须借助第三个空杯子）。例如，交换两个整型变量里的数值：int a=7,b=9,t; t=a; a=b; b=t; (不借助第三者，也能交换两个整型变量里的数值，但不通用，只是一个题目而已。 例如：int a=7,b=9; a=a+b; b=a-b; a=a-b;) 2）累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。 3）累乘 累乘算法的要领是形如“s=s*A”的累乘式，此式必须出现在循环中才能被反复执行，从而实现累乘功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为1。 2．非数值计算常用经典算法 1）穷举法 也称为“枚举法”，即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。 例如，用穷举法输出“将1元人民币兑换成1分、2分、5分硬币”的所有方法。 main() {int y,e,w; for(y=0;y<=100;y++) for(e=0;e<=50;e++) for(w=0;w<=20;w++)

c语言经典排序算法(8种-含源代码)

天行健，君子以自强不息 常见经典排序算法 1.希尔排序 2.二分插入法 3.直接插入法 4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序 一.希尔（Shell）排序法（又称宿小增量排序，是1959年由D.L.Shell提出来的） /* Shell 排序法 */ #include void sort(int v[],int n) { int gap,i,j,temp; for(gap=n/2;gap>0;gap /= 2) /* 设置排序的步长，步长gap每次减半，直到减到1 */ { for(i=gap;i= 0) && (v[j] > v[j+gap]);j -= gap ) /* 比较相距gap远的两个元素的大小，根据排序方向决定如何调换 */ { temp=v[j]; v[j]=v[j+gap]; v[j+gap]=temp; } } } } 二.二分插入法

/* 二分插入法 */ void HalfInsertSort(int a[], int len) { int i, j,temp; int low, high, mid; for (i=1; i temp) /* 如果中间元素比但前元素大，当前元素要插入到中间元素的左侧 */ { high = mid-1; } else /* 如果中间元素比当前元素小，但前元素要插入到中间元素的右侧 */ { low = mid+1; } } /* 找到当前元素的位置，在low和high之间 */ for (j=i-1; j>high; j--)/* 元素后移 */ { a[j+1] = a[j]; } a[high+1] = temp; /* 插入 */ } } 三.直接插入法 /*直接插入法*/ void InsertionSort(int input[],int len) { int i,j,temp; for (i = 1; i < len; i++) { temp = input[i]; /* 操作当前元素，先保存在其它变量中 */