排序
冒泡法
int main()
{
int i,j,a[10],t;
printf("*冒泡排序法*\n请输入10个数:\n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(j=1;j<10;j++)
for(i=0;i<10-j;i++)
if(a[i]>a[i+1])
{
t=a[i+1];
a[i+1]=a[i];
a[i]=t;
}
printf("冒泡排序后的结果为(小—大):");
for(i=0;i<10;i++)
//printf("%2d",a[i]);
printf("%d\ ",a[i]);
printf("\n");
return 0;
}
冒泡排序每一趟排序把最大的放在最右边。比如：
87 12 56 45 78
87和12交换：12 87 56 45 78
87和56交换：12 56 87 45 78
87和45交换：12 56 45 87 78
87和78交换：12 56 45 78 87
到此第一趟排序结束，接下来的每一趟排序都是这样
快速排序法
快速排序法是对冒泡排序的一种改进，但都是基于交换排序思想。
快速排序：通过一遍排序将需要排序的数据划分为两部分，使其中一部分比另一部分数据小，然后再分别对这两部分数据继续进行这种排序，按此规则继续，直到每个部分为空或为1个数。
这是一种分治策略，将大批的数据进行逐步分解，可使用递归的方法。
#include<stdio.h>
#include "4-1 CreateData.c"
#define ARRAYLEN 10
int Division(int a[],int left,int right)
{
int base=a[left];
while(left<right)
{
//从右向左找第一个比基准小的元素
while(left<right && a[right]>base)
--right;
a[left]=a[right];
while(left<right && a[left]<base)
++left;
a[right]=a[left];
}
a[left]=base;
return left;
}
void QuickSort(int a[],int left,int right)
{
int i,j;
if(left<right)
{
i=Division(a,left,right);
QuickSort(a,left,i-1);
QuickSort(a,i+1,right);
}
}
int main()
{
int i,a[ARRAYLEN];
for(i=0;i<ARRAYLEN;i++)
a[i]=0;
if(!CreateData(a,ARRAYLEN,1,100))
{
prinf("生成随机数不成功！\n");
getch();
return 1;
}
printf("原数据：");
for(i=0;i<ARRAYLEN;i++)
printf("\n");
QuickSort(a,0,ARRAYLEN-1);
printf("排序后：\n");
for(i=0;i<ARRAYLEN;i++)
printf("%d",a[i]);
printf("\n");
getch();
return 0;
}
选择法
int main()
{
int i,j,a[10],t,min;
printf("*选择排序法*\n请输入10位数:\n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<9;i++)
{
min=i;
for(j=i+1;j<10;j++)
{
if(a[j]<a[min])
min=j;
}
t=a[i];
a[i]=a[min];
a[min]=t;
}
printf("选择排序后结果为:");
for(i=0;i<10;i++)
printf("%d\ ",a[i]);
printf("\n");
return 0;
}
/*
初始序列：{ 49 27 65 97 76 12 38 }
第1趟：12与49交换：12 { 27 65 97 76 49 38 }
第2趟：27不动 ：12 27 { 65 97 76 49 38 }
第3趟：65与38交换：12 27 38 { 97 76 65 49}
第4趟：97与49交换：12 27 38 49 { 97 76 65 }
第5趟：76与65交换：12 27 38 49 65 { 97 76 }
第6趟：97与76交换：12 27 38 49 65 76 97 完成
*/
其他排序
堆排序、直接插入排序、希尔排序(听说高效率)、合并排序等。
多趣味算法题
/*试卷有甲乙丙3类题，
甲类题共6道，每题4分，
乙类题共8道，每题5分，
丙类题共8道，每题7分，
问最后学生分数有多少种可能
*/
void main()
{
int a,b,c,s,i=0,j,k,min;
int Length=0;
int m[120];
for(a=0;a<7;a++)
{
for(b=0;b<9;b++)
{
for(c=0;c<9;c++)
{
s=4*a+5*b+7*c;
m[i]=s;
i++;
Length++;
for(i=0;i<Length;i++)
{
for(j=i+1;j<Length;j++)
{
if(m[j] == m[i])
{
for(k=j+1;k<Length;k++)
{
m[k-1]=m[k];
Length--;
}
}
}
}
}
}
}
//排序
for(i=0;i<Length;i++)
for(j=i+1;j<Length;j++)
{
if(m[j]<m[i])
{
min=m[j];
m[j]=m[i];
m[i]=min;
}
}
printf("分数情况为：\n");
for(i=0;i<Length;i++)
{
printf("%-5d",m[i]);
if((i+1)%10==0)
printf("\n");
}
printf("\n总共有 %d 种情况\n",Length);
}
递推算法
斐波数列
int main()
{
long int f1,f2;
int i;
f1=1;f2=1;//第一组的两个数
for(i=1;i<=15;i++)
{
printf("%-12d %-12d",f1,f2);
if(i%2==0)
printf("\n");
f1=f1+f2;
f2=f2+f1;
}
printf("\n");
return 0;
}
递归算法
所谓递归算法，就是在程序过程中不断调用自身求解的方法。
求阶乘
#include<stdio.h>
int fact(int n);
int main()
{
int i;
printf("请输入要求阶乘的整数：");
scanf("%d",&i);
printf("%d的阶乘为：%d\n",i,fact(i));
getch();
return 0;
}
int fact(int n)
{
if(n<=1)
return 1;
else
return n*fact(n-1);
}
进制转换
#include<stdio.h>
#include<string.h>
void convto(char *s,int n,int b)
{
char bit[]={"0123456789ABCDEF"};
int len;
if(n==0)
{
strcpy(s,"");
return;
}
convto(s,n/b,b);
len = strlen(s);
s[len] = bit[n%b];
s[len+1] = '\0';
}
void main(void)
{
char s[80];
int i,base,old;
printf("请输入十进制数：");
scanf("%d",&old);
printf("请输入转换的进制：");
scanf("%d",&base);
convto(s,old,base);
printf("%s\n",s);
getch();
return;
}
分治算法
分治算法的基本思想是将一个计算复杂的问题分为若干个子问题来进行求解，然后综合各个小问题得到复杂问题的最终答案。
乒乓球比赛日程安排
#include<stdio.h>
#define MAXN 64
int a[MAXN+1][MAXN+1]={0};
void gamecal(int k,int n)
{
int i,j;
if(n==2)
{
a[k][1]=k;
a[k][2]=k+1;
a[k+1]][1]=k+1；
a[k+1][2]=k;
}
else
{
gamecal(k,n/2);
gamecal(k+n/2,n/2);
for(i=k;u<k+n/2;i++)
{
for(j=n/2+1;j<=n;j++)
{
a[i][j]=a[i+n/2][j-n/2];
}
}
for(i=k+n/2;i<k+n;i++)
{
for(j=n/2+1;j<=n;j++)
{
a[i][j]=a[i-n/2][j-n/2];
}
}
}
}
int main()
{
int m,i,j;
printf("输入参赛选手人数：");
scanf("%d",&m);
j=2;
for(i=2;i<8;i++)
{
j=j*2;
if(j==m)
break;
}
if(i>=8)
{
printf("参赛选手人数必须为2的整数次幂，且不超过64！\n");
getch();
return 0;
}
gamecal(1,m);
prin1("\n编号");
for(i=2;i<=m;i++)
printf("%2d天",i-1);
prinf("\n");
for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++)
printf("%4d",a[i][j]);
printf("\n");
}
getch();
return 0;
}
贪婪算法
贪婪算法的思想非常简单而且算法效率很高，在一些问题的解决上有着明显的优势，它所作出的选择只是局部最优，得不到整体最优解，其最终结果却是最优解的近似解。
贪婪算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出近似解。
找零钱方案
人民币有100、50、20、10、5、2、1、0.5、0.2、0.1等多种面额，要找68.9的零钱，方案有很多。
#include<stdio.h>
#define MAXN 9
int parvalue[MAXN]={10000,5000,2000,1000,500,200,100,50,20,10};//人民币面额
int num[MAXN]={0};
int exchange(int n)
{
int i,j;
for(i=0;i<MAXN;i++)
if(n>parvalue[i]) break;
while(n>0 && i<MAXN)
{
if(n>=parvalue[i])
{
n-=parvalue[i];
num[i]++;
}
else if(n<10 && n>=5)
{
num[MAXN-1]++；
break;
}
else
i++;
}
return 0;
}
int main()
{
int i;
float m;
printf("请输入找零的金额：");
scanf("%f",&m);
exchange((int)100*m);
printf("\n%.2f元零钱的组成：\n",m);
for(i=0;i<MAXN;i++)
if(num[i]>0)
printf("6.2f:%d张\n",(float)parvalue[i]/100.0,num[i]);
getch();
return 0;
}
试探算法
试探算法也称为回溯法，它是一种系统地搜索问题解的方法，该算法设计思想适用范围相当广。
算法基本思想：从问题的某一种状态出发，搜索从这种状态出发所能达到的所有状态，当一条路走到尽头的时候，先退几步，接着从另一种可能的状态出发，继续搜索，直到所有的路径都尝试一遍。
利用试探法生成彩票数字：
常见的彩票号码都是由一些数字组成的，假设每组由7个1-29的数字组成，且这7个数字不能相同，编写程序生成所有的号码组合。
#include<stdio.h>
#define1 MAXN 7
//设置每一注彩票的位数
#define NUM 29
int num[NUM];
int lottery[MAXN];
void combine(int n,int m)
{
int i,j;
for(i=n;i>=m;i--)
{
lottery[m-1]=num[i-1];
if(m>1)
combine(i-1,m-1);
else
{
for(j=MAXN-1;j>=0;j--)
printf("%3d",lottery[j]);
getch();
printf("\n");
}
}
}
int main()
{
int i,j;
for(i=0;i<NUM;i++)
num[i]=i+1;
for(i=0;i<MAXN;i++)
lottery[i]=0;
combine(NUM,MAXN);
getch();
return 0;
}
查找算法
查找算法分为简单查找、二叉树、索引、散列表等。
求π旳近似值
int main()
{
int s;
float n,t,pi;
t=1,pi=0;
n=1.0;
s=1;
while(fabs(t)>1e-6)
{
pi=pi+t;
n=n+2;
s=-s;
t=s/n;
}
pi=pi*4; // π/4=1-1/3+1/5-1/7+……
printf("pi=%10.6f\n",pi);
return 0;
}
求素数
int main()
{
int m,k,i,n=0;
for(m=101;m<=200;m+=2)//101~200之间的素数
{
k=sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0)
break;//r若能整除，结束内层for循环
if(i>=k+1)
{
printf("%4d",m);
n+=1;
}
if(n%7==0)
printf("\n");
}
printf("\n");
printf("素数的个数为：%d\n",n);
return 0;
}
辗转相除/最大公约
int main()
{
int a,b,num1,num2,temp;
printf("请输入两个数：\n");
scanf("%d %d",&num1,&num2);
if(num2<num1)
{
temp=num1;
num1=num2;
num2=temp;
}
a=num1;
b=num2;
while(b!=0)
{
temp=a%b;
a=b;
b=temp;
}
printf("公约数：%d\n",a);
printf("公倍数：%d\n",num1*num2/a);
}