c语言常用算法

一、求两个整数的最大公约数、最小公倍数

分析：求最大公约数的算法思想：(最小公倍数=两个整数之积/最大公约数) (1) 对于已知两数m，n，使得m>n； (2) m除以n得余数r；

(3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； (4) m←n，n←r，再重复执行(2)。

例如: 求 m=14 ,n=6 的最大公约数. m n r 14 6 2 6 2 0

void main() {

int a,r,n,m,t;

printf(\"please input two numbers:\\n\"); scanf(\"%d,%d\ a=n*m; if (mt=n; n=m; m=t; }

r=m%n; while (r!=0) {

m=n; n=r; r=m%n; }

printf(\"最大公约数:%d\\n\ printf(\"最小公倍数:%d\\n\ }

二、判断素数

只能被1或本身整除的数称为素数 基本思想：把m作为被除数，将2到(int)sqrt(m)之间所有的整数作为除数，如果都除不尽，m就是素数，否则就不是。（可用以下程序段实现） void main() {

int m,i,k;

printf(\"please input a number:\\n\"); scanf(\"%d\ k=sqrt(m);

for(i=2;iif(m%i==0) break; }

if(i>=k)

printf(\"该数是素数\"); else

printf(\"该数不是素数\"); }

三、排序算法 1.冒泡法：

冒泡法原理详见教材例7.3，教材134页 #include

void BubbleSort(int* pData,int Count) {

int iTemp;

for(int i=1;ifor(int j=Count-1;j>=i;j--) {

if(pData[j]iTemp = pData[j-1]; pData[j-1] = pData[j]; pData[j] = iTemp; } } } }

void main() {

int data[] = {10,9,8,7,6,5,4}; BubbleSort(data,7); for (int i=0;i<7;i++) {

printf(“%d\\n”, data[i]); } }

2.比较交换法

比较交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换 #include

void ExchangeSort(int* pData,int Count) {

int iTemp;

for(int i=0;ifor(int j=i+1;jif(pData[j]iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; } } } }

void main() {

int data[] = {10,9,8,7,6,5,4}; ExchangeSort(data,7); for (int i=0;i<7;i++) {

printf(“%d\\n”, data[i]); } }

3.选择法：

选择法原理详见教材例10.9，教材241页 此处为另一种写法，原理相同 #include

void SelectSort(int* pData,int Count) {

int iTemp; int iPos;

for(int i=0;iiTemp = pData[i]; iPos = i;

for(int j=i+1;jif(pData[j]iTemp = pData[j]; iPos = j; } }

pData[iPos] = pData[i]; pData[i] = iTemp; } }

void main() {

int data[] = {10,9,8,7,6,5,4}; SelectSort(data,7); for (int i=0;i<7;i++) {

printf(“%d\\n”, data[i]); } }

4. 插入法

插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张

#include

void InsertSort(int* pData,int Count) {

int iTemp; int iPos;

for(int i=1;iiTemp = pData[i]; iPos = i-1;

while((iPos>=0) && (iTemppData[iPos+1] = pData[iPos]; iPos--; }

pData[iPos+1] = iTemp; } }

void main() {

int data[] = {10,9,8,7,6,5,4}; InsertSort(data,7); for (int i=0;i<7;i++) {

printf(“%d\\n”, data[i]); } }

四、查找法

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 main() {

int a[10],p,x,i;

printf(\"please input the array:\\n\"); for(i=0;i<10;i++) {

scanf(\"%d\ }

printf(\"please input the number you want find:\\n\"); scanf(\"%d\ printf(\"\\n\"); p=0;

while(x!=a[p]&&p<10) p++; if(p>=10)

printf(\"the number is not found!\\n\"); else

printf(\"the number is found the no%d!\\n\ }

2．折半查找法（只能对有序数列进行查找）

基本思想：设n个有序数（从小到大）存放在数组中，要查找的数为x。用变量bot、top、mid 分别表示查找数据范围的底部（数组下界）、顶部（数组的上界）和中间，mid=(top+bot)/2，折半查找的算法如下：

（1）x=a(mid)，则已找到退出循环，否则进行下面的判断；

（2）xa(mid)，x必定落在mid+1和top的范围之内，即bot=mid+1；

（4）在确定了新的查找范围后，重复进行以上比较，直到找到或者bot<=top。 将上面的算法写成如下程序：

void main() {

int a[10],mid,bot,top,x,i,find; printf(\"please input the array:\\n\"); for(i=0;i<10;i++) scanf(\"%d\

printf(\"please input the number you want find:\\n\"); scanf(\"%d\ printf(\"\\n\"); bot=0; top=9; find=0;

while(botmid=(top+bot)/2; if(x==a[mid]) {

find=1;break; }

else if(xtop=mid-1; else

bot=mid+1; }

if (find==1)

printf(\"the number is found the no%d!\\n\ else

printf(\"the number is not found!\\n\"); }