《计算机常用算法与程序设计案例教程》习题解答 下载本文

你知道韩信至少有多少兵?

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 void main() { long int x; x=65; while(1) { x=x+66;

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 void main()

{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 #include void main()

{ 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 #include void main()

{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 void main()

{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+jj)

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非二位数,则返回。