10个重要算法C实现

包括拉格朗日，牛顿插值，高斯，龙贝格，牛顿迭代，牛顿-科特斯，雅克比，秦九昭，幂法，高斯塞德尔 。都是经典的数学算法，希望能开托您的思路。转自kunli.info

1.拉格朗日插值多项式 ，用于离散数据的拟合

C/C++ code

#include < stdio.h > #include < conio.h > #include < alloc.h > float lagrange( float * x, float * y, float xx, int n) /* 拉格朗日插值算法 */ { int i,j; float * a,yy = 0.0 ; /* a作为临时变量，记录拉格朗日插值多项式 */ a = ( float * )malloc(n * sizeof ( float )); for (i = 0 ;i <= n - 1 ;i ++ ) { a[i] = y[i]; for (j = 0 ;j <= n - 1 ;j ++ ) if (j != i) a[i] *= (xx - x[j]) / (x[i] - x[j]); yy += a[i]; } free(a); return yy; } main() { int i,n; float x[ 20 ],y[ 20 ],xx,yy; printf( " Input n: " ); scanf( " %d " , & n); if (n >= 20 ) {printf( " Error!The value of n must in (0,20). " ); getch(); return 1 ;} if (n <= 0 ) {printf( " Error! The value of n must in (0,20). " ); getch(); return 1 ;} for (i = 0 ;i <= n - 1 ;i ++ ) { printf( " x[%d]: " ,i); scanf( " %f " , & x[i]); } printf( " \n " ); for (i = 0 ;i <= n - 1 ;i ++ ) { printf( " y[%d]: " ,i);scanf( " %f " , & y[i]);} printf( " \n " ); printf( " Input xx: " ); scanf( " %f " , & xx); yy = lagrange(x,y,xx,n); printf( " x=%f,y=%f\n " ,xx,yy); getch(); }

2.牛顿插值多项式，用于离散数据的拟合

C/C++ code

#include < stdio.h > #include < conio.h > #include < alloc.h > void difference( float * x, float * y, int n) { float * f; int k,i; f = ( float * )malloc(n * sizeof ( float )); for (k = 1 ;k <= n;k ++ ) { f[ 0 ] = y[k]; for (i = 0 ;i < k;i ++ ) f[i + 1 ] = (f[i] - y[i]) / (x[k] - x[i]); y[k] = f[k]; } return ; } main() { int i,n; float x[ 20 ],y[ 20 ],xx,yy; printf( " Input n: " ); scanf( " %d " , & n); if (n >= 20 ) {printf( " Error! The value of n must in (0,20). " ); getch(); return 1 ;} if (n <= 0 ) {printf( " Error! The value of n must in (0,20). " );getch(); return 1 ;} for (i = 0 ;i <= n - 1 ;i ++ ) { printf( " x[%d]: " ,i); scanf( " %f " , & x[i]); } printf( " \n " ); for (i = 0 ;i <= n - 1 ;i ++ ) { printf( " y[%d]: " ,i);scanf( " %f " , & y[i]);} printf( " \n " ); difference(x,( float * )y,n); printf( " Input xx: " ); scanf( " %f " , & xx); yy = y[ 20 ]; for (i = n - 1 ;i >= 0 ;i -- ) yy = yy * (xx - x[i]) + y[i]; printf( " NewtonInter(%f)=%f " ,xx,yy); getch(); }

3.高斯列主元消去法,求解其次线性方程组

C/C++ code

#include < stdio.h > #include < math.h > #define N 20 int main() { int n,i,j,k; int mi,tmp,mx; float a[N][N],b[N],x[N]; printf( " \nInput n: " ); scanf( " %d " , & n); if (n > N) { printf( " The input n should in(0,N)!\n " ); getch(); return 1 ; } if (n <= 0 ) { printf( " The input n should in(0,N)!\n " ); getch(); return 1 ; } printf( " Now input a(i,j),i,j=0...%d:\n " ,n - 1 ); for (i = 0 ;i < n;i ++ ) { for (j = 0 ;j < n;j ++ ) scanf( " %f " , & a[i][j]);} printf( " Now input b(i),i,j=0...%d:\n " ,n - 1 ); for (i = 0 ;i < n;i ++ ) scanf( " %f " , & b[i]); for (i = 0 ;i < n - 2 ;i ++ ) { for (j = i + 1 ,mi = i,mx = fabs(a[i][j]);j < n - 1 ;j ++ ) if (fabs(a[j][i]) > mx) { mi = j; mx = fabs(a[j][i]); } if (i < mi) { tmp = b[i];b[i] = b[mi];b[mi] = tmp; for (j = i;j < n;j ++ ) { tmp = a[i][j]; a[i][j] = a[mi][j]; a[mi][j] = tmp; } } for (j = i + 1 ;j < n;j ++ ) { tmp =- a[j][i] / a[i][i]; b[j] += b[i] * tmp; for (k = i;k < n;k ++ ) a[j][k] += a[i][k] * tmp; } } x[n - 1 ] = b[n - 1 ] / a[n - 1 ][n - 1 ]; for (i = n - 2 ;i >= 0 ;i -- ) { x[i] = b[i]; for (j = i + 1 ;j < n;j ++ ) x[i] -= a[i][j] * x[j]; x[i] /= a[i][i]; } for (i = 0 ;i < n;i ++ ) printf( " Answer:\n x[%d]=%f\n " ,i,x[i]); getch(); return 0 ; } #include < math.h > #include < stdio.h > #define NUMBER 20 #define Esc 0x1b #define Enter 0x0d float A[NUMBER][NUMBER + 1 ] ,ark; int flag,n; exchange( int r, int k); float max( int k); message(); main() { float x[NUMBER]; int r,k,i,j; char celect; clrscr(); printf( " \n\nUse Gauss. " ); printf( " \n\n1.Jie please press Enter. " ); printf( " \n\n2.Exit press Esc. " ); celect = getch(); if (celect == Esc) exit( 0 ); printf( " \n\n input n= " ); scanf( " %d " , & n); printf( " \n\nInput matrix A and B: " ); for (i = 1 ;i <= n;i ++ ) { printf( " \n\nInput a%d1--a%d%d and b%d: " ,i,i,n,i); for (j = 1 ;j <= n + 1 ;j ++ ) scanf( " %f " , & A[i][j]); } for (k = 1 ;k <= n - 1 ;k ++ ) { ark = max(k); if (ark == 0 ) { printf( " \n\nIt's wrong! " );message(); } else if (flag != k) exchange(flag,k); for (i = k + 1 ;i <= n;i ++ ) for (j = k + 1 ;j <= n + 1 ;j ++ ) A[i][j] = A[i][j] - A[k][j] * A[i][k] / A[k][k]; } x[n] = A[n][n + 1 ] / A[n][n]; for ( k = n - 1 ;k >= 1 ;k -- ) { float me = 0 ; for (j = k + 1 ;j <= n;j ++ ) { me = me + A[k][j] * x[j]; } x[k] = (A[k][n + 1 ] - me) / A[k][k]; } for (i = 1 ;i <= n;i ++ ) { printf( " \n\nx%d=%f " ,i,x[i]); } message(); } exchange( int r, int k) { int i; for (i = 1 ;i <= n + 1 ;i ++ ) A[ 0 ][i] = A[r][i]; for (i = 1 ;i <= n + 1 ;i ++ ) A[r][i] = A[k][i]; for (i = 1 ;i <= n + 1 ;i ++ ) A[k][i] = A[ 0 ][i]; } float max( int k) { int i; float temp = 0 ; for (i = k;i <= n;i ++ ) if (fabs(A[i][k]) > temp) { temp = fabs(A[i][k]); flag = i; } return temp; } message() { printf( " \n\n Go on Enter ,Exit press Esc! " ); switch (getch()) { case Enter: main(); case Esc: exit( 0 ); default :{printf( " \n\nInput error! " );message();} } }

4.龙贝格求积公式，求解定积分

C/C++ code

#include < stdio.h > #include < math.h > #define f(x) (sin(x)/x) #define N 20 #define MAX 20 #define a 2 #define b 4 #define e 0.00001 float LBG( float p, float q, int n) { int i; float sum = 0 ,h = (q - p) / n; for (i = 1 ;i < n;i ++ ) sum += f(p + i * h); sum += (f(p) + f(q)) / 2 ; return (h * sum); } void main() { int i; int n = N,m = 0 ; float T[MAX + 1 ][ 2 ]; T[ 0 ][ 1 ] = LBG(a,b,n); n *= 2 ; for (m = 1 ;m < MAX;m ++ ) { for (i = 0 ;i < m;i ++ ) T[i][ 0 ] = T[i][ 1 ]; T[ 0 ][ 1 ] = LBG(a,b,n); n *= 2 ; for (i = 1 ;i <= m;i ++ ) T[i][ 1 ] = T[i - 1 ][ 1 ] + (T[i - 1 ][ 1 ] - T[i - 1 ][ 0 ]) / (pow( 2 , 2 * m) - 1 ); if ((T[m - 1 ][ 1 ] < T[m][ 1 ] + e) && (T[m - 1 ][ 1 ] > T[m][ 1 ] - e)) { printf( " Answer=%f\n " ,T[m][ 1 ]); getch(); return ; } } }

C/C++ code

5 .牛顿迭代公式，求方程的近似解

C/C++ code

#include < stdio.h > #include < math.h > #include < conio.h > #define N 100 #define PS 1e-5 #define TA 1e-5 float Newton( float ( * f)( float ), float ( * f1)( float ), float x0 ) { float x1,d = 0 ; int k = 0 ; do { x1 = x0 - f(x0) / f1(x0); if ((k ++> N) || (fabs(f1(x1)) < PS)) { printf( " \nFailed! " ); getch(); exit(); } d = (fabs(x1) < 1 ? x1 - x0:(x1 - x0) / x1); x0 = x1; printf( " x(%d)=%f\n " ,k,x0); } while ((fabs(d)) > PS && fabs(f(x1)) > TA) ; return x1; } float f( float x) { return x * x * x + x * x - 3 * x - 3 ; } float f1( float x) { return 3.0 * x * x + 2 * x - 3 ; } void main() { float f( float ); float f1( float ); float x0,y0; printf( " Input x0: " ); scanf( " %f " , & x0); printf( " x(0)=%f\n " ,x0); y0 = Newton(f,f1,x0); printf( " \nThe root is x=%f\n " ,y0); getch(); }

6. 牛顿-科特斯求积公式，求定积分

C/C++ code

#include < stdio.h > #include < math.h > int NC(a,h,n,r,f) float ( * a)[]; float h; int n,f; float * r; { int nn,i; float ds; if (n > 1000 || n < 2 ) { if (f) printf( " \n Faild! Check if 1<n<1000!\n " ,n); return ( - 1 ); } if (n == 2 ) { * r = 0.5 * (( * a)[ 0 ] + ( * a)[ 1 ]) * (h); return ( 0 ); } if (n - 4 == 0 ) { * r = 0 ; * r =* r + 0.375 * (h) * (( * a)[n - 4 ] + 3 * ( * a)[n - 3 ] + 3 * ( * a)[n - 2 ] + ( * a)[n - 1 ]); return ( 0 ); } if (n / 2 - (n - 1 ) / 2 <= 0 ) nn = n; else nn = n - 3 ; ds = ( * a)[ 0 ] - ( * a)[nn - 1 ]; for (i = 2 ;i <= nn;i = i + 2 ) ds = ds + 4 * ( * a)[i - 1 ] + 2 * ( * a)[i]; * r = ds * (h) / 3 ; if (n > nn) * r =* r + 0.375 * (h) * (( * a)[n - 4 ] + 3 * ( * a)[n - 3 ] + 3 * ( * a)[n - 2 ] + ( * a)[n - 1 ]); return ( 0 ); } main() { float h,r; int n,ntf,f; int i; float a[ 16 ]; printf( " Input the x[i](16):\n " ); for (i = 0 ;i <= 15 ;i ++ ) scanf( " %d " , & a[i]); h = 0.2 ; f = 0 ; ntf = NC(a,h,n, & r,f); if (ntf == 0 ) printf( " \nR=%f\n " ,r); else printf( " \n Wrong!Return code=%d\n " ,ntf); getch(); }

7.雅克比迭代，求解方程近似解

C/C++ code

#include < stdio.h > #include < math.h > #define N 20 #define MAX 100 #define e 0.00001 int main() { int n; int i,j,k; float t; float a[N][N],b[N][N],c[N],g[N],x[N],h[N]; printf( " \nInput dim of n: " ); scanf( " %d " , & n); if (n > N) { printf( " Faild! Check if 0<n<N!\n " ); getch(); return 1 ; } if (n <= 0 ) {printf( " Faild! Check if 0<n<N!\n " ); getch(); return 1 ;} printf( " Input a[i,j],i,j=0…%d:\n " ,n - 1 ); for (i = 0 ;i < n;i ++ ) for (j = 0 ;j < n;j ++ ) scanf( " %f " , & a[i][j]); printf( " Input c[i],i=0…%d:\n " ,n - 1 ); for (i = 0 ;i < n;i ++ ) scanf( " %f " , & c[i]); for (i = 0 ;i < n;i ++ ) for (j = 0 ;j < n;j ++ ) { b[i][j] =- a[i][j] / a[i][i]; g[i] = c[i] / a[i][i]; } for (i = 0 ;i < MAX;i ++ ) { for (j = 0 ;j < n;j ++ ) h[j] = g[j]; { for (k = 0 ;k < n;k ++ ) { if (j == k) continue ; h[j] += b[j][k] * x[k]; } } t = 0 ; for (j = 0 ;j < n;j ++ ) if (t < fabs(h[j] - x[j])) t = fabs(h[j] - x[j]); for (j = 0 ;j < n;j ++ ) x[j] = h[j]; if (t < e) { printf( " x_i=\n " ); for (i = 0 ;i < n;i ++ ) printf( " x[%d]=%f\n " ,i,x[i]); getch(); return 0 ; } printf( " after %d repeat , return\n " ,MAX); getch(); return 1 ; } getch(); }

8.秦九昭算法

C/C++ code

#include < math.h > float qin( float a[], int n, float x) { float r = 0 ; int i; for (i = n;i >= 0 ;i -- ) r = r * x + a[i]; return r; } main() { float a[ 50 ],x,r = 0 ; int n,i; do { printf( " Input frequency: " ); scanf( " %d " , & n); } while (n < 1 ); printf( " Input value: " ); for (i = 0 ;i <= n;i ++ ) scanf( " %f " , & a[i]); printf( " Input frequency: " ); scanf( " %f " , & x); r = qin(a,n,x); printf( " Answer:%f " ,r); getch(); }

9.幂法

C/C++ code

#include < stdio.h > #include < math.h > #define N 100 #define e 0.00001 #define n 3 float x[n] = { 0 , 0 , 1 }; float a[n][n] = {{ 2 , 3 , 2 },{ 10 , 3 , 4 },{ 3 , 6 , 1 }}; float y[n]; main() { int i,j,k; float xm,oxm; oxm = 0 ; for (k = 0 ;k < N;k ++ ) { for (j = 0 ;j < n;j ++ ) { y[j] = 0 ; for (i = 0 ;i < n;i ++ ) y[j] += a[j][i] * x[i]; } xm = 0 ; for (j = 0 ;j < n;j ++ ) if (fabs(y[j]) > xm) xm = fabs(y[j]); for (j = 0 ;j < n;j ++ ) y[j] /= xm; for (j = 0 ;j < n;j ++ ) x[j] = y[j]; if (fabs(xm - oxm) < e) { printf( " max:%f\n\n " ,xm); printf( " v[i]:\n " ); for (k = 0 ;k < n;k ++ ) printf( " %f\n " ,y[k]); break ; } oxm = xm; } getch(); }

10.高斯塞德尔

C/C++ code

#include < math.h > #include < stdio.h > #define N 20 #define M 99 float a[N][N]; float b[N]; int main() { int i,j,k,n; float sum,no,d,s,x[N]; printf( " \nInput dim of n: " ); scanf( " %d " , & n); if (n > N) { printf( " Faild! Check if 0<n<N!\n " ); getch(); return 1 ; } if (n <= 0 ) { printf( " Faild! Check if 0<n<N!\n " );getch(); return 1 ;} printf( " Input a[i,j],i,j=0…%d:\n " ,n - 1 ); for (i = 0 ;i < n;i ++ ) for (j = 0 ;j < n;j ++ ) scanf( " %f " , & a[i][j]); printf( " Input b[i],i=0…%d:\n " ,n - 1 ); for (i = 0 ;i < n;i ++ ) scanf( " %f " , & b[i]); for (i = 0 ;i < n;i ++ ) x[i] = 0 ; k = 0 ; printf( " \nk=%dx= " ,k); for (i = 0 ;i < n;i ++ ) printf( " %12.8f " ,x[i]); do { k ++ ; if (k > M){printf( " \nError!\n”);getch();} break ; } no = 0.0 ; for (i = 0 ;i < n;i ++ ) { s = x[i]; sum = 0.0 ; for (j = 0 ;j < n;j ++ ) if (j != i) sum = sum + a[i][j] * x[j]; x[i] = (b[i] - sum) / a[i][i]; d = fabs(x[i] - s); if (no < d) no = d; } printf( " \nk=%2dx= " ,k); for (i = 0 ;i < n;i ++ ) printf( " %f " ,x[i]); } while (no >= 0.1e-6 ); if (no < 0.1e-6 ) { printf( " \n\n answer=\n " ); printf( " \nk=%d " ,k); for (i = 0 ;i < n;i ++ ) printf( " \n x[%d]=%12.8f " ,i,x[i]); } getch(); }