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

1、2011程序设计竞赛选拔赛(实训1、排列数由1个“1”，2个“2”，k个“3”(1WkW6)能组成多少个不同的排列？输入k,输出排列个数。k=4,输出：k=5,输出：(1)设计要点注意到1个“1”，2个“2”，k个“3”组成k+3位数，首先通过k+2个10相乘计算k+3位数的起点b=10A(k+2),为枚举提供范围t(b4*b-1)。为了检测k+3位数t含有多少个数字1、2、3,每个k+3位整数t赋2d(以保持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

2、中数字3的个数h。检测每一个k+3位整数：若f=1andg=2andh=k,则应用s进行统计。最后输出所得排列个数So(2)程序设计/排列数#includevoidmain()intc,f,g,h,i,j,k;longb,d,s,t;printf(请输入数字3的个数k(1wkW6):);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

3、=2)g+;/统计数字2的个数if(c=3)h+;/统计数字3的个数if(f=1&g=2&h=k)s+;/统计个数sprintf(s=%ldn,s);(3)程序运行示例请输入数字3的个数k(14W6):4s=105请输入数字3的个数k(14W6):5s=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个

4、“1”。3)因而得不同的排列数为：(C(k+1,2)+C(k+1,1)*C(k+3,1)=(k+1)*(k+2)*(k+3)/2/排列数#includevoidmain()intk;longs;printf(请输入数字3的个数k:);scanf(%d,&k);s=(k+1)*(k+2)*(k+3)/2;printf(s=%ldn,s);请输入数字3的个数k:100s=530553(5)实训1计算由2个“1”、2个“2”、k个“3”的排列数。计算由3个“1”、2个“2”、k个“3”的排列数。测试数据：k=502、求最值iiis(n)1设n为正整数，11/211/21/311/21/n,式中各项符

5、号为二正一负。求当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#includevoidmain()longa,n,n1;doublem,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/

6、n;/ts为各项的分母if(n%3=0)s=s-1/ts;/求代数和selses=s+1/ts;if(fabs(s-a)m)/比较，当n=n1时，和si最接近am=fabs(s-a);n1=n;s1=s;printf(n=%ld,s(%d尸fn,n1,n1,s1);请输入a:1000n=29126,s(29126)=999.959989请输入a：2011n=63376,s(63376)=2011.040087111式中各项符号为a ?s(n)1-实训I2:设n为正整数，11/211/21/311/21/n正一负，分母符号一正一负。求当n为多大时，s(n)最接近指定的正整数#include输入a

7、,输出s(n)最接近a的n,s(n)。测试数据：a=20113、倒立的勾股数把求勾股数变通为求倒立的勾股数。定义满足方程式 TOC o 1-5 h z 1112xyz的正整数x,y,z,称为一组倒立的勾股数。试求指定区间a,b内的倒立勾股数组。(1)求指定区间30,100内的倒立勾股数组.(2)求指定区间100,200内的倒立勾股数组.(1)设计要点显然倒立勾股数组中x,y不可能相等，且x,yz。为避免重复，不妨设xyz。在指定区间a,b上根据x,y,z的大小关系设置循环：z从a至b-2,y从z+1至b-1,x从y+1至bo对每一组x,y,z,如果直接应用条件式1/(x*x)+1/(y*y)=

8、1/(z*z)作判别，因分数计算的不可避免的误差，有可能把一些成立的倒立勾股数组解遗失，虱口造成遗漏。注意到上述分数条件式作通分整理得到的下面的正整数条件式z*z*(x*x+y*y)=x*x*y*y程序中为防止发生解的遗漏，应用上述整数条件作判别是适宜的。(2)求区间内倒立勾股数程序设计/求指定区间内倒立勾股数组#includevoidmain()inta,b,n;longx,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

9、;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/%ldA2+1/%ldA2=1/%ldA2n,x,y,z);printf(共%d组勾股数.,n);(3)程序运行示例区间30,100中倒立的勾股数组有:1/60A2+1/45A2=1/36A21/80A2+1/60A2=1/48A21/100A2+1/75A2=1/60A2共3组勾股数.区间100,200中倒立的勾股数组有:1/180A2+1/135A2=1/108A21/200A2+1/

10、150A2=1/120A2共2组勾股数4、双和数组寻求6个互不相等的正整数a,b,c,d,e,f并分成(a,b,c)与(d,e,f)两个组，若这两组数具有以下两个相等特性：abcdef111111abcdef则把数组(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,即输入整数s/1。设置a,b与d,e循环。注意到a+b+c=s,且aba,因而d起点为a+1。把比较倒数和相等1/a+1/b+1/c=1/d+1/

11、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#includevoidmain()inta,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)

12、/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

13、,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)两个组，若这两组数具有以下两个相等特性：abcdefabcdef则把数组(a,b,c)与(d,e,f)称为和积数组(约定abc,def,ad)。)设a+b+c=d+e+f=s,存在和积数组,s至少为多大？)当s=89时有多少个不同的和积数组?5、m位完美平方数用0,1,2,9能组成多少个没有重复数字的m(1mW10)位平方数？输入m,输出没有重复数字的m位平方数的个数，并输出其中最大的。m=7,输出:m=10,输出:/用0,1

14、,2,.,9组成没有重复数字的m位平方数#include#includevoidmain()intk,m,n,t,f10;doublea,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;b

15、reak;/测试平方数是否有重复数字if(t=0)/测试平方数中没有重复数字n+;d1=d;a1=a;printf(共可组成%d个没有重复数字的%d位平方数.,n,m);printf(其中最大的为：.0f=%.0fA2n”,d1,a1); TOC o 1-5 h z 请确定整数m:7共可组成123个没有重复数字的7位平方数淇中最大的为：9872164=3142A2请确定整数m:10共可组成87个没有重复数字的10位平方数.其中最大的为：9814072356=99066A2实训4：用0,1,2,9能组成没有重复数字的m(1mW10)位平方数的个数为s(m).问：(1)求s(10)，即求出没有重复

16、数字的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#includevoidmain()longc,t;doublea,b,d,j;printf(B给出整

17、数b:);scanf(%lf,&b);a=1;while(1)a+;d=a*b;j=d;t=0;while(j0)分离积的各个数字cc=(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; TOC o 1-5 h z B给出整数b:73A寻求整数a:137：a*b的最小01串积为:10001B给出整数b:54A寻求整数a:203909465：a*b的最小01串积为:11011111110(2)二进制

18、枚举，应用余数判别。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。)判别余数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)程序