程序设计实训题4.doc

基础实训215. 分解质因数整数分解质因数是最基本的分解。例如，90=2*3*3*5, 1960=23*5*72，前者为质因数乘积形式，后者为质因数的指数形式。把指定区间上的所有整数分解质因数,每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。例如, 92=2*2*23, 91(素数!)。分解：1671861 5845271 （1） 设计要点对每一个被分解的整数i，赋值给b(以保持判别运算过程中i不变)，用k(从2开始递增取值)试商:若不能整除，说明该数k不是b的因数，k增1后继续试商。若能整除，说明该数k是b的因数，打印输出k*；b除以k的商赋给b(b=b/k)后继续用k试商(注意，可能有多个k因数)，直至不能整除，k增1后继续试商。按上述从小至大试商确定的因数显然为质因数。循环取值k的终值如何确定，一定程度上决定了程序的效率。终值定为i-1或i/2，无效循环太多。循环终值定为i的平方根sqrt(i)可大大精简试商次数，此时如果有大于sqrt(i)的因数(至多一个!),在试商循环结束后要注意补上，不要遗失。如果整个试商后b的值没有任何缩减，仍为原待分解数i，说明i是素数，作素数说明标记。（2） 质因数分解乘积形式程序设计/ 质因数分解乘积形式#includemath.h#include void main()long int b,i,k,m,n,w=0;printf(m,n中整数分解质因数（乘积形式）.n);printf(请输入m,n:);scanf(%ld,%ld,&m,&n);for(i=m;i=n;i+) / i为待分解的整数 printf(%ld=,i); b=i;k=2; while(k1) printf(%ld*,k);continue; / k为质因数,返回再试 if(b=1) printf(%ldn,k); k+; if(b1 & bi) printf(%ldn,b); / 输出大于i平方根的因数 if(b=i) printf(素数!)n);w+; / b=i,表示i无质因数 printf(其中共%d个素数.n,w);1671861=3*31*17977 5845271=233*250876. 构建横竖折对称方阵试观察图所示的横竖折对称方阵的构造特点，总结归纳其构造规律，设计并输出n（奇数）阶对称方阵。图 7阶横竖对称方阵输出15阶、19阶横竖折对称方阵。解: 这是一道培养与锻炼观察能力、归纳能力与设计能力的有趣案例。设置2维数组ann存储n阶方阵的元素，数组ann就是数据结构。本案例求解算法主要是给a数组赋值与输出。一个一个元素赋值显然行不通，必须根据方阵的构造特点，归纳其构建规律，分区域给各元素赋值。（1） 构造规律与赋值要点观察横竖折对称方阵的构造特点，方阵横向与纵向正中有一对称轴。两对称轴所分4个小矩形区域表现为同数字横竖折递减，至4顶角元素为1。设阶数n（奇数）从键盘输入，对称轴为m=(n+1)/2。设置2维a数组存储方阵中元素，行号为i，列号为j，aij为第i行第j列元素。可知主对角线（从左上至右下）有：i=j；次对角线（从右上至左下）有：i+j=n+1。按两条对角线把方阵分成上部、左部、右部与下部4个区,如图所示。图 对角线分成的4个区对角线上元素可归纳到上、下部，即上、下部区域带等号即可。上、下部按列号j的函数abs(m-j)赋值： if(i+j=n+1 & i=n+1 & i=j) aij=abs(m-j);左、右部按行号i的函数abs(m-i)赋值： if(i+jj | i+jn+1 & ij) aij=abs(m-i);输出时,按aij打印。（2）程序设计/ 横竖折对称方阵#include #include void main()int i,j,m,n,a3030; / 定义数据结构 printf( 请确定方阵阶数(奇数)n: ); scanf(%d,&n); if(n%2=0) printf( 请输入奇数！);return; m=(n+1)/2; for(i=1;i=n;i+) for(j=1;j=n;j+) if(i+j=n+1 & i=n+1 & i=j) aij=abs(m-j); / 方阵上、下部元素赋值 if(i+jj | i+jn+1 & ij) aij=abs(m-i); / 方阵左、右部元素赋值 printf( %d阶对称方阵为:n,n); for(i=1;i=n;i+) for(j=1;j=n;j+) / 输出对称方阵 printf(%3d,aij); printf(n); 7. n个1 整除一个整数为n个1，它能被指定正整数p(约定为个位数字非5的奇数)整除，问n至少为多大？输入p，输出n。p=57, n= p=2011, n= 设计1： 模拟竖式除法/ n个1 被p 整除 #includevoid main() int a,b,c,n,p;printf( 请输入整数p: ); scanf(%d,&p);n=4; c=1111; / 确定初始值 while(c!=0) a=c*10+1; b=a/p; printf(%d,b); c=a%p; n+; / 实施除乘竖式计算模拟 printf(n 至少%d个1才能初被%d整除.n,n,p);设计2： 余数统计法/ n个1 被2011 整除 #includevoid main() int c,n,s,p;printf( 请输入整数p: ); scanf(%d,&p);n=1; c=1; s=1; / 确定初始值 while(s!=0) n+; c=c*10%p; / c为第n位除以p的余数 s=(s+c)%p; / 统计n个1险乎以p的余数 printf( 至少%d个1才能初被%d整除.n,n,p);请输入整数p: 57 至少18个1才能初被57整除. 请输入整数p: 2011 至少670个1才能初被2011整除.8. 基于素数的代数和定义s(n)=1*3-3*5-5*7+7*9+9*11-25*27(2n-1)*(2n+1)(一般项(2k-1)*(2k+1)的符号识别：当(2k-1)与(2k+1)中有且只有一个素数，取“+”；其余取“-”。)1) 求s(1000)。2) 设1=n=1000，当n为多大时，s(n)最大。3) 设1=n=1000，当n为多大时，s(n)最小。（1） C程序设计/ 基于素数的整数和 #include#includevoid main() int t,j,n,k,k1,k2,a3000; long s,smax,smin; printf( 请输入整数n: ); scanf(%d,&n); for(k=1;k=n+1;k+) ak=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) ak=1; / 标记第k个奇数2k-1为素数 s=0;smax=0;smin=10000; for(k=1;ksmax)smax=s;k1=k; / 比较求最大值smax if(ssmin)smin=s;k2=k; / 比较求最大值smin printf(s(%d)=%ld n,n,s);printf(当k=%d时s有最大值: %ldn,k1,smax);printf(当k=%d时s有最小值: %ldn,k2,smin);（2） 运行结果 请输入整数n: 300s(300)=1142382当k=255时s有最大值: 2986031当k=174时s有最小值: -174700请输入整数n: 1000s(1000)=-161348876当k=387时s有最大值: 7076531当k=985时s有最小值: -1810704119. 三组平方把1，2，.，9这9个数字分成三个组，每组至少一个数字，使得这三个组中的所有数字分别能排列成平方数a，b，c（abc）。设计程序，求出满足要求的所有分法（若某一分法中某组的数字能排列成不同的平方数，例如1369=372，1936=442，这只算一种分法）。（1）设计要点。a=a1*a1，a1在1sqrt(798)中循环取值。b=b1*b1，因ab，则c1在b1+1sqrt(9876543)中循环取值，因c可能达7位数。这样设置三重循环，确保a，b，c都是平方数。设置d数组，d(1)=a，d(2)=b，d(3)=c。分离三平方数的各个数字分别存储到f数组：f(k)为数字k的个数，k=1,2,9。检验f(k)是否都为1：只要有一个不为1，说明有重复数字可缺少某数字，不满足题意，标记m=1；若f(k)都为1，说明没有重复数字，保持原有m=0。对m=0且f(0)=0（即没有数字0）时，排除重复打印，输出三组平方解。所谓重复打印，存在有3个或3个以上不同数字可组成不同的平方数，如256=162，625=252等。为了避免重复打印，在打印输出的条件中增加了条件： （x!=d1 | y!=d2) & (x!=d1 | z!=d3)即前两个平方至少有一个不同，且第一个与第三个平方数中也至少有一个不同。（2）一般的三组数字平方程序设计。/ 一般的三组数字平方 #include #include void main() int k,m,n,f10; long a1,b1,c1,x,y,z,w,d4; printf( 三组平方的所有分法为:n); n=0; x=0;y=0;z=0; for(a1=1;a1=sqrt(798);a1+) for(b1=a1+1;b1=sqrt(8976);b1+) for(c1=b1+1;c1=sqrt(9876543);c1+) d1=a1*a1; / 确保均为平方数 d2=b1*b1; d3=c1*c1; for(k=0;k=9;k+) fk=0; for(k=1;k0) m=w%10; fm+; w=w/10; for(m=0,k=1;k=9;k+) if(fk!=1) m=1; / 测试三个平方数是否有重复数字 if(m=0 & f0=0 & (x!=d1|y!=d2)&(x!=d1|z!=d3) n+; printf( %2d: ,n); printf( %ld=(%ld2),d1,a1); printf( %ld=(%ld2),d2,b1); printf( %ld=(%ld2) n ,d3,c1); x=d1;y=d2;z=d3; printf( n 共 %d 种分法.,n);（3）程序运行结果与讨论。 三组平方的所有分法为： 1 : 1 ( 1 2) 4 ( 2 2) 3297856 (1816 2) 2 : 1 ( 1 2) 49 ( 7 2) 872356 ( 934 2) 3 : 1 ( 1 2) 64 ( 8 2) 537289 ( 733 2) 4 : 1 ( 1 2) 256 (16 2) 73984 ( 272 2) 5 : 4 ( 2 2) 16 ( 4 2) 537289 ( 733 2) 6 : 4 ( 2 2) 25 ( 5 2) 139876 ( 374 2) 7 : 4 ( 2 2) 289 (17 2) 15376 ( 124 2) 8 : 9 ( 3 2) 324 (18 2) 15876 ( 126 2) 9 : 16 ( 4 2) 25 ( 5 2) 73984 ( 272 2) 10 : 16 ( 4 2) 784 (28 2) 5329 ( 73 2) 11 : 25 ( 5 2) 784 (28 2) 1369 ( 37 2) 12 : 25 ( 5 2) 841 (29 2) 7396 ( 86 2) 13 : 36 ( 6 2) 81 ( 9 2) 74529 ( 273 2) 14 : 36 ( 6 2) 729 (27 2) 5184 ( 72 2) 15 : 81 ( 9 2) 324 (18 2) 7569 ( 87 2) 16 : 81 ( 9 2) 576 (24 2) 3249 ( 57 2) 17 : 81 ( 9 2) 729 (27 2) 4356 ( 66 2) 18 : 361 (19 2) 529 (23 2) 784 ( 28 2) 共18种分法.显然，最后一组解即为三组三位平方的解。10. 统计试统计含有数字7且不能被7整除的m位整数的个数s1，并指出这s1个数中不含有数字4的整数的个数s2。 输入m, 输出s1,s2。m=5, 输出： m=6, 输出： 11. 构建斜折对称方阵试观察图所示的斜折对称方阵的构造特点，总结归纳其构造规律，设计并输出n（