算法題目及答案

1、1.題目描述： 對輸入的n個數(shù)進行排序并輸出。輸入： 輸入的第一行包括一個整數(shù)n(1=n=100)。 接下來的一行包括n個整數(shù)。輸出： 可能有多組測試數(shù)據(jù)，對于每組數(shù)據(jù)，將排序后的n個整數(shù)輸出，每個數(shù)后面都有一個空格。 每組測試數(shù)據(jù)的結果占一行。樣例輸入：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個學生的數(shù)據(jù)，將學生數(shù)據(jù)按成績高低排序，如果成績相同則按姓名字符的字母序排序，如果姓名的字母序也相同則按照學生的年齡排序，并輸出N個學生排序后的信息。輸入： 測試數(shù)據(jù)有多組，每組輸入第一行有一個整數(shù)N（N=1000），接下來的N行包括N個學生的數(shù)據(jù)。 每個學生的數(shù)據(jù)包括姓名（長度不超過100的字符串）、年齡（整形數(shù)）、成績（小于等于100的正數(shù)）。輸出： 將學生信

3、息按成績進行排序，成績相同的則按姓名的字母序進行排序。 然后輸出學生信息，按照如下格式： 姓名 年齡 成績樣例輸入：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ù)進行排序。輸入：輸入第一行包括1個整數(shù)N，1=N=1000，代表輸入數(shù)據(jù)的個數(shù)。接下來的一行有N個整數(shù)。輸出：可能有多組測試數(shù)據(jù)，對于每組數(shù)據(jù)，第一行輸出一個整數(shù)，代表N個整數(shù)中的最大值，并將此值從數(shù)組中去除，將剩下的數(shù)進行排序。第二行將排序的結果輸出。樣例輸入：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可以對一組紀錄按任意指定列排序?，F(xiàn)請你編寫程序實現(xiàn)類似功能。 對每個測試用例，首先輸出1行“Case i:”，其中 i 是測試用例的編號（從1開始）。隨后在 N 行中輸出按要求排序后的結果，即：當 C=1 時，按學號遞增排序；當 C=2時，按姓名的非遞減字典序排序；當 C=3 時，按成績的非遞減排序。當若干學生具有相同姓名或者相

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

8、排序；當 C=2時，按姓名的非遞減字典序排序；當 C=3 時，按成績的非遞減排序。當若干學生具有相同姓名或者相同成績時，則按他們的學號遞增排序。樣例輸入：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.題目描述：輸入一個字符串，長度小于等于200，然后將輸出按字符順序升序排序后的字符串。

12、輸入：測試數(shù)據(jù)有多組，輸入字符串。輸出：對于每組輸入,輸出處理后的結果。樣例輸入：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. 題目描述：有兩個日期，求兩個日期之間的天數(shù)，如果兩個

13、日期是連續(xù)的我們規(guī)定他們之間的天數(shù)為兩天輸入：有多組數(shù)據(jù)，每組數(shù)據(jù)有兩行，分別表示兩個日期，形式為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; /日期格式轉化 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. 題目描述：/蔡勒公式計算星期幾公式#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. 題目描述：輸入年、月、日，計算該天是本年的第幾天。輸入：包括三個整數(shù)年(1=Y=3000)、月(1=M=12)、日(1=D=31)。輸出：輸入可能有多組測試數(shù)據(jù)，對于每一組測試數(shù)據(jù)，輸出一個整數(shù)，代表Input中的年、月、日對應本年的第幾天。樣例輸入：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天是幾月幾號。輸入：輸入包括兩個整數(shù)y(1=y=3000)，n(1=n=366)。輸出：可能有多組測試數(shù)據(jù)，對于每組數(shù)據(jù)，按 yyyy-mm-dd的格式將輸入中對應的日期打印出來。樣例輸入：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) /潤年 month1 = 29; for(i = 0, sum = 0; i 12; i +) if(sum dates) sum += monthi; else break; /獲取月份 m = i; /獲取當月的天數(shù) d = monthi - 1 - (sum - dates); /格式化輸出 printf(%04d-%02d-%02dn,year, m, d);11. 題目描述：讀入N名學生的成績，將獲得某一給定分數(shù)的學生人數(shù)輸出。輸入：測試輸入包含若干測試用例，

27、每個測試用例的格式為第1行：N第2行：N名學生的成績，相鄰兩數(shù)字用一個空格間隔。第3行：給定分數(shù)當讀到N=0時輸入結束。其中N不超過1000，成績分數(shù)為（包含）0到100之間的一個整數(shù)。輸出：對每個測試用例，將獲得給定分數(shù)的學生人數(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. 題目描述： 輸入一個ip地址串，判斷是否合法。輸入： 輸入的第一行包括一個整數(shù)n(1=n=500)，代表下面會出現(xiàn)的IP地址的個數(shù)。 接下來的n行每行有一個IP地址，IP地址的形式為a.b.c.d，其中a、b、c、d都是整數(shù)。輸出： 可能有多組測試數(shù)據(jù)，對于每組數(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個整數(shù)，請按從大到小的順序輸出其中前m大的數(shù)。輸入：每組測試數(shù)據(jù)有兩行，第一行有兩個數(shù)n,m(0n,m1000000)，第二行包含n個各不相同，且都處于區(qū)間

30、-500000,500000的整數(shù)。輸出：對每組測試數(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.題目描述： “臭味相投”這是我們描述朋友時喜歡用的詞匯。兩個人是朋友通常意味著他們存在著許多共同的興趣。然而作為一個宅男，你發(fā)現(xiàn)自己與他人相互了解的機會并不太多。幸運的是，你意外得到了一份北大圖書館的圖書借閱記錄，于是你挑燈熬夜地編程，想從中發(fā)現(xiàn)潛在的朋友。 首先你對借閱記錄進行了一番整理，把N個讀者依次編號為1,2,N，把M本書依次編號為1,2,M。同時，按照“臭味相投”的原則，和你喜歡讀同一本書的人，就是你的潛

33、在朋友。你現(xiàn)在的任務是從這份借閱記錄中計算出每個人有幾個潛在朋友。輸入： 每個案例第一行兩個整數(shù)N,M，2 = N ，M= 200。接下來有N行，第i(i = 1,2,N)行每一行有一個數(shù)，表示讀者i-1最喜歡的圖書的編號P(1=P=M)輸出： 每個案例包括N行，每行一個數(shù)，第i行的數(shù)表示讀者i有幾個潛在朋友。如果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