内容发布更新时间 : 2024/12/23 12:47:58星期一 下面是文章的全部内容请认真阅读。
你知道韩信至少有多少兵?
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)?后继
续用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 基于素数代数和的最大最小 定义和： 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); if(s>smax){smax=s;k1=k;} // 比较求最大值smax if(s } printf(\ printf(\当k=%d时s有最大值: %ld\\n\printf(\当k=%d时s有最小值: %ld\\n\} 2-5 特定数字组成的平方数 用数字2,3,5,6,7,8,9可组成多少个没有重复数字的7位平方数？ 解：求出最小7位数的平方根b, 最大7位数的平方根c. 用a枚举[b，c]中的所有整数，计算d=a*a，这样确保所求平方数在d中。 设置f数组统计d中各个数字的个数。如果f[3]=2，即平方数d中有2个“3”。 检测若f[k]>1(k=0——9)，说明d中存在有重复数字，返回。 在不存在重复数字的情形下，检测若f[0]+f[1]+f[4]=0，说明7位平方数d中没有数字“0”,“1”,“4”,d满足题意要求，打印输出。 // 组成没有重复数字的7位平方数 #include {int k,m,n,t,f[10]; long a,b,c,d,w; n=0; b=sqrt(2356789);c=sqrt(9876532); for(a=b;a<=c;a++) {d=a*a; w=d; // 确保d为平方数 for(k=0;k<=9;k++) f[k]=0; while(w>0) { m=w;f[m]++;w=w/10;} for(t=0,k=1;k<=9;k++) if(f[k]>1) t=1; // 测试三个平方数是否有重复数字 if(t==0 && f[0]+f[1]+f[4]==0) // 测试平方数中没有数字0,1,4 {n++; printf(\ printf(\ } } printf(\共可组成%d个没有重复数字的7位平方数.\\n\} 2-6 写出例2-2中对称方阵的完整程序，并运行程序。 对称方阵程序： #include {int i,j,n,a[30][30]; printf(\请确定方阵阶数n: \ scanf(\ for(i=1;i<=n;i++) for(j=1;j<=n;j++) {if(i+j<=n+1 && i<=j) a[i][j]=(n+1)/2-i+1; // 方阵上部元素赋值 if(i+j a[i][j]=(n+1)/2-j+1; // 方阵左部元素赋值 if(i+j>=n+1 && i>=j) a[i][j]=i-n/2; // 方阵下部元素赋值 if(i+j>n+1 && i a[i][j]=j-n/2; // 方阵右部元素赋值 } printf(\阶对称方阵为:\\n\ for(i=1;i<=n;i++) { for(j=1;j<=n;j++) // 输出对称方阵 printf(\ printf(\ } } 2-7 四则运算式 把数字1,2,...,9这9个数字填入以下含加减乘除的综合运算式中的9个□中,?使得该式成立 □□×□+□□□÷□-□□=0 要求数字1,2,...,9这9个数字在各式中都出现一次且只出现一次，且约定数字“1”不出现在数式的一位数中（即排除各式中的各个1位数为1这一平凡情形）。 （1） 求解要点 设式右的5个整数从左至右分别为a,b,c,d,e,其中a,e为二位整数，b,d为大于1的一位整数，c为三位整数。设置a,b,c,d循环，对每一组a,b,c,d,计算e=a*b+c/d。若其中的c/d非整数，或所得e非二位数，则返回。