2023年程序设计竞赛基础实训完整版

2023年程序设计竞赛基础实训2２１解不等式其中m为从键盘输入的正整数,式中符号为二个“+”号后一个“-”号，即分母能被3整除时为“－”。输入正整数ｍ,输出满足不等式的n。测试数据：(1）m=4（2）m＝7设计要点１：式中出现减运算,导致不等式的解也许分段。设立条件循环，每三项（包含二正一负)一起求和，得一个区间解。然后回过头来一项项求和,得个别离散解。为叙述方便,记通过循环知s（d+1)>m,且n=d+１为“－”,可得n＝ｄ为一个解;而n=ｄ＋2时1.0/(ｎ+3）为“+”，可得s（d+2）>m;以后各项中，“－”项小于其前面的“+”项,可知对于n>d+2有s(ｎ)>ｍ成立。因而有区间解:n≥ｄ在n<d时是否有解，逐个求和检查拟定离散解。这一步不能省,否则出现遗解。程序设计1:/／解不等式:m＜1+1/２－1/3+1/4+1/5-1/6＋．．.+-１/n#inclｕde<stdio.h＞vｏiｄmaiｎ(){longd,ｎ,ｍ，k；douｂlｅｓ;ｐｒintｆ(＂＼n请输入ｍ:")；ｓｃanf("%ｄ＂,＆m);n=-2;ｓ=0;while(s<=m){n＝n＋３;ｓ=s+1.0/n+1.0/(n+1）-1．0/（ｎ+2）;}d=ｎ+1;ｓ=0；//可拟定区间解n≥d(１）ｆor（k=1;ｋ<=n；k+＋）{if(k%3＞0)ｓ=s+1.0/k；ｅlｓes=s-1.0/ｋ;if(s>m)ｐrintf(＂n＝%ｌd，＂,k);／/逐个得离散解}ｐriｎtf("n>=%ｌd＼n＂,d)；｝程序运营示例：请输入ｍ:4n=101５１，n=10153,n>=10154请输入m：7n＝8227３51１,n＝8227３５１3,n>=822７35１4注意:要特别注意，不要把离散解遗失。思考:假如把后一个离散解写入区间解中?设计要点2:为叙述方便，记(１)通过循环累加，当加到s=ｓ+１.0／ｎ+1.0/（n+1）-1.0／(n+2);得s(n+2)>ｍ,令d=n+1,可知：n≥d为解；(2)此时,s(n)有也许大于m，因而在原s基础上ｓ-1．0／d+１.0/(ｄ+１）得s(n）:若s(n）>m,合并得区间解:ｎ≥d-1；若s(n)<m,区间解为：n≥ｄ；（因可肯定ｓ(n－1)＜ｍ)但s（n-2)尚有也许大于m，因而在上s基础上s＋１.0/(d-２)－1．0/（ｄ-1),得ｓ(ｎ－２):若s(n－2)>m,得一个离散解:ｎ＝d-３;若s(n-2)<m,没有离散解。程序设计2:／/解不等式:m<１＋1/２－1/3+1/４＋1/5-1／6+...+-1/n#include<stｄiｏ.h>voidmain()｛lonｇd，n,m；ｄｏｕblｅs;pｒｉｎtf（＂\n请输入m：＂)；ｓcａnｆ("%d",&m）;ｎ=-２;ｓ=0;wｈｉle(s<=ｍ){ｎ=n+３；ｓ=s+1.0/n+1．0/(n+1)－1.0／（n+２)；｝ｄ＝ｎ＋１；//可拟定区间解n≥d(1)s=s-1.0/d+1.０／(d＋1）;/／得s(n）if(s>ｍ）ｐrintf("n>=%ld\n＂,ｄ-1);//输出区间解ｅlｓeprｉｎtf("n>=%ld\n＂,ｄ);ｓ=s＋１.0/(ｄ-２)－1．０/（d-1);／／得s（n-２)ｉf(s＞m）pｒiｎｔf（＂n=%lｄ\n",d-３)；／/输出一个离散解}数据测试：请输入m:4ｎ>=1015３n=1０15１请输入ｍ:7ｎ>=822７３513n＝8227３5１1程序设计3：请判断以下程序是否对的？//解不等式：ｍ<１＋１/2-1/3+1/4＋1/5－1/6+...+-1/n#inclｕdｅ<ｓtdio.h>voiｄｍａin()｛doｕbｌｅn，m,ｓ;printｆ（＂＼n请输入m：");scａｎf("%lf",&m）;n=0；s＝3.0/2；while（s<=m）｛ｎ＝n+3；ｓ=s－１．0／n+1.０/(n+１）+1.０/（n+2）;｝d＝n+２;priｎtf(＂ｎ=%．0ｆ,"，ｄ）;／/得一个离散解(1）ｓ=s-1.0/(n+3)+1.０/(n+4）;d=ｎ+4；iｆ(ｓ＞ｍ)printf("n>=%.0f＼n",d);//可拟定区间解ｎ≥ｄ(２)elsｅprintf("n＞＝%.0f\n",d+1)；//?？}(１)一方面s(d)>m,n=d为一个解;而ｓ（d－3)＜=m,n=d-２为“-”项，其绝对值大于n=d-1的“＋”项，可得s（d-1)<m；且知ｎ<d时无解。同时由，可得s(ｄ+1）＜m,即ｎ=d为一个离散解。(2)当ｓ（n＋4)>m时,以后的“-”项绝对值小于其前面的“+”项，故得区间解n≥d;当s(n+４）<＝ｍ时,因可知s(ｎ+５)>m;但不能拟定s(ｎ+6)＞０，因而不能拟定n≥d+1为区间解！2求最大值设指定区间[a，b]内的正整数x,y，z,w满足其中a≤x<y<z<w≤b，试求s＝x＋y+z+w的最大值。输入正整数a，b（１≤a＜b＜10０00）,输出s的最大值。测试数据：a=50０，ｂ=1０00a=100０,b=2023设计要点:对每一组满足条件的解,通过比较求得最大值。程序设计：//求最大值#inｃlｕde<stｄio．ｈ>#incluｄe<maｔh.h>voidmain(){lonｇａ,ｂ,ｄ，s,x，y,z，ｗ,max;printf（＂请输入区间[ａ,ｂ］的上下限a,b:＂)；scanf（"％ｌd,%lｄ",&a，&ｂ);maｘ=0;fｏｒ（x=a;ｘ<＝sqｒt（b*b/3);ｘ＋＋）for(ｙ=x+１；y＜=sqrｔ(（b*b-x*ｘ)/２）;y++)for(z=y+1;z<=ｓqrｔ(ｂ*b-x*x-ｙ＊y);z++)｛d=x*x+ｙ*y+z*z;w=（ｉnt)sqrt(d)；//w为x,y,ｚ的平方和开平方if（w>b)breａk;ｉf（w*w==d)//满足条件时记录{s=x+y+z+w；ｉf（s>mａx)maｘ＝s;}}prｉｎtf("s的最大值为：%ld\n＂,max);}数据测试:请输入区间[a，b]的上下限a,b:500,1000s的最大值为：2728请输入区间[a,b]的上下限ａ,ｂ：100０,２0２3ｓ的最大值为：54９6３带中转站的交通路线在某城区的完整方格交通网中，中转站（a，ｂ)与终点（ｍ,n)为交通网中的任意两交叉点，这里a,b,m，n为非负整数。试记录从始点(0,０）经中转点(a，b）到终点(m，n)的不同最短路线(路线中各段只能靠近目的点而不能远离目的点）的条数。(注:若a>m且b>n时，从(0，0)点至（a,b）点这一段允许通过（m,ｎ)点）交通网格示意图输入非负整数a,b,m，ｎ,输出从始点(0，0)经(a,b）到终点(ｍ,ｎ)的最短路线的条数。测试数据：a=9,b＝7,ｍ=20,n=1２ａ＝2０,b=12,ｍ＝９,n＝7设计要点:假如路线中没有设指定的必经点,从始点(０,0)到终点(m,n)每一条路线共ｍ+n段，其中横向m段,纵向ｎ段,每一条不同路线相应从m＋n个元素中取m个元素(以放置横向段)的组合数，不同路线条数为今设立了路线中的必经点(ａ,b）,须分以下两步记录。设从始点(０,０)到交叉点（ａ，ｂ)的不同路线条数为y,从交叉点(a,b)到终点（m,n)的不同路线条数为ｚ。据乘法原理,从始点(0,0)经（a,b)到终点(ｍ,n)的最短路线的条数为yz。为了求y,分以下两种情形计算：1)若a=０或ｂ=0,即必经点与起点在横向或纵向同线，ｙ=1。2）若ａ>0且b>0，即a,b为正整数时，ｙ=。为了求z,分以下两种情形计算：１)若ｍ=ａ或n=ｂ,即必经点与终点在横向或纵向同线,z=1。2）若ｍ≠ａ且ｎ≠b，必经点与终点在横向相差，在纵向相差，z=。程序设计:／/带中转站的最短路线＃iｎclｕｄe＜stdio.ｈ>#includｅ<math.h>voiｄｍaiｎ(){doublea,b,c，d,m，ｎ,k，y,ｚ；prinｔf("请输入正整数ａ,b:＂）;scａnf("％ｌｆ,%lf＂,＆a,&b）；printｆ("请输入正整数m，ｎ:");scａnｆ("%lf,%ｌf"，&m,&n）;ｙ=1;iｆ(ａ*b>０)for(k=1;k<＝a;k+＋）y=y*(ｂ+ｋ)/k;/／计算C(ａ+ｂ,ａ)z=1;ｉf（(ｍ-ａ)*(n－b)!=0）{c=fabs(m－a）；d=fabs(n－b);for(k＝１;k＜=ｃ；k+＋)z=z*（d+k)/k;//计算Ｃ（｜m－a|＋|ｎ－b｜,｜m-a|)}pｒintf（＂不同最短路线条数为:%.0f\n"，y*ｚ);}数据测试:请输入正整数a,b:9，７请输入正整数ｍ,ｎ:20,１2不同最短路线条数为:４9９6９920请输入正整数a,b：２0,12请输入正整数m,n:9,７不同最短路线条数为：附无障碍无中转站的交通路线问题程序：//无障碍完整交通路线问题＃ｉｎｃluｄe<stdiｏ.h>vｏidmaｉn（）{ｉｎtk,ｍ,ｎ,x，y,z,f[５0]［50];pｒinｔf("请输入正整数m，n：")；scanf("%d，%d"，&m,&n);foｒ(x=１；x<=ｍ;x++）f[x][0]＝１；foｒ(ｙ=1;y<＝n;y＋+）f[０］[ｙ]=1;//拟定边界条件for(ｘ=1;ｘ＜=ｍ;x++)for（ｙ=1;y<=n;y++)//实行递推得目的值f（ｍ，n)f[x][y]=f[x－１][y]+ｆ[ｘ][ｙ-１];pｒinｔf("不同最短路线条数为:%d＼n＂,ｆ[m][n]);z=１;for（ｋ=1;k<=m；k+＋)z=z*(n+k)/ｋ;ｐriｎtf("不同最短路线组合数为:％d\ｎ",z);}请输入正整数m,n:7,1０不同最短路线条数为:19４484双码二部数序列试求双码二部数升序序列的第m项。测试数据：m=2０23;m=202３４设计1:把双码二部数升序序列的第ｍ项换算为n位的第m０项。注意到2位双码二部数共9*9=８1个；3位双码二部数共2*9*9=2*81个;……//求双码二部数升序序列的第m项#incluｄe＜stdio.h>#incｌudｅ<maｔh.h>ｖｏｉdmain(){inｔa,b,a0,ｂ０,i，n,ｍ,m0,la，lb,la0,lb０,s;priｎtf("请依次输入整数m:");sｃａnｆ（＂％d"，&ｍ);ｓ=0；n=0;while(s<m）｛n＋＋；ｓ＝s+n＊81;｝m0＝ｍ-（s-n*8１）;n++;s=0；//换算为n位的第m0项ｆｏｒ(a＝１;a＜=９；a＋+）／/高部数字a从小到大枚举｛for(la=1;lａ<＝ｎ-2；la＋+）/／高部位数la分3环节枚举{lｂ=n-lａ;for(ｂ=0；b＜＝a-1;b＋＋）{s＋+;／/变量ｓ记录个数if(s==ｍ0)//记录第m个数的信息｛ａ0＝a;ｂ0=b;la０＝lａ；lb0＝lｂ;}｝}ｌa=n-１;ｌｂ＝1;foｒ(b=0；b<=９;b++)if(a！=b)//当a=ｂ时跳过{s＋＋；ｉｆ(s==ｍ0){a0=a；b0＝b;la0＝ｌa；lb0=lb；}}for(ｌa＝n-２；la>=1；la－-){ｌｂ=n-la;ｆｏr(b=a+1；ｂ<=9;ｂ++){s++;if(s＝=ｍ0）{a０=a;b０=ｂ;la0=ｌａ；ｌb0=lb;｝}}}prｉntf(＂双码二部数升序序列的第%d个数为：",m）;fｏｒ（i=1;i＜＝lａ0;i＋+) prinｔf("%d",a０）;for（i=1；ｉ<＝ｌｂ0；i++)ﻩｐｒiｎｔｆ（"%ｄ＂，b0);prinｔｆ("\ｎ");prinｔｆ("(式中％d个％d,%d个%d)\n＂，la0,a0,ｌb0，b０）;}设计2:从ｎ=2位开始记录／/求双码二部数从小到大排列的第ｍ个数#inclｕde<stdｉo.h>voｉdmaiｎ（)｛intａ,b,a０，b0,i,ｍ,n,ｐ,lａ,ｌa0,lb０；ｐriｎtf("请输入整数m:"）;sｃanf(＂％ｄ",＆m）；n=1;ｐ=0;wｈilｅ(１）｛ｎ++;ｐ＋+;ａ=1;b=0；lａ＝1;/／默认n位第１个为1后ｎ-1个0if（p=＝m）{a0=a;b０=b；la0＝la;ｌb0=n－ｌa0;breａｋ;}while(la<ｎ-1｜|a<９||b<８){p＋＋;ﻩｉｆ(b＝=9）／/此时b不能增１,有以下2种选择if(la==１){a＋＋;ｂ=0;}／/①a增1后，b从0开始eｌsｅ{la--;b=ａ+1；}//②a段长增1后,b从a+１开始ｅlsｅｉf(ｂ!=a-１)b++；//a与la不变,b增１ elｓeif（la!=n-1）｛lａ+＋;b＝０;}//ａ段长增1后,ｂ从0开始ﻩelseｉf(b<8)b＋=２；／／ｂ增２跳过a=b情形ｉf(p==ｍ) {a０＝a；b0=b;la0=la;lｂ0=n－la0；break；}}ｉｆ(p＝＝m）ｂｒeak;}prinｔf("第%d个双码二部数为:%d(%d）％d(%d)\n",ｍ,ａ0，lａ0,b，lb0);prｉｎｔｆ("其中从小到大第%ｄ个数为：＂，m）;for（i=1;i<=ｌa0；i+＋） printf(＂％d",a０);fｏｒ(i=1;i<=lb0;ｉ＋+)ﻩｐrｉｎtf("%ｄ",b０);prｉntｆ（＂＼n＂);｝数据测试:请依次输入整数m:２023双码二部数升序序列的第202３个数为：5599９9９９(式中２个5,6个9)请依次输入整数m:202３4双码二部数升序序列的第２０234个数为:（式中4个8，1９个2)５求代数和设n为正整数,求和式中各项符号为二正一负，分母符号为一正一负。正整数n从键盘输入,输出和s四舍五入精确到小数点后5位。输入ｎ＝１00输出:输入n=2023输出：//求代数和1#include<stdio.h＞＃ｉnclude<mａth.h＞ｖoｉdmaiｎ（){longj,n;ｄoubletｓ,s;prｉntf（"请输入ｎ:");scanｆ("%d",&ｎ)；ｊ＝０;ts=0;s=０;whiｌe（j＜n){ｊ=j＋１；iｆ(j％2==0)ｔs=ts-(ｄｏuｂle)1／j；/／ts为各项的分母elsｅts＝ts+（dｏuｂle）1/j;ﻩif（j%３==０）ｓ=s－ｓｑrt(j)／ts;/／求代数和ｓﻩelｓes＝s+ｓqrt(ｊ)/ｔs;｝priｎtf("ｓ=%.5ｆ\n",s);}／/求代数和2#include<stdio．h>#iｎclude<ｍａth．h>ｖoｉdmaiｎ(）{doｕｂlｅj,n，ts，s;printf（"请输入ｎ:");scanf(＂%lfｄ＂,＆n);j=0;ｔs＝0;s＝0;ｗｈile(j<ｎ){ｊ=ｊ＋1；if(fmod（j,2)=＝0)ts=ts-1/j;//ｔｓ为各项的分母ｅlsets＝tｓ+1/j； if（fｍｏd（j，3)==0)ｓ=s-sｑｒt(j）／ｔs;／/求代数和ｓﻩelsｅs＝s+sqrt(j)/ts;}pｒｉntｆ("ｓ=%.5f\n",s)；｝请输入ｎ:１０0s=３24.74013请输入n:2０23ｓ＝２89２4．４8725请输入n:202３s=2８９89.22300变通：设2<ｎ≤202３,当n为什么值时，和s最接近2023？6合数世纪探求１．问题的提出20世纪的100个年号[19０1—2０23]中有13个素数,而21世纪的1０0个年号[２0２３,2100]中有14个素数。那么，是否存在一个世纪的100个年号中一个素数都没有?定义一个世纪的10０个年号中不存在一个素数，即100个年号全为合数的世纪称为合数世纪。设计程序探索第m(约定m<１00）个合数世纪。测试数据:(1)m=1(2)m=10２.设计要点应用穷举搜索，设立ａ世纪的的50个奇数年号（偶数年号无疑均为合数)为b，用ｋ试商判别b是否为素数,用变量ｓ记录这50个奇数中的合数的个数。对于a世纪,若ｓ＝５0，即50个奇数都为合数，找到a世纪为合数世纪,用n记录合数世纪的个数。当n＝m时打印输出a世纪。当n=ｍ时退出循环结束。３.合数世纪程序设计//探求第1个与第ｍ个合数世纪#inclｕde<stdiｏ.h>#ｉnclｕｄe＜ｍａｔh.h＞ｖoｉdｍaiｎ(){loｎga,ｂ,k;iｎtｍ,n，s,x;ｐｒｉntf("请拟定ｍ:");scanf（"%d",&ｍ);a=１;ｎ=0；wｈｉle(1){ａ++;s=0;／/检查a世纪for(b=a＊１00－９9;b<=a＊１00-１;b+=２)/／穷举a世纪奇数年号b｛x=0;for(ｋ=3；k＜＝ｓqｒt(b);k+=2)iｆ（ｂ%k==０){x=1；ｂreaｋ；｝if（ｘ==０）break;／/当前为非合数世纪时,跳出循环进行下一个世纪的探求ｓ=s+x;/／年号b为合数时,x=１，s增1}if(s==50)／／s＝50,即50个奇数均为合数 {n＋+; if（n＝=m)ﻩﻩpriｎtf(＂第%d个合数世纪为：%ld世纪。\n",n,a);}ﻩiｆ(n＝=m)bｒeａｋ;}}4.程序运营示例请拟定m:10第1个合数世纪为：167１9世纪。第１０个合数世纪为：58453世纪。16７19世纪尽管是最早的合数世纪，它的１00个年号为[1６7１801,1６719００]全为合数。这是一个非常漫长的年代，可谓天长地久,地老天荒!7分解质因数整数分解质因数是最基本的分解。例如，9０＝２＊3＊3*5，1960=2^３*５*7＾２，前者为质因数乘积形式，后者为质因数的指数形式。把指定区间上的所有整数分解质因数,每一整数表达为质因数从小到大顺序的乘积形式。假如被分解的数自身是素数，则注明为素数。例如,92=2*2*２3,91(素数!)。分解：1６7186１=58４5271＝(1)设计要点对每一个被分解的整数i,赋值给b(以保持判别运算过程中i不变），用k(从2开始递增取值）试商:若不能整除，说明该数k不是b的因数,k增1后继续试商。若能整除，说明该数ｋ是b的因数,打印输出"k*";ｂ除以k的商赋给b(b=b/k）后继续用k试商（注意,也许有多个ｋ因数)，直至不能整除,k增1后继续试商。按上述从小至大试商拟定的因数显然为质因数。循环取值k的终值如何拟定,一定限度上决定了程序的效率。终值定为i-1或i/２，无效循环太多。循环终值定为i的平方根ｓqrt(i)可大大精简试商次数，此时假如有大于sｑrt(ｉ）的因数(至多一个!),在试商循环结束后要注意补上，不要遗失。假如整个试商后b的值没有任何缩减,仍为原待分解数i，说明i是素数，作素数说明标记。(2）质因数分解乘积形式程序设计//质因数分解乘积形式#iｎcluｄｅ"ｍatｈ.h"#iｎｃｌudｅ<stdio.ｈ>vｏidmaｉｎ(){lｏｎｇintｂ,ｉ，k,ｍ,n,w＝０;ｐrintf("[m，n］中整数分解质因数（乘积形式）．\n＂);pｒintf("请输入ｍ,ｎ：＂)；ｓcanf("%ld，％ｌd",&m，＆n)；ｆｏr(i=m；ｉ<=ｎ;i++)//i为待分解的整数{printf(＂%ｌｄ＝",ｉ);b=ｉ;ｋ＝２;wｈiｌe（k＜=sｑｒt(i))//k为试商因数{iｆ(ｂ%ｋ==0){b=b／ｋ;ｉf（b>1）{printf("％ld*＂，k);cｏｎtinｕe；//ｋ为质因数,返回再试｝if(b=＝1)printf（"%ｌd\n＂,k）;｝k++；}if(b>1＆&b＜i)prｉntf("%ｌd\n",ｂ);//输出大于i平方根的因数if(b=＝i){ｐrｉｎtf("(素数！)＼n");w+＋；｝//b=ｉ,表达i无质因数｝prｉntf("其中共%d个素数.\n",ｗ);｝１6７18６1=３*31＊1７9775８45276=2＊２*223＊6553［m，n]中整数分解质因数（乘积形式)请输入m,n:16７18０１，16718９９(验证第1个倒数世纪年号）16７1801=３*２３*2４229１６7180２=2*1１*７59911671803＝7*2388２9１6718０４=2*２*3*3＊4６4３916７1８0５＝5*23９２*７６9*10８71671807=３*5572６916718０８=2*2＊2*２*２＊2*2*37*3５3１671809=599＊2７9１1671810=2*３*5*７*19*４１916718１1=137*12２031671８12=2*2*４1７9５３167１81３=3*3*3*11＊13＊４3316７181４=2＊17＊４9１71１67181５=5*３34３631671８16=2*2*2*3*４１*169９16７1817=７*２41＊99116７18１8=２*８359０9167１819=３*５5７273167１82０=２*２*5*８3591１671８21=29*57649１671822=２*3*3＊131*７0９167１823=1９1*87５31６71８24=2*2＊2*2*7*１1*２3*5９１6７1825=3*5*5*222９116７1826=2＊１3*64３0116718２７=61*274071671828＝2＊2*3*12７*109７1６７182９=19*879９1１６７183０=2＊5＊３１*5３931６718３1=3*3*7*7*17*２231６71832＝2*2＊2*５3*39４31671８３３=１289*12971６７1834=２＊3*278639１6７１835=５*11*１13*269１671836=２*２*４１79591671837=3*4７＊71*167１671838=2*7*１194171６7183９=13*128６０3１６７1840=２*2*2*2*2*3*3*３＊３*3*5*4３１６71８41=1２23*１3６7１６71８42=2*１0９*766916７1８４３=3*5５７281167１844=2*2*41７96116７18４5=5*7*37*１29１1671846＝2*3*1１*７３*3４7１671８４７＝23＊7268９167184８=2*2*2*１７＊19＊6471６７１849=3＊3*4３１*4３11671８５0=2*５*5＊29＊１1５31671851＝６7＊24953167１852=2*2*3＊7*１3*15３1１6718５３＝101*１6５531671854=2*835927１6718５5=３*５*２27*49116７1856=2*2＊2*2*1０44911671８5７＝11