2023年程序設(shè)計(jì)競賽選拔賽實(shí)訓(xùn)

２02３程序設(shè)計(jì)競賽選拔賽（實(shí)訓(xùn)８)1、排列數(shù)由1個(gè)“１”,2個(gè)“2”,k個(gè)“3”(１≤k≤6)能組成多少個(gè)不同的排列?輸入k,輸出排列個(gè)數(shù)。ｋ=4,輸出：ｋ＝5,輸出:（1)設(shè)計(jì)要點(diǎn)注意到1個(gè)“１”,２個(gè)“2”，ｋ個(gè)“3”組成k+3位數(shù),一方面通過k+2個(gè)１0相乘計(jì)算ｋ+3位數(shù)的起點(diǎn)ｂ=10^（k+2)，為枚舉提供范圍t(ｂ—4＊ｂ-1)。為了檢測k+3位數(shù)t具有多少個(gè)數(shù)字1、2、３，每個(gè)ｋ+3位整數(shù)ｔ賦給ｄ(以保持ｔ不變),然后通過k+3次求余先后分離出t的k＋3個(gè)數(shù)字c:if(ｃ＝=1)f++,記錄整數(shù)t中數(shù)字1的個(gè)數(shù)f；if（c=＝2)g++,記錄整數(shù)t中數(shù)字２的個(gè)數(shù)ｇ;if(c==3)h++,記錄整數(shù)t中數(shù)字3的個(gè)數(shù)h。檢測每一個(gè)k＋3位整數(shù):若f=1anｄg＝2anｄh＝k,則應(yīng)用ｓ進(jìn)行記錄。最后輸出所得排列個(gè)數(shù)s。（2)程序設(shè)計(jì)//排列數(shù)#incluｄe<sｔｄｉo．h>ｖoｉdmain(){intｃ，ｆ,g,h,i,j，k;lonｇｂ,d,ｓ,t;pｒintf（"請(qǐng)輸入數(shù)字3的個(gè)數(shù)k(1≤ｋ≤6):＂);scａnf("%d"，＆k);ｂ＝1;s=0；for(i=１;i<=k＋2;i+＋)b＝ｂ*10;//計(jì)算k+3位數(shù)的起點(diǎn)ｆor(ｔ=b;ｔ<=４＊b-1；t+＋)／／枚舉首位為３的ｋ+３位數(shù){d=t；f=0;g=0;h=0；fｏr(j=1;ｊ＜=k+3；j++)?{ｃ=d%10;d=d/1０;if（c=＝1)f++;／/記錄數(shù)字1的個(gè)數(shù)if(c==2)g＋+;/／記錄數(shù)字2的個(gè)數(shù)if（c==3)h++;//記錄數(shù)字3的個(gè)數(shù)?｝ if(f=＝1＆&g=＝2&&ｈ==k)ｓ＋+;//記錄個(gè)數(shù)s ｝ｐｒiｎtf(＂s=%lｄ\n＂,s);}(3)程序運(yùn)營示例請(qǐng)輸入數(shù)字3的個(gè)數(shù)k（1≤ｋ≤6）:４s=10５請(qǐng)輸入數(shù)字3的個(gè)數(shù)k(１≤k≤6):5ｓ=１68（4）拓廣若需求k=１0０時(shí)的排列數(shù)，如何求？1）注意到一排k個(gè)“3”的空位共k+1個(gè)。這k+1個(gè)選2個(gè)空位共C（k+1，2）種組合，每一空位放置１個(gè)“2”。這ｋ+1個(gè)選1個(gè)空位共C(k+1，１)種組合，空位中放置２個(gè)“2”。2）注意到一排ｋ個(gè)“3”與2個(gè)“２”的空位共k＋3個(gè)。這ｋ+３個(gè)選１個(gè)空位共C(k+3，1）種組合，空位中放置1個(gè)“1”。3)因而得不同的排列數(shù)為：（C(k+1,2)+Ｃ（k+1，１））*Ｃ(k＋3,1)=(k+1）*(k+2)＊(k+3)/2/／排列數(shù)#inclｕｄe<sｔdiｏ.h>voiｄmaｉｎ(){inｔk;lonｇs;pｒintf("請(qǐng)輸入數(shù)字3的個(gè)數(shù)ｋ："）；ｓcanｆ("%ｄ＂，&k）;s＝（ｋ＋1）*(k+2)*（k+３)／2;prinｔｆ（"ｓ=％ld＼n"，s);｝請(qǐng)輸入數(shù)字3的個(gè)數(shù)k:100s＝5３０55３(５)實(shí)訓(xùn)１計(jì)算由２個(gè)“1”、2個(gè)“2”、ｋ個(gè)“3”的排列數(shù)。計(jì)算由3個(gè)“1”、2個(gè)“2”、k個(gè)“3”的排列數(shù)。測試數(shù)據(jù):ｋ＝5０2、求最值設(shè)ｎ為正整數(shù)，,式中各項(xiàng)符號(hào)為二正一負(fù)。求當(dāng)n為多大時(shí),s(ｎ）最接近指定的正整數(shù)a?輸入a,輸出ｓ（n)最接近a的n,s(n）。（1）輸入1000,輸出:(2）輸入20２3,輸出:解:一般地求當(dāng)n為多大時(shí)，s(n)最接近正整數(shù)ａ？其中a從鍵盤輸入a。／/ｓ(n)=１＋1/(1+1/2）－1/（1+１/2＋１/３）+.．.+１／(1+1/2+...＋１/n）#ｉncluｄe<ｓtdio.h＞#iｎｃlude<ｍａt(yī)h.h>ｖｏidmain(){ｌonga，n,n1；ｄｏublem,ｔｓ,s,ｓ1;pｒｉｎtf("請(qǐng)輸入a:");ｓcanf（"%d"，&a)；n＝０;ｔｓ=0;ｓ=0;m=100000.0;while(ｓ<a＋1０){n=ｎ+１;ts=ts＋（ｄoｕbｌe）1/n;//ts為各項(xiàng)的分母?if(n％3＝=0)s=s-1/ｔs；/／求代數(shù)和s?ｅlsｅs=s+１／ts;if（ｆａbｓ(s－a)＜ｍ)//比較,當(dāng)ｎ=n1時(shí)，和s1最接近a{m=fａｂｓ(s-a);n1=n；s１=s;｝}prｉnｔf("ｎ=%ld，ｓ(%d）=％ｆ＼n",ｎ１，n１,s1）;｝請(qǐng)輸入a:10０0n＝２9126,ｓ(29１2６)=９99．959９8９請(qǐng)輸入a：２０23ｎ＝6337６,s(63376）=20２3.040087實(shí)訓(xùn)2：設(shè)ｎ為正整數(shù),,式中各項(xiàng)符號(hào)為二正一負(fù)，分母符號(hào)一正一負(fù)。求當(dāng)n為多大時(shí)，s(ｎ）最接近指定的正整數(shù)ａ？輸入a,輸出s(n)最接近ａ的n,ｓ(ｎ)。測試數(shù)據(jù):a=20２33、倒立的勾股數(shù)把求勾股數(shù)變通為求倒立的勾股數(shù)。定義滿足方程式的正整數(shù)x,y，z，稱為一組倒立的勾股數(shù)。試求指定區(qū)間[a,b]內(nèi)的倒立勾股數(shù)組。(1)求指定區(qū)間[30,1０0］內(nèi)的倒立勾股數(shù)組.(2)求指定區(qū)間[1００,20０]內(nèi)的倒立勾股數(shù)組.（1)設(shè)計(jì)要點(diǎn)顯然,倒立勾股數(shù)組中x,y不也許相等,且x,y＞ｚ。為避免反復(fù),不妨設(shè)x＞ｙ>z。在指定區(qū)間[ａ,b]上根據(jù)x，y,ｚ的大小關(guān)系設(shè)立循環(huán):z從ａ至b－2,y從z＋１至b-1,x從ｙ+1至b。對(duì)每一組ｘ,y,z,假如直接應(yīng)用條件式1／(x*x)＋1/(ｙ＊y)＝1/(z＊z)作判別,因分?jǐn)?shù)計(jì)算的不可避免的誤差,有也許把一些成立的倒立勾股數(shù)組解遺失，即導(dǎo)致漏掉。注意到上述分?jǐn)?shù)條件式作通分整理得到的下面的正整數(shù)條件式z＊z*(x＊x+y＊y）=x＊x＊y*y程序中為防止發(fā)生解的漏掉,應(yīng)用上述整數(shù)條件作判別是適宜的。(2)求區(qū)間內(nèi)倒立勾股數(shù)程序設(shè)計(jì)／/求指定區(qū)間內(nèi)倒立勾股數(shù)組＃ｉｎclude<stdiｏ.h>#include<math.h＞voidmａｉｎ(){iｎtａ,b,n;ｌongｘ，y,ｚ;prｉntｆ(＂求指定區(qū)間[a，ｂ]內(nèi)倒立的勾股數(shù)組.");ｐrｉntf(＂＼n請(qǐng)輸入?yún)^(qū)間［ａ,b]的上下限a,ｂ:");sｃanｆ("%d,％ｄ",&ａ,&ｂ);ｐrintｆ(＂\n區(qū)間[％d,%d]中倒立的勾股數(shù)組有:＼n",a，b)；n＝0;foｒ(ｚ=a;ｚ＜=b－2;z++)for(y＝z+１;ｙ<=ｂ-1；y++)ｆｏr（x=ｙ＋1；x<=b;x++)ｉf(z＊z*（x＊x+y＊ｙ)==ｘ*ｘ*y*y)／／滿足倒立勾股數(shù)條件時(shí)輸出{n++;printｆ("1/%lｄ^2＋1/%ld^2=1/%ｌｄ^2\ｎ"，ｘ,y,ｚ);}ｐrintf("共%ｄ組勾股數(shù)．"，n）；}（3）程序運(yùn)營示例區(qū)間[30,100]中倒立的勾股數(shù)組有:1/60^２+1/４5^2=1/36^21/80＾2＋１/60^2=1/４8^２１/1０0^２+１／75＾2=1／6０＾２共3組勾股數(shù).區(qū)間[100,200]中倒立的勾股數(shù)組有:1/１８０^２＋1/１35^2=1／108^21／200^２＋1/１50＾２=1/1２0^２共２組勾股數(shù)．4、雙和數(shù)組尋求6個(gè)互不相等的正整數(shù)a,ｂ,ｃ,d，e,f并提成(ａ,b，c)與(ｄ,e，f）兩個(gè)組,若這兩組數(shù)具有以下兩個(gè)相等特性:則把數(shù)組(a,ｂ,c)與(d,e,f）稱為雙和數(shù)組(約定a＜ｂ<ｃ,d<e＜f,a<d)。1）設(shè)a+b+c＝d+e+f=s,存在雙和數(shù)組,ｓ至少為多大?２）當(dāng)ｓ=9８時(shí)有多少個(gè)不同的雙和數(shù)組?(1)求解要點(diǎn)從鍵盤輸入整數(shù)s,因6個(gè)不同正整數(shù)之和至少為21,即輸入整數(shù)s≥1１。設(shè)立a,ｂ與d,e循環(huán)。注意到a+b+c=s，且ａ<b<c,因而a,b循環(huán)取值為:a:１——(s－3)/3。因b比a至少大１,c比a至少大２。b：a+1——(s－ａ-１)/2。因c比b至少大1。c=s-a=b。設(shè)立d,e循環(huán)基本同上,只是d>a，因而d起點(diǎn)為a+1。把比較倒數(shù)和相等1/a+1／b+1/ｃ=１／d+１/e+１／f轉(zhuǎn)化為比較整數(shù)相等ｄ*e*f*(b*ｃ+c*a＋a*b)＝ａ＊ｂ＊c*(e*f+f*d+d*e)(*）若上式不成立,即倒數(shù)和不相等,則返回。同時(shí)注意到兩個(gè)3元組中若部分相同部分不同，不能有倒數(shù)和相等，因而可省略排除以上6個(gè)正整數(shù)中是否存在相等的檢測。若式(＊)成立,打印輸出和為s的雙和數(shù)組，并用ｘ記錄解的個(gè)數(shù)。(2）C程序設(shè)計(jì)／/雙和數(shù)組探索＃iｎcｌude<stdiｏ.h>#ｉncluｄe<math.h>voidｍａiｎ(）{ｉｎｔa,b,c,d,ｅ,ｆ,ｘ，ｓ;for(ｓ＝21；s<＝10０;s＋+){ｐｒinｔf("s＝%ｄ:＼n",s）;x=０；fｏr(a＝１；a<=(s－3）/3;a++)ｆor(b=a+1;b<=(s－a-1)／２;ｂ+＋）for(d=a＋1;d＜=(s-３)/3;d++)foｒ(e=ｄ+１;e<=(ｓ-ｄ－1)/2；e+＋){c＝ｓ-a-b;f=s-d－e；if(a＊b*c*(e＊f＋f*d+d*e)!＝d*ｅ＊f*(b＊c＋c*ａ+a*b)）continuｅ;//排除倒數(shù)和不相等x++;pｒintf("％3ｄ:(%２d,%2d,％２d)",x，a，b,ｃ);ｐrｉｎｔf(＂(%２d,％2ｄ，%2ｄ)\n"，d,e,f);}if(ｘ=＝0）printf("無解！\n"）；}}(3）程序運(yùn)營結(jié)果與討論s=26:1:(４,１０，1２)(5,6,１5）s＝98：1：(2,3６,60)(3,５，90）2：(７，28，63)（８,１８,7２)３:(7，35,56)(8,2０，70)４：(1０，33,55)（１2,20,６6)(4）實(shí)訓(xùn)3尋求6個(gè)互不相等的正整數(shù)ａ,b，ｃ,d，e,f并提成(a,b,c)與(ｄ,e,ｆ)兩個(gè)組,若這兩組數(shù)具有以下兩個(gè)相等特性:則把數(shù)組（a,b,c)與(d，e,f)稱為和積數(shù)組(約定a＜ｂ<c,ｄ<e＜ｆ,a＜d）。1）設(shè)a+b+ｃ＝d＋e+f=s,存在和積數(shù)組,s至少為多大？2）當(dāng)s＝89時(shí)有多少個(gè)不同的和積數(shù)組？５、ｍ位完美平方數(shù)用0，１,2,．..,9能組成多少個(gè)沒有反復(fù)數(shù)字的m(1<m≤１0)位平方數(shù)?輸入m，輸出沒有反復(fù)數(shù)字的m位平方數(shù)的個(gè)數(shù)，并輸出其中最大的。m=７，輸出：ｍ=10,輸出:／/用0，1,２,．．.,９組成沒有反復(fù)數(shù)字的m位平方數(shù)#incluｄe<ｍath.h>#incｌｕdｅ<sｔdｉｏ.h>voidmain(){iｎtｋ，m,n,t，f[10]；dｏublｅａ，b，c,d,w，x,a1，d１;prinｔf("請(qǐng)擬定整數(shù)m:")；scanf(＂%d",&m）；x=1．0;ｆor（k=２；k<=m;k++）x＝x*10；/／擬定m位數(shù)的起點(diǎn)xn＝0;b=(int）pow(x,0.5）；c＝ｐｏw(10*x-1,0.5）；ｆor(ａ=b+１;a<＝c;ａ++){d=a*a；w=d；／／保證d為m位平方數(shù)ｆor（ｋ＝０;k<=9;ｋ+＋）ｆ[k］=0;whiｌe(ｗ>0){t=(ｉnt)fmod(w,1０);ｆ［t]=f[t]+1；ｗ=floor(w/10);}ｆｏr(t＝0,k＝0；k＜＝9;ｋ++)ｉf(ｆ［ｋ]>1){t=1；break;}//測試平方數(shù)是否有反復(fù)數(shù)字if(t＝=０）//測試平方數(shù)中沒有反復(fù)數(shù)字{n++;ｄ１=d;a1=a;}}pｒｉntf("共可組成%ｄ個(gè)沒有反復(fù)數(shù)字的%d位平方數(shù)."，n,m)；prｉｎｔf("其中最大的為:％.0ｆ=%.0ｆ^2\ｎ",d1,a1);}請(qǐng)擬定整數(shù)ｍ:７共可組成1２3個(gè)沒有反復(fù)數(shù)字的７位平方數(shù).其中最大的為:９8７２164=314２^2請(qǐng)擬定整數(shù)m:１０共可組成8７個(gè)沒有反復(fù)數(shù)字的10位平方數(shù).其中最大的為:＝99066^2實(shí)訓(xùn)４:用0,1,2,...,９能組成沒有反復(fù)數(shù)字的m(１<m≤10）位平方數(shù)的個(gè)數(shù)為ｓ(m)．問:（1）求s(10)，即求出沒有反復(fù)數(shù)字的１0位平方數(shù)的個(gè)數(shù)。(2)當(dāng)m為多大時(shí)，沒有反復(fù)數(shù)字的ｍ位平方數(shù)個(gè)數(shù)ｓ(ｍ)最大？６、最小01串積程序設(shè)計(jì)愛好者A，B進(jìn)行計(jì)算游戲:B任給一個(gè)正整數(shù)b,Ａ尋求另一個(gè)整數(shù)a,使a與b的積最小且全為0與1組成的數(shù)。例如,B給出整數(shù)24，A尋求整數(shù)ａ:４６25，使得a*b的最小01串積為:１11000輸入b,輸出a與最小01串積。b=24,輸出：ｂ＝2023,輸出：(1)對(duì)ａ枚舉考慮到a與積d也許大于１0位,用雙精度型。對(duì)ａ遞增枚舉,檢測積d=a＊ｂ是否為01串//01串積對(duì)a枚舉#iｎcｌｕｄe＜ｍaｔh.h>#include＜ｓtdio.h＞ｖoｉdｍain（)｛ｌoｎgｃ,t;doubleａ，ｂ,d,j;pｒintf("B給出整數(shù)b:");ｓcaｎf("%lf",&b);a＝１；whilｅ(１）{a++;d=a*b;ｊ＝ｄ；t＝0；whiｌe(j>０)//分離積的各個(gè)數(shù)字c{c＝(ｉnt)fｍｏd(ｊ,1０）；ｊ=fｌoｏr(j/10); if(c>1){t=１;break;｝／/檢測是否具有0,１以外的數(shù)字?} if(t==0)?{prinｔｆ(＂A尋求整數(shù)a:%.0ｆ：\n",ａ); pｒintf(＂a*b的最小0１串積為:%.0f＼n"，d）;?ｂreak;?｝}}B給出整數(shù)b：73Ａ尋求整數(shù)a:137:a＊b的最小01串積為:100０1B給出整數(shù)b:54A尋求整數(shù)a::a*b的最小01串積為:(2）二進(jìn)制枚舉，應(yīng)用余數(shù)判別。1)注意到０1串積為十進(jìn)制數(shù),應(yīng)用求余運(yùn)算“%”可分別求得個(gè)位“１”,十位“1”,…,分別除以已給b的余數(shù),存放在c數(shù)組中：c（１)為１,ｃ(2）為10除以b的余數(shù)，c(3)為1００除以ｂ的余數(shù)，…。2）要從小到大搜索０１串,不反復(fù)也不漏掉，從中找出最小的能被b整除01串積。為此,設(shè)立k從1開始遞增,把k轉(zhuǎn)化為二進(jìn)制，就得到所需要的這些串。但是，這時(shí)每個(gè)串不再看作二進(jìn)制數(shù)，而要看作十進(jìn)制數(shù)。3）在某一k轉(zhuǎn)化為二進(jìn)制數(shù)過程中,每轉(zhuǎn)化一位a(ｉ)(0或1），求出該位除以b的余數(shù)a(ｉ)*ｃ（ｉ)，通過累加求和得k轉(zhuǎn)化的整個(gè)二進(jìn)制數(shù)除以ｂ的余數(shù)s。4）判別余數(shù)s是否被ｂ整除:若s％b＝0，即找到所求最小的0１串積。a從高位開始除以b的商存儲(chǔ)在d數(shù)組,實(shí)行整數(shù)除法運(yùn)算:x=ｅ*10＋ａ［j];//e為上輪余數(shù),x為被除數(shù)ｄ[j]=ｘ／b;/／d為ａ從高位開始除以ｂ的商ｅ=x%b；//e為試商余數(shù)去掉d數(shù)組的高位“0”后,輸出d即為所尋求的數(shù)。最后從高位開始打印a數(shù)組，即為01串積。(3)程序設(shè)計(jì)／/01串積二進(jìn)制枚舉#include<sｔdｉo.h>voidmaｉn(){ｉntb,e,ｉ,j,t,x,a[2023],d［202３]，c[2023];longk,s;priｎtｆ("B給出整數(shù)b：");scaｎf（"%d",&b）;c[1]=1;for(i=２；ｉ<2０0；i++）c[i]＝1０*c[