算法題目及答案

1、1.題目描述： 對(duì)輸入的n個(gè)數(shù)進(jìn)行排序并輸出。輸入： 輸入的第一行包括一個(gè)整數(shù)n(1=n=100)。 接下來的一行包括n個(gè)整數(shù)。輸出： 可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，將排序后的n個(gè)整數(shù)輸出，每個(gè)數(shù)后面都有一個(gè)空格。 每組測(cè)試數(shù)據(jù)的結(jié)果占一行。樣例輸入：41 4 3 2樣例輸出：1 2 3 4#include #include #include using namespace std;int main() int n; while(cinn&n=1&n=100) vector ivec; int itemp; for(int i=0;iitemp; ivec.push_back(itemp)

2、; sort(ivec.begin(),ivec.end(); for(vector:iterator j=ivec.begin();j!=ivec.end();j+) cout*j ; coutendl; return 0;2.有N個(gè)學(xué)生的數(shù)據(jù)，將學(xué)生數(shù)據(jù)按成績(jī)高低排序，如果成績(jī)相同則按姓名字符的字母序排序，如果姓名的字母序也相同則按照學(xué)生的年齡排序，并輸出N個(gè)學(xué)生排序后的信息。輸入： 測(cè)試數(shù)據(jù)有多組，每組輸入第一行有一個(gè)整數(shù)N（N=1000），接下來的N行包括N個(gè)學(xué)生的數(shù)據(jù)。 每個(gè)學(xué)生的數(shù)據(jù)包括姓名（長(zhǎng)度不超過100的字符串）、年齡（整形數(shù)）、成績(jī)（小于等于100的正數(shù)）。輸出： 將學(xué)生信

3、息按成績(jī)進(jìn)行排序，成績(jī)相同的則按姓名的字母序進(jìn)行排序。 然后輸出學(xué)生信息，按照如下格式： 姓名 年齡 成績(jī)樣例輸入：3abc 20 99bcd 19 97bed 20 97樣例輸出：bcd 19 97bed 20 97abc 20 99#include#includestruct student char name101; int age; int score;int main() int n,i,j; struct student a1000,temp; while(scanf(%d,&n)!=EOF) for(i=0;in;i+) scanf(%s %d %d,&,&ai.a

4、ge,&ai.score); for(i=1;in;i+) for(j=1;jaj.score) temp=aj-1; aj-1=aj; aj=temp; else if(aj-1.score=aj.score) if(strcmp(,)0) temp=aj-1; aj-1=aj; aj=temp; else if(strcmp(,)=0) if(aj-1.ageaj.age) temp=aj-1; aj-1=aj; aj=temp; for(i=0;in;i+) printf(%s %d %dn,,ai.age,a

5、i.score); return 0;4. 題目描述：輸入一系列整數(shù)，將其中最大的數(shù)挑出，并將剩下的數(shù)進(jìn)行排序。輸入：輸入第一行包括1個(gè)整數(shù)N，1=N=1000，代表輸入數(shù)據(jù)的個(gè)數(shù)。接下來的一行有N個(gè)整數(shù)。輸出：可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，第一行輸出一個(gè)整數(shù)，代表N個(gè)整數(shù)中的最大值，并將此值從數(shù)組中去除，將剩下的數(shù)進(jìn)行排序。第二行將排序的結(jié)果輸出。樣例輸入：41 3 4 2樣例輸出：41 2 3#include int main()int i,n,t,j,a1000;while(scanf(%d,&n)!=EOF) for(i=0;i=0&ajt) aj+1=aj;j-; aj+1=t;

6、 printf(%dn,an-1);if(n=1) printf(-1n);else for(i=0;in-1;i+) printf(%d,ai); if(i!=n-2) printf( ); else printf(n);return 0;5. 題目描述： Excel可以對(duì)一組紀(jì)錄按任意指定列排序?，F(xiàn)請(qǐng)你編寫程序?qū)崿F(xiàn)類似功能。 對(duì)每個(gè)測(cè)試用例，首先輸出1行“Case i:”，其中 i 是測(cè)試用例的編號(hào)（從1開始）。隨后在 N 行中輸出按要求排序后的結(jié)果，即：當(dāng) C=1 時(shí)，按學(xué)號(hào)遞增排序；當(dāng) C=2時(shí)，按姓名的非遞減字典序排序；當(dāng) C=3 時(shí)，按成績(jī)的非遞減排序。當(dāng)若干學(xué)生具有相同姓名或者相

7、同成績(jī)時(shí)，則按他們的學(xué)號(hào)遞增排序。輸入： 測(cè)試輸入包含若干測(cè)試用例。每個(gè)測(cè)試用例的第1行包含兩個(gè)整數(shù) N (N=100000) 和 C，其中 N 是紀(jì)錄的條數(shù)，C 是指定排序的列號(hào)。以下有N行，每行包含一條學(xué)生紀(jì)錄。每條學(xué)生紀(jì)錄由學(xué)號(hào)（6位數(shù)字，同組測(cè)試中沒有重復(fù)的學(xué)號(hào)）、姓名（不超過8位且不包含空格的字符串）、成績(jī)（閉區(qū)間0, 100內(nèi)的整數(shù)）組成，每個(gè)項(xiàng)目間用1個(gè)空格隔開。當(dāng)讀到 N=0 時(shí)，全部輸入結(jié)束，相應(yīng)的結(jié)果不要輸出。輸出： 對(duì)每個(gè)測(cè)試用例，首先輸出1行“Case i:”，其中 i 是測(cè)試用例的編號(hào)（從1開始）。隨后在 N 行中輸出按要求排序后的結(jié)果，即：當(dāng) C=1 時(shí)，按學(xué)號(hào)遞增

8、排序；當(dāng) C=2時(shí)，按姓名的非遞減字典序排序；當(dāng) C=3 時(shí)，按成績(jī)的非遞減排序。當(dāng)若干學(xué)生具有相同姓名或者相同成績(jī)時(shí)，則按他們的學(xué)號(hào)遞增排序。樣例輸入：3 1000007 James 85000010 Amy 90000001 Zoe 604 2000007 James 85000010 Amy 90000001 Zoe 60000002 James 984 3000007 James 85000010 Amy 90000001 Zoe 60000002 James 900 0樣例輸出：Case 1:000001 Zoe 60000007 James 85000010 Amy 90Case

9、2:000010 Amy 90000002 James 98000007 James 85000001 Zoe 60Case 3:000001 Zoe 60000007 James 85000002 James 90000010 Amy 90#include #include #include #include using namespace std;struct info string id; string name; int score;bool cmp_id(const struct info a,const struct info b) return a.idb.id;bool cmp

10、_name(const struct info a,const struct info b) if(=) return a.idb.id; else return ;bool cmp_score(const struct info a,const struct info b) if(a.score=b.score) return a.idb.id; else return a.scorenc) if(n=0&c=0) break; count+; struct info datan; for(int i=0;

11、datai.score; switch(c) case 1: sort(data,data+n,cmp_id); break; case 2: sort(data,data+n,cmp_name); break; case 3: sort(data,data+n,cmp_score); printf(Case %d:n,count); for(int i=0;in;i+) printf(%s %s %dn,datai.id.c_str(),.c_str(),datai.score); 6.題目描述：輸入一個(gè)字符串，長(zhǎng)度小于等于200，然后將輸出按字符順序升序排序后的字符串。

12、輸入：測(cè)試數(shù)據(jù)有多組，輸入字符串。輸出：對(duì)于每組輸入,輸出處理后的結(jié)果。樣例輸入：bacd樣例輸出：Abcd#include#includeint main() char string200,temp; int i,j,n; while(scanf(%s,string)!=EOF) n=0; while(stringn) n+; for(i=1;in;i+) for(j=0;j0) temp=stringj; stringj=stringj+1; stringj+1=temp; printf(%sn,string); return 0;7. 題目描述：有兩個(gè)日期，求兩個(gè)日期之間的天數(shù)，如果兩個(gè)

13、日期是連續(xù)的我們規(guī)定他們之間的天數(shù)為兩天輸入：有多組數(shù)據(jù)，每組數(shù)據(jù)有兩行，分別表示兩個(gè)日期，形式為YYYYMMDD輸出：每組數(shù)據(jù)輸出一行，即日期差值樣例輸入：2011041220110422樣例輸出：11#include#include#define MAX_DATE_SIZE 9int Days12=31,28,31,30,31,30,31,31,30,30,31;typedef struct Date int Year; int Month; int Day;Date;int main(int argc,char *argv) int i,L; int HLN1,HLN2; int sDa

14、y,eDay; Date sDate,eDate; char sdateMAX_DATE_SIZE,edateMAX_DATE_SIZE; while(scanf(%s,sdate)!=EOF) sDay=0; eDay=0; /日期格式轉(zhuǎn)化 sDate.Year=(sdate0-0)*1000+(sdate1-0)*100+(sdate2-0)*10+(sdate3-0); sDate.Month=(sdate4-0)*10+(sdate5-0); sDate.Day=(sdate6-0)*10+(sdate7-0); scanf(%s,edate); eDate.Year=(edate0-

15、0)*1000+(edate1-0)*100+(edate2-0)*10+(edate3-0); eDate.Month=(edate4-0)*10+(edate5-0); eDate.Day=(edate6-0)*10+(edate7-0); HLN1=(int)(sDate.Year/4)-(int)(sDate.Year/100)+(int)(sDate.Year/400); HLN2=(int)(eDate.Year/4)-(int)(eDate.Year/100)+(int)(eDate.Year/400); for(i=0;isDate.Month-1;+i) sDay+=Days

16、i; for(i=0;ieDate.Month-1;+i) eDay+=Daysi; sDay+=sDate.Day; eDay+=eDate.Day; L=(int)fabs(sDate.Year*365+HLN1+sDay)-(eDate.Year*365+HLN2+eDay)+1; printf(%dn,L); return 1;8. 題目描述：/蔡勒公式計(jì)算星期幾公式#includeusingnamespacestd;intmain()intyear,month,day;while(cinyearmonthday)if(month3）year-=1;month+=12;charb710

17、=sunday,monday,tuesday,wednesday,thursday,friday,saturday;intc=int(year/100），y=year-100*c;intw=int(c/4）-2*c+y+int(y/4）+（26*(month+1）/10）+day-1;w=(w%7+7）%7;coutbwendl;We now use the Gregorian style of dating in Russia. The leap years are years with number divisible by 4 but not divisible by 100, or d

18、ivisible by 400.For example, years 2004, 2180 and 2400 are leap. Years 2004, 2181 and 2300 are not leap.Your task is to write a program which will compute the day of week corresponding to a given date in the nearest past or in the future using todays agreement about dating.輸入：There is one single lin

19、e contains the day number d, month name M and year number y(1000y3000). The month name is the corresponding English name starting from the capital letter.輸出：Output a single line with the English name of the day of week corresponding to the date, starting from the capital letter. All other letters mu

20、st be in lower case.樣例輸入：9 October 200114 October 2001樣例輸出：TuesdaySunday#include#includeusing namespace std;int main() char month1220=January,February,March,April,May,June,July,August,September,October,November,December;/egg broken. string week7=Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturd

21、ay; int m_day12=0,3,3,6,1,4,6,2,5,0,3,5; int l_day12=0,3,4,0,2,5,0,3,6,1,4,6; int year,day,m,ans; char mon20; while(cindaymonyear) int i; for(i=0;i12;i+) if(strcmp(monthi,mon)=0) m=i; if(year%4=0&year%100!=0)|(year%400=0) ans=(year+year/4+year/400-year/100-2+l_daym+day)%7; else ans=(year+year/4+year

22、/400-year/100-1+m_daym+day)%7; coutweekansendl; return 0;9. 題目描述：輸入年、月、日，計(jì)算該天是本年的第幾天。輸入：包括三個(gè)整數(shù)年(1=Y=3000)、月(1=M=12)、日(1=D=31)。輸出：輸入可能有多組測(cè)試數(shù)據(jù)，對(duì)于每一組測(cè)試數(shù)據(jù)，輸出一個(gè)整數(shù)，代表Input中的年、月、日對(duì)應(yīng)本年的第幾天。樣例輸入：1990 9 202000 5 1樣例輸出：263122#include using namespace std;bool fun(int year,int month) if(year%400=0|(year%4=0&year

23、%100!=0)&month2)return true;/是閏年且月份大于2月 else return false;int main() int y,m,d; while(cinymd) if(y3000|m12|d31)return 1; int sum=0; switch(m) case 12: sum+=30; case 11: sum+=31; case 10: sum+=30; case 9: sum+=31; case 8: sum+=31; case 7: sum+=30; case 6: sum+=31; case 5: sum+=30; case 4: sum+=31; ca

24、se 3: sum+=28; case 2: sum+=31; default:break; sum+=d; if(fun(y,m)sum+; coutsumendl; return 0;10. 題目描述：給出年分m和一年中的第n天，算出第n天是幾月幾號(hào)。輸入：輸入包括兩個(gè)整數(shù)y(1=y=3000)，n(1=n=366)。輸出：可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，按 yyyy-mm-dd的格式將輸入中對(duì)應(yīng)的日期打印出來。樣例輸入：2000 32000 312000 402000 602000 612001 60樣例輸出：2000-01-032000-01-312000-02-092000-02-

25、292000-03-012001-03-01#include #include #include void showFormatdate(int, int);int main() int year, dates; while(scanf(%d %d, &year, &dates) != EOF) showFormatdate(year, dates); void showFormatdate(int year, int dates) int sum, i, m, d; int month12 = 31,28,31,30,31,30,31,31,30,31,30,31; if(year % 10

26、0 = 0) & (year % 400 = 0) | (year % 4 = 0) & (year % 100 != 0) /潤(rùn)年 month1 = 29; for(i = 0, sum = 0; i 12; i +) if(sum dates) sum += monthi; else break; /獲取月份 m = i; /獲取當(dāng)月的天數(shù) d = monthi - 1 - (sum - dates); /格式化輸出 printf(%04d-%02d-%02dn,year, m, d);11. 題目描述：讀入N名學(xué)生的成績(jī)，將獲得某一給定分?jǐn)?shù)的學(xué)生人數(shù)輸出。輸入：測(cè)試輸入包含若干測(cè)試用例，

27、每個(gè)測(cè)試用例的格式為第1行：N第2行：N名學(xué)生的成績(jī)，相鄰兩數(shù)字用一個(gè)空格間隔。第3行：給定分?jǐn)?shù)當(dāng)讀到N=0時(shí)輸入結(jié)束。其中N不超過1000，成績(jī)分?jǐn)?shù)為（包含）0到100之間的一個(gè)整數(shù)。輸出：對(duì)每個(gè)測(cè)試用例，將獲得給定分?jǐn)?shù)的學(xué)生人數(shù)輸出。樣例輸入：380 60 9060285 660560 75 90 55 75750樣例輸出：102#include #include #include using namespace std;double t1005,a;int N;int main() int i; while(cinN & N) int ans = 0; for(i = 0; iti; c

28、ina; for(i = 0; iN; i+) if(ti = a)ans+; coutansendl; return 0;12. 題目描述： 輸入一個(gè)ip地址串，判斷是否合法。輸入： 輸入的第一行包括一個(gè)整數(shù)n(1=n=500)，代表下面會(huì)出現(xiàn)的IP地址的個(gè)數(shù)。 接下來的n行每行有一個(gè)IP地址，IP地址的形式為a.b.c.d，其中a、b、c、d都是整數(shù)。輸出： 可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，如果IP地址合法則輸出Yes!”，否則輸出No!”。樣例輸入：2555樣例輸出：Yes!No!提示：合法的IP地址為：a、b、c、d都是0-255的整數(shù)。#

29、include using namespace std; int main() int n; int p1,p2,p3,p4; while (cinn) for(int i=0;ip1cp2cp3cp4; if(p1=0 & p2=0 & p3=0 & p4=0 & p1=255 & p2=255 & p3=255 & p4=255) coutYes!endl; else coutNo!endl; return 0;13. 題目描述：給你n個(gè)整數(shù)，請(qǐng)按從大到小的順序輸出其中前m大的數(shù)。輸入：每組測(cè)試數(shù)據(jù)有兩行，第一行有兩個(gè)數(shù)n,m(0n,m1000000)，第二行包含n個(gè)各不相同，且都處于區(qū)間

30、-500000,500000的整數(shù)。輸出：對(duì)每組測(cè)試數(shù)據(jù)按從大到小的順序輸出前m大的數(shù)。樣例輸入：5 33 -35 92 213 -644樣例輸出：213 92 3#include #include #include using namespace std; #define left(i) (i + 1) * 2 - 1)#define right(i) (left(i) + 1)#define parent(i) (i + 1) / 2) void heapify(int a, int n, int index) while (true) int i = index; int l = lef

31、t(i), r = right(i); if (l n) i = ai al ? i : l; if (r n) i = ai = 0; -i) heapify(a, n, i); int main() int n, m; while (scanf(%d %d, &n, &m) != EOF) int *a = new intm; for (int i = 0; i m; +i) scanf(%d, &ai); make_heap(a, m); int num; for (int i = m; i a0) a0 = num; heapify(a, m, 0); sort(a, a + m, g

32、reater(); printf(%d, a0); for (int i = 1; i m; +i) printf( %d, ai); printf(n); return 0;14.題目描述： “臭味相投”這是我們描述朋友時(shí)喜歡用的詞匯。兩個(gè)人是朋友通常意味著他們存在著許多共同的興趣。然而作為一個(gè)宅男，你發(fā)現(xiàn)自己與他人相互了解的機(jī)會(huì)并不太多。幸運(yùn)的是，你意外得到了一份北大圖書館的圖書借閱記錄，于是你挑燈熬夜地編程，想從中發(fā)現(xiàn)潛在的朋友。 首先你對(duì)借閱記錄進(jìn)行了一番整理，把N個(gè)讀者依次編號(hào)為1,2,N，把M本書依次編號(hào)為1,2,M。同時(shí)，按照“臭味相投”的原則，和你喜歡讀同一本書的人，就是你的潛

33、在朋友。你現(xiàn)在的任務(wù)是從這份借閱記錄中計(jì)算出每個(gè)人有幾個(gè)潛在朋友。輸入： 每個(gè)案例第一行兩個(gè)整數(shù)N,M，2 = N ，M= 200。接下來有N行，第i(i = 1,2,N)行每一行有一個(gè)數(shù)，表示讀者i-1最喜歡的圖書的編號(hào)P(1=P=M)輸出： 每個(gè)案例包括N行，每行一個(gè)數(shù)，第i行的數(shù)表示讀者i有幾個(gè)潛在朋友。如果i和任何人都沒有共同喜歡的書，則輸出“BeiJu”（即悲劇， ）樣例輸入：4 52321樣例輸出：1BeiJu1BeiJu#include #include using namespace std; int main(void) multiset record; int N, M; int ss200; while (cin N M) for (int i=0; i ssi; record.insert(ssi); for (int i=0; i N; i+) if (record.count(ssi) = 1) cout BeiJu end