数学与程序设计.ppt
数学 与与程序设计数学 与与程序设计* Welcome To The Programmer World *System Starting.#SUCCESS#UserGuest#UserGuest#cd Catalog- - 1、引 入 2、约 数- - 3、同 余 4、素 数- - 5、数 列 6、组 合- - 7、概 率 8、几 何- -#Please Select-$ 引 入 $-问题概述：一百个铜钱买了一百只鸡，其中公鸡一只5钱、母鸡一只3钱，小鸡一钱3只，问一百只鸡中公鸡、母鸡、小鸡各多少）。这是一个古典数学问题，设一百只鸡中公鸡、母鸡、小鸡分别为x，y，z，问题化为三元一次方程组：这里x,y,z为正整数，且z是3的倍数；由于鸡和钱的总数都是100，可以确定x,y,z的取值范围：1) x的取值范围为1202) y的取值范围为1333) z的取值范围为399，步长为3对于这个问题我们可以用穷举的方法，遍历x,y,z的所有可能组合，最后得到问题的解。UserGuest引入百钱白鸡#-#includeint main()int x,y,z,ca=1;for(x=1;x=20;x+)for(y=1;y=33;y+)for(z=3;zEND-$ 约 数 $-问题概述：一个房间里有N盏灯，门外有N个人，他们的编号都是1N，一开始所有的灯都是关着的，现在每个人过去，把编号是自己编号倍数的开关都按一下，问所有人按完以后那些灯是亮着的？其中N-#include#define N 1005int vN;int main()int i,j,n;while(scanf(%d,&n)for(i=1;i=n;i+)vi=0;for(i=1;i=n;i+)for(j=i;j=n;j+=i)if(vj=1) vj=0;else vj=1;for(i=1;iEND-$ 约 数 $-如果N-#includeint main()int i,n;while(scanf(%d,&n)for(i=1;i*iEND-$ 约 数 $-比较两个算法，那个更优？表现在那里？（1）代码的长度短了；（2）空间复杂度小了；（3）时间复杂度大大减少；-$ 同 余 $-数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即m|(a-b)，那么就称整数a与b对模m同余，记作ab(mod m)。对模m同余是整数的一个等价关系。问题概述：给定一个数N（0N-#include#includechar a1005;int main()int i,k,s;while(scanf(%s,a)k=strlen(a);for(i=0,s=0;iEND-$ 素 数 $-问题概述：给定一个大于等于6的偶数n（n-#includeint ju(int x)int i;for(i=2;i*i=x;i+)if(x%i=0) return 0;return 1;int main()int i,n;while(scanf(%d,&n)for(i=3;iEND-$ 素 数 $-用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。如有：1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 301不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是：3 5 7 9 11 13 15 17 19 21 23 25 27 29剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为：2 3 5 7 11 13 17 19 23 29UserGuest筛法求素数#-#include#define N 100005int vN,aN;int main()int i,j;for(i=2;iN;i+) vi=1;for(i=2;i*iN;i+)if(vi) for(j=i+i;jN;j+=i) vj=0;for(i=2,j=0;iN;i+)if(vi) aj+=i;for(i=0;iEND-$ 数 列 $-问题概述：有一对兔子，从出生后第三个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假设所有兔子都不死，问地K(k-#includeint a45;int main()int i,k;a1=a2=1;for(i=3;iEND-$ 组 合 $-利用数学归纳法：由C(n,k) = C(n-1,k) + C(n-1,k-1）；对应于杨辉三角：11 11 2 11 3 3 11 4 6 4 1问题概述：给定一个整数N，用式子a1+a2+am=N表示，可以表示成多少种形式，其中N、m-#include_int64 C5555;void init()int i,j;for(i=0;i55;i+)for(j=0;jEND-$ 概 率 $-问题概述：班级举行活动，要求n个同学每人准备一份礼物，然后由你随机的将这些礼物分还给每一位同学，问你每个同学拿到的都不是自己的礼物的概率是多少？首先求概率往往要用到排列组合的知识，我们只要知道所有的方案有多少种，符合要求的多少种，除一下就是概率了。总方案数简单，为n！。符合要求的情况怎么计算？可以利用递推的思想来解决，设n个人都拿错的方案数为an，那么他可以看成是由两种情况转变而来，第一、原来n-1个人已经错排，那么在n-1中选择一对，和现在的对调就是错排了，方案有(n-1)*an-1，第二、原来n-1对中有一对是对的，其他都是错的，那么只要这一对和现在加进来的这一对对调九可以了，方案数为(n-1)*an-2。最后得到递推关系an=(n-1)*(an-1+an-2)。UserGuest错排概率#-#includeint main() int i,n; _int64 a21=1,1,2,b21=0,0,1; for(i=3;iEND-$ 几 何 $-问题概述：在一度钱的边上有一个木桩，木桩上拴着一条狗，已知木桩离墙的距离是a(0a=100)，拴着狗的绳子长b(0b-#include#include#define pi acos(-1.0)int main()double a,b,c,s,ss;while(scanf(%lf%lf,&a,&b)s=b*b*pi;if(aEND* T h a n k s F o r Y o u r C o m i n g *System Shut Down.#ByeBye
