2021年程序设计竞赛基础实训.doc

程序设计竞赛基本实训31
1
8 记录
试记录具有数字7且不能被7整除m位整数个数s1，并指出这s1个数中不具有数字4整数个数s2。
输入m，输出s1,s2。
m=5，输出：
m=6，输出：

(1) 设计要点
一方面通过乘m-1个10计算m位数起点b=10^(m-1),为枚举提供范畴t(b—10*b-1)。
为了检测m位数t具有多少个数字7，每个m位整数t赋给d(以保持t不变),然后通过m次求余先后分离出tm个数字c，if(c==7) f++，记录整数t中数字7个数f。
同步记录数字4个数g。
如果f>0，阐明整数t中具有数字7。如果g=0，阐明整数t中不含数字4。
对每一种m位整数，据f>0 && t%7>0，s1作相应记录。据f>0 && t%7>0 && g==0，s2作相应记录。

（2） 程序设计
// 记录含数字7且不能被7整除m位整数个数s1，其中不含数字4个数s2
#include <stdio.h>
void main()
{ int c,f,g,i,j,m；
long b,d,s1,s2,t；
printf(" 请输入位数m (2<=m<=9)：")； scanf("%d",&m)；
b=1；s1=0;s2=0;
for(i=2;i<=m;i++) b=b*10； // 计算m位数起点
for(t=b;t<=10*b-1;t++) // 枚举每一种m位数
{ d=t;
f=0;g=0;
for(j=1;j<=m;j++)
{ c=d%10；d=d/10;
if(c==7) f++； // 记录数字7个数
if(c==4) g++； // 记录数字4个数
}
if(f>0 && t%7>0) s1++； // 记录含数字7且不能被7整除数个数
if(f>0 && t%7>0 && g==0) s2++；// 记录其中不含数字4个数
}
printf(" s1=%ld ,s2=%ld \n",s1,s2)；
}
（3） 程序运营示例
请输入位数m (2<=k<=9)：5
s1=32152 ,s2=20412

请输入位数m (2<=k<=9)：6
s1=366522 ,s2=208300

变通1：试记录具有数字7且能被7整除没有重复数字m位整数个数s1，并指出其中最大一种数。
为了比较与否存在重复数字，设立f数组，f[3]=2为2个数字“3”。
#include <stdio.h>
void main()
{ int c,e,g,i,j,m,f[10]；
long b,d,s1,t；
printf(" 请输入位数m (2<=m<=9)：")； scanf("%d",&m)；
b=1；s1=0;
for(i=2;i<=m;i++) b=b*10； // 计算m位数起点
for(t=b;t<=10*b-1;t++) // 枚举每一种m位数
{ d=t;
for(j=0;j<=9;j++) f[j]=0； // 数组清零
for(j=1;j<=m;j++)
{ c=d%10；d=d/10;
f[c]++； // 记录数字c个数
}
for(g=0,j=0;j<=9;j++)
if(f[j]>1) g=1； // 存在重复数字标注g=1
if(f[7]>0 && t%7==0 && g==0)
{s1++；e=t;} // 记录个数,并把满足条件数赋值给e
}
printf(" s1=%ld ,e=%d \n",s1,e)；
}
请输入位数m (2<=m<=9)：5
s1=1978 ,e=98763
请输入位数m (2<=m<=9)：6
s1=11704 ,e=987651

变通2：试记录恰含一种数字7与2个数字4且能被7整除m（m>3）位整数个数s1，并指出其中从小到大排序第n个数。

#include <stdio.h>
void main()
{ int c,e,i,j,m,n,f[10]；
long b,d,s1,t；
printf(" 请输入m,n：")； scanf("%d,%d",&m,&n)；
b=1；s1=0;
for(i=2;i<=m;i++) b=b*10； // 计算m位数起点
for(t=b;t<=10*b-1;t++) // 枚举每一种m位数
{ d=t;
for(j=0;j<=9;j++) f[j]=0； // 数组清零
for(j=1;j<=m;j++)
{ c=d%10；d=d/10;
f[c]++； // 记录数字c个数
}
if(f[7]==1 && f[4]==2 && t%7==0)
{s1++；
if(s1==n) e=t； // 记录个数,并把第n个数赋值给e
}
}
printf(" s1=%ld ,e=%d \n",s1,e)；
}
请输入m,n：6,1000
s1=4096 ,e=417242
9 真分数最值
记录分母在指定区间[a,b]最简真分数(分子不大于分母，且分子分母无公因数)共有多少个，并求其中最接近指定分数x/y最简真分数。
输入a,b，输出[a,b]中最简真分数个数、指出最接近417/最简真分数。
测试数据：
a=10,b=99，输出：
a=100,b=999，输出：

（1）设计要点
设计求解普通情形：记录分母在指定区间[a,b]最简真分数个数,并求这些最简真分数和(正整数a,b从键盘输入)。
设分数分子为i，分母为j，最简真分数个数为n，其和为s。
在指定范畴[a,b]内枚举分数分母j:a——b；
同步对每一种分母j枚举分子i:1——j-1。
对每一分数i/j，置标志t=0，然后进行与否存在公因数检测。
如果分子i与分母j存在不不大于1公因数u，阐明i/j非最简真分数,应予舍略。由于分子分母同步约去u后，分母也许不在[a,b]，虽然在[a,b]时前面已作了记录求和。
注意到公因数u取值范畴为[2,i]，因而设立u循环在[2,i]中枚举，若满足条件
j%u==0 && i%u==0
阐明分子分母存在公因数，标记t=1后退出，不予记录与求和。
否则保持原t=0，阐明分子分母无公因数，用n实行迭代“n=n+1”记录个数。
为了求最接近s=x/y最简真分数，设双精度型变量smin存储｜i/j-x/y|最小值，把分数i/j转变为double型减去s并求绝对值与smin比较，若fabs((double)i/j-s)<smin，则把fabs((double)i/j-s)赋值给smin，同步用i1存储i，用j存储1j。
每得一种最简真分数i/j，就与smin比较一次。枚举完毕，则i1/j1即为所求最接近x/y最简真分数。
(2) 求最简真分数程序设计
// 求分母在[a,b]最简真分数个数,及最接近x/y分数
#include <stdio.h>
#include <math.h>
void main()
{int a,b,i,j,i1,j1,t,u,x,y;long n;
double s,smin;
printf(" 最简真分数分母在[a,b]内,请拟定a,b：");
scanf("%d,%d",&a,&b)； // 输入区间上下限
printf(" 指定分数为x/y,请拟定x,y：");
scanf("%d,%d",&x,&y)； // 输入指定分数
n=0;s=(double)x/y;smin=10;
for(j=a;j<=b;j++) // 枚举最简真分数分母
for(i=1;i<=j-1;i++) // 枚举最简真分数分子
{ for(t=0,u=2;u<=i;u++) // 枚举因数
if(j%u==0 && i%u==0)
{ t=1;break;} // 分子分母有公因数,则舍去
if(t==0)
{ n++； // 记录最简真分数个数
if(fabs((double)i/j-s)<smin)
{smin=fabs((double)i/j-s);i1=i;j1=j； }
// 比较求最接近x/y最简真分数
}
}
printf(" 最简真分数个数：%ld \n",n);
printf(" 最接近%d/%d最简真分数为：%d/%d \n",x,y,i1,j1);
}

(3) 程序运营示例
最简真分数分母在[a,b]内,请拟定a,b：10,99
指定分数为x/y,请拟定x,y：417,
最简真分数个数：2976
最接近417/最简真分数为：17/82

最简真分数分母在[a,b]内,请拟定a,b：100,999
指定分数为x/y,请拟定x,y：417,
最简真分数个数：300788
最接近417/最简真分数为：62/299

10 特定数字构成平方数
用数字2,3,5,6,7,8,9可构成多少个没有重复数字7位平方数？

解：求出最小7位数平方根b，最大7位数平方根c.
用a枚举[b，c]中所有整数，计算d=a*a，这样保证所求平方数在d中。
设立f数组记录d中各个数字个数。如果f[3]=2，即平方数d中有2个“3”。
检测若f[k]>1(k=0——9)，阐明d中存在有重复数字，返回。
在不存在重复数字情形下，检测若f[0]+f[1]+f[4]=0，阐明7位平方数d中没有数字“0”,“1”,“4”,d满足题意规定，打印输出。
// 构成没有重复数字7位平方数
#include <math.h>
#include <stdio.h>
void main()
{int k,m,n,t,f[10]；
long a,b,c,d,w;
n=0;
b=sqrt(2356789);c=sqrt(9876532);
for(a=b;a<=c;a++)
{d=a*a；w=d； // 保证d为平方数
for(k=0;k<=9;k++) f[k]=0;
while(w>0)
{ m=w%10;f[m]++;w=w/10;}
for(t=0,k=1;k<=9;k++)
if(f[k]>1) t=1； // 测试平方数与否有重复数字
if(t==0 && f[0]+f[1]+f[4]==0) // 测试平方数中没有数字0,1,4
{n++;
printf(" %2d：",n);
printf(" %ld=%ld^2 \n",d,a)；
}
}
printf(" 共可构成%d个没有重复数字7位平方数.\n",n);
}
1： 3297856=1816^2
2： 3857296=1964^2
3： 5827396=2414^2
4： 6385729=2527^2
5： 8567329=2927^2
6： 9572836=3094^2
共可构成6个没有重复数字7位平方数.

变通1： 用1,2,…，9这9 个数字可以构成多少个没有重复数字9位平方数？
// 构成没有重复数字9位平方数
#include <math.h>
#include <stdio.h>
void main()
{int k,m,n,t,f[10]；
long a,b,c,d,w;
n=0;
b=(int)sqrt();c=(int)sqrt();
for(a=b;a<=c;a++)
{d=a*a；w=d； // 保证d为平方数
for(k=0;k<=9;k++) f[k]=0;
while(w>0)
{ m=w%10;f[m]++;w=w/10;}
for(t=0,k=1;k<=9;k++)
if(f[k]>1) t=1； // 测试平方数与否有重复数字
if(t==0 && f[0]==0) // 测试平方数中没有重复数字，也没有数字0
{n++;
printf(" %2d：",n);
printf(" %ld=%ld^2 \n",d,a)；
}
}
printf(" 共可构成%d个没有重复数字9位平方数.\n",n);
}

1： =11826^2
2： =12363^2
3： =12543^2
4： =14676^2
5： =15681^2
6： =15963^2
7： =18072^2
8： =19023^2
9： =19377^2
10： =19569^2
11： =19629^2
12： =20316^2
13： =22887^2
14： =23019^2
15： =23178^2
16： =23439^2
17： =24237^2
18： =24276^2
19： =24441^2
20： =24807^2
21： =25059^2
22： =25572^2
23： =25941^2
24： =26409^2
25： =26733^2
26： =27129^2
27： =27273^2
28： =29034^2
29： =29106^2
30： =30384^2
共可构成30个没有重复数字9位平方数.

11 构建横竖折对称方阵
试观测图所示横竖折对称方阵构造特点，总结归纳其构造规律，设计并输出n（奇数）阶对称方阵。

图 7阶横竖对称方阵

输出15阶、19阶横竖折对称方阵。
解： 这是一道培养与锻炼观测能力、归纳能力与设计能力有趣案例。
设立2维数组a[n][n]存储n阶方阵元素，数组a[n][n]就是数据构造。本案例求解算法重要是给a数组赋值与输出。一种一种元素赋值显然行不通，必要依照方阵构造特点，归纳其构建规律，分区域给各元素赋值。
（1） 构造规律与赋值要点
观测横竖折对称方阵构造特点，方阵横向与纵向正中有一对称轴。两对称轴所分4个小矩形区域体现为同数字横竖折递减，至4顶角元素为1。
设阶数n（奇数）从键盘输入，对称轴为m=(n+1)/2。
设立2维a数组存储方阵中元素，行号为i，列号为j，a[i][j]为第i行第j列元素。
可知主对角线（从左上至右下）有：i=j；
次对角线（从右上至左下）有：i+j=n+1。
按两条对角线把方阵提成上部、左部、右部与下部4个区,如图所示。

图 对角线提成4个区
对角线上元素可归纳到上、下部，即上、下部区域带等号即可。
上、下部按列号j函数m-abs(m-j)赋值：
if(i+j<=n+1 && i<=j || i+j>=n+1 && i>=j)
a[i][j]=m-abs(m-j);
左、右部按行号i函数m-abs(m-i)赋值：
if(i+j<n+1 && i>j || i+j>n+1 && i<j)
a[i][j]=m-abs(m-i);
输出时,按m-a[i][j]打印。
（2）程序设计
// 横竖折对称方阵
#include <stdio.h> // 调用2个头文献
#include <math.h>
void main()
{int i,j,m,n,a[30][30]； // 定义数据构造
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<=j || i+j>=n+1 && i>=j)
a[i][j]=m-abs(m-j)； // 方阵上、下部元素赋值
if(i+j<n+1 && i>j || i+j>n+1 && i<j)
a[i][j]=m-abs(m-i)； // 方阵左、右部元素赋值
}
printf(" %d阶对称方阵为:\n",n);
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++) // 输出对称方阵
printf("%3d",m-a[i][j]);
printf("\n");
}
}

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

正整数x,y,z，称为一组倒立勾股数。
试求指定区间[a,b]内倒立勾股数组。
1) 求指定区间[30,100]内倒立勾股数组.
2) 求指定区间[100,200]内倒立勾股数组.

13 基于素数代数和
定义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)最小。

14 幂序列
求解双幂集合

元素由小到大排序第n项与前n项之和。
输入正整数n，输出序列第n项与前n项之和。
测试数据：
1） 40
2） 46