程序设计竞赛选拔赛

1、XXXX程序设计竞赛选拔赛1、排列数由1个“1”，2个“2”，k个“3" (iwkw6)能组成多少个不同的排列？ 输入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

2、+,统计整数t中数字3的个数ho检测每一个k+3位整数：若f=1 and g=2 and h=k,则应用s进行统计。最后输出所得排列个数s。(2)程序设计/排列数#include <stdio.h>void main() int c,f,g,h,i,j,k;long b,d,s,t;printf(" 请输入数字 3 的个数 k (1<k<6): "); 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

3、;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+;/ 统计个数 sprintf(" s=%ld n",s);(3)程序运行示例请输入数字3的个数k (1<k<6): 4s=105请输入数字3的个数k (1<k<6): 5s=168(4)拓广若需求k=100时

4、的排列数，如何求？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 <stdio.h>void main() int k;long s;printf("请输入数字 3 的个数 k:

5、 "); scanf("%d",&k);s=(k+1)*(k+2)*(k+3)/2;printf(" s=%ld n",s);请输入数字3的个数k: 100s=530553(5)实训1运算由2个“1”、2个“2”、k个“3”的排列数。运算由3个“1”、2个“2”、k个“3”的排列数。测试数据：k=502、求最值设n为正整数，Q) 1 _J1_1 ,式中各项符号为二11/21 1/2 1/31 1/21/n正一负。求当n为多大时，s(n)最接近指定的正整数a?输入a,输出s(n)最接近a的n,s(n)。(1) 输入1000输出：(2) 输

6、入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 <stdio.h>#include<math.h>void main() long a,n,n1;double m,ts,s,s1;printf(" 请输入 a: "); scanf("%d",&a);while(s<a+10) n=n+1;ts=ts+(double)1/n;if(n%3=0)s=s-1/ts;e

7、lses=s+1/ts;if(fabs(s-a)<m)n=0;ts=0;s=0;m=100000.0; ts为各项的分母/求代数和s/比较，当n=n1时，和si最接近am=fabs(s-a);n1=n;s1=s;printf(" n=%ld,s(%d)=%f n",n1,n1,s1);请输入a： 1000n=29126,s(29126)=999.959989请输入a: 2011n=63376,s(63376)=2011.040087实训2:设n为正整数，而)i， ii ,式中各项1 1/2 1 1/2 1/31 1/21/n符号为二正一负，分母符号一正一负。求当n为多

8、大时，s(n)最接近指定的正整数a?输入a,输出s(n)最接近a的n,s(n)。测试数据：a=20113、倒立的勾股数把求勾股数变通为求倒立的勾股数。定义满足方程式222x y z的正整数x,y,z,称为一组倒立的勾股数。试求指定区间a,b内的倒立勾股数组。(1)求指定区间30,100内的倒立勾股数组.(2)求指定区间100,200内的倒立勾股数组.(1)设计要点明显，倒立勾股数组中x,y不可能相等，且x,y>z。为幸免重复，不妨设x>y>z。在指定区间a,b上按照x,y,z的大小关系设置循环:zAa b-2,y从z+1至 b-1,x 从 y+1 至 bo对每一组x,y,z,

9、如果直截了当应用条件式1/(x*x)+1/(y*y)=1/(z*z)作判不，因分数运算的不可幸免的误差，有可能把一些成立的倒立勾 股数组解遗失，？即造成遗漏。注意到上述分数条件式作通分整理得到的下面的正整数条件式z*z*(x*x+y*y)=x*x*y*y程序中为防止发生解的遗漏，应用上述整数条件作判不是适宜的。(2)求区间内倒立勾股数程序设计/求指定区间内倒立勾股数组#include <stdio.h>#include <math.h>void main()int a,b,n; long x,y,z;printf("求指定区间a,b内倒立的勾股数组."

10、;)；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/%ldA2+1/%ldA2=1/%ldA2 n",x,y,z);)printf("

11、;共d 组勾股数.",n);)(3)程序运行示例区间30,100中倒立的勾股数组有：1/60八2+1/45八2=1/36八21/80八2+1/60八2=1/48八21/100八2+1/75八2=1/60八2共3组勾股数.区间100,200中倒立的勾股数组有：1/180八2+1/135八2=1/108八21/200A2+1/150A2=1/120A2共2组勾股数.4、双和数组寻求6个互不相等的正整数a,b,c,d,e,f并分成(a,b,c>W(d,e,f)两个组，若 这两组数具有以下两个相等特性：a b c d e f111111则把数组%均(d,e,ff)称为双和数组(约定a&

12、lt;b<c,d<e<f,a<d)。1) 设a+b+c=d+e+f=s,存在双和数组，s至少为多大？2)当s=98时有多少个不同的双和数组？(1)求解要点从键盘输入整数s,因6个不同正整数之和至少为21,即输入整数s>11。设置a,b与d,e循环。注意到a+b+c=s,且a<b<c,因而a,b循环取值为：a: 1 (s-3)/3。因b比a至少大1, c比a至少大2。b: a+1(s-a-1)/2。因 c 比 b 至少大 1。c=s-a=b。设置d,e循环差不多同上，只是d>a,因而d起点为a+1。把比较倒数和相等1/a+1/b+1/c= 1/d+

13、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<stdio.h>#include<math.h>void main()int a,b,c,d,e,f,x,s;for(s=21;s<=100;s+)printf(" s=%d: n&

14、quot;,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)

15、 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>W(d,e,f)两个组，若 这两组数具有以下两个相等特性：a b c d e f a b c def则把数组(a,b,c)与(d,e,f)称为和积数组(约定a<b<c,d<e<f

16、,a<d)。1)设a+b+c=d+e+f=s,存在和积数组，s至少为多大？2)当s=89时有多少个不同的和积数组？5: m位完美平方数用0,1,2，,9能组成多少个没有重复数字的 m(1<m< 10)位平方数？ 输入m,输出没有重复数字的m位平方数的个数，并输出其中最大的。m=7,输出:m=10,输出:用0,1,2，,9组成没有重复数字的m位平方数#include <math.h>#include <stdio.h>void main()int k,m,n,t,f10;double a,b,c,d,w,x,a1,d1;printf("请确定整

17、数 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;k<=9;k+) fk=0; while(w>0) t=(int)fmod(w,10);ft=ft+1;w=floor(w/10); for(t=0,k=0;k<=9;k+)if(fk>1) t=1; break;

18、测试平方数是否有重复数字if(t=0 )/测试平方数中没有重复数字n+;d1=d;a1=a;printf("共可组成%d个没有重复数字的%d位平方数.",n,m);printf("其中最大的为：%.0f=%.0fA2 n",d1,a1);请确定整数m: 7共可组成123个没有重复数字的7位平方数.其中最大的为：9872164二3142/2请确定整数m: 10共可组成87个没有重复数字的10位平方数.其中最大的为：9814072356=99066八2实训4:用0,1,2，,9能组成没有重复数字的 m(1<mw 10)位平方数的个数为s (m).咨询：

19、(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 <math.h>#include &

20、lt;stdio.h>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(j>0)/分离积的各个数字c c=(int)fmod(j,10); j=floor(j/10); if(c>1) t=1;break;检测是否含有0,1以外的数字if(t=0) printf(" A 寻求整数 a: %.0f: n",a);printf(" a*b

21、 的最小 01 串积为:%.0fn",d);break;B给出整数b: 73A寻求整数a: 137:a*b的最小01串积为:10001B给出整数b: 54A 寻求整数 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转化为二进制

22、，就得到所 需要的这些串。只是，这时每个串不再看作二进制数，而要看作十进制数。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串积二进制枚举#include<stdio.h>void main() int b,e,i,j,t,x,a2000,d2000,c2000;long k,s;printf(" B 给出整数 b: &quo