XXXX程序设计竞赛选拔赛(实训8)

编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第10页 共10页2011程序设计竞赛选拔赛(实训8)1、 排列数由1个“1”,2个“2”,k个“3” (1k6)能组成多少个不同的排列？ 输入k, 输出排列个数。k=4, 输出： k=5, 输出： (1) 设计要点注意到1个“1”,2个“2”,k个“3”组成k+3位数，首先通过k+2个10相乘计算k+3位数的起点b=10(k+2),为枚举提供范围t(b4*b-1)。为了检测k+3位数t含有多少个数字1、2、3，每个k+3位整数t赋给d(以保持t不变),然后通过k+3次求余先后分离出t的k+3个数字c：if(c=1) f+, 统计整数t中数字1的个数f；if(c=2) g+, 统计整数t中数字2的个数g；if(c=3) h+, 统计整数t中数字3的个数h。检测每一个k+3位整数：若f=1 and g=2 and h=k，则应用s进行统计。最后输出所得排列个数s。（2） 程序设计/ 排列数#include void main() int c,f,g,h,i,j,k; long b,d,s,t; printf( 请输入数字3的个数k (1k6): ); scanf(%d,&k); b=1; s=0; for(i=1;i=k+2;i+) b=b*10; / 计算k+3位数的起点 for(t=b;t=4*b-1;t+) / 枚举首位为3的k+3位数 d=t;f=0;g=0;h=0; for(j=1;j=k+3;j+) c=d%10; d=d/10;if(c=1) f+; / 统计数字1的个数if(c=2) g+; / 统计数字2的个数if(c=3) h+; / 统计数字3的个数 if(f=1 & g=2 & h=k) s+; / 统计个数s printf( s=%ld n,s); （3） 程序运行示例 请输入数字3的个数k (1k6): 4 s=105 请输入数字3的个数k (1k6): 5 s=168（4） 拓广 若需求k=100时的排列数，如何求？1） 注意到一排k个“3”的空位共k+1个。这k+1个选2个空位共C(k+1,2)种组合，每一空位放置1个“2”。这k+1个选1个空位共C(k+1,1)种组合，空位中放置2个“2”。2） 注意到一排k个“3”与2个“2”的空位共k+3个。这k+3个选1个空位共C(k+3,1)种组合，空位中放置1个“1”。3） 因而得不同的排列数为：(C(k+1,2)+C(k+1,1)*C(k+3,1)=(k+1)*(k+2)*(k+3)/2/ 排列数#include void main() int k;long s; printf( 请输入数字3的个数k: ); scanf(%d,&k); s=(k+1)*(k+2)*(k+3)/2; printf( s=%ld n,s); 请输入数字3的个数k: 100 s=530553(5) 实训1计算由2个“1”、2个“2”、k个“3”的排列数。计算由3个“1”、2个“2”、k个“3”的排列数。测试数据: k=502、 求最值设n为正整数，式中各项符号为二正一负。求当n为多大时，s(n)最接近指定的正整数a？输入a, 输出s(n)最接近a的n,s(n)。（1） 输入1000,输出： （2） 输入2011,输出： 解： 一般地求当n为多大时，s(n)最接近正整数a？其中a从键盘输入a。/ s(n)=1+1/(1+1/2)-1/(1+1/2+1/3)+.+1/(1+1/2+.+1/n)#include #includevoid main() long a,n,n1; double m,ts,s,s1; printf( 请输入a: ); scanf(%d,&a); n=0;ts=0;s=0;m=100000.0; while(sa+10) n=n+1; ts=ts+(double)1/n; / ts为各项的分母if(n%3=0) s=s-1/ts; / 求代数和selse s=s+1/ts; if(fabs(s-a)z。为避免重复,不妨设xyz。在指定区间a,b上根据x,y,z的大小关系设置循环:z从a至b-2,y从z+1至b-1,x从y+1至b。对每一组x,y,z,如果直接应用条件式 1/(x*x)+1/(y*y)=1/(z*z)作判别，因分数计算的不可避免的误差，有可能把一些成立的倒立勾股数组解遗失,即造成遗漏。注意到上述分数条件式作通分整理得到的下面的正整数条件式 z*z*(x*x+y*y)=x*x*y*y程序中为防止发生解的遗漏，应用上述整数条件作判别是适宜的。（2） 求区间内倒立勾股数程序设计/ 求指定区间内倒立勾股数组 #include #include void main()int a,b,n; long x,y,z; printf( 求指定区间a,b内倒立的勾股数组.); printf(n 请输入区间a,b的上下限a,b: ); scanf(%d,%d,&a,&b); printf(n 区间%d,%d中倒立的勾股数组有:n,a,b); n=0; for(z=a;z=b-2;z+) for(y=z+1;y=b-1;y+) for(x=y+1;x=b;x+) if(z*z*(x*x+y*y)=x*x*y*y) / 满足倒立勾股数条件时输出 n+; printf( 1/%ld2+1/%ld2=1/%ld2 n,x,y,z); printf(共%d组勾股数.,n); （3） 程序运行示例区间30,100中倒立的勾股数组有: 1/602+1/452=1/362 1/802+1/602=1/482 1/1002+1/752=1/602共3组勾股数.区间100,200中倒立的勾股数组有: 1/1802+1/1352=1/1082 1/2002+1/1502=1/1202共2组勾股数.4、 双和数组寻求6个互不相等的正整数a,b,c,d,e,f并分成(a,b,c)与(d,e,f)两个组，若这两组数具有以下两个相等特性： 则把数组(a,b,c)与(d,e,f)称为双和数组(约定abc,def,ad）。1） 设a+b+c=d+e+f=s, 存在双和数组, s至少为多大？2） 当s=98时有多少个不同的双和数组?(1) 求解要点从键盘输入整数s，因6个不同正整数之和至少为21，即输入整数s11。设置a,b与d,e循环。注意到a+b+c=s，且aba，因而d起点为a+1。把比较倒数和相等1/a+1/b+1/c1/d+1/e+1/f转化为比较整数相等d*e*f*(b*c+c*a+a*b)=a*b*c*(e*f+f*d+d*e) (*)若上式不成立，即倒数和不相等，则返回。同时注意到两个3元组中若部分相同部分不同，不能有倒数和相等，因而可省略排除以上6个正整数中是否存在相等的检测。若式（*）成立，打印输出和为s的双和数组，并用x统计解的个数。(2) C程序设计/ 双和数组探索 #include#includevoid main()int a,b,c,d,e,f,x,s;for(s=21;s=100;s+)printf( s=%d: n,s); x=0;for(a=1;a=(s-3)/3;a+)for(b=a+1;b=(s-a-1)/2;b+)for(d=a+1;d=(s-3)/3;d+)for(e=d+1;e=(s-d-1)/2;e+)c=s-a-b; f=s-d-e;if(a*b*c*(e*f+f*d+d*e)!=d*e*f*(b*c+c*a+a*b)continue; / 排除倒数和不相等 x+;printf(%3d: (%2d,%2d,%2d) ,x,a,b,c);printf(%2d,%2d,%2d)n,d,e,f);if(x=0) printf( 无解！n); (3) 程序运行结果与讨论s=26:1: ( 4,10,12) ( 5, 6,15) s=98:1: ( 2,36,60) ( 3, 5,90) 2: ( 7,28,63) ( 8,18,72) 3: ( 7,35,56) ( 8,20,70) 4: (10,33,55) (12,20,66) （4） 实训3寻求6个互不相等的正整数a,b,c,d,e,f并分成(a,b,c)与(d,e,f)两个组，若这两组数具有以下两个相等特性： 则把数组(a,b,c)与(d,e,f)称为和积数组(约定abc,def,ad）。1） 设a+b+c=d+e+f=s, 存在和积数组, s至少为多大？2） 当s=89时有多少个不同的和积数组?5、 m位完美平方数用0,1,2,.,9能组成多少个没有重复数字的m(1m10)位平方数? 输入m,输出没有重复数字的m位平方数的个数，并输出其中最大的。m=7, 输出:m=10, 输出:/ 用0,1,2,.,9组成没有重复数字的m位平方数 #include #include void main()int k,m,n,t,f10; double a,b,c,d,w,x,a1,d1;printf( 请确定整数m: ); scanf(%d,&m);x=1.0;for(k=2;k=m;k+) x=x*10; / 确定m位数的起点xn=0;b=(int)pow(x,0.5);c=pow(10*x-1,0.5);for(a=b+1;a=c;a+)d=a*a; w=d; / 确保d为m位平方数 for(k=0;k0) t=(int)fmod(w,10);ft=ft+1;w=floor(w/10); for(t=0,k=0;k1) t=1; break; / 测试平方数是否有重复数字 if(t=0 ) / 测试平方数中没有重复数字 n+;d1=d;a1=a;printf( 共可组成%d个没有重复数字的%d位平方数.,n,m);printf( 其中最大的为：%.0f=%.0f2 n,d1,a1); 请确定整数m: 7共可组成123个没有重复数字的7位平方数. 其中最大的为：9872164=31422请确定整数m: 10共可组成87个没有重复数字的10位平方数. 其中最大的为：9814072356=990662实训4：用0,1,2,.,9能组成没有重复数字的m(1m10)位平方数的个数为s(m). 问： （1） 求s(10)，即求出没有重复数字的10位平方数的个数。（2）当m为多大时，没有重复数字的m位平方数个数s(m)最大？6、 最小01串积程序设计爱好者A，B进行计算游戏：B任给一个正整数b，A寻求另一个整数a, 使a 与b的积最小且全为0与1组成的数。例如，B给出整数24，A寻求整数a：4625，使得a*b的最小01串积为：111000输入b,输出a与最小01串积。b=24, 输出： b=2011, 输出： （1）对a枚举考虑到a与积d可能大于10位,用双精度型。对a递增枚举，检测积d=a*b是否为01串/ 01串积对a枚举 #include #include void main() long c,t;double a,b,d,j; printf( B给出整数b: ); scanf(%lf,&b); a=1; while(1) a+;d=a*b; j=d;t=0; while(j0) / 分离积的各个数字c c=(int)fmod(j,10); j=floor(j/10); if(c1) t=1;break; / 检测是否含有0,1以外的数字 if(t=0) printf( A寻求整数a: %.0f：n,a); printf( a*b的最小01串积为: %.0fn,d); break; B给出整数b: 73 A寻求整数a: 137： a*b的最小01串积为: 10001B给出整数b: 54 A寻求整数a: 203909465： a*b的最小01串积为: 11011111110（2） 二进制枚举，应用余数判别。1） 注意到01串积为十进制数，应用求余运算“%”可分别求得个位“1”，十位“1”，分别除以已给b的余数，存放在c数组中：c(1)为1,c(2)为10除以b的余数,c(3)为100除以b的余数，。2） 要从小到大搜索01串，不重复也不遗漏，从中找出最小的能被b整除01串积。为此，设置k从1开始递增，把k转化为二进制，就得到所需要的这些串。不过，这时每个串不再看作二进制数，而要看作十进制数。3） 在某一k转化为二进制数过程中，每转化一位a(i)(0或1)，求出该位除以b的余数a(i)*c(i)，通过累加求和得k转化的整个二进制数除以b的余数s。4） 判别余数s 是否被b整除：若s%b=0, 即找到所求最小的01串积。a 从高位开始除以b的商存储在d数组，实施整数除法运算：x=e*10+aj; / e为上轮余数，x为被除数 dj=x/b; / d为a 从高位开始除以b的商 e=x%b; / e为试商余数 去掉d数组的高位“0”后，输出d即为所寻求的数。最后从高位开始打印a数组，即为01串积。（3） 程序设计/ 01串积二进制枚举 #includevoid main() int b,e,i,j,t,x,a2000,d2000,c2000; long k,s; printf( B给出整数b: ); scanf(%d,&b); c1=1; for(i=2;i0) i+;ai=j%2;s+=ai*ci;j=j/2; s=s%b; / 除2取余法转化为二进制 if(s%b=0) for(e=0,j=i;j=1;j-) x=e*10+aj; dj=x/b; e=x%b; / a 从高位开始除以b的商为d j=i; while(dj=0) j-; / 去掉d数组的高位0 printf( A寻求整数a：); for(t=j;t=1;t-) printf(%d,dt); printf(n a*b的最小01串积为：); for(t=i;t=1;t-) printf(%d,at); printf(n);break; （4） 程序运行示例B给出整数b: 54， A寻求整数a：203909465 a*b的最小01串积为：11011111110B给出整数b: 2011， A寻求整数a：4977628101 a*b的最小01串积为：10010010111111（5） 实训51）任给一个正整数b，寻求另一个整数a, 使a 与b的积最小且全为0与5组成的数。2）任给一个正整数b，寻求另一个整数a, 使a 与b的积最小且全为2与5组成的数。3）任给一个正整数b，寻求另一个整数a, 使a 与b的积最小且全为0、1、2组成的数。测试数据: b=54; b=2011第 10 页 共 10 页