基本算法題庫(kù)個(gè)基本算法

程序設(shè)計(jì)試題及答案（備注：試題難度評(píng)價(jià)采取五級(jí)評(píng)價(jià)體系，分基礎(chǔ)、容易、一般、稍難、難五個(gè)等級(jí)，其中的一、二、三級(jí)都屬于程序設(shè)計(jì)的基礎(chǔ)試題級(jí)別，同學(xué)們稍加思考均有能力求得正確解答，對(duì)于四級(jí)試題屬于程序設(shè)計(jì)試題基礎(chǔ)級(jí)別的思考題，五級(jí)難度試題在此沒(méi)有涉及，在程序設(shè)計(jì)高級(jí)試題中另行講解。對(duì)于基礎(chǔ)和容易兩個(gè)級(jí)別的程序設(shè)計(jì)試題，若能夠給出語(yǔ)句分類(lèi)（如 If條件語(yǔ)句、條件語(yǔ)句嵌套、循環(huán)語(yǔ)句、多重循環(huán)語(yǔ)句等）的將盡量給出。若屬于 13 大類(lèi)別的將盡量標(biāo)注。）程序設(shè)計(jì)試題幾大分類(lèi)：1、 素?cái)?shù)類(lèi)問(wèn)題（求素?cái)?shù)的幾種算法）：2、 數(shù)據(jù)排序問(wèn)題（數(shù)據(jù)排序的幾種方法）：3、 最大公約數(shù)和最小公倍數(shù)問(wèn)題（幾種算法）：4、 公式求解類(lèi)問(wèn)題（如求圓周率 、自然常數(shù) e、解方程等等）：5、 編號(hào)相反處理問(wèn)題：6、 約瑟夫問(wèn)題（或猴子選大王問(wèn)題、密碼問(wèn)題）：7、 回文數(shù)問(wèn)題：8、 高精度數(shù)值計(jì)算問(wèn)題：9、 數(shù)值計(jì)算問(wèn)題：10、 進(jìn)制相互轉(zhuǎn)換問(wèn)題：11、 字符串倒置問(wèn)題：12、 排列與組合類(lèi)問(wèn)題：13、 因子、質(zhì)因子（質(zhì)因數(shù)）類(lèi)相關(guān)問(wèn)題：答案部分：（程序設(shè)計(jì)的源程序沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)答案，實(shí)現(xiàn)程序的算法也是多種多樣，但結(jié)果是唯一的，算法也有優(yōu)劣之分，一個(gè)程序的優(yōu)劣，關(guān)鍵在于是否找到了第 頁(yè) 共 90 頁(yè)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)程序設(shè)計(jì)試題答案部分 第 2 頁(yè) 2好的算法，以下程序和算法不一定就是最佳算法和最佳程序，只能僅供參考，希望同學(xué)們能夠?qū)δ承┏绦蛱岢龈玫乃惴▉?lái)改進(jìn)程序）（經(jīng)常碰到的判斷是否為素?cái)?shù)、是否為回文數(shù)、求兩個(gè)數(shù)的最大公約數(shù)、求兩個(gè)數(shù)的最小公倍數(shù)等問(wèn)題的子函數(shù)源程序，請(qǐng)務(wù)必記住?。? 判斷是否為素?cái)?shù)，若是素?cái)?shù)則返回 true，若不是素?cái)?shù)則返回 false：function prime(x:longint):boolean;varj,y:longint;beginprime:=true;if xai-j+1 thenbegin huiwen:=false; exit; end;end;3 求最大公約數(shù)子函數(shù)，返回兩個(gè)正整數(shù)的最大公約數(shù)，采用輾轉(zhuǎn)相除法算法；function gcd(a,b:longint):longint;beginif b=0 then gcd:=aelse gcd:=gcd(b,a mod b);end;4 求最小公倍數(shù)：lcm=a*b div gcd(a,b);（以下程序設(shè)計(jì)試題來(lái)自?shī)W賽經(jīng)典（語(yǔ)言篇）第 2 章 基本語(yǔ)句與程序結(jié)構(gòu)例題部分：1、 求梯形的面積。（梯形面積公式： ）1()2Shab（，測(cè)試數(shù)據(jù) 12、 求一元二次方程 ax2bxC0 的兩個(gè)實(shí)根。（求根公式：）1,24bacx（，測(cè)試數(shù)據(jù) a1，b5，c6；答案：x 12、x 23）3、 輸入一個(gè)三位的自然數(shù)，然后把這個(gè)數(shù)的百位與個(gè)位對(duì)調(diào)，輸出對(duì)調(diào)后的結(jié)果。 （） 4、 輸入三個(gè)數(shù) a、b 、c，首先判斷這三個(gè)數(shù)能否構(gòu)成三角形，若能，則求出三角形的面積。第 頁(yè) 共 90 頁(yè)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)程序設(shè)計(jì)試題答案部分 第 4 頁(yè) 4（提示：海倫公式 ，其中 ，()()Sdabdc2abcda、b、c 為邊長(zhǎng)）（，If 條件語(yǔ)句，測(cè)試數(shù)據(jù) a5，b6，c7；答案： 14.7）5、 從鍵盤(pán)讀入三個(gè)數(shù)，按從大到小的順序把它們打印出來(lái)。（，If 條件語(yǔ)句）6、 輸入三角形的三邊，判斷它是否是直角三角形。（，If 條件語(yǔ)句，測(cè)試數(shù)據(jù) 13、4、5；24、5、 6；答案 1Yes；2No ）7、 編寫(xiě)一個(gè)根據(jù)用戶(hù)鍵入的兩個(gè)操作數(shù)和一個(gè)運(yùn)算符，由計(jì)算機(jī)輸出運(yùn)算結(jié)果的程序。（）8、 輸入一個(gè)年號(hào)，判斷它是否為閏年。（，If 條件語(yǔ)句，測(cè)試數(shù)據(jù) 11900；22000；32008 ；答案：1No；2Yes ；3Yes ）9、 編程計(jì)算 S123 100。（，循環(huán)語(yǔ)句， 答案：5050）相關(guān)練習(xí)：（1） ； （2） ；130 2210S（3） ； （4）246S；14701S（相關(guān)練習(xí)答案：（1）5.19（保留 2 為小數(shù)）；（2）338350；（3）2550；（4）1717）10、 根據(jù)公式 ，計(jì)算圓周率的 值。2221163n（，循環(huán)語(yǔ)句，測(cè)試數(shù)據(jù) n10000；答案：3.1414971639）program e;vari:longint;s:real;beginwriteln; s:=0;for i:=1 to 10000 do s:=s+1/(i*i);writeln(sqrt(6*s);第 頁(yè) 共 90 頁(yè)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)程序設(shè)計(jì)試題答案部分 第 5 頁(yè) 5end.11、 計(jì)算 n!。（n!123n ，取 n10）（，循環(huán)語(yǔ)句，10！3628800）12、 已知一對(duì)兔子，每個(gè)月可以生一對(duì)小兔，而小兔過(guò)一個(gè)月后也可生一對(duì)小兔。即兔子的對(duì)數(shù)是：第一個(gè)月 1 對(duì)，第二個(gè)月 2 對(duì)，第三個(gè)月3 對(duì)，第四個(gè)月 5 對(duì)，假設(shè)兔子的生育期是 12 個(gè)月，并且不死，問(wèn)一年后，這對(duì)兔子有多少對(duì)活著的后代？（Fibonacci 數(shù)列問(wèn)題）（，循環(huán)語(yǔ)句， 1、2、3、5、8、13、21、34、55、89、144、233；答案 233）13、 求兩個(gè)整數(shù) a 與 b 的最大公約數(shù)和最小公倍數(shù)。（，循環(huán)語(yǔ)句、If 條件語(yǔ)句，測(cè)試數(shù)據(jù) 16 和 24，最大公約數(shù) 8，最小公倍數(shù) 48）14、 利用格利高公式求 。 ，直到最后一項(xiàng)的值小14357于 106 為止。（，循環(huán)語(yǔ)句） （答案：3.1415946569E+00）program e2_32;varn,fh:longint;s,t,p:real;beginwriteln; n:=1; s:=0; t:=1; fh:=1;while (abs(t)=1e-6) dobegin t:=fh/n; s:=s+t; n:=n+2; fh:=-fh; end;p:=4*s;writeln(pi=,p);end.相關(guān)練習(xí)：利用公式 ，求 。1183579（計(jì)算前 10000 項(xiàng)時(shí)，答案為 3.1415426536）program e;var第 頁(yè) 共 90 頁(yè)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)程序設(shè)計(jì)試題答案部分 第 6 頁(yè) 6i,a,b:longint;x,s:real;beginwriteln; s:=0;for i:=1 to 10000 do begin a:=(4*i-3); b:=(4*i-1); s:=s+1/(a*b); end;writeln(8*s);end.15、 求 100999 中的水仙花數(shù)。（若三位數(shù) ABC，ABCA 3B 3C 3，則稱(chēng) ABC 為水仙花數(shù)。例如 153，1 35 33 3153，則 153 是水仙花數(shù)。） （，循環(huán)語(yǔ)句）（答案：153、370、371、407）program e12;vari,a,b,c:integer;beginwriteln;for i:=100 to 999 dobegina:=i div 100;b:=(i mod 100) div 10;c:=i mod 10;if i=a*a*a+b*b*b+c*c*c then write(i:8);end;end.16、 試編寫(xiě)能夠打印輸出如下圖形的程序。（，循環(huán)語(yǔ)句）AAAAAAAAAAAAAAAAAAAAAAAAAprogram e;第 頁(yè) 共 90 頁(yè)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)程序設(shè)計(jì)試題答案部分 第 7 頁(yè) 7const n=5;vari,j:integer;beginwriteln;for i:=1 to n dobeginwrite(:i);for j:=1 to (n-i)*2+1 do write(A);writeln;end;end.17、 四個(gè)學(xué)生上地理課，回答我國(guó)四大淡水湖大小時(shí)這樣說(shuō)：（）甲：“最大洞庭湖，最小洪澤湖，鄱陽(yáng)湖第三?！币遥骸白畲蠛闈珊钚《赐ズ?，鄱陽(yáng)湖第二，太湖第三?！北骸白钚『闈珊?，洞庭湖第三?！倍。骸白畲筵蛾?yáng)湖，最小太湖，洪澤湖第二，洞庭湖第三。”對(duì)于每個(gè)湖的大小，每個(gè)學(xué)生僅答對(duì)一個(gè)，請(qǐng)編程確定四個(gè)湖的大小。習(xí)題部分：1、 已知三角形的兩邊 a、b 和夾角 jc 的值，求第三邊（已知條件由鍵盤(pán)輸入）。 （）（提示：余角公式 ）22coscab（測(cè)試數(shù)據(jù)：輸入 a3、b4、jc90； 輸出 5）program e2_5;vara,b,c,jc:real;beginwriteln(input a,b,jc:); readln(a,b,jc);c:=sqrt(a*a+b*b-2*a*b*cos(pi*jc/180);writeln(c:8:2);第 頁(yè) 共 90 頁(yè)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)程序設(shè)計(jì)試題答案部分 第 8 頁(yè) 8end.2、 編寫(xiě)程序把一個(gè)四位整數(shù) 3581 顛倒成 1853。（）program e;const n=3581;vara,b,c,d:integer;beginwriteln;a:=n mod 10;b:=(n div 10) mod 10;c:=(n div 100) mod 10;d:=n div 1000;writeln(a,b,c,d);end.相關(guān)練習(xí)：任意輸入一個(gè)正整數(shù)，顛倒輸出該數(shù)。program e;varn:longint;beginwriteln; writeln(input a integer number:); readln(n);repeatwrite(n mod 10); n:=n div 10;until n=0;end.3、 輸入 a、b 、c 三個(gè)數(shù)，打印出最大者。（，If 條件語(yǔ)句）program e;vara,b,c:real;beginwriteln(input three number for a,b,c:);readln(a,b,c);第 頁(yè) 共 90 頁(yè)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)程序設(shè)計(jì)試題答案部分 第 9 頁(yè) 9if (ab)and(ac) then writeln(a);else if (ba)and(bc) then writeln(b);else writeln(c);end.4、 從鍵盤(pán)讀入兩個(gè)數(shù)，比較其大小，把大數(shù)置于 x，小數(shù)置于 y。請(qǐng)?jiān)O(shè)計(jì)實(shí)現(xiàn)該功能的程序。（，If 條件語(yǔ)句）（程序略）5、 輸入三個(gè)數(shù)，判斷以這三個(gè)數(shù)為邊能否組成一個(gè)三角形。若不能，則給出適當(dāng)信息；若能，則進(jìn)一步判斷它們構(gòu)的是銳角三角形、直角三角形還是鈍角三角形，并輸出其特征（等邊、等腰、直角、一般）、求其面積。 （，If 條件語(yǔ)句）（算法分析：對(duì)于判斷是銳角、直角、還是鈍角三角形，只需判斷最大邊的平方與其余兩邊的平方和的大小比較即可，小于則為銳角、等于則為直角、大于則為鈍角。）（測(cè)試數(shù)據(jù)：11、2、3；23、4、5；3）4、4、7；45、5、5；答案：1No；2 直角、面積 6.00；3 鈍角、等腰、面積 6.78；4 銳角、等邊、面積 10.83）program e;vara,b,c,t,s,d,ja,jb,jc:real;beginwriteln(input three number for a,b,c:);readln(a,b,c);if ac)or(a=c)and(ca) then第 頁(yè) 共 90 頁(yè)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)程序設(shè)計(jì)試題答案部分 第 10 頁(yè) 10writeln(deng yao san jiao xing.)else if (a*ab*b+c*c) then writeln(yi ban san jiao xing.);d:=(a+b+c)/2; s:=sqrt(d*(d-a)*(d-b)*(d-c); writeln(s=,s:0:2);endelse writeln(NO!);end.6、 設(shè)我國(guó)目前的人口為 11 億，且每年的增長(zhǎng)率為 1.5。問(wèn)多少年后，我國(guó)的人口會(huì)翻一番？（） （答案：47）program e2_22;vari:integer;s:real;beginwriteln; s:=11; i:=0;while s22 dobegin s:=s*(1.015); inc(i); end;writeln(i);end.7、 Fibonacci 數(shù)列問(wèn)題：數(shù)列的頭兩個(gè)數(shù)分別是 0 和 1，從第三