【精品】求阶乘等简单算法25
一、计数、求和、求阶乘等简单{ int 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; 的初值。 例:用随机函数产
printf("%4d",a[i]); 生100个[0,99]范围内的随机整
数,统计个位上的数字分别为1,if(i%10==0)printf("\n");
2,3,4,5,6,7,8,9,0的
} 数的个数并打印出来。
for(i=1;i<=100;i++) 本题使用数组来处理,用数
组a[100]存放产生的确100个随{ p=a[i]%10; 机整数,数组x[10]来存放个位上
if(p==0) p=10; 的数字分别为1,2,3,4,5,
6,7,8,9,0的数的个数。即x[p]=x[p]+1; 个位是1的个数存放在x[1]中,
}
个位是2的个数存放在x[2]
for(i=1;i<=10;i++) 中,……个位是0的个数存放在
x[10]。
{ p=i;
void main()
例如: 求 m=14 ,n=6 的最大公if(i==10) p=0;
约数. m n r printf("%d,%d\n",p,x[i]);
14 6 2 }
6 2 0
printf("\n");
void main() }
{ int nm,r,n,m,t;
二、求两个整数的最大公约
printf("please input two numb数、最小公倍数
ers:\n");
分析:求最大公约数的算法
:(最小公倍数=两个整数之scanf("%d,%d",&m,&n);
积/最大公约数)
nm=n*m; (1) 对于已知两数m,n,使得m>
if (m
=k) } printf("该数是素数");
三、判断素数 else
只能被1或本身整除的数称printf("该数不是素数"); 为素数 基本思想:把m作为被
}
除数,将2—INT( )作为除数,
将其写成一函数,若为素数返回如果都除不尽,m就是素数,否
1,不是则返回0 则就不是。(可用以下程序段实
现)
int prime( m%) void main()
{int i,k; { int m,i,k;
k=sqrt(m); printf("please input a number:\
for(i=2;i=k)
基本思想:n为大于等于6的任
return 1;
一偶数,可分解为n1和n2两个
else 数,分别检查n1和n2是否为素
数,如都是,则为一组解。如n
return 0;
1不是素数,就不必再检查n2是
} 否素数。先从n1=3开始,检验n
1和n2(n2=N-n1)是否素数。main()
然后使n1+2 再检验n1、n2是
{ int x,i; 否素数,… 直到n1=n/2为止。
printf("please input a even nu 利用上面的prime函数,验
mber(>=6):\n"); 证哥德巴赫猜想的程序代码如
下: scanf("%d",&x); #include "math.h" if (x<6||x%2!=0) int prime(int m) printf("data error!\n");
{ int i,k; else
k=sqrt(m); for(i=2;i<=x/2;i++) for(i=2;ia[j]) imin=j; 数,与第1个数交换位置;
if(i!=imin)
2)除第1 个数外,其余n-1个
{s=a[i]; a[i]=a[imin]; a[imin]=s;
数中选最小的数,与第2个数交
}
换位置;
printf("%d\n",a[i]); 3)依次类推,选择了n-1次后,
} 这个数列已按升序排列。
} { int a[10];
2(冒泡法排序(升序) int i,j,t;
基本思想:(将相邻两个数比printf("input 10 numbers\n");
较,小的调到前头)
for(i=0;i<10;i++) 1)有n个数(存放在数组a(n)
scanf("%d",&a[i]); 中),第一趟将每相邻两个数比
printf("\n"); 较,小的调到前头,经n-1次两
两相邻比较后,最大的数已“沉
for(j=0;j<=8;j++) 底”,放在最后一个位置,小数上
for(i=0;i<9-j;i++) 升“浮起”;
if(a[i]>a[i+1]) 2)第二趟对余下的n-1个数(最
大的数已“沉底”)按上法比较,{t=a[i];a[i]=a[i+1];a[i+1]=t;}
经n-2次两两相邻比较后得次大
printf("the sorted numbers:\n"); 的数;
for(i=0;i<10;i++) 3)依次类推,n个数共进行n-1
趟比较,在第j趟中要进行n-jprintf("%d\n",a[i]); 次两两比较。
}
程序段如下
void main()
3(合并法排序(将两个有序for(i=0;i<10;i++) 数组A、B合并成另一个有序的
scanf("%d",&a[i]); 数组C,升序)
for(i=0;i<10;i++)
基本思想:
scanf("%d",&b[i]); 1)先在A、B数组中各取第一个
printf("\n"); 元素进行比较,将小的元素放入
C数组;
ia=0;ib=0;ic=0; 2)取小的元素所在数组的下一个
while(ia<10&&ib<10) 元素与另一数组中上次比较后较
{ if(a[ia]=10)
n");
printf("the number is not found!\n"); for(i=0;i<10;i++)
scanf("%d",&a[i]); else
printf("the number is found thprintf("please input the numbe
r you want find:\n"); e no%d!\n",p);
} scanf("%d",&x); 思考:将上面程序改写一查找函printf("\n"); 数Find,若找到则返回下标值,
index=-1;
找不到返回-1
for(i=0;i<10;i++) ?基本思想:一列数放在数组a[1]
if(x==a[i]) ---a[n]中,待查找的关键值为ke
y,把key与a数组中的元素从
{ index=i; break; 头到尾一一进行比较查找,若相
} 同,查找成功,若找不到,则查
找失败。(查找子过程如下。indeif(index==-1) x:存放找到元素的下标。)
void main()
printf("the number is not foun(2)xa(mid),x必定落在midprintf("the number is found th
+1和top的范围之内,即bot=me no%d!\n",index);
id+1;
}
(4)在确定了新的查找范围后,
2(折半查找法(只能对有序重复进行以上比较,直到找到或数列进行查找) 者bot<=top。
基本思想:设n个有序数(从将上面的算法写成如下程序: 小到大)存放在数组a[1]----a[n]
void main() 中,要查找的数为x。用变量bo
t、top、mid 分别表示查找数据{
范围的底部(数组下界)、顶部
int a[10],mid,bot,top,x,i,find;
(数组的上界)和中间,mid=(t
printf("please input the array:\op+bot)/2,折半查找的算法如
n"); 下:
for(i=0;i<10;i++) (1)x=a(mid),则已找到退出循
环,否则进行下面的判断;
scanf("%d",&a[i]);
printf("please input the numbeprintf("the number is found th
r you want find:\n"); e no%d!\n",mid); scanf("%d",&x); else
printf("the number is not founprintf("\n");
d!\n");
bot=0;top=9;find=0;
}
while(bota[p]&&pp; i--) 八、矩阵(二维数组)运算 a[i]=a[i-1]; (1)矩阵的加、减运算 a[p]=x; C(i,j)=a(i,j)+b(i,j) 加法 } C(i,j)=a(i,j)-b(i,j) 减法 main() (2)矩阵相乘
{ int a[N+1]={1,3,4,7,8,11,13,1(矩阵A有M*L个元素,矩阵B
有L*N个元素,则矩阵C=A*B8,56,78}, x, i;
有M*N个元素)。矩阵C中任for(i=0; i }
float fsqrt(float a) main()
{ float x0, x1; { int a[M][N]={{1,23,45,-5},{5,6,
x1=a/2; -7,6},{0,33,8,15}};
do{ min(a);
x0=x1; }
换成数的基(如二进制的基是2,x1=0.5*(x0+a/x0);
八进制的基是8等),函数输出}while(fabs(x1-x0)>0.00001);
结果是字符串。
return(x1);
char *trdec(int idec, int ibase)
}
{ char strdr[20], t; main()
int i, idr, p=0; { float a;
while(idec!=0) scanf("%f", &a);
{ idr=idec % ibase; printf("genhao =%f\n", fsqrt
if(idr>=10)
(a));
strdr[p++]=idr-10+65; }
else
十、数制转换
strdr[p++]=idr+48;
将一个十进制整数m转换
成 ?r(2,16)进制字符串。 idec/=ibase;
方法:将m不断除 r 取余}
数,直到商为零,以反序得到结
for(i=0; i 1(简单加密和解密
char *jiami(char stri[]) 加密的思想是: 将每个字母C
加(或减)一序数K,即用它后{ int i=0;
char strp[50],ia;
while(stri[i]!=?\0?) main()
{ if(stri[i]>=?A?&&stri[i]<=?Z?) { char s[50]; { ia=stri[i]+5; gets(s); if (ia>?Z?) ia-=26; printf("%s\n", jiami(s));
} }
else if(stri[i]>=?a?&&stri[i]<=?z?) 2(统计文本单词的个数
输入一行字符,统计其中有多少{ ia=stri[i]+5;
个单词,单词之间用格分隔开。 if (ia>?z?) ia-=26;
算法思路:
}
(1)从文本(字符串)的左边开else ia=stri[i];
始,取出一个字符;设逻辑量wstrp[i++]=ia; ord表示所取字符是否是单词内
的字符,初值设为0 }
(2)若所取字符不是“空格”,“逗strp[i]=?\0?;
号”,“分号”或“感叹号”等单词的return(strp); 分隔符,再判断word是否为1,
若word不为1则表是新单词的}
开始,让单词数num = num +else if(word==0) 1,让word =1;
{ word=1; (3)若所取字符是“空格”,“逗
num++;}
号”,“分号”或“感叹号”等单词的
printf("There are %d word in 分隔符, 则表示字符不是单词内
the line.\n",num); 字符,让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++)
例: 将一张面值为100元的人if(c==' ') word=0; 民币等值换成100张5元、1元
和0.5元的零钞,要求每种零钞 用自身的结构来描述自身,
称递归 不少于1张,问有哪几种组合,
main()
VB允许在一个Sub子过程{ int i, j, k;
和Function过程的定义内部调
5角\n"); printf(" 5元 1元
用自己,即递归Sub子过程和递for(i=1; i<=20; i++) 归Function函数。递归处理一般
用栈来实现,每调用一次自身,for(j=1; j<=100-i; j++)
把当前参数压栈,直到递归结束{ k=100-i-j; 条件;然后从栈中弹出当前参数,
直到栈空。 if(5*i+1*j+0.5*k==100)
递归条件:(1)递归结束条件及printf(" %3d %3d %3d\n", i, j,
结束时的值;(2)能用递归形式 k);
表示,且递归向终止条件发展。 }
例:编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)); }