基础算法思想

基础算法思想

1. 编程的灵魂：数据结构+算法
2. 算法的作用
3. 递推算法
4. 枚举(穷举)算法
5. 递归算法
6. 分治算法
7. 贪婪算法
8. 试探算法
9. 模拟算法
10. 算法的评价

1、猜价格（算法的作用）

#include <stdio.h>
#include <cstdlib> 
//#include<curses.h>int main()
{int oldprice,price=0,i=0;printf("请首先设置商品的真实价格:");scanf("%d",&oldprice);system("clear");printf("请输入试猜的价格:n");while(oldprice!=price){i++;printf("参与者:"); scanf("%d",&price);printf("主持人:") ;if(price>oldprice){printf("高了n");                  }else if(price<oldprice){printf("低了n");}else{printf("恭喜你，答对了，该商品属于你了!nn你一共试猜了%d次.n",i);}}//getch();return 0;    
}

2、兔子数列（顺推）

#include <stdio.h>
#define NUM 13
int main() 
{ int i;long fib[NUM] = {1,1}; for(i=2;i<NUM;i++) { fib[i] = fib[i-1]+fib[i-2]; } for(i=0;i<NUM;i++) { printf("%d月兔子总数:%ldn", i, fib[i]); } //getch();return 0; 
}

3、存款问题（逆推）

#include <stdio.h>
#define FETCH 1000
#define RATE 0.0171
int main()
{double corpus[49];int i;corpus[48]=(double)FETCH;for(i=47;i>0;i--){corpus[i]=(corpus[i+1]+FETCH)/(1+RATE/12);}for(i=48;i>0;i--){printf("第%d月末本利合计:%.2fn",i,corpus[i]);}//getch();return 0;
}

4、填数字（穷举）

#include <stdio.h>
int main()
{int i1,i2,i3,i4,i5;long multi,result;for(i1=1;i1<=9;i1++){for(i2=0;i2<=9;i2++){for(i3=0;i3<=9;i3++){for(i4=0;i4<=9;i4++){for(i5=0;i5<=9;i5++){multi=i1*10000+i2*1000+i3*100+i4*10+i5;result=i5*100000+i5*10000+i5*1000+i5*100+i5*10+i5;if(multi*i1==result){printf("n%5d%2d%2d%2d%2dn",i1,i2,i3,i4,i5);printf("X%12dn",i1);printf("______________n");printf("%3d%2d%2d%2d%2d%2dn",i5,i5,i5,i5,i5,i5); }}}}}}    //getch();return 0;
}

5、填运算符（穷举） 

#include <stdio.h>
int main()
{int j,i[5]; //循环变量 ，数组i用来表示4个运算符 int sign;//累加运算时的符号   int result; //保存运算式的结果值 int count=0; //计数器，统计符合条件的方案 int num[6];  //保存操作数 float left,right; //保存中间结果 char oper[5]={' ','+','-','*','/'}; //运算符 printf("请输入5个数：");for(j=1;j<=5;j++)scanf("%d",&num[j]);printf("请输入结果：");scanf("%d",&result);for(i[1]=1;i[1]<=4;i[1]++)//循环4种运算符，1表示+，2表示-,3表示*，4表示/{if((i[1]<4) || (num[2]!=0))//运算符若是/,则第二个运算数不能为0{for(i[2]=1;i[2]<=4;i[2]++){if((i[2]<4) || (num[3]!=0)){for(i[3]=1;i[3]<=4;i[3]++){if((i[3]<4) || num[4]!=0){for(i[4]=1;i[4]<=4;i[4]++){if((i[4]<4) || (num[5]!=0)){left=0;right=num[1];sign=1;for(j=1;j<=4;j++){switch(oper[i[j]]){case '+': left=left+sign*right;sign=1;right=num[j+1];break;case '-': left=left+sign*right;sign=-1;right=num[j+1];break;//通过f=-1实现减法case '*': right=right*num[j+1];break;//实现乘法case '/': right=right/num[j+1];//实现除法break;}}if(left+sign*right==result){count++;printf("%3d：",count);for(j=1;j<=4;j++)printf("%d%c",num[j],oper[i[j]]);printf("%d=%dn",num[5],result);} }}}}}}}}if(count==0)printf("没有符合要求的方法！n");//getch();return 0;
}

6、求阶乘（递归）

#include <stdio.h>
int fact(int n);
int main()
{int i;printf("请输入要求阶乘的一个整数："); scanf("%d",&i);printf("%d的阶乘结果为：%dn",i,fact(i)); //getch();return 0;
}
int fact(int n)
{if(n<=1)return 1;elsereturn n*fact(n-1);
}

7、进制转化（递归）

#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] = '';
}int main(void)
{char s[80];int i, base,old;printf("请输入十进制数:");scanf("%d",&old); printf("请输入转换的进制：");scanf("%d", &base);convto(s, old, base);printf("%sn", s);//getch();return 0;
}

8 、比赛赛程安排（分治算法）

#include <stdio.h>
#define MAXN 64
int a[MAXN+1][MAXN+1]={0};
void gamecal(int k,int n)//处理编号k开始的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;i<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);printf("n编号 ");for(i=2;i<=m;i++)printf("%2d天 ",i-1);printf("n");for(i=1;i<=m;i++){for(j=1;j<=m;j++)printf("%4d ",a[i][j]);printf("n");}//getch();return 0;    
}

9、找零钱（贪心算法）

#include <stdio.h>
#define MAXN 9
int parvalue[MAXN]={10000,5000,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; //找到比n小的最大面额 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;
}

10、生成彩票号码组合（试探算法）

#include <stdio.h>
int main()
{int i[7],j;for(i[0]=1;i[0]<=29;i[0]++)for(i[1]=1;i[1]<=29;i[1]++){if(i[0]==i[1]) continue;for(i[2]=1;i[2]<=29;i[2]++){if(i[0]==i[2] || i[1]==i[2]) continue;for(i[3]=1;i[3]<=29;i[3]++){if(i[0]==i[3] || i[1]==i[3] || i[2]==i[3]) continue;for(i[4]=1;i[4]<=29;i[4]++){if(i[0]==i[4] || i[1]==i[4] || i[2]==i[4] || i[3]==i[4]) continue;for(i[5]=1;i[5]<=29;i[5]++){if(i[0]==i[5] || i[1]==i[5]  || i[2]==i[5] || i[3]==i[5] || i[4]==i[5]) continue;for(i[6]=1;i[6]<=29;i[6]++){if(i[0]==i[6] || i[1]==i[6]  || i[2]==i[6] || i[3]==i[6] || i[4]==i[6] || i[5]==i[6]) continue;for(j=0;j<7;j++)printf("%3d",i[j]);printf("n");// getch();}}                        }                                        }                }}   return 0;      
}

11、生成彩票号码组合（试探算法）

#include <stdio.h>
int main()
{int i[7],j;for(i[0]=1;i[0]<=29;i[0]++)for(i[1]=1;i[1]<=29;i[1]++){if(i[0]==i[1]) continue;for(i[2]=1;i[2]<=29;i[2]++){if(i[0]==i[2] || i[1]==i[2]) continue;for(i[3]=1;i[3]<=29;i[3]++){if(i[0]==i[3] || i[1]==i[3] || i[2]==i[3]) continue;for(i[4]=1;i[4]<=29;i[4]++){if(i[0]==i[4] || i[1]==i[4] || i[2]==i[4] || i[3]==i[4]) continue;for(i[5]=1;i[5]<=29;i[5]++){if(i[0]==i[5] || i[1]==i[5]  || i[2]==i[5] || i[3]==i[5] || i[4]==i[5]) continue;for(i[6]=1;i[6]<=29;i[6]++){if(i[0]==i[6] || i[1]==i[6]  || i[2]==i[6] || i[3]==i[6] || i[4]==i[6] || i[5]==i[6]) continue;for(j=0;j<7;j++)printf("%3d",i[j]);printf("n");// getch();}}                        }                                        }                }}   return 0;      
}

#include <stdio.h>
#define 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      //若m=1,输出一注号码 {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;
}

12、猜数字（模拟算法） 

 #include <time.h>#include <stdio.h>#include <stdlib.h>
int main(){int n,m,i=0;srand(time(NULL));n=rand() % 100 + 1;do{printf("输入所猜数字:");scanf("%d",&m);i++;if (m>n)printf("错误!所猜数太大了!n");else if (m<n)printf("错误!所猜数太小了!n");}while(m!=n);printf("答对了!n");printf("共猜测了%d次。n",i);if(i<=5)printf("你太聪明了，这么快就猜出来了！");else if(i>5)printf("还需改进方法，以便更快猜出来！");//getch();return 0;
}

12、模拟骰子（模拟算法） 

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void play(int n)
{int i,m=0,t=0;for(i=0;i<n;i++){t=rand()%6+1;m+=t;printf("t第%d粒:%d;n",i+1,t);}printf("t总点数为:%dn",m);                    
}
int main(void)
{int c;//参赛人数int n;//骰子数量 int i,m;do{srand(time(NULL));printf("设置骰子数量(输入0退出):");scanf("%d",&n);if(n==0) break;//至少一个骰子 printf("n输入本轮参赛人数(输入0退出):");scanf("%d",&c);if(c==0) break;for(i=0;i<c;i++){printf("n第%d位选手掷出的骰子为：n",i+1); play(n);}printf("n");}while(1);return 0;
}