算法訓練-普通試題.doc

1、試題編號ALGO-101算法訓練圖形顯示問題描述編寫一個程序，首先輸入一個整數(shù)，例如 5，然后在屏幕上顯示如下的圖形（ 5 表示行數(shù)）：* * * *本題的 C+ 參考代碼如下：#include using namespace std;int main()int n;cin n;for (int i = 0; i n; i+)for (int j = 1; j = n - i; j+)cout *;if (j n - i)cout ;elsecout endl;return0;本題的 C 參考代碼如下：#includeint main()int i,j,a100100,n;while(scan

2、f(%d,&n)!=EOF)for(i=0;in;i+)for(j=0;jn-i;j+)printf(*);if(j!=n-i-1)printf( );if(j=n-1-i)printf(n);試題編號ALGO-97算法訓練排序問題描述編寫一個程序，輸入3 個整數(shù)，然后程序?qū)@三個整數(shù)按照從大到小進行排列。輸入格式：輸入只有一行，即三個整數(shù)，中間用空格隔開。輸出格式：輸出只有一行，即排序后的結(jié)果。輸入輸出樣例樣例輸入9230樣例輸出3092本題的 C+ 參考代碼如下：#includeusing namespace std;int main()int a,b,t,c;while(cinabc)

3、if(ab)t=a;a=b;b=t;if(ac)t=a;a=c;c=t;if(bc)t=b;b=c;c=t;couta b cendl;return 0;本題的 C 參考代碼如下：#include#include#define num 100int main(void)int i,j,t,a3=0;for (i=0;i3;i+)scanf(%d,&ai);for (i=0;i3;i+) for (j=i;j3;j+)if (ai=aj)t=ai;ai=aj;aj=t; for (i=0;i3;i+)printf(%d,ai); if(i!=2) printf( );printf(n);retu

4、rn 0;試題編號ALGO-95算法訓練2 的次冪表示問題描述任何一個正整數(shù)都可以用將這種 2 進制表示寫成2 進制表示，例如：137 的 2 進制表示為2 的次冪的和的形式， 令次冪高的排在前面，10001001?？傻玫饺缦卤磉_式：137=27+23+20現(xiàn)在約定冪次用括號來表示，即ab 表示為 a（ b）此時， 137 可表示為： 2（ 7） +2（ 3） +2 （ 0）進一步： 7=22+2+20（ 21 用 2 表示）3=2+20所以最后 137 可表示為： 2（ 2（ 2）+2+2 （ 0） +2（ 2+2（ 0） +2（ 0）又如： 1315=210+28+25+2+1所以 131

5、5 最后可表示為：2（ 2（2+2（ 0） +2） +2（ 2（ 2+2（0） +2（ 2（ 2） +2（ 0） +2+2 （0）輸入格式正整數(shù)（ 1=n=20000 ）輸出格式符合約定的n 的 0， 2 表示（在表示中不能有空格）樣例輸入137樣例輸出2(2(2)+2+2(0)+2(2+2(0)+2(0)樣例輸入1315樣例輸出2(2(2+2(0)+2)+2(2(2+2(0)+2(2(2)+2(0)+2+2(0)提示用遞歸實現(xiàn)會比較簡單，可以一邊遞歸一邊輸出本題的 C+ 參考代碼如下：#includeusing namespace std;/遞歸實現(xiàn)思路是先轉(zhuǎn)換成二進制int fun(int

6、 n)int i=0;int a20=0;int m=n;while(m)ai=m%2;m/=2;i+;for(int j=i-1;j=0;j-)/高位到低位排列但是要注意每位的權(quán)改變if(aj=1)/ 若是最后一個 1 則之后不要加號int flag=1;for(int k=j-1;k=0;k-)if(ak=1)flag=0;break;if(flag)/ 是最后一位if(j=1)cout2;elseif(j=0)cout2(j);elsecout2(;fun(j);cout);else/不是最后一位if(j=1)cout2+;elseif(j=0)cout2(j)+;elsecout2(;

7、fun(j);coutn;fun(n);coutendl;return 0;本題的 C 參考代碼如下：#include int l=0;char temp1000=0;void show(int n)if(n=0) templ=0;l+;return ;if(n=2)templ=2,l+;return ; int a15=0,i=0,j;while(n!=0)ai=n%2;n/=2;i+;for(j=i-1;j=0;j-)if(aj=1)if(j=1)if(templ-1=) | templ-1=2 ) templ=+;l+;templ=2;l+;elseif(templ-1=) | temp

8、l-1=2 ) templ=+;l+;templ=2;l+;templ=(;l+;show(j);templ=);l+;int main()int n;scanf(%d,&n);show(n);printf(%s,temp);return 0;試題編號ALGO-92算法訓練前綴表達式問題描述編寫一個程序， 以字符串方式輸入一個前綴表達式，然后計算它的值。 輸入格式為：“運算符對象 1 對象 2”，其中，運算符為“+”（加法）、“ -”（減法）、“ * ”（乘法）或“/ ”（除法），運算對象為不超過 10 的整數(shù)，它們之間用一個空格隔開。要求：對于加、減、乘、除這四種運算，分別設(shè)計相應(yīng)的函數(shù)來實

9、現(xiàn)。輸入格式：輸入只有一行，即一個前綴表達式字符串。輸出格式：輸出相應(yīng)的計算結(jié)果（如果是除法，直接采用c 語言的“ /”運算符，結(jié)果為整數(shù)）。輸入輸出樣例樣例輸入+ 5 2樣例輸出7本題的 C+ 參考代碼如下：#includeusing namespace std;int main()char c;int a,b;cincab;int res;if(c=+)res=a+b;else if(c=-)res=a-b;else if(c=*)res=a*b;else res=a/b;coutres;return 0;本題的 C 參考代碼如下：#includeint main() int a2;int

10、 i,j;char c=getchar();for(i=0;i2;i+)scanf(%d,&ai);if(c=+)j=a0+a1;else if(c=-)j=a0-a1;else if(c=*)j=a0*a1;else if(c=/)j=a0/a1;printf(%d,j);return 0;試題編號ALGO-91算法訓練Anagrams 問題問題描述Anagrams 指的是具有如下特性的兩個單詞：在這兩個單詞當中，每一個英文字母（不區(qū)分大小寫） 所出現(xiàn)的次數(shù)都是相同的。 例如，“ Unclear”和“Nuclear ”、“ Rimon ”和“ MinOR ” 都是 Anagrams 。編寫一

11、個程序， 輸入兩個單詞， 然后判斷一下， 這兩個單詞是否是 Anagrams 。每一個單詞的長度不會超過 80 個字符，而且是大小寫無關(guān)的。輸入格式：輸入有兩行，分別為兩個單詞。輸出格式：輸出只有一個字母Y 或 N，分別表示Yes 和 No。輸入輸出樣例樣例輸入UnclearNuclear樣例輸出Y本題的 C+ 參考代碼如下：#include #include #include #include #include #include #include #include #include #include using namespace std;char GetCapital(char c)if(

12、c=Z)return c;elsereturn c-(a-A);int main(int argc, char* argv) map a,b;string t;cint;for(int i=0;it;for(int i=0;it.length();i+)bGetCapital(ti)+;if(a=b)coutY;elsecoutN;return 0;本題的 C 參考代碼如下：#include void sort(char a,int len)int i,j,max;for(i=0;ilen;i+)max=i;for(j=i+1;jamax) max=j;j=ai;ai=amax;amax=j;

13、void strtoupper(char a,int len)int i;for(i=0;i=a & ai=z) ai-=32;int mystrcmp(char a,int l1,char b,int l2)if(l1!=l2) return 0;int i;for(i=0;in;if(n = 0) return 0;string *a = new stringn;int i;for(i = 0; i ai;string number = a0;int count = 1;int flag = 1;for(i = 1; i count)count = flag;number = ai - 1

14、;flag = 1;coutnumberendl;return 0;本題的 C 參考代碼如下：#include int main()int n,i,j,t,max=1,num=0;scanf(%d,&n);if(n0)int an;for(i=0;in;i+)scanf(%d,a+i);j=num=a0;t=1;for(i=1;imax)max=t;num=ai;elset=1;j=ai;printf(%d,num);return 0;試題編號ALGO-87算法訓練字串統(tǒng)計問題描述給定一個長度為n 的字符串S，還有一個數(shù)字L，統(tǒng)計長度大于等于L 的出現(xiàn)次數(shù)最多的子串（不同的出現(xiàn)可以相交），如果

15、有多個，輸出最長的，如果仍然有多個，輸出第一次出現(xiàn)最早的。輸入格式第一行一個數(shù)字L 。第二行是字符串S。L 大于 0，且不超過S 的長度。輸出格式一行，題目要求的字符串。輸入樣例1：4bbaabbaaaaa輸出樣例1：bbaa輸入樣例2：2bbaabbaaaaa輸出樣例2：aa數(shù)據(jù)規(guī)模和約定n=60S 中所有字符都是小寫英文字母。提示枚舉所有可能的子串，統(tǒng)計出現(xiàn)次數(shù)，找出符合條件的那個本題的 C+ 參考代碼如下：#include#includeint main()char s65,str65;int max=0,t,n,len;scanf(%d%s,&n,s);len=strlen(s);if

16、(n=n;i-)ssi=tti=0;for(int j=0;j=len-i;j+)t=1;for(int k=0;ki;k+)ssk=sk+j;for(int x=j+1;x=len-i;x+)for(int y=0;ymax)max=t;strcpy(str,ss);/printf(%sn,str);printf(%sn,str);本題的 C 參考代碼如下：#include#includeint main()char S1000,str10001000,temp100,out100;int L,i=0,s,otongji=0,ttongji,a,b,c;scanf(%d%c%c,&L,&S0

17、,&S0);while(Si!=n)scanf(%c,&Si+1);i+;Si = 0;for(s=i+1;L=s;L+)for(a=0;as+1-L;a+)/ 賦值for(b = 0;b L;b+)strab=Sa+b;strab = 0;for(i = 0;i a-1;)/比較for(b = 0;ba;b+)if(strb0!=0)for(c = 0;cL;c+)tempc=strbc;tempc = 0;ttongji = 1;i+;strb0 = 0;break;for(b+;botongji|(ttongji=otongji&strlen(temp)strlen(out)strcpy

18、(out,temp);otongji = ttongji;i = 0;while(outi != 0)printf(%c,outi);i+;getchar();return 0;試題編號ALGO-86算法訓練矩陣乘法問題描述輸入兩個矩陣，分別是m*s ，s*n 大小。輸出兩個矩陣相乘的結(jié)果。輸入格式第一行，空格隔開的三個正整數(shù)m,s,n（均不超過200）。接下來 m 行，每行 s 個空格隔開的整數(shù)，表示矩陣A （ i ， j）。接下來 s 行，每行 n 個空格隔開的整數(shù)，表示矩陣B （i ， j ）。輸出格式m 行，每行 n 個空格隔開的整數(shù)，輸出相乘後的矩陣C（ i ，j ）的值。樣例輸入2

19、 321 0-11 1-30 31 23 1樣例輸出-3 2-8 2提示矩陣 C 應(yīng)該是 m 行 n 列，其中 C(i,j) 等于矩陣 A 第 i 行行向量與矩陣例如樣例中C(1,1)=(1,0,-1)*(0,1,3) = 1 * 0 +0*1+(-1)*3=-3B 第j 列列向量的內(nèi)積。本題的 C+ 參考代碼如下：#include#include#include#includeint main()int m,s,n;int sum=0;int i,j,l;int a200200,b200200,c200200;scanf(%d%d%d,&m,&s,&n);for(i=0;im;i+)for(

20、j=0;js;j+)scanf(%d,&aij);for(i=0;is;i+)for(j=0;jn;j+)scanf(%d,&bij);for(i=0;im;i+)for(j=0;jn;j+)for(l=0;ls;l+)sum+=(ail*blj);cij=sum;sum=0;for(i=0;im;i+)for(j=0;jn;j+)printf(%d ,cij);printf(n);return 0;本題的 C 參考代碼如下：# include int main()int m,s,n,i,j,k,a200200,b200200,c200200; scanf(%d%d%d,&m,&s,&n);

21、for(i=1;i=m;i+)for(j=1;j=s;j+)scanf(%d,&aij);for(i=1;i=s;i+)for(j=1;j=n;j+)scanf(%d,&bij);for(i=1;i=m;i+)for(j=1;j=n;j+)cij=0;for(i=1;i=m;i+)for(j=1;j=n;j+)for(k=1;k=s;k+)cij=cij+aik*bkj;for(i=1;i=m;i+)for(j=1;j=n;j+)printf(%d ,cij);printf(n);return 0;試題編號ALGO-84算法訓練大小寫轉(zhuǎn)換問題描述編寫一個程序，輸入一個字符串（長度不超過20），

22、然后把這個字符串內(nèi)的每一個字符進行大小寫變換，即將大寫字母變成小寫，小寫字母變成大寫，然后把這個新的字符串輸出。輸入格式： 輸入一個字符串，而且這個字符串當中只包含英文字母，不包含其他類型的字符，也沒有空格。輸出格式：輸出經(jīng)過轉(zhuǎn)換后的字符串。輸入輸出樣例樣例輸入AeDb樣例輸出aEdB本題的 C+ 參考代碼如下：#include #include using namespace std;int main()string str;cinstr;unsigned i;for(i=0;i=A&stri=a&stri=z)stri-=32;coutstr;return 0;本題的 C 參考代碼如下：#

23、include int main()int i;char ch100;gets(ch);i=0;while(chi!=0)if(chi=a)chi-=32;else chi+=32;i+;puts(ch);return 0;試題編號ALGO-81算法訓練動態(tài)數(shù)組使用從鍵盤讀入n 個整數(shù)，使用動態(tài)數(shù)組存儲所讀入的整數(shù)，并計算它們的和與平均值分別輸出。要求盡可能使用函數(shù)實現(xiàn)程序代碼。平均值為小數(shù)的只保留其整數(shù)部分。樣例輸入534002樣例輸出9 1樣例輸入73275291樣例輸出29 4本題的 C+ 參考代碼如下：#includeusing namespace std;int main()int

24、n,a,sum=0;cinn;for(int i=0;ia;sum+=a;coutsum sum/nendl;return 0;本題的 C 參考代碼如下：#include int main()int i,n,a100,b100,sum=0,avg=0;scanf(%d,&n);for(i=0;in;arr = new intn;int num = 0;for (int i=0; iarri;if(arri != 0)+num;coutnumendl;for (int i=0; in; +i)if(arri = 0)continue;coutarri ;return 0;本題的 C 參考代碼如下

25、：#include stdio.hint CompactIntegers(int a, int len)int i, j, k;for(k=0; klen; k+)for(i=0; ilen; i+)if(ai = 0)for(j=i; jlen-1; j+)aj = aj+1;len-;return len;void print(int a, int len)int i;for(i=0; ilen; i+)printf(%d , ai);printf(n);int main()int a100000;int n;scanf(%d, &n);int i;for(i=0; i1)printf(%

26、dn, len);print(a, len);elseprintf(%d, 0);getchar();getchar();getchar();return 0;試題編號ALGO-53算法訓練最小乘積 (基本型 )問題描述給兩組數(shù)，各n 個。請調(diào)整每組數(shù)的排列順序，使得兩組數(shù)據(jù)相同下標元素對應(yīng)相乘，然后相加的和最小。要求程序輸出這個最小值。例如兩組數(shù)分別為 :1 3-5和-241那么對應(yīng)乘積取和的最小值應(yīng)為：(-5)*4+3*(-2)+1*1=-25輸入格式第一個行一個數(shù)T 表示數(shù)據(jù)組數(shù)。后面每組數(shù)據(jù)，先讀入一個n，接下來兩行每行n 個數(shù)，每個數(shù)的絕對值小于等于1000。n=8,T=1000輸出

27、格式一個數(shù)表示答案。樣例輸入2313-5-24151234510101樣例輸出-256本題的 C+ 參考代碼如下：#include#includeusing namespace std;int a8,b8;int main()int T,n;int i,j;cinT;while(T-)int sum=0;cinn;for(i=0;iai;for(i=0;ibi;sort(a,a+n);sort(b,b+n);for(i=0;in;i+)sum+=ai*bn-1-i;coutsumendl;return 0;本題的 C 參考代碼如下：#includevoid sort1(int *a,int n

28、)int i,j;int tmp;for(i=0;in-1;i+)for(j=0;jaj+1)tmp=aj;aj=aj+1;aj+1=tmp;void sort2(int *a,int n)int i,j;int tmp;for(i=0;in-1;i+)for(j=0;jn-1-i;j+)if(ajaj+1)tmp=aj;aj=aj+1;aj+1=tmp;int main(void)int T;int n,i;int total;int a8,b8,c8;scanf(%d,&T);while(T)total=0;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&ai);

29、for(i=0;in;i+)scanf(%d,&bi);sort1(a,n);sort2(b,n);for(i=0;in;i+)ci=ai*bi;for(i=0;in;i+)total+=ci;printf(%dn,total);T-;return 0;試題編號ALGO-51算法訓練Torry 的困惑 (基本型 )問題描述Torry 從小喜愛數(shù)學。一天，老師告訴他，像2、3、5、7 這樣的數(shù)叫做質(zhì)數(shù)。Torry突然想到一個問題，前10、 100、 1000、 10000 個質(zhì)數(shù)的乘積是多少呢？他把這個問題告訴老師。老師愣住了，一時回答不出來。于是Torry求助于會編程的你，請你算出前n 個質(zhì)數(shù)

30、的乘積。不過，考慮到你才接觸編程不久，Torry只要你算出這個數(shù)模上50000 的值。輸入格式僅包含一個正整數(shù)n，其中 n=100000 。輸出格式輸出一行，即前n 個質(zhì)數(shù)的乘積模50000 的值。樣例輸入1樣例輸出2本題的 C+ 參考代碼如下：#include using namespace std;int a100005;int main()unsigned int i, j, n, cnt = 1, cj = 2;cin n;if (n = 1)cout 2 endl;return 0;a0 = 2;for (i = 3; i 2000000; i+)for (j = 0; j i)break;elseif (!(i % aj)break;if (aj * aj i)acnt+ = i;cj = (cj % 50000) * (i % 50000) ;if (cnt = n)break;cout cj % 50000 endl;return 0;本題的 C 參考代碼如下：#includeint pr100010;int top;int isPrime(int n)int i;for(i = 0; i top; i+)if(n % pri = 0)return 0;return 1