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

程序设计竞赛基本实训22
1 解不等式

其中m为从键盘输入正整数，式中符号为二个“+”号后一种“-”号，即分母能被3整除时为“-”。
输入正整数m，输出满足不等式n。
测试数据： (1) m=4 (2) m=7

设计要点1：
式中浮现减运算，导致不等式解也许分段。
设立条件循环，每三项（包括二正一负）一起求和，得一种区间解。
然后回过头来一项项求和，得个别离散解。
为论述以便，记
（1） 通过循环知s(d+1)>m，且n=d+1为“-”，可得n=d为一种解；
而n=d+2时1.0/(n+3)为“+”，可得s(d+2)>m;后来各项中，“-”项不大于其前面“+”项，可知对于n>d+2有s(n)>m成立。
因而有区间解：n≥d
（2） 在n<d时与否有解，逐个求和检查拟定离散解。这一步不能省，否则浮现遗解。
程序设计1：
// 解不等式：m<1+1/2-1/3+1/4+1/5-1/6+...+-1/n
#include <stdio.h>
void main()
{ long d,n,m,k；double s;
printf("\n 请输入m：")；scanf("%d",&m);
n=-2;s=0;
while(s<=m)
{ n=n+3;s=s+1.0/n+1.0/(n+1)-1.0/(n+2)；}
d=n+1；s=0； // 可拟定区间解n≥d（1）
for(k=1;k<=n;k++)
{ if(k%3>0) s=s+1.0/k;
else s=s-1.0/k;
if(s>m) printf(" n=%ld，",k)； // 逐个得离散解
}
printf("n>=%ld \n",d)；
}
程序运营示例：
请输入m：4
n=10151，n=10153，n>=10154
请输入m：7
n=82273511，n=82273513，n>=82273514
注意：要特别注意，不要把离散解遗失。
思考：如果把后一种离散解写入区间解中？

设计要点2：
为论述以便，记
(1) 通过循环累加，当加到s=s+1.0/n+1.0/(n+1)-1.0/(n+2);得s(n+2)>m，令d=n+1,可知：n≥d为解；
(2) 此时，s(n)有也许不不大于m,因而在原s基本上s-1.0/d+1.0/(d+1)得s(n):
若s(n)>m,合并得区间解：n≥d-1；
若s(n)<m,区间解为：n≥d；（因可必定s(n-1)<m）
但s(n-2)尚有也许不不大于m,因而在上s基本上s+1.0/(d-2)-1.0/(d-1),得s(n-2):
若s(n-2)>m，得一种离散解：n＝d-3；
若s(n-2)<m，没有离散解。
程序设计2：
// 解不等式：m<1+1/2-1/3+1/4+1/5-1/6+...+-1/n
#include <stdio.h>
void main()
{ long d,n,m；double s;
printf("\n 请输入m：")；scanf("%d",&m);
n=-2;s=0;
while(s<=m)
{ n=n+3;s=s+1.0/n+1.0/(n+1)-1.0/(n+2)；}
d=n+1； // 可拟定区间解n≥d（1）
s=s-1.0/d+1.0/(d+1)； // 得s(n)
if(s>m) printf(" n>=%ld \n",d-1)； // 输出区间解
else printf(" n>=%ld \n",d);
s=s+1.0/(d-2)-1.0/(d-1)； // 得s(n-2)
if(s>m) printf(" n=%ld \n",d-3)； // 输出一种离散解
}
数据测试：
请输入m：4
n>=10153
n=10151
请输入m：7
n>=82273513
n=82273511

程序设计3：请判断如下程序与否对的？
// 解不等式：m<1+1/2-1/3+1/4+1/5-1/6+...+-1/n
#include <stdio.h>
void main()
{ double n,m,s;
printf("\n 请输入m：")；scanf("%lf",&m);
n=0;s=3.0/2;
while(s<=m)
{ n=n+3;s=s-1.0/n+1.0/(n+1)+1.0/(n+2)；}
d=n+2;
printf(" n=%.0f,",d)； // 得一种离散解（1）
s=s-1.0/(n+3)+1.0/(n+4);d=n+4;
if(s>m) printf(" n>=%.0f\n",d)； // 可拟定区间解n≥d（2）
else printf(" n>=%.0f\n",d+1)； // ??
}

(1) 一方面s(d)>m，n=d为一种解；
而s(d-3)<=m，n=d-2为“-”项，其绝对值不不大于n=d-1“+”项，可得s(d-1)<m；且知n<d时无解。
同步由，可得s(d+1)<m，即n=d为一种离散解。
(2) 当s(n+4)>m时,后来“-”项绝对值不大于其前面“+”项，故得区间解n≥d;
当s(n+4)<=m时,因可知s(n+5)>m；但不能拟定s(n+6)>0,因而不能拟定n≥d+1为区间解！

2 求最大值
设指定区间[a,b]内正整数x,y,z,w满足

其中a≤x<y<z<w≤b，试求s=x+y+z+w最大值。
输入正整数a,b（1≤a<b<10000），输出s最大值。
测试数据：
（1） a=500,b=1000
（2） a=1000,b=
设计要点：对每一组满足条件解，通过比较求得最大值。
程序设计：
// 求最大值
#include <stdio.h>
#include <math.h>
void main()
{long a,b,d,s,x,y,z,w,max;
printf(" 请输入区间[a,b]上下限a,b：");
scanf("%ld,%ld",&a,&b);
max=0;
for(x=a;x<=sqrt(b*b/3);x++)
for(y=x+1;y<=sqrt((b*b-x*x)/2);y++)
for(z=y+1;z<=sqrt(b*b-x*x-y*y);z++)
{ d=x*x+y*y+z*z；
w=(int)sqrt(d)； // w为x,y,z平方和开平方
if(w>b) break;
if(w*w==d) // 满足条件时记录
{ s=x+y+z+w;
if(s>max) max=s;
}
}
printf(" s最大值为：%ld \n",max);
}
数据测试：
请输入区间[a,b]上下限a,b：500,1000
s最大值为：2728
请输入区间[a,b]上下限a,b：1000,
s最大值为：5496

3 带中转站交通路线
在某城区完整方格交通网中，中转站(a,b)与终点(m,n)为交通网中任意两交叉点，这里a,b,m,n为非负整数。
试记录从始点(0,0)经中转点（a,b）到终点(m,n)不同最短路线(路线中各段只能接近目的点而不能远离目的点)条数。（注：若a>m且b>n时，从(0,0)点至(a,b)点这一段容许通过(m,n)点）

交通网格示意图
输入非负整数a,b,m,n，输出从始点(0,0)经(a,b)到终点(m,n)最短路线条数。
测试数据：
（1） a=9,b=7,m=20,n=12
（2） a=20,b=12,m=9,n=7
设计要点：
如果路线中没有设指定必经点，从始点(0,0)到终点(m,n)每一条路线共m+n段，其中横向m段，纵向n段，每一条不同路线相应从m+n个元素中取m个元素（以放置横向段）组合数，不同路线条数为

今设立了路线中必经点(a,b)，须分如下两步记录。设从始点(0,0)到交叉点(a,b)不同路线条数为y，从交叉点(a,b)到终点(m,n)不同路线条数为z。据乘法原理，从始点(0,0)经(a,b)到终点(m,n)最短路线条数为yz。
为了求y,分如下两种情形计算：
1） 若a=0或b=0，即必经点与起点在横向或纵向同线，y＝1。
2） 若a>0且b>0，即a,b为正整数时，y=。
为了求z,分如下两种情形计算：
1） 若m=a或n=b，即必经点与终点在横向或纵向同线，z＝1。
2） 若m≠a且n≠b，必经点与终点在横向相差，在纵向相差，z=。
程序设计：
// 带中转站最短路线
#include <stdio.h>
#include <math.h>
void main()
{ double a,b,c,d,m,n,k,y,z；
printf(" 请输入正整数a,b：")；scanf("%lf,%lf",&a,&b);
printf(" 请输入正整数m,n：")；scanf("%lf,%lf",&m,&n)；
y=1;
if(a*b>0)
for(k=1;k<=a;k++)
y=y*(b+k)/k； // 计算C(a+b,a)
z=1;
if((m-a)*(n-b)!=0)
{ c=fabs(m-a);d=fabs(n-b);
for(k=1;k<=c;k++)
z=z*(d+k)/k； // 计算C(|m-a|+|n-b|,|m-a|)
}
printf(" 不同最短路线条数为：%.0f \n",y*z);
}
数据测试：
请输入正整数a,b：9,7
请输入正整数m,n：20,12
不同最短路线条数为：49969920
请输入正整数a,b：20,12
请输入正整数m,n：9,7
不同最短路线条数为：

附无障碍无中转站交通路线问题程序：
// 无障碍完整交通路线问题
#include <stdio.h>
void main()
{ int k,m,n,x,y,z,f[50][50]；
printf(" 请输入正整数m,n：")；scanf("%d,%d",&m,&n)；
for(x=1;x<=m;x++) f[x][0]=1;
for(y=1;y<=n;y++) f[0][y]=1； // 拟定边界条件
for(x=1;x<=m;x++)
for(y=1;y<=n;y++) // 实行递推得目的值f(m,n)
f[x][y]=f[x-1][y]+f[x][y-1];
printf(" 不同最短路线条数为：%d \n",f[m][n]);
z=1;
for(k=1;k<=m;k++)
z=z*(n+k)/k;
printf(" 不同最短路线组合数为：%d \n",z);
}

请输入正整数m,n：7,10
不同最短路线条数为：19448
4 双码二部数序列
试求双码二部数升序序列第m项。
测试数据：m=；m=4

设计1： 把双码二部数升序序列第m项换算为n位第m0项。
注意到2位双码二部数共9*9＝81个；3位双码二部数共2*9*9＝2*81个；……
// 求双码二部数升序序列第m项
#include <stdio.h>
#include <math.h>
void main()
{ int a,b,a0,b0,i,n,m,m0,la,lb,la0,lb0,s;
printf(" 请依次输入整数m：");
scanf("%d",&m);
s=0;n=0;
while(s<m)
{n++;s=s+n*81;}
m0=m-(s-n*81);n++;s=0； // 换算为n位第m0项
for(a=1;a<=9;a++) // 高部数字a从小到大枚举
{ for(la=1;la<=n-2;la++) // 高部位数la分3环节枚举
{ lb=n-la;
for(b=0;b<=a-1;b++)
{ s++； // 变量s记录个数
if(s==m0) // 记录第m个数信息
{ a0=a;b0=b;la0=la;lb0=lb;}
}
}
la=n-1;lb=1;
for(b=0;b<=9;b++)
if(a!=b) // 当a=b时跳过
{ s++;
if(s==m0){ a0=a;b0=b;la0=la;lb0=lb;}
}
for(la=n-2;la>=1;la--)
{ lb=n-la;
for(b=a+1;b<=9;b++)
{ s++;
if(s==m0){ a0=a;b0=b;la0=la;lb0=lb;}
}
}
}
printf(" 双码二部数升序序列第%d个数为：",m);
for(i=1;i<=la0;i++)
printf("%d",a0);
for(i=1;i<=lb0;i++)
printf("%d",b0);
printf(" \n");
printf(" （式中%d个%d，%d个%d)\n"，la0,a0,lb0,b0);
}

设计2： 从n=2位开始记录
// 求双码二部数从小到大排列第m个数
#include<stdio.h>
void main()
{ int a,b,a0,b0,i,m,n,p,la,la0,lb0;
printf(" 请输入整数m：");
scanf("%d",&m);
n=1;p=0；
while(1)
{ n++;p++;a=1;b=0;la=1； // 默认n位第1个为1后n-1个0
if(p==m) {a0=a;b0=b;la0=la;lb0=n-la0;break;}
while(la<n-1 || a<9 || b<8)
{ p++;
if(b==9) // 此时b不能增1,有如下2种选取
if(la==1){a++；b=0;} // ① a增1后，b从0开始
else {la--；b=a+1;} // ② a段长增1后，b从a+1开始
else if(b!=a-1) b++； // a与la不变，b增1
else if(la!=n-1){la++;b=0;} // a段长增1后，b从0开始
else if(b<8) b+=2； // b增2跳过a=b情形
if(p==m)
{a0=a;b0=b;la0=la;lb0=n-la0;break;}
}
if(p==m) break；
}
printf(" 第%d个双码二部数为：%d(%d)%d(%d)\n",m,a0,la0,b,lb0);
printf(" 其中从小到大第%d个数为：",m);
for(i=1;i<=la0;i++)
printf("%d",a0);
for(i=1;i<=lb0;i++)
printf("%d",b0);
printf(" \n");
}
数据测试：
请依次输入整数m：
双码二部数升序序列第个数为：55999999
（式中2个5，6个9)
请依次输入整数m：4
双码二部数升序序列第4个数为：
（式中4个8，19个2)

5 求代数和
设n为正整数，求和

式中各项符号为二正一负，分母符号为一正一负。
正整数n从键盘输入，输出和s四舍五入精准到小数点后5位。
输入n=100 输出：
输入n= 输出：

// 求代数和1
#include <stdio.h>
#include<math.h>
void main()
{ long j,n；
double ts,s;
printf(" 请输入n：")；scanf("%d",&n);
j=0;ts=0;s=0;
while(j<n)
{ j=j+1;
if(j%2==0)
ts=ts-(double)1/j； // ts为各项分母
else
ts=ts+(double)1/j；
if(j%3==0)
s=s-sqrt(j)/ts； // 求代数和s
else
s=s+sqrt(j)/ts;
}
printf(" s=%.5f \n",s);
}

// 求代数和2
#include <stdio.h>
#include<math.h>
void main()
{ double j,n,ts,s;
printf(" 请输入n：")； scanf("%lfd",&n);
j=0;ts=0;s=0;
while(j<n)
{ j=j+1;
if(fmod(j,2)==0)
ts=ts-1/j； // ts为各项分母
else
ts=ts+1/j；
if(fmod(j,3)==0)
s=s-sqrt(j)/ts； // 求代数和s
else
s=s+sqrt(j)/ts;
}
printf(" s=%.5f \n",s);
}

请输入n：100 s=324.74013
请输入n： s=28924.48725
请输入n： s=28989.22300
变通：设2<n≤,当n为什么值时，和s最接近？

6 合数世纪探求
1. 问题提出
20世纪100个年号[1901—]中有13个素数，而21世纪100个年号[，2100]中有14个素数。
那么，与否存在一种世纪100个年号中一种素数都没有？
定义一种世纪100个年号中不存在一种素数，即100个年号全为合数世纪称为合数世纪。
设计程序摸索第m（商定m<100）个合数世纪。
测试数据：
(1) m=1
(2) m=10
2. 设计要点
应用穷举搜索，设立a世纪50个奇数年号(偶数年号无疑均为合数)为b，用k试商鉴别b与否为素数，用变量s记录这50个奇数中合数个数。
对于a世纪，若s=50，即50个奇数都为合数，找到a世纪为合数世纪，用n记录合数世纪个数。当n=m时打印输出a 世纪。
当n=m时退出循环结束。
3. 合数世纪程序设计
// 探求第1个与第m个合数世纪
#include <stdio.h>
#include <math.h>
void main()
{long a,b,k；int m,n,s,x;
printf(" 请拟定m：")；scanf("%d",&m);
a=1;n=0;
while (1)
{a++;s=0； // 检查a世纪
for(b=a*100-99;b<=a*100-1;b+=2) // 穷举a世纪奇数年号b
{x=0;
for(k=3;k<=sqrt(b);k+=2)
if(b%k==0)
{x=1;break;}
if(x==0)break； // 当前为非合数世纪时，跳出循环进行下一种世纪探求
s=s+x； // 年号b为合数时，x=1，s增1
}
if(s==50) // s=50，即50个奇数均为合数
{ n++;
if(n==m)
printf(" 第%d个合数世纪为：%ld 世纪。\n",n,a);
}
if(n==m) break;
}
}
4. 程序运营示例
请拟定m：10
第1个合数世纪为： 16719世纪。
第10个合数世纪为： 58453世纪。
16719 世纪尽管是最早合数世纪，它100个年号为[1671801，1671900]全为合数。这是一种非常漫长年代，可谓天长地久，地老天荒！
7 分解质因数
整数分解质因数是最基本分解。例如，90=2*3*3*5，1960=2^3*5*7^2，前者为质因数乘积形式，后者为质因数指数形式。
把指定区间上所有整数分解质因数,每一整数表达为质因数从小到大顺序乘积形式。如果被分解数自身是素数，则注明为素数。
例如，92=2*2*23，91(素数!)。
分解：
1671861＝
5845271＝

（1） 设计要点
对每一种被分解整数i，赋值给b(以保持鉴别运算过程中i不变)，用k(从2开始递增取值)试商:
若不能整除，阐明该数k不是b因数，k增1后继续试商。
若能整除，阐明该数k是b因数，打印输出"k*"；b除以k商赋给b(b=b/k)后继续用k试商(注意，也许有各种k因数)，直至不能整除，k增1后继续试商。
按上述从小至大试商拟定因数显然为质因数。
循环取值k终值如何拟定，一定限度上决定了程序效率。终值定为i-1或i/2，无效循环太多。循环终值定为i平方根sqrt(i)可大大精简试商次数，此时如果有不不大于sqrt(i)因数(至多一种!),在试商循环结束后要注意补上，不要遗失。
如果整个试商后b值没有任何缩减，仍为原待分解数i，阐明i是素数，作素数阐明标记。
（2） 质因数分解乘积形式程序设计
// 质因数分解乘积形式
#include"math.h"
#include <stdio.h>
void main()
{long int b,i,k,m,n,w=0;
printf("[m,n]中整数分解质因数（乘积形式）.\n");
printf("请输入m,n:");
scanf("%ld,%ld",&m,&n);
for(i=m;i<=n;i++) // i为待分解整数
{ printf("%ld=",i);
b=i;k=2;
while(k<=sqrt(i)) // k为试商因数
{if(b%k==0)
{b=b/k;
if(b>1)
{printf("%ld*",k);
continue； // k为质因数,返回再试
}
if(b==1) printf("%ld\n",k);
}
k++;
}
if(b>1 && b<i)
printf("%ld\n",b)； // 输出不不大于i平方根因数
if(b==i)
{printf("(素数!)\n");w++;} // b=i,表达i无质因数
}
printf("其中共%d个素数.\n",w);
}

1671861=3*31*17977
5845276=2*2*223*6553

[m,n]中整数分解质因数（乘积形式）
请输入m,n:1671801,1671899 （验证第1个倒数世纪年号）
1671801=3*23*24229
1671802=2*11*75991
1671803=7*238829
1671804=2*2*3*3*46439
1671805=5*239*1399
1671806=2*769*1087
1671807=3*557269
1671808=2*2*2*2*2*2*2*37*353
1671809=599*2791
1671810=2*3*5*7*19*419
1671811=137*12203
1671812=2*2*417953
1671813=3*3*3*11*13*433
1671814=2*17*49171
1671815=5*334363
1671816=2*2*2*3*41*1699
1671817=7*241*991
1671818=2*835909
1671819=3*557273
1671820=2*2*5*83591
1671821=29*57649
1671822=2*3*3*131*709
1671823=191*8753
1671824=2*2*2*2*7*11*23*59
1671825=3*5*5*22291
1671826=2*13*64301
1671827=61*27407
1671828=2*2*3*127*1097
1671829=19*87991
1671830=2*5*31*5393
1671831=3*3*7*7*17*223
1671832=2*2*2*53*3943
1671833=1289*1297
1671834=2*3*278639
1671835=5*11*113*269
1671836=2*2*417959
1671837=3*47*71*167
1671838=2*7*119417
1671839=13*128603
1671840=2*2*2*2*2*3*3*3*3*3*5*43
1671841=1223*1367
1671842=2*109*7669
1671843=3*557281
1671844=2*2*417961
1671845=5*7*37*1291
1671846=2*3*11*73*347
1671847=23*72689
1671848=2*2*2*17*19*647
1671849=3*3*431*431
1671850=2*5*5*29*1153
1671851=67*24953
1671852=2*2*3*7*13*1531
1671853=101*16553
1671854=2*835927
1671855=3*5*227*491
1671856=2*2*2*2*104491
1671857=11*11*41*337
1671858=2*3*3*293*317
1671859=7*238837
1671860=2*2*5*179*467
1671861=3*31*17977
1671862=2*835931
1671863=359*4657
1671864=2*2*2*3*69661
1671865=5*13*17*17*89
1671866=2*7*119419
1671867=3*3*3*19*3259
1671868=2*2*11*37997
1671869=83*3
1671870=2*3*5*23*2423
1671871=487*3433
1671872=2*2*2*2*2*2*151*173
1671873=3*7*79613
1671874=2*835937
1671875=5*5*5*5*5*5*107
1671876=2*2*3*3*46441
1671877=79*21163
1671878=2*13*64303
1671879=3*11*29*1747
1671880=2*2*2*5*7*7*853
1671881=331*5051
1671882=2*3*17*37*443
1671883=43*59*659
1671884=2*2*47*8893
1671885=3*3*5*53*701
1671886=2*19*43997
1671887=7*238841
1671888=2*2*2*2*3*61*571
1671889=521*3209
1671890=2*5*11*15199
1671891=3*13*163*263
1671892=2*2*31*97*139
1671893=23*157*463
1671894=2*3*3*3*7*4423
1671895=5*334379
1671896=2*2*2*103*2029
1671897=3*181*3079
1671898=2*41*20389
1671899=17*98347
其中共0个素数.

8 记录
试记录具有数字7且不能被7整除m位整数个数s1，并指出这s1个数中不具有数字4整数个数s2。
输入m，输出s1,s2。
测试数据：
m=5，输出：
m=6，输出：
9 真分数最值
记录分母在指定区间[a,b]最简真分数(分子不大于分母，且分子分母无公因数)共有多少个，并求其中最接近指定分数x/y最简真分数。
输入a,b，输出[a,b]中最简真分数个数、指出最接近417/最简真分数。
测试数据：
a=10,b=99，输出：
a=100,b=999，输出：

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

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

图 7阶横竖对称方阵

输出15阶、19阶横竖折对称方阵。