计算机算法基础:C语言算法基础

算法(Algorithm):计算机解题基本思想思路方法和步骤算法描述:是对要解决个问题或要完成项任务所采取思路方法和步骤描述包括需要什么数据(输入什么数据、输出什么结果)、采用什么结构、使用什么语句以及如何安排这些语句等通常使用自然语言、结构化流程图、伪代码等来描述算法
、计数、求和、求阶乘等简单算法
此类问题都要使用循环要注意根据问题确定循环变量初值、终值或结束条件更要注意用来表示计数、和、阶乘变量初值
例:用随机产生100个[099]范围内随机整数统计个位上数字分别为1234567890数个数并打印出来
本题使用来处理用a[100]存放产生确100个随机整数x[10]来存放个位上数字分别为1234567890数个数即个位是1个数存放在x[1]中个位是2个数存放在x[2]中……个位是0个数存放在x[10]
void
{a[101],x[11],i,p;
for(i=0;i<=11;i)
x[i]=0;
for(i=1;i<=100;i)
{a[i]=rand%100;
prf(\"%4d\",a[i]);
(i%100)prf(\"\\n\");
}
for(i=1;i<=100;i)
{p=a[i]%10;
(p0)p=10;
x[p]=x[p]+1;
}
for(i=1;i<=10;i)
{p=i;
(i10)p=0;
prf(\"%d,%d\\n\",p,x[i]);
}
prf(\"\\n\");
}
2、求两个整数最大公约数、最小公倍数
分析:求最大公约数算法思想:(最小公倍数=两个整数的积/最大公约数)
(1)对于已知两数mn使得m>n；
(2)m除以n得余数r；
(3)若r=0则n为求得最大公约数算法结束；否则执行(4)；
(4)m←nn←r再重复执行(2)
例如:求m=14,n=6最大公约数.mnr
1462
620
void
{nm,r,n,m,t;
prf(\"pleaseinputtwonumbers:\\n\");
scanf(\"%d,%d\",&m,&n);
nm=n*m;
(m<n)
{t=n;n=m;m=t;}
r=m%n;
while(r!=0)
{m=n;n=r;r=m%n;}
prf(\"最大公约数:%d\\n\",n);
prf(\"最小公倍数:%d\\n\",nm/n);
}
3、判断素数
只能被1或本身整除数称为素数基本思想:把m作为被除数将2—INT()作为除数如果都除不尽m就是素数否则就不是(可用以下段实现)
void
{m,i,k;
prf(\"pleaseinputanumber:\\n\");
scanf(\"%d\",&m);
k=sqrt(m);
for(i=2;i<k;i)
(m%i0);
(i>=k)
prf(\"该数是素数\");

prf(\"该数不是素数\");
}
将其写成,若为素数返回1不是则返回0
prime(m%)
{i,k;
k=sqrt(m);
for(i=2;i<k;i)
(m%i0)0;
1;
}
4、验证哥德巴赫猜想
(任意个大于等于6偶数都可以分解为两个素数的和)
基本思想:n为大于等于6任偶数可分解为n1和n2两个数分别检查n1和n2是否为素数如都是则为组解如n1不是素数就不必再检查n2是否素数先从n1=3开始检验n1和n2(n2=N-n1)是否素数然后使n1+2再检验n1、n2是否素数…直到n1=n/2为止
利用上面prime验证哥德巴赫猜想代码如下:
#\"math.h\" [Page]
prime(m)
{i,k;
k=sqrt(m);
for(i=2;i<k;i)
(m%i0);
(i>=k)
1;

0;
}

{x,i;
prf(\"pleaseinputaevennumber(>=6):\\n\");
scanf(\"%d\",&x);
(x<6||x%2!=0)
prf(\"dataerror!\\n\");

for(i=2;i<=x/2;i)
(prime(i)&&prime(x-i))
{
prf(\"%d+%d\\n\",i,x-i);
prf(\"验证成功!\");
;
}
}
5、排序问题
1．选择法排序(升序)
基本思想:
1)对有n个数序列(存放在a(n)中)从中选出最小数和第1个数交换位置；
2)除第1个数外其余n-1个数中选最小数和第2个数交换位置；
3)依次类推选择了n-1次后这个数列已按升序排列

代码如下:
void
{i,j,imin,s,a[10];
prf(\"\\ninput10numbers:\\n\");
for(i=0;i<10;i)
scanf(\"%d\",&a[i]);
for(i=0;i<9;i)
{imin=i;
for(j=i+1;j<10;j)
(a[imin]>a[j])imin=j;
(i!=imin)
{s=a[i];a[i]=a[imin];a[imin]=s;}
prf(\"%d\\n\",a[i]);
}
}
2．冒泡法排序(升序)
基本思想:(将相邻两个数比较小调到前头)
1)有n个数(存放在a(n)中)第趟将每相邻两个数比较小调到前头经n-1次两两相邻比较后最大数已“沉底”放在最后个位置小数上升“浮起”；
2)第 2趟对余下n-1个数(最大数已“沉底”)按上法比较经n-2次两两相邻比较后得次大数；
3)依次类推n个数共进行n-1趟比较在第j趟中要进行n-j次两两比较
段如下
void
{a[10];
i,j,t;
prf(\"input10numbers\\n\");
for(i=0;i<10;i)
scanf(\"%d\",&a[i]);
prf(\"\\n\");
for(j=0;j<=8;j)
for(i=0;i<9-j;i)
(a[i]>a[i+1])
{t=a[i];a[i]=a[i+1];a[i+1]=t;}
prf(\"thesortednumbers:\\n\");


for(i=0;i<10;i)
prf(\"%d\\n\",a[i]);
}
3．合并法排序(将两个有序A、B合并成另个有序C升序)
基本思想:
1)先在A、B中各取第个元素进行比较将小元素放入C；
2)取小元素所在下个元素和另中上次比较后较大元素比较重复上述比较过程直到某个被先排完；
3)将另个剩余元素抄入C合并排序完成
段如下:
void
{a[10],b[10],c[20],i,ia,ib,ic;
prf(\"pleaseinputthefirst.gif' />:\\n\");
for(i=0;i<10;i)
scanf(\"%d\",&a[i]);
for(i=0;i<10;i)
scanf(\"%d\",&b[i]);
prf(\"\\n\");
ia=0;ib=0;ic=0;
while(ia<10&&ib<10)
{(a[ia]<b[ib])
{c[ic]=a[ia];ia;}

{c[ic]=b[ib];ib;}
ic;
}
while(ia<=9)
{c[ic]=a[ia];
ia;ic;
}
while(ib<=9) [Page]
{c[ic]=b[ib];
b;ic;
}
for(i=0;i<20;i)
prf(\"%d\\n\",c[i]);
}
6、查找问题
1．①顺序查找法(在列数中查找某数x)
基本思想:列数放在a[1]---a[n]中待查找数放在x中把x和a中元素从头到尾进行比较查找用变量p表示a元素下标p初值为1使x和a[p]比较如果x不等于a[p]则使p=p+1不断重复这个过程；旦x等于a[p]则退出循环；另外如果p大于长度循环也应该停止(这个过程可由下语句实现)
void
{a[10],p,x,i;
prf(\"pleaseinputthe.gif' />:\\n\");
for(i=0;i<10;i)
scanf(\"%d\",&a[i]);
prf(\"pleaseinputthenumberyouwantfind:\\n\");
scanf(\"%d\",&x);
prf(\"\\n\");
p=0;
while(x!=a[p]&&p<10)
p;
(p>=10)
prf(\"thenumberisnotfound!\\n\");

prf(\"thenumberisfoundtheno%d!\\n\",p);
}
研究:将上面改写查找Find若找到则返回下标值找不到返回-1
②基本思想:列数放在a[1]---a[n]中待查找关键值为key把key和a中元素从头到尾进行比较查找若相同查找成功若找不到则查找失败(查找子过程如下index:存放找到元素下标)
void
{a[10],index,x,i;
prf(\"pleaseinputthe.gif' />:\\n\");
for(i=0;i<10;i)
scanf(\"%d\",&a[i]);
prf(\"pleaseinputthenumberyouwantfind:\\n\");
scanf(\"%d\",&x);
prf(\"\\n\");
index=-1;
for(i=0;i<10;i)
(xa[i])
{index=i;;
}
(index-1)
prf(\"thenumberisnotfound!\\n\");

prf(\"thenumberisfoundtheno%d!\\n\",index);
}
2．折半查找法(只能对有序数列进行查找)
基本思想:设n个有序数(从小到大)存放在a[1]----a[n]中要查找数为x用变量bot、top、mid分别表示查找数据范围底部(下界)、顶部(上界)和中间mid=(top+bot)/2折半查找算法如下:
(1)x=a(mid)则已找到退出循环否则进行下面判断；
(2)x<a(mid)x必定落在bot和mid-1范围的内即top=mid-1；
(3)x>a(mid)x必定落在mid+1和top范围的内即bot=mid+1；
(4)在确定了新查找范围后重复进行以上比较直到找到或者bot<=top
将上面算法写成如下:
void
{
a[10],mid,bot,top,x,i,find;
prf(\"pleaseinputthe.gif' />:\\n\");
for(i=0;i<10;i)
scanf(\"%d\",&a[i]);
prf(\"pleaseinputthenumberyouwantfind:\\n\");
scanf(\"%d\",&x);
prf(\"\\n\");
bot=0;top=9;find=0;
while(bot<top&&find0)
{mid=(top+bot)/2; [Page]
(xa[mid])
{find=1;;}
(x<a[mid])
top=mid-1;

bot=mid+1;
}
(find1)
prf(\"thenumberisfoundtheno%d!\\n\",mid);

prf(\"thenumberisnotfound!\\n\");
}
7、插入法
把个数插到有序数列中插入后数列仍然有序
基本思想:n个有序数(从小到大)存放在a(1)—a(n)中要插入数x首先确定x插在中位置P；(可由以下语句实现)
#N10
voidinsert(a,x)
{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;
}

{a[N+1]={1,3,4,7,8,11,13,18,56,78},x,i;
for(i=0;i<N;i)prf(\"%d,\",a[i]);
prf(\"\\nInputx:\");
scanf(\"%d\",&x);
insert(a,x);
for(i=0;i<=N;i)prf(\"%d,\",a[i]);
prf(\"\\n\");
}
8、矩阵( 2维)运算
(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)
#M2
#L4
#N3


voidmv(a[M][L],b[L][N],c[M][N])
{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];
}
}

{a[M][L]={{1,2,3,4},{1,1,1,1}};
b[L][N]={{1,1,1},{1,2,1},{2,2,1},{2,3,1}},c[M][N];
i,j;
mv(a,b,c);
for(i=0;i<M;i)
{for(j=0;j<N;j)
prf(\"%4d\",c[i][j]);
prf(\"\\n\");
}
}
(3)矩阵传置
例:有 2维a(5,5)要对它实现转置可用下面两种方式:
#N3
voidch1(a[N][N])
{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;
}
}
voidch2(a[N][N])
{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;
}
}

{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)
prf(\"%4d\",a[i][j]);
prf(\"\\n\");
}
}
(4)求 2维中最小元素及其所在行和列
基本思路同维可用下面段实现(以 2维a[3][4]为例): [Page]
‘变量max中存放最大值row,column存放最大值所在行列号
#N4
#M3
voidmin(a[M][N])
{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)
(a[i][j]<min)
{min=a[i][j];
row=i;
column=j;
}
prf(\"Min=%d\\nAtRow%d,Column%d\\n\",min,row,column);
}

{a[M][N]={{1,23,45,-5},{5,6,-7,6},{0,33,8,15}};
min(a);
}
9、迭代法
算法思想:对于个问题求解x可由给定个初值x0根据某迭代公式得到个新值x1这个新值x1比初值x0更接近要求值x；再以新值作为初值即:x1→x0,重新按原来思路方法求x1,重复这过和直到|x1-x0|<ε(某给定精度)此时可将x1作为问题解
例:用迭代法求某个数平方根已知求平方根迭代公式为:
#<math.h>
floatfsqrt(floata)
{floatx0,x1;
x1=a/2;
do{
x0=x1;
x1=0.5*(x0+a/x0);
}while(fabs(x1-x0)>0.00001);
(x1);
}

{floata;
scanf(\"%f\",&a);
prf(\"genhao=%f\\n\",fsqrt(a));
}
十、数制转换
将个十进制整数m转换成→r(2－16)进制串
思路方法:将m不断除r取余数直到商为零以反序得到结果下面写出转换参数idec为十进制数ibase为要转换成数基(如 2进制基是2 8进制基是8等)输出结果是串
char*trdec(idec,ibase)
{charstrdr[20],t;
i,idr,p=0;
while(idec!=0)
{idr=idec%ibase;
(idr>=10)
strdr[p]=idr-10+65;

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’;
(strdr);
}

{x,d;
scanf(\"%d%d\",&x,&d);
prf(\"%s\\n\",trdec(x,d));
}
十、串般处理
1．简单加密和解密
加密思想是:将每个字母C加(或减)序数K即用它后第K个字母代替变换式公式:c=c+k
例如序数k为5这时A→Fa→fB→?G…当加序数后字母超过Z或z则c=c+k-26
例如:Youaregood→Dtzfwjltti
解密为加密逆过程
将每个字母C减(或加)序数K即c=c-k,
例如序数k为5这时Z→Uz→uY→T…当加序数后字母小于A或a则c=c-k+26
下段是加密处理:
#<stdio.h>
char*jiami(charstri)
{i=0;
charstrp[50],ia;
while(stri[i]!=’\\0’)
{(stri[i]>=’A’&&stri[i]<=’Z’) [Page]
{ia=stri[i]+5;
(ia>’Z’)ia-=26;
}
(stri[i]>=’a’&&stri[i]<=’z’)
{ia=stri[i]+5;
(ia>’z’)ia-=26;
}
ia=stri[i];
strp[i]=ia;
}
strp[i]=’\\0’;
(strp);
}

{chars[50];
gets(s);
prf(\"%s\\n\",jiami(s));
}
2．统计文本单词个数
输入行统计其中有多少个单词单词的间用格分隔开
算法思路:
(1)从文本(串)左边开始取出个；设逻辑量word表示所取是否是单词内初值设为0
(2)若所取不是“空格”“逗号”“分号”或“感叹号”等单词分隔符再判断word是否为1若word不为1则表是新单词开始让单词数num=num+1让word=1;


(3)若所取是“空格”“逗号”“分号”或“感叹号”等单词分隔符则表示不是单词内让word=0;
(4)再依次取下个重得(2)(3)直到文本结束
下面段是串中包含单词数
#\"stdio.h\"

{charc,[80];
i,num=0,word=0;
gets();
for(i=0;(c=[i])!=’\\0’;i)
(c’’)word=0;
(word0)
{word=1;
num;}
prf(\"Thereare%dwordheline.\\n\",num);
}
十 2、穷举法
穷举法(又称“枚举法”)基本思想是:列举各种可能情况并判断哪种可能是符合要求解这是种“在没有其它办法情况思路方法”是种最“笨”思路方法然而对些无法用解析法求解问题往往能奏效通常采用循环来处理穷举问题
例:将张面值为100元人民币等值换成100张5元、1元和0.5元零钞要求每种零钞不少于1张问有哪几种组合？

{i,j,k;
prf(\"5元1元5角\\n\");
for(i=1;i<=20;i)
for(j=1;j<=100-i;j)
{k=100-i-j;
(5*i+1*j+0.5*k100)
prf(\"%3d%3d%3d\\n\",i,j,k);
}
}
十 3、递归算法
用自身结构来描述自身称递归
VB允许在个Sub子过程和Function过程定义内部自己即递归Sub子过程和递归Function递归处理般用栈来实现每次自身把当前参数压栈直到递归结束条件；然后从栈中弹出当前参数直到栈空
递归条件:(1)递归结束条件及结束时值；(2)能用递归形式表示且递归向终止条件发展
例:编fac(n)=n!递归
fac(n)
{(n1)
(1);

(n*fac(n-1));
}

{n;
scanf(\"%d\",&n);
prf(\"n!=%d\\n\",fac(n));
}

延伸阅读

• 2011-9-25-- c语言,小女也爱C#(4)---由C语言引入C#
• 2010-12-9-- php算法,PHP基础算法
• 2009-9-12-- 计算机算法基础:RSA算法基础-实战
• 2011-7-9-- c语言面向对象,C++对C语言的非面向对象特性扩充(3)
• 2011-6-23-- c语言,C ++
• 2010-12-23-- c语言,C ++
• 2011-3-13-- c语言,C++ 工程实践(5)：避免使用虚函数作为库的接口
• 2011-7-4-- c语言,笨办法学C语言
• 2008-12-2-- c.k:C++
• 2009-2-12-- 6120c:C# 问关键字之：base、this