2021年程序设计竞赛选拔赛实训.doc

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

1、排列数
由1个“1”,2个“2”,k个“3” (1≤k≤6)能构成多少个不同排列？
输入k，输出排列个数。
k=4， 输出：
k=5， 输出：

(1) 设计要点
注意到1个“1”,2个“2”,k个“3”构成k+3位数，一方面通过k+2个10相乘计算k+3位数起点b=10^(k+2),为枚举提供范畴t(b—4*b-1)。
为了检测k+3位数t具有多少个数字1、2、3，每个k+3位整数t赋给d(以保持t不变),然后通过k+3次求余先后分离出tk+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 <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;t++) // 枚举首位为3k+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 (1≤k≤6)：4
s=105
请输入数字3个数k (1≤k≤6)：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 <stdio.h>
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=50
2、求最值
设n为正整数，，式中各项符号为二正一负。求当n为多大时，s(n)最接近指定正整数a？
输入a，输出s(n)最接近an,s(n)。

（1） 输入1000,输出：

（2） 输入,输出：

解： 普通地求当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);
n=0;ts=0;s=0;m=100000.0;
while(s<a+10)
{ n=n+1;
ts=ts+(double)1/n； // ts为各项分母
if(n%3==0)
s=s-1/ts； // 求代数和s
else
s=s+1/ts;
if(fabs(s-a)<m) // 比较，当n=n1时，和s1最接近a
{m=fabs(s-a);n1=n;s1=s;}
}
printf(" n=%ld,s(%d)=%f \n",n1,n1,s1);
}

请输入a：1000
n=29126,s(29126)=999.959989
请输入a：
n=63376,s(63376)=.040087

实训2：设n为正整数，，式中各项符号为二正一负，分母符号一正一负。求当n为多大时，s(n)最接近指定正整数a？
输入a，输出s(n)最接近an,s(n)。
测试数据：a=

3、倒立勾股数
把求勾股数变通为求倒立勾股数。定义满足方程式

正整数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大小关系设立循环: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 <stdio.h>
#include <math.h>
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/%ld^2+1/%ld^2=1/%ld^2 \n",x,y,z);
}
printf("共%d组勾股数.",n);
}
（3） 程序运营示例
区间[30,100]中倒立勾股数组有:
1/60^2+1/45^2=1/36^2
1/80^2+1/60^2=1/48^2
1/100^2+1/75^2=1/60^2
共3组勾股数.
区间[100,200]中倒立勾股数组有:
1/180^2+1/135^2=1/108^2
1/200^2+1/150^2=1/120^2
共2组勾股数.
4、双和数组
谋求6个互不相等正整数a,b,c,d,e,f并提成(a,b,c)与(d,e,f)两个组，若这两组数具备如下两个相等特性：

则把数组(a,b,c)与(d,e,f)称为双和数组(商定a<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+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",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)称为和积数组(商定a<b<c,d<e<f,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,f[10]；
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位数起点x
n=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++) f[k]=0;
while(w>0)
{ t=(int)fmod(w,10);f[t]=f[t]+1;w=floor(w/10);}
for(t=0,k=0;k<=9;k++)
if(f[k]>1) {t=1；break;} // 测试平方数与否有重复数字
if(t==0 ) // 测试平方数中没有重复数字
{n++;d1=d;a1=a;}
}
printf(" 共可构成%d个没有重复数字%d位平方数.",n,m);
printf(" 其中最大为：%.0f=%.0f^2 \n",d1,a1)；
}

请拟定整数m：7
共可构成123个没有重复数字7位平方数. 其中最大为：9872164=3142^2
请拟定整数m：10
共可构成87个没有重复数字10位平方数. 其中最大为：=99066^2

实训4：
用0,1,2,...,9能构成没有重复数字m(1<m≤10)位平方数个数为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=，输出：

（1）对a枚举
考虑到a与积d也许不不大于10位,用双精度型。
对a递增枚举，检测积d=a*b与否为01串
// 01串积对a枚举
#include <math.h>
#include <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最小01串积为：%.0f\n",d);
break;
}
}
}
B给出整数b：73
A谋求整数a：137：
a*b最小01串积为：10001

B给出整数b：54
A谋求整数a：：
a*b最小01串积为：

（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+a[j]； // e为上轮余数，x为被除数
d[j]=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,a[],d[],c[];
long k,s;
printf(" B给出整数b：")；scanf("%d",&b);
c[1]=1;
for(i=2;i<200;i++)
c[i]=10*c[i-1]%b； // c(i)为右边第i位1除以b余数
k=1;
while(1)
{k++;j=k;i=0;s=0;
while(j>0)
{i++;a[i]=j%2;
s+=a[i]*c[i];j=j/2；s=s%b；// 除2取余法转化为二进制
}
if(s%b==0)
{for(e=0,j=i;j>=1;j--)
{x=e*10+a[j];
d[j]=x/b；e=x%b； // a 从高位开始除以b商为d
}
j=i;
while(d[j]==0) j--； // 去掉d数组高位"0"
printf(" A谋求整数a：");
for(t=j;t>=1;t--)
printf("%d",d[t])；
printf("\n a*b最小01串积为：");
for(t=i;t>=1;t--)
printf("%d",a[t]);
printf("\n");
break;
}
}
}
（4） 程序运营示例
B给出整数b：54， A谋求整数a：
a*b最小01串积为：

B给出整数b：， A谋求整数a：
a*b最小01串积为：11

（5） 实训5
1）任给一种正整数b，谋求另一种整数a，使a 与b积最小且全为0与5构成数。
2）任给一种正整数b，谋求另一种整数a，使a 与b积最小且全为2与5构成数。
3）任给一种正整数b，谋求另一种整数a，使a 与b积最小且全为0、1、2构成数。
测试数据：b=54； b=