c常用算法.txt

本书主要内容包括经典电磁理论及其数学基础

else if(x<a[mid]) 
top=mid-1; 
else 
bot=mid+1; 
} 
if (find==1) 
printf("the number is found the no%d!\n",mid); 
else 
printf("the number is not found!\n"); 
} 

　　七、插入法 

　　把一个数插到有序数列中，插入后数列仍然有序 

　　基本思想：n个有序数（从小到大）存放在数组a(1)—a(n)中，要插入的数x。首先确定x插在数组中的位置P；（可由以下语句实现） 
#define N 10 
void insert(int a[],int x) 
{ int p, i; 
p=0; 
while(x>a[p]&&p<N) 
p++; 
for(i=N; i>p; i--) 
a[i]=a[i-1]; 
a[p]=x; 
} 
main() 
{ int a[N+1]={1,3,4,7,8,11,13,18,56,78}, x, i; 
for(i=0; i<N; i++) printf("%d,", a[i]); 
printf("\nInput x:"); 
scanf("%d", &x); 
insert(a, x); 
for(i=0; i<=N; i++) printf("%d,", a[i]); 
printf("\n"); 
} 

　　八、矩阵（二维数组）运算 

（1）矩阵的加、减运算 
C(i,j)=a(i,j)+b(i,j) 加法 
C(i,j)=a(i,j)-b(i,j) 减法 
（2）矩阵相乘 
（矩阵A有M*L个元素，矩阵B有L*N个元素，则矩阵C=A*B有M*N个元素）。矩阵C中任一元素 (i=1,2,…,m; j=1,2,…,n) 
#define M 2 
#define L 4 
#define N 3 
void mv(int a[M][L], int b[L][N], int c[M][N]) 
{ int i, j, k; 
for(i=0; i<M; i++) 
for(j=0; j<N; j++) 
{ c[i][j]=0; 
for(k=0; k<L; k++) 
c[i][j]+=a[i][k]*b[k][j]; 
} 
} 
main() 
{ int a[M][L]={{1,2,3,4},{1,1,1,1}}; 
int b[L][N]={{1,1,1},{1,2,1},{2,2,1},{2,3,1}}, c[M][N]; 
int i, j; 
mv(a,b,c); 
for(i=0; i<M; i++) 
{ for(j=0; j<N; j++) 
printf("%4d", c[i][j]); 
printf("\n"); 
} 
} 
（3）矩阵传置 
例:有二维数组a(5,5)，要对它实现转置，可用下面两种方式： 
#define N 3 
void ch1(int a[N][N]) 
{ int i, j, t; 
for(i=0; i<N; i++) 
for(j=i+1; j<N; j++) 
{ t=a[i][j]; 
a[i][j]=a[j][i]; 
a[j][i]=t; 
} 
} 
void ch2(int a[N][N]) 
{ int i, j, t; 
for(i=1; i<N; i++) 
for(j= 0; j<i; j++) 
{ t=a[i][j]; 
a[i][j]=a[j][i]; 
a[j][i]=t; 
} 
} 
main() 
{ int a[N][N]={{1,2,3},{4,5,6},{7,8,9}}, i, j; 
ch1(a); /*或ch2(a);*/ 
for(i=0; i<N; i++) 
{ for(j=0; j<N; j++) 
printf("%4d", a[i][j]); 
printf("\n"); 
} 
} 
（4）求二维数组中最小元素及其所在的行和列 
基本思路同一维数组，可用下面程序段实现（以二维数组a[3][4]为例）： 
‘变量max中存放最大值，row,column存放最大值所在行列号 
#define N 4 
#define M 3 
void min(int a[M][N]) 
{ int min, row, column, i, j; 
min=a[0][0]; 
row=0; 
column=0; 
for(i=0; i<M; i++) 
for(j=0; j<N; j++) 
if(a[i][j]<min) 
{ min=a[i][j]; 
row=i; 
column=j; 
} 
printf("Min=%d\nAt Row%d,Column%d\n", min, row, column); 
} 
main() 
{ int a[M][N]={{1,23,45,-5},{5,6,-7,6},{0,33,8,15}}; 
min(a); 
} 

　　九、迭代法 

　　算法思想：对于一个问题的求解x，可由给定的一个初值x0，根据某一迭代公式得到一个新的值x1，这个新值x1比初值x0更接近要求的值x；再以新值作为初值，即：x1→x0,重新按原来的方法求x1,重复这一过和直到|x1-x0|<ε(某一给定的精度)。此时可将x1作为问题的解。 
例：用迭代法求某个数的平方根。 已知求平方根的迭代公式为： 
#include<math.h> 
float fsqrt(float a) 
{ float x0, x1; 
x1=a/2; 
do{ 
x0=x1; 
x1=0.5*(x0+a/x0); 
}while(fabs(x1-x0)>0.00001); 
return(x1); 
} 
main() 
{ float a; 
scanf("%f", &a); 
printf("genhao =%f\n", fsqrt(a)); 
} 

　　十、数制转换 

　　将一个十进制整数m转换成 →r(2－16)进制字符串。 

　　方法：将m不断除 r 取余数，直到商为零，以反序得到结果。下面写出一转换函数，参数idec为十进制数，ibase为要转换成数的基（如二进制的基是2，八进制的基是8等），函数输出结果是字符串。 
char *trdec(int idec, int ibase) 
{ char strdr[20], t; 
int i, idr, p=0; 
while(idec!=0) 
{ idr=idec % ibase; 
if(idr>=10) 
strdr[p++]=idr-10+65; 
else 
strdr[p++]=idr+48; 
idec/=ibase; 
} 
for(i=0; i<p/2; i++) 
{ t=strdr[i]; 
strdr[i]=strdr[p-i-1]; 
strdr[p-i-1]=t; 
} 
strdr[p]=’\0’; 
return(strdr); 
} 
main() 
{ int x, d; 
scanf("%d%d", &x, &d); 
printf("%s\n", trdec(x,d)); 
} 

　　十一、字符串的一般处理 

　　1．简单加密和解密 
加密的思想是： 将每个字母C加（或减）一序数K，即用它后的第K个字母代替，变换式公式： c=c+k 
例如序数k为5，这时 A→ F， a→f，B→?G… 当加序数后的字母超过Z或z则 c=c+k -26 
例如：You are good→ Dtz fwj ltti 
解密为加密的逆过程 
将每个字母C减（或加）一序数K，即 c=c-k, 
例如序数k为5，这时 Z→U，z→u，Y→T… 当加序数后的字母小于A或a则 c=c-k +26 
下段程序是加密处理： 
#include<stdio.h> 
char *jiami(char stri[]) 
{ int i=0; 
char strp[50],ia; 
while(stri[i]!=’\0’) 
{ if(stri[i]>=’A’&&stri[i]<=’Z’) 
{ ia=stri[i]+5; 
if (ia>’Z’) ia-=26; 
} 
else if(stri[i]>=’a’&&stri[i]<=’z’) 
{ ia=stri[i]+5; 
if (ia>’z’) ia-=26; 
} 
else ia=stri[i]; 
strp[i++]=ia; 
} 
strp[i]=’\0’; 
return(strp); 
} 
main() 
{ char s[50]; 
gets(s); 
printf("%s\n", jiami(s)); 
} 
2．统计文本单词的个数 
输入一行字符，统计其中有多少个单词，单词之间用格分隔开。 
算法思路： 
（1）从文本（字符串）的左边开始，取出一个字符；设逻辑量word表示所取字符是否是单词内的字符，初值设为0 
（2）若所取字符不是“空格”，“逗号”，“分号”或“感叹号”等单词的分隔符，再判断word是否为1，若word不为1则表是新单词的开始，让单词数num = num +1，让word =1; 
（3）若所取字符是“空格”，“逗号”，“分号”或“感叹号”等单词的分隔符， 则表示字符不是单词内字符，让word=0; 
(4) 再依次取下一个字符，重得（2）(3)直到文本结束。 
下面程序段是字符串string中包含的单词数 
#include "stdio.h" 
main() 
{char c,string[80]; 
int i,num=0,word=0; 
gets(string); 
for(i=0;(c=string[i])!='\0';i++) 
if(c==' ') word=0; 
else if(word==0) 
{ word=1; 
num++;} 
printf("There are %d word in the line.\n",num); 
} 

　　十二、穷举法 
　　
　　穷举法（又称“枚举法”）的基本思想是：一一列举各种可能的情况，并判断哪一种可能是符合要求的解，这是一种“在没有其它办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。 
例： 将一张面值为100元的人民币等值换成100张5元、1元和0.5元的零钞，要求每种零钞不少于1张，问有哪几种组合？ 
main() 
{ int i, j, k; 
printf(" 5元 1元 5角\n"); 
for(i=1; i<=20; i++) 
for(j=1; j<=100-i; j++) 
{ k=100-i-j; 
if(5*i+1*j+0.5*k==100) 
printf(" %3d %3d %3d\n", i, j, k); 
} 
} 

　　十三、递归算法 
　　
　　用自身的结构来描述自身，称递归 
　　
　　VB允许在一个Sub子过程和Function过程的定义内部调用自己，即递归Sub子过程和递归Function函数。递归处理一般用栈来实现，每调用一次自身，把当前参数压栈，直到递归结束条件；然后从栈中弹出当前参数，直到栈空。 
递归条件：（1）递归结束条件及结束时的值；（2）能用递归形式表示，且递归向终止条件发展。 
例：编fac(n)=n! 的递归函数 
int fac(int n) 
{ if(n==1) 
return(1); 
else 
return(n*fac(n-1)); 
} 
main() 
{ int n; 
scanf("%d", &n); 
printf("n!=%d\n", fac(n)); 
}