c程序设计的常用算法.htm

C程序设计的常用算法,还是值得学习的,包括几个排序的算法

if(p&gt;=10)<br>
printf(&quot;the number is not found!\n&quot;);<br>
else<br>
printf(&quot;the number is found the no%d!\n&quot;,p);<br>
}<br>
思考：将上面程序改写一查找函数Find，若找到则返回下标值，找不到返回-1<br>
②基本思想：一列数放在数组a[1]---a[n]中，待查找的关键值为key，把key与a数组中的元素从头到尾一一进行比较查找，若相同，查找成功，若找不到，则查找失败。(查找子过程如下。index：存放找到元素的下标。)<br>
void main()<br>
{ int a[10],index,x,i;<br>
printf(&quot;please input the array:\n&quot;);<br>
for(i=0;i&lt;10;i++)<br>
scanf(&quot;%d&quot;,&amp;a[i]);<br>
printf(&quot;please input the number you want find:\n&quot;);<br>
scanf(&quot;%d&quot;,&amp;x);<br>
printf(&quot;\n&quot;);<br>
index=-1;<br>
for(i=0;i&lt;10;i++)<br>
if(x==a[i]) <br>
{ index=i; break;<br>
}<br>
if(index==-1)<br>
printf(&quot;the number is not found!\n&quot;);<br>
else<br>
printf(&quot;the number is found the no%d!\n&quot;,index);<br>
}<br>
2．折半查找法（只能对有序数列进行查找）<br>
基本思想：设n个有序数（从小到大）存放在数组a[1]----a[n]中，要查找的数为x。用变量bot、top、mid 分别表示查找数据范围的底部（数组下界）、顶部（数组的上界）和中间，mid=(top+bot)/2，折半查找的算法如下：<br>
（1）x=a(mid)，则已找到退出循环，否则进行下面的判断；<br>
（2）x&lt;a(mid)，x必定落在bot和mid-1的范围之内，即top=mid-1；<br>
（3）x&gt;a(mid)，x必定落在mid+1和top的范围之内，即bot=mid+1；<br>
（4）在确定了新的查找范围后，重复进行以上比较，直到找到或者bot&lt;=top。<br>
将上面的算法写成如下程序：<br>
void main()<br>
{<br>
int a[10],mid,bot,top,x,i,find;<br>
printf(&quot;please input the array:\n&quot;);<br>
for(i=0;i&lt;10;i++)<br>
scanf(&quot;%d&quot;,&amp;a[i]);<br>
printf(&quot;please input the number you want find:\n&quot;);<br>
scanf(&quot;%d&quot;,&amp;x);<br>
printf(&quot;\n&quot;);<br>
bot=0;top=9;find=0;<br>
while(bot&lt;top&amp;&amp;find==0)<br>
{ mid=(top+bot)/2;<br>
if(x==a[mid])<br>
{find=1;break;}<br>
else if(x&lt;a[mid])<br>
top=mid-1;<br>
else<br>
bot=mid+1;<br>
}<br>
if (find==1)<br>
printf(&quot;the number is found the no%d!\n&quot;,mid);<br>
else<br>
printf(&quot;the number is not found!\n&quot;);<br>
}<br>
七、插入法<br>
把一个数插到有序数列中，插入后数列仍然有序<br>
基本思想：n个有序数（从小到大）存放在数组a(1)—a(n)中，要插入的数x。首先确定x插在数组中的位置P；（可由以下语句实现）<br>
#define N 10<br>
void insert(int a[],int x)<br>
{ int p, i;<br>
p=0;<br>
while(x&gt;a[p]&amp;&amp;p&lt;N)<br>
p++;<br>
for(i=N; i&gt;p; i--)<br>
a[i]=a[i-1];<br>
a[p]=x;<br>
}<br>
main()<br>
{ int a[N+1]={1,3,4,7,8,11,13,18,56,78}, x, i;<br>
for(i=0; i&lt;N; i++) printf(&quot;%d,&quot;, a[i]);<br>
printf(&quot;\nInput x:&quot;);<br>
scanf(&quot;%d&quot;, &amp;x);<br>
insert(a, x);<br>
for(i=0; i&lt;=N; i++) printf(&quot;%d,&quot;, a[i]);<br>
printf(&quot;\n&quot;);<br>
}<br>
八、矩阵（二维数组）运算<br>
（1）矩阵的加、减运算<br>
C(i,j)=a(i,j)+b(i,j) 加法<br>
C(i,j)=a(i,j)-b(i,j) 减法<br>
（2）矩阵相乘<br>
（矩阵A有M*L个元素，矩阵B有L*N个元素，则矩阵C=A*B有M*N个元素）。矩阵C中任一元素 (i=1,2,…,m; j=1,2,…,n)<br>
#define M 2<br>
#define L 4<br>
#define N 3<br>
void mv(int a[M][L], int b[L][N], int c[M][N])<br>
{ int i, j, k;<br>
for(i=0; i&lt;M; i++)<br>
for(j=0; j&lt;N; j++)<br>
{ c[i][j]=0;<br>
for(k=0; k&lt;L; k++)<br>
c[i][j]+=a[i][k]*b[k][j];<br>
}<br>
}<br>
main()<br>
{ int a[M][L]={{1,2,3,4},{1,1,1,1}};<br>
int b[L][N]={{1,1,1},{1,2,1},{2,2,1},{2,3,1}}, c[M][N];<br>
int i, j;<br>
mv(a,b,c);<br>
for(i=0; i&lt;M; i++)<br>
{ for(j=0; j&lt;N; j++)<br>
printf(&quot;%4d&quot;, c[i][j]);<br>
printf(&quot;\n&quot;);<br>
}<br>
} <br>
（3）矩阵传置<br>
例:有二维数组a(5,5)，要对它实现转置，可用下面两种方式：<br>
#define N 3<br>
void ch1(int a[N][N])<br>
{ int i, j, t;<br>
for(i=0; i&lt;N; i++)<br>
for(j=i+1; j&lt;N; j++)<br>
{ t=a[i][j];<br>
a[i][j]=a[j][i];<br>
a[j][i]=t;<br>
}<br>
}<br>
void ch2(int a[N][N])<br>
{ int i, j, t;<br>
for(i=1; i&lt;N; i++)<br>
for(j= 0; j&lt;i; j++)<br>
{ t=a[i][j];<br>
a[i][j]=a[j][i];<br>
a[j][i]=t;<br>
}<br>
}<br>
main()<br>
{ int a[N][N]={{1,2,3},{4,5,6},{7,8,9}}, i, j;<br>
ch1(a); /*或ch2(a);*/<br>
for(i=0; i&lt;N; i++)<br>
{ for(j=0; j&lt;N; j++)<br>
printf(&quot;%4d&quot;, a[i][j]);<br>
printf(&quot;\n&quot;);<br>
}<br>
}<br>
（4）求二维数组中最小元素及其所在的行和列 <br>
基本思路同一维数组，可用下面程序段实现（以二维数组a[3][4]为例）：<br>
‘变量max中存放最大值，row,column存放最大值所在行列号<br>
#define N 4<br>
#define M 3<br>
void min(int a[M][N])<br>
{ int min, row, column, i, j;<br>
min=a[0][0]; <br>
row=0;<br>
column=0;<br>
for(i=0; i&lt;M; i++)<br>
for(j=0; j&lt;N; j++)<br>
if(a[i][j]&lt;min)<br>
{ min=a[i][j];<br>
row=i;<br>
column=j;<br>
} <br>
printf(&quot;Min=%d\nAt Row%d,Column%d\n&quot;, min, row, column);<br>
}<br>
main()<br>
{ int a[M][N]={{1,23,45,-5},{5,6,-7,6},{0,33,8,15}};<br>
min(a);<br>
}<br>
九、迭代法<br>
算法思想：对于一个问题的求解x，可由给定的一个初值x0，根据某一迭代公式得到一个新的值x1，这个新值x1比初值x0更接近要求的值x；再以新值作为初值，即：x1→x0,重新按原来的方法求x1,重复这一过和直到|x1-x0|&lt;ε(某一给定的精度)。此时可将x1作为问题的解。<br>
例：用迭代法求某个数的平方根。 已知求平方根的迭代公式为： <br>
#include&lt;math.h&gt;<br>
float fsqrt(float a)<br>
{ float x0, x1;<br>
x1=a/2;<br>
do{<br>
x0=x1;<br>
x1=0.5*(x0+a/x0); <br>
}while(fabs(x1-x0)&gt;0.00001);<br>
return(x1);<br>
}<br>
main()<br>
{ float a;<br>
scanf(&quot;%f&quot;, &amp;a);<br>
printf(&quot;genhao =%f\n&quot;, fsqrt(a));<br>
}<br>
十、数制转换<br>
将一个十进制整数m转换成 →r(2－16)进制字符串。<br>
方法：将m不断除 r 取余数，直到商为零，以反序得到结果。下面写出一转换函数，参数idec为十进制数，ibase为要转换成数的基（如二进制的基是2，八进制的基是8等），函数输出结果是字符串。<br>
char *trdec(int idec, int ibase)<br>
{ char strdr[20], t;<br>
int i, idr, p=0;<br>
while(idec!=0)<br>
{ idr=idec % ibase;<br>
if(idr&gt;=10)<br>
strdr[p++]=idr-10+65;<br>
else<br>
strdr[p++]=idr+48;<br>
idec/=ibase;<br>
}<br>
for(i=0; i&lt;p/2; i++)<br>
{ t=strdr[i];<br>
strdr[i]=strdr[p-i-1];<br>
strdr[p-i-1]=t;<br>
}<br>
strdr[p]=’\0’;<br>
return(strdr);<br>
}<br>
main()<br>
{ int x, d;<br>
scanf(&quot;%d%d&quot;, &amp;x, &amp;d);<br>
printf(&quot;%s\n&quot;, trdec(x,d));<br>
}<br>
十一、字符串的一般处理<br>
1．简单加密和解密<br>
加密的思想是： 将每个字母C加（或减）一序数K，即用它后的第K个字母代替，变换式公式： c=c+k<br>
例如序数k为5，这时 A→ F， a→f，B→?G… 当加序数后的字母超过Z或z则 c=c+k -26<br>
例如：You are good→ Dtz fwj ltti <br>
解密为加密的逆过程<br>
将每个字母C减（或加）一序数K，即 c=c-k,<br>
例如序数k为5，这时 Z→U，z→u，Y→T… 当加序数后的字母小于A或a则 c=c-k +26<br>
下段程序是加密处理：<br>
#include&lt;stdio.h&gt;<br>
char *jiami(char stri[])<br>
{ int i=0;<br>
char strp[50],ia;<br>
while(stri[i]!=’\0’)<br>
{ if(stri[i]&gt;=’A’&amp;&amp;stri[i]&lt;=’Z’)<br>
{ ia=stri[i]+5;<br>
if (ia&gt;’Z’) ia-=26;<br>
}<br>
else if(stri[i]&gt;=’a’&amp;&amp;stri[i]&lt;=’z’)<br>
{ ia=stri[i]+5;<br>
if (ia&gt;’z’) ia-=26;<br>
}<br>
else ia=stri[i];<br>
strp[i++]=ia;<br>
}<br>
strp[i]=’\0’;<br>
return(strp);<br>
}<br>
main()<br>
{ char s[50];<br>
gets(s);<br>
printf(&quot;%s\n&quot;, jiami(s));<br>
}<br>
2．统计文本单词的个数 <br>
输入一行字符，统计其中有多少个单词，单词之间用格分隔开。<br>
算法思路：<br>
（1）从文本（字符串）的左边开始，取出一个字符；设逻辑量word表示所取字符是否是单词内的字符，初值设为0<br>
（2）若所取字符不是“空格”，“逗号”，“分号”或“感叹号”等单词的分隔符，再判断word是否为1，若word不为1则表是新单词的开始，让单词数num =
num +1，让word =1;<br>
（3）若所取字符是“空格”，“逗号”，“分号”或“感叹号”等单词的分隔符， 则表示字符不是单词内字符，让word=0;<br>
(4) 再依次取下一个字符，重得（2）(3)直到文本结束。<br>
下面程序段是字符串string中包含的单词数<br>
#include &quot;stdio.h&quot;<br>
main()<br>
{char c,string[80];<br>
int i,num=0,word=0;<br>
gets(string);<br>
for(i=0;(c=string[i])!='\0';i++)<br>
if(c==' ') word=0;<br>
else if(word==0)<br>
{ word=1; <br>
num++;}<br>
printf(&quot;There are %d word in the line.\n&quot;,num);<br>
}<br>
十二、穷举法<br>
穷举法（又称“枚举法”）的基本思想是：一一列举各种可能的情况，并判断哪一种可能是符合要求的解，这是一种“在没有其它办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。<br>
例： 将一张面值为100元的人民币等值换成100张5元、1元和0.5元的零钞，要求每种零钞不少于1张，问有哪几种组合？<br>
main()<br>
{ int i, j, k;<br>
printf(&quot; 5元 1元 5角\n&quot;);<br>
for(i=1; i&lt;=20; i++)<br>
for(j=1; j&lt;=100-i; j++)<br>
{ k=100-i-j;<br>
if(5*i+1*j+0.5*k==100)<br>
printf(&quot; %3d %3d %3d\n&quot;, i, j, k);<br>
}<br>
}<br>
十三、递归算法<br>
用自身的结构来描述自身，称递归<br>
VB允许在一个Sub子过程和Function过程的定义内部调用自己，即递归Sub子过程和递归Function函数。递归处理一般用栈来实现，每调用一次自身，把当前参数压栈，直到递归结束条件；然后从栈中弹出当前参数，直到栈空。<br>
递归条件：（1）递归结束条件及结束时的值；（2）能用递归形式表示，且递归向终止条件发展。<br>
例：编fac(n)=n! 的递归函数<br>
int fac(int n)<br>
{ if(n==1)<br>
return(1);<br>
else<br>
return(n*fac(n-1));<br>
}<br>
main()<br>
{ int n;<br>
scanf(&quot;%d&quot;, &amp;n);<br>
printf(&quot;n!=%d\n&quot;, fac(n));<br>
}<o:p></o:p></span></p>

<p><span lang=EN-US>&nbsp;<o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

</div>

</body>

</html>