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

程序设计竞赛基本实训221 解不等式 其中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;后来各项中，“-”项不大于其前面“+”项，可知对于nd+2有s(n)m成立。因而有区间解：nd（2） 在nd时与否有解，逐个求和检查拟定离散解。这一步不能省，否则浮现遗解。程序设计1：/ 解不等式：m1+1/2-1/3+1/4+1/5-1/6+.+-1/n #include 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； / 可拟定区间解nd（1） for(k=1;k0) s=s+1.0/k; else s=s-1.0/k; if(sm) 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,可知：nd为解；(2) 此时，s(n)有也许不不大于m,因而在原s基本上s-1.0/d+1.0/(d+1)得s(n):若s(n)m,合并得区间解：nd-1；若s(n)m,区间解为：nd；（因可必定s(n-1)m，得一种离散解：nd-3；若s(n-2)m，没有离散解。程序设计2：/ 解不等式：m1+1/2-1/3+1/4+1/5-1/6+.+-1/n #include void main() long d,n,m；double s; printf(n 请输入m：)；scanf(%d,&m); n=-2;s=0; while(sm) 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(sm) printf( n=%ld n,d-3)； / 输出一种离散解 数据测试： 请输入m：4n=10153n=10151 请输入m：7n=82273513n=82273511程序设计3：请判断如下程序与否对的？/ 解不等式：m1+1/2-1/3+1/4+1/5-1/6+.+-1/n #include void main() double n,m,s; printf(n 请输入m：)；scanf(%lf,&m); n=0;s=3.0/2; while(sm) printf( n=%.0fn,d)； / 可拟定区间解nd（2） else printf( n=%.0fn,d+1)； / ?(1) 一方面s(d)m，n=d为一种解；而s(d-3)=m，n=d-2为“-”项，其绝对值不不大于n=d-1“+”项，可得s(d-1)m；且知nd时无解。同步由，可得s(d+1)m时,后来“-”项绝对值不大于其前面“+”项，故得区间解nd;当s(n+4)m；但不能拟定s(n+6)0,因而不能拟定nd+1为区间解！2 求最大值设指定区间a,b内正整数x,y,z,w满足 其中axyzwb，试求s=x+y+z+w最大值。输入正整数a,b（1ab10000），输出s最大值。测试数据：（1） a=500,b=1000（2） a=1000,b=设计要点：对每一组满足条件解，通过比较求得最大值。程序设计：/ 求最大值#include #include 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;zb) break; if(w*w=d) / 满足条件时记录 s=x+y+z+w; if(smax) max=s; printf( s最大值为：%ld n,max);数据测试：请输入区间a,b上下限a,b：500,1000 s最大值为：2728 请输入区间a,b上下限a,b：1000, s最大值为：54963 带中转站交通路线在某城区完整方格交通网中，中转站(a,b)与终点(m,n)为交通网中任意两交叉点，这里a,b,m,n为非负整数。试记录从始点(0,0)经中转点（a,b）到终点(m,n)不同最短路线(路线中各段只能接近目的点而不能远离目的点)条数。（注：若am且bn时，从(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，即必经点与起点在横向或纵向同线，y1。2） 若a0且b0，即a,b为正整数时，y=。为了求z,分如下两种情形计算：1） 若m=a或n=b，即必经点与终点在横向或纵向同线，z1。2） 若ma且nb，必经点与终点在横向相差，在纵向相差，z=。程序设计：/ 带中转站最短路线 #include #include 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*b0)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 void main() int k,m,n,x,y,z,f5050； printf( 请输入正整数m,n：)；scanf(%d,%d,&m,&n)；for(x=1;x=m;x+) fx0=1; for(y=1;y=n;y+) f0y=1； / 拟定边界条件for(x=1;x=m;x+) for(y=1;y=n;y+) / 实行递推得目的值f(m,n)fxy=fx-1y+fxy-1;printf( 不同最短路线条数为：%d n,fmn);z=1;for(k=1;k=m;k+) z=z*(n+k)/k;printf( 不同最短路线组合数为：%d n,z);请输入正整数m,n：7,10 不同最短路线条数为：194484 双码二部数序列试求双码二部数升序序列第m项。测试数据：m=；m=4设计1： 把双码二部数升序序列第m项换算为n位第m0项。注意到2位双码二部数共9*981个；3位双码二部数共2*9*92*81个；/ 求双码二部数升序序列第m项#include #include 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(sm)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=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个数 #includevoid 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(lan-1 | a9 | b8) 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(b8) 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 #includevoid main() long j,n； double ts,s; printf( 请输入n：)；scanf(%d,&n); j=0;ts=0;s=0; while(jn) 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 #includevoid main() double j,n,ts,s; printf( 请输入n：)； scanf(%lfd,&n); j=0;ts=0;s=0; while(jn) 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变通：设2n,当n为什么值时，和s最接近？6 合数世纪探求1. 问题提出20世纪100个年号1901中有13个素数，而21世纪100个年号，2100中有14个素数。那么，与否存在一种世纪100个年号中一种素数都没有？定义一种世纪100个年号中不存在一种素数，即100个年号全为合数世纪称为合数世纪。设计程序摸索第m（商定m100）个合数世纪。测试数据：(1) m=1(2) m=102. 设计要点应用穷举搜索，设立a世纪50个奇数年号(偶数年号无疑均为合数)为b，用k试商鉴别b与否为素数，用变量s记录这50个奇数中合数个数。对于a世纪，若s=50，即50个奇数都为合数，找到a世纪为合数世纪，用n记录合数世纪个数。当n=m时打印输出a 世纪。当n=m时退出循环结束。3. 合数世纪程序设计/ 探求第1个与第m个合数世纪#include #include 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=23*5*72，前者为质因数乘积形式，后者为质因数指数形式。把指定区间上所有整数分解质因数,每一整数表达为质因数从小到大顺序乘积形式。如果被分解数自身是素数，则注明为素数。例如，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） 质因数分解乘积形式程序设计/ 质因数分解乘积形式#includemath.h#include 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(k1) printf(%ld*,k);continue； / k为质因数,返回再试 if(b=1) printf(%ldn,k); k+; if(b1 & bi) printf(%ldn,b)； / 输出不不大于i平方根因数 if(b=i) printf(素数!)n);w+; / b=i,表达i无质因数 printf(其中共%d个素数.n,w);1671861=3*31*179775845276=2*2*223*6553m,n中整数分解质因数（乘积形式）请输入m,n:1671801,1671899 （验证第1个倒数世纪年号）1671801=3*23*242291671802=2*11*759911671803=7*2388291671804=2*2*3*3*464391671805=5*239*13991671806=2*769*10871671807=3*5572691671808=2*2*2*2*2*2*2*37*3531671809=599*27911671810=2*3*5*7*19*4191671811=137*122031671812=2*2*4179531671813=3*3*3*11*13*4331671814=2*17*491711671815=5*3343631671816=2*2*2*3*41*16991671817=7*241*9911671818=2*8359091671819=3*5572731671820=2*2*5*835911671821=29*576491671822=2*3*3*131*7091671823=191*87531671824=2*2*2*2*7*11*23*591671825=3*5*5*222911671826=2*13*643011671827=61*274071671828=2*2*3*127*10971671829=19*879911671830=2*5*31*53931671831=3*3*7*7*17*2231671832=2*2*2*53*39431671833=1289*12971671834=2*3*2786391671835=5*11*113*2691671836=2*2*4179591671837=3*47*71*1671671838=2*7*1194171671839=13*1286031671840=2*2*2*2*2*3*3*3*3*3*5*431671841=1223*13671671842=2*109*76691671843=3*5572811671844=2*2*4179611671845=5*7*37*12911671846=2*3*11*73*3471671847=23*726891671848=2*2*2*17*19*6471671849=3*3*431*4311671850=2*5*5*29*11531671851=67*249531671852=2*2*3*7*13*15311671853=101*165531671854=2*8359271671855=3*5*227*4911671856=2*2*2*2*1044911671857=11*11*41*3371671858=2*3*3*293*3171671859=7*2388371671860=2*2*5*179*4671671861=3*31*179771671862=2*8359311671863=359*46571671864=2*2*2*3*696611671865=5*13*17*17*891671866=2*7*1194191671867=3*3*3*19*32591671868=2*2*11*379971671869=83*31671870=2*3*5*23*24231671871=487*34331671872=2*2*2*2*2*2*151*1731671873=3*7*796131671874=2*8359371671875=5*5*5*5*5*5*1071671876=2*2*3*3*464411671877=79*211631671878=2*13*643031671879=3*11*29*17471671880=2*2*2*5*7*7*8531671881=331*50511671882=2*3*17*37*4431671883=43*59*6591671884=2*2*47*88931671885=3*3*5*53*7011671886=2*19*439971671887=7*2388411671888=2*2*2*2*3*61*5711671889=521*32091671890=2*5*11*151991671891=3*13*163*2631671892=2*2*31*97*1391671893=23*157*4631671894=2*3*3*3*7*44231671895=5*3343791671896=2*2*2*103*20291671897=3*181*30791671898=2*41*203891671899=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阶横竖折对称方阵。