WORD格式可编辑
习题2
2-1 解不等式
设n为正整数，解不等式
2010?1?111?????2011 1?1/21?1/2?1/31?1/2???1/n解：上下限一般为键盘输入的a,b。
// 解不等式: a<1+1/(1+1/2)+...+1/(1+1/2+...+1/n) #include
{ long a,b,c,d,i; double ts,s;
printf(\请输入a,b: \ scanf(\ i=0;ts=0;s=0; while(s ts=ts+(double)1/i; s=s+1/ts; } c=i; while(s ts=ts+(double)1/i; s=s+1/ts; } d=i-1; printf(\满足不等式的正整数n为: %ld≤n≤%ld \\n\} 2-2 韩信点兵 韩信在点兵的时候，为了知道有多少个兵，同时又能保住军事机密，便让士兵排队报数。 按从1至5报数,记下最末一个士兵报的数为1； 再按从1至6报数,记下最末一个士兵报的数为5； 再按1至7报数,记下最末一个报的数为4； 最后按1至11报数,最末一个士兵报的数为10。 专业知识分享 WORD格式可编辑 你知道韩信至少有多少兵? 1. 求解要点 设兵数为x，则x满足下述的同余方程组: x=5y+1 即 x=1 (mod 5) x=6z+5 x=5 (mod 6) x=7u+4 x=4 (mod 7) x=11v+10 x=10 (mod 11) 其中y,z,u,v都为正整数。试求满足以上方程组的最小正整数x。 应用枚举可得到至少的兵数。x从1开始递增1取值枚举当然可以，但不必要。事实上枚举次数可联系问题的具体实际大大缩减。 （1) 注意到x除11余10，于是可设置x从21开始，以步长11递增。此时，只要判别前三个条件即可。 （2) 由以上第2，4两方程知x+1为11的倍数，也为6的倍数。而11与6互素，因而x+1必为66的倍数。于是取x=65开始，以步长66递增。此时,只要判别x%5=1与x%7=4 两个条件即可。 这样可算得满足条件的最小整数x即点兵的数量。 2. 程序实现 // 韩信点兵 #include if(x%5==1 && x%7==4) { printf(\至少有兵: %ld 个。\ break; } } } 2-3 分解质因数 对给定区间[m,n]的正整数分解质因数,?每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。 例如, 2012=2*2*503, 2011=(素数!)。 解：对区间中的每一个整数i(b=i)，用k(2——sqrt(i))试商： 若不能整除，说明该数k不是b的因数，k增1后继续试商。 若能整除，说明该数k是b的因数，打印输出\；b除以k的商赋给b(b=b/k)?后继 专业知识分享 WORD格式可编辑 续用k试商(注意，可能有多个k因数)，直至不能整除，k增1后继续试商。 按上述从小至大试商确定的因数显然为质因数。 如果有大于sqrt(n)的因数(至多一个!)?,在试商循环结束后要注意补上，不要遗失。 如果整个试商后b的值没有任何缩减，仍为原待分解数n，说明n是素数，作素数说明标记。 若k是b的因数，按格式输出，然后b=b/k后继续试商k。 若k不是b的因数，则k增1后继续。 若上述试商完成后1 // 质因数分解乘积形式 #include\#include {long int b,i,k,m,n,w=0; printf(\中整数分解质因数（乘积形式）.\\n\printf(\请输入m,n:\scanf(\ for(i=m;i<=n;i++) // i为待分解的整数 { printf(\ b=i;k=2; while(k<=sqrt(i)) // k为试商因数 {if(b%k==0) {b=b/k; if(b>1) {printf(\ continue; // k为质因数,返回再试 } if(b==1) printf(\} k++; } if(b>1 && b printf(\输出大于i平方根的因数 if(b==i) {printf(\素数!)\\n\表示i无质因数 } } 2-4 基于素数代数和的最大最小 专业知识分享 WORD格式可编辑 定义和： s(n)?1?3?3?5?5?7?7?9???(2n?1)?(2n?1) (和式中第k项±(2k-1)*(2k+1)的符号识别：当(2k-1)与(2k+1)中至少有一个素数，取“+”；其余取“-”。例如和式中第13项取“-”，即为-25*27。) 1) 求s(2011)。 2) 设1<=n<=2011，当n为多大时，s(n)最大。 3) 设1<=n<=2011，当n为多大时，s(n)最小。 解：代数和式中各项的符号并不是简单的正负相间，而是随着构成素数而改变。因而在求和之前应用“试商判别法”对第k个奇数2k-1是否为素数进行标注： 若2k-1为素数，标注a[k]=1； 否则，若2k-1不是素数，a[k]=0。 设置k循环（1——n），循环中分别情况求和： 若a[k]+a[k+1]>=1，即(2k-1)与(2k+1)中至少有一个素数，实施“+”； 否则，若a[k]+a[k+1]==0，即(2k-1)与(2k+1)中没有素数，实施“-”。 同时，设置最大值变量smax，最小值变量smin。 在循环中，每计算一个和值s，与smax比较确定最大值，同时记录此时的项数k1；与smin比较确定最小值，同时记录此时的项数k2。 // 基于素数的整数和 #include { int t,j,n,k,k1,k2,a[3000]; long s,smax,smin; printf(\请输入整数n: \ scanf(\ for(k=1;k<=n+1;k++) a[k]=0; for(k=2;k<=n+1;k++) {for(t=0,j=3;j<=sqrt(2*k-1);j+=2) if((2*k-1)%j==0) {t=1;break;} if(t==0) a[k]=1; // 标记第k个奇数2k-1为素数 } s=3;smax=0;smin=s; for(k=2;k<=n;k++) {if(a[k]+a[k+1]>=1) s+=(2*k-1)*(2*k+1); // 实施代数和 else s-=(2*k-1)*(2*k+1);