C程序设计的常用算法

九、迭代法

　　算法思想：对于一个问题的求解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 =%fn", 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;
strdr=strdr[p-i-1];
strdr[p-i-1]=t;
}
strdr[p]=’’;
return(strdr);
}
main()
{ int x, d;
scanf("%d%d", &x, &d);
printf("%sn", 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!=’’)
{ if(stri>=’A’&&stri<=’Z’)
{ ia=stri+5;
if (ia>’Z’) ia-=26;
}
else if(stri>=’a’&&stri<=’z’)
{ ia=stri+5;
if (ia>’z’) ia-=26;
}
else ia=stri;
strp[i++]=ia;
}
strp=’’;
return(strp);
}
main()
{ char s[50];
gets(s);
printf("%sn", 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++)
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 %3dn", 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!=%dn", fac(n));
}