约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列
|
#include <stdio.h> #include <stdlib.h> #define N 41 #define M 3 int main() { int man[N]={0}; int count=1; int i=0,pos=-1+k; int alive=0; while(count<=N) { do{ pos=(pos+1) % N; //环状处理 if(man[pos]==0) i++; if(i==M) //报数3的人 { i=0; break; } }while(1); man[pos]=count; count++; } printf("\n约瑟夫排列(最初位置-约瑟夫环位置):\n"); for(i=0;i<N;i++) { printf("%d-%d ",i+1,man[i]); if(i!=0 && i%10==0) //每输出10个则换行 printf("\n"); } printf("\n\n准备剩下的人数？"); scanf("%d", &alive); printf("这%d人初始位置应排在以下序号:\n",alive); alive=N-alive; for(i=0;i<N;i++) if(man[i]>alive) printf("初始序号:%d,约瑟夫环序号:%d\n",i+1,man[i]); printf("\n"); getch(); return 0; } |
百钱买百鸡：公鸡5文钱1只，母鸡3文钱1只，小鸡3只1文钱，要求用100文钱买100只鸡，求公鸡、母鸡和小鸡各应该买多少只？
x+y+z=100
5x+3y+z/3=100
设一个整数参数k，就有：
x=4k
y=25 - 7k
z=75 + 3k
|
#include <stdio.h> int main() { int x,y,z,k; for(k = 0; k <= 3; k++) { x=4*k; y=25-7*k; z=100-x-y; printf("公鸡:%d，母鸡:%d，小鸡:%d\n", x, y, z); } getch(); return 0; } |
阶梯数：有一次，大科学家爱因斯坦给他的朋友出了这样一道数学题：在你面前有一条长长的阶梯。如果你每步跨2阶，那么最后剩一阶。如果你每步跨3阶，那么最后剩2阶。如果你每步跨5阶，最后剩4阶，如果你每步跨6阶，最后剩5阶。只有当你能够每步跨7阶时，才正好到头，一阶也不剩。你想一想，这阶梯到底有多少阶
|
#include <stdio.h> int main() { int ladder=7; while(1) { if((ladder%2==1) && (ladder%3==2) && (ladder%5==4) && (ladder%6==5)) break; ladder+=7; } printf("该阶梯至少有%d阶。\n",ladder); getch(); return 0; } |
背包问题
有一个背包最多可装重量8公斤的物品，假设要用该背包装如下水果，要求使背包中装的物品的价值最大，应该装下列哪些物品才能达到要求？
各水果的重量和价值：
苹果：5公斤，40元；
梨：2公斤，12元；
桃：1公斤，7元；
葡萄：1公斤，8元；
香蕉：6公斤，48元。
分析：01背包问题的最优子问题是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
已知前i-1件商品的最优化结果；那么在添加第i件商品时的最优化结果可以由上式表示
|
#include <stdio.h> typedef struct goods { double *value; //价值 double *weight; //重量 char *select; //是否选中到方案 int num;//物品数量 double limitw; //限制重量 }GOODS; double maxvalue,totalvalue;//方案最大价值,物品总价值 char *select1; //临时数组 void backpack(GOODS *g, int i, double tw, double tv)//参数为物品i,当前选择已经达到的重量tw,本方案可能达到的总价值 tv { int k; if (tw + g->weight[i] <= g->limitw)//将物品i包含在当前方案,且重量小于等于限制重量 { select1[i] = 1; //选中第i个物品 if (i < g->num - 1) //若物品i不是最后一个物品 backpack(g, i + 1, tw + g->weight[i], tv); //递归调用,继续添加下一物品 else //若已到最后一个物品 { for (k = 0; k < g->num; ++k) //将状态标志复制到option数组中 g->select[k] = select1[k]; maxvalue = tv; //保存当前方案的最大价值 } } select1[i] = 0; //取消物品i的选择状态 if (tv - g->value[i] > maxvalue)//若物品总价值减去物品i的价值还大于maxv方案中已有的价值,说明还可以继续向方案中添加物品 { if (i < g->num - 1) //若物品i不是最后一个物品 backpack(g, i + 1, tw, tv - g->value[i]); //递归调用,继续加入下一物品 else //若已到最后一个物品 { for (k = 0; k < g->num; ++k) //将状态标志复制到option数组中 g->select[k] = select1[k]; maxvalue = tv - g->value[i]; //保存当前方案的最大价值(从物品总价值中减去物品i的价值) } } } |
求最大公约数和最小公倍数
欧几里德算法
欧几里德算法采用辗转相除的方法来求最大公约数，这是计算两个数最大公约数的传统算法
其算法思路为：
（1）对于已知两数m、n，使m>n；
（2）m除以n得余数r；
（3）若r=0，则n为求得的最大公约数，跳至第（5）求最小公倍数；否则执行第4步；
（4）将n的值保存到m中，将r的值保存到n中，重复执行步骤（2）和（3）。
（5）有了两数的最大公约数，则最小公倍数就很简单了，将两数相乘的积除以最大公约数即可。
|
#include <stdio.h> int gcd(int a, int b) //最大公约数 { int m,n,r; m=a>=b?a:b; //m保存较大数 n=a<b?a:b; //n保存较小数 r=m%n; //求余数 while(r!=0) //辗转相除 { m=n; n=r; r=m%n; } return n; //返回最大公约数 } int lcm(int a,int b) //最小公倍数 { int t = gcd(a,b); //获取最大公约数 return (a*b)/t; //返回最小公倍数 }
int main(void) { int a,b; printf("输入两个整数(用空格分隔):"); scanf("%d%d",&a,&b); printf("最大公约数:%d\n",gcd(a,b)); printf("最小公倍数:%d\n",lcm(a,b)); getch(); return 0; } |