作者：gnuhpc?
出處：http://www.cnblogs.com/gnuhpc/

1.清華計(jì)算機(jī)系研究生考試上機(jī)07年試題解答（自己今天上午做的，有一個不能完成所有測試用例～）

?

清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

2007 年碩士研究生招生復(fù)試

2007 年 3 月 24 日

注意事項(xiàng)：

1. 試題共三題，總計(jì) 100 分，考試時間為一個半小時。

2. 不得使用自帶的電子設(shè)備，包括筆記本、 U 盤、手機(jī)等；不得使用參考書籍和資料。

3. 編程環(huán)境為 Windows 2000 Professional + Visual Studio 6.0 ，只能使用 C/C++ 語言。

4. 每一題的輸入數(shù)據(jù)都從文件 input.txt 中讀取，將結(jié)果輸出至文件 output.txt ，請嚴(yán)格按照每一題的輸入輸出格式 。在考試過程中，我們恕不提供除試題中樣例以外的測試數(shù)據(jù)，請自行生成輸入數(shù)據(jù)以對程序進(jìn)行自測。

5. 在考試結(jié)束之前自行設(shè)置編譯環(huán)境和配置編譯參數(shù)，將所寫的程序編譯成可執(zhí)行文件，文件名在每一題中都有規(guī)定。生成的可執(zhí)行文件將作為最終測試的唯一依據(jù)，若無法運(yùn)行您的可執(zhí)行文件，最終成績將記為零分。

6. 程序?qū)γ總€測試數(shù)據(jù)的可用運(yùn)行時間上限 1 秒，若超時或結(jié)果錯誤，則該測試用例不能得分。

7. 在考試過程中，若計(jì)算機(jī)出現(xiàn)故障，請及時通知工作人員，以免耽誤您的考試時間。

8. 上機(jī)考試結(jié)束后，請勿馬上離開，工作人員將會直接進(jìn)行現(xiàn)場測試，需要您的合作。

第一題（可執(zhí)行文件名 program1.exe ）

求正整數(shù) N(N>1) 的質(zhì)因數(shù)的個數(shù)。注意： 1 不是 N 的質(zhì)因數(shù)：若 N 為質(zhì)數(shù)， N 是 N 的質(zhì)因數(shù)。相同的質(zhì)因數(shù)需要重復(fù)計(jì)算。

如 120=2*2*2*3*5 ，共有 5 個質(zhì)因數(shù)。

輸入：

正整數(shù)N ，1<N<10⁹

輸出：

N 的質(zhì)因數(shù)的個數(shù)

樣例輸入：

120

樣例輸出

5

#include<stdlib.h> #include<stdio.h> #include<math.h>int main(void) {int i=2,count=1;long int N;char buffer[10];FILE *fp1,*fp2;fp1=fopen("input","r");fgets(buffer,10,fp1);N=atol(buffer);while(i<=sqrt(N)){for(;i<=sqrt(N);i++)if(N%i==0){N=N/i;printf("%d*",i);count++;break;}}printf("%d",N);fp2=fopen("output","w");itoa(count,buffer,10);fputs(buffer,fp2);rewind(fp2);fclose(fp1);fclose(fp2);return 0; }

第二題（可執(zhí)行文件名：program2.exe ）

對于一個十進(jìn)制數(shù)A ，將A 轉(zhuǎn)換為二進(jìn)制數(shù)，然后按位逆序排列，再轉(zhuǎn)換為十進(jìn)制數(shù)B ，我們乘B 為A 的二進(jìn)制逆序數(shù) 。

例如對于十進(jìn)制數(shù)173 ，它的二進(jìn)制形式為101011101 ，逆序排列得到10110101 ，其十進(jìn)制數(shù)為181 ，181 即為173 的二進(jìn)制逆序數(shù)

輸入：

一個1000 位( 即2⁹⁹⁹ ) 以內(nèi)的十進(jìn)制數(shù)。

輸出：

輸入的十進(jìn)制數(shù)的二進(jìn)制逆序數(shù)。

樣例輸入：

173

樣例輸出：

181

（下列程序只能忍受部分測試用例）

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h>#define MAX 100 #define LEN 1000long int process(long int N) {long int M=0;int count=0;int i,j;int temp[LEN];int *p=temp;int tempr[LEN];int *r=tempr;long int tmpnumber=N;for(i=0;tmpnumber!=0;tmpnumber/=2,i++){*p++=tmpnumber%2;*r++=pow(2,i);count++;}for(i=0,j=count-1;i<count;i++,j--){printf("temp[i]*tempr[j]=%d/n",temp[i]*tempr[j]);M+=temp[i]*tempr[j];}return M; }int main(void) {long int N,M;FILE *fp1,*fp2;char buffer[MAX];fp1=fopen("input","r");fgets(buffer,MAX,fp1);N=atol(buffer);M=process(N);fp2=fopen("output","w");ltoa(M,buffer,10);fputs(buffer,fp2);fclose(fp1);fclose(fp2);return 0; }

第三題（可執(zhí)行文件名program3.exe ）

有若干張郵票，要求從中選取最少的郵票張數(shù)湊成一個給定的總值。

如，有1 分，3 分，3 分，3 分，4 分五張郵票，要求湊成10 分，則使用3 張郵票：3 分、3 分、4 分即可。

輸入：

首先是要求湊成的郵票總值M ，M<100

然后是一個數(shù)N ，N 〈20 ，表示有N 張郵票。接下來是N 個正整數(shù)，分別表示這N 張郵票的面值，且以升序排列。

輸出：

能夠湊成總值M 的最少郵票張數(shù)。若無解，輸出0 。

樣例輸入：

10 5 1 3 3 3 4

樣例輸出：

3

分析：這是最簡單的背包問題，動態(tài)規(guī)劃的方法，寫得不是很規(guī)范，不過結(jié)果很不錯，線形復(fù)雜度 ~~

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h>#define MAX 100 #define LEN 1000void process(int M,int *a,int offset,int *flag) {if(offset>=0){if(M-a[offset]>0){if((M-a[offset])>=a[offset-1]){flag[offset]=1;if(M>=0)process(M-a[offset],a,offset-1,flag);}else{if(M>=0)process(M,a,offset-1,flag);}}else if(M-a[offset]==0)flag[offset]=1;} } int main(void) {int N,M,i,number=0;int result;int count=0;FILE *fp1,*fp2;char tmp;int value[MAX];int option[MAX];int *p=value;int *flag=option;fp1=fopen("input","r");fscanf(fp1,"%d %d",&M,&N);printf("M=%d,N=%d/n",M,N);for(i=0;i<N;i++){fgetc(fp1);tmp=fgetc(fp1);value[i]=atoi(&tmp);printf("value=%d/n",value[i]);}process(M,p,N-1,flag);for(i=0;i<N;i++){if(*flag++==1){printf("%d",value[i]);count+=value[i];number++;}}result=(count==M?number:0);fp2=fopen("output","w");fprintf(fp2,"%d",result);fclose(fp1);fclose(fp2);return 0; }

2.清華計(jì)算機(jī)系研究生考試上機(jī)06年試題解答（自己今天下午做的，郁悶之中。。。做的時間太長）

一、輸入：兩行
第一行：M和N
第二行：X
M和N是一個十進(jìn)制數(shù)，M和N都在[2-36]之間，X是一個M進(jìn)制數(shù)，X在[1-2*10^19]
輸出：一行
第一行：現(xiàn)在要求你將M進(jìn)制數(shù)X轉(zhuǎn)換成N進(jìn)制數(shù)輸出
輸入一：
16 10
F
輸出一：
15

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #define MAX 100 /* 顯示錯誤信息 */ void printerror(char errno,char *num,int base1) {switch (errno){case 1 : printf("/nError : Origin number %s(%d) is valid !!!/n",num,base1);break;case 2 :printf("/nError : radix (%d) is invalid !!!/n%s/n",base1,"Correct : radix>=2 and radix <=36");break;} } /* 數(shù)制轉(zhuǎn)換函數(shù) */ void transnum(char *num,int base1,int base2) {int len,k,l,m,j,ibase1,ibase2;long inum=0;char temp[20];double r=0;len = strlen(num); /* 數(shù)值的長度 */ibase1 = base1; /* 數(shù)基1 */if ((ibase1<2) || (ibase1>36))printerror(2,"",base1); /* 有效嗎? */ibase2 = base2; /* 數(shù)基2 */if ((ibase2<2) || (ibase2>36))printerror(2,"",base2); /* 有效嗎? */for (j=0;j<len;j++) //這個循環(huán)是為了將要轉(zhuǎn)換的數(shù)字轉(zhuǎn)換為十進(jìn)制{ /*******判斷字母或者數(shù)字，轉(zhuǎn)化為相應(yīng)的數(shù)字******************/r = pow(ibase1,len-j-1); /* 計(jì)算數(shù)基的冪指數(shù) */if (ibase1<=10)l = '9' - (10 - ibase1); /* 計(jì)算有效的數(shù)范圍 */else{ /* 計(jì)算有效的數(shù)范圍 */m = 'a' + (ibase1 - 11);l = '9';}if ((num[j]>=48) && (num[j]<=l)) /* 求每位數(shù)字的十進(jìn)制值 */k = num[j]-48;else if (ibase1>10){/* 求每個字母所代表的十進(jìn)制值 */if ((num[j]>='A') && (num[j]<=m - 32))k = num[j] - 'A'+10;else if ((num[j]>='a') && (num[j]<=m))k = num[j] - 'a'+10;else printerror(1,num,base1);}elseprinterror(1,num,base1);/***************************************************/inum += k * (int) r; /* 累加計(jì)算結(jié)果 */}/* 輸出轉(zhuǎn)換結(jié)果 */printf("%s(%d) = %s(%d)/n",num,ibase1,ltoa(inum,temp,ibase2),ibase2); } /* 主程序 */ int main(void) {char number[MAX];unsigned int m,n;static char num[10];static int base1,base2;printf("m進(jìn)制轉(zhuǎn)為n進(jìn)制，請輸入m和n：/n");scanf("%d %d", &m, &n);if(m<2||n<2){printf("非法輸入！");return 1;}getchar();printf("萬能進(jìn)制轉(zhuǎn)換程序。請輸入欲轉(zhuǎn)換的數(shù)：/n");gets(number);/*將輸入的m進(jìn)制數(shù)作為一個字符串接收*/strcpy(num,number);base1=m;base2=n;transnum(num,base1,base2); }

二、按照手機(jī)鍵盤輸入字母的方式，計(jì)劃所花費(fèi)的時間
如：a,b,c都在“1”鍵上，輸入a只需要按一次，輸入c需要連續(xù)按三次。
如果連續(xù)兩個字符不在同一個按鍵上，則可直接按，如：ad需要按兩下，kz需要按6下
如果連續(xù)兩字符在同一個按鍵上，則兩個按鍵之間需要等一段時間，如ac，在按了a之后，需要等一會兒才能按 C。
現(xiàn)在假設(shè)每按一次需要花費(fèi)一個時間段，等待時間需要花費(fèi)兩個時間段。
現(xiàn)在給出一串字符，需要計(jì)劃出它所需要花費(fèi)的時間。
輸入一：bob
輸出一：7
輸入二：www

#include <stdlib.h> #include <stdio.h> #include <string.h> #define MAX 100 int process(char *str,int len) {int flag=0;int delayflag=1;int i,j,delay=0;int length[9]={0,3,3,3,3,3,3,3,4};int location=0;int count;int press=len;char *pstr=str;int *number;int table[27][2];int (*p)[2]=table;number=malloc(sizeof(int)*(len+1));for(i=0;i<len;i++){number[i]=((*pstr++)-96);// printf("%d/n",number[i]);}number[i]=number[i-1];for(i=0;i<=26;i++)//初始化表的其他行{*(*(p+i))=i;switch(i){case 3:case 6:case 9:case 12:case 15:case 19:case 22:case 26:*(*(p+i)+1)=1;break;default:*(*(p+i)+1)=0;break;}}for(i=0;i<len-1;i++){printf("number[i]=%d/n",number[i]);printf("number[i+1]=%d/n",number[i+1]);delayflag=1;if((number[i]-number[i+1])<0){ for(j=number[i];j<number[i+1];j++){if(*(*(p+1)+j)==1)delayflag=0;printf("delayflag=%d/n",delayflag);}if(delayflag){delay+=1;}}else if((number[i]-number[i+1])>0){ for(j=number[i+1];j<number[i];j++){if(*(*(p+1)+j)==1)delayflag=0;}if(delayflag){delay+=1;}}else{delay+=1;}printf("delay=%d/n",delay);}for(i=0;i<len;i++){count=0;j=number[i];do{if((*(*(p+j)+1))==0)count+=1;}while((*(*(p+(j++))+1))==0);printf("count=%d",count);location+=(length[i+1]-count);printf("location=%d/n",location);}if(location==0)return (delay*2+location+len);elsereturn (delay*2+location); } int main(void) {int len;char str[MAX];char *p=str;gets(str);len=strlen(str);printf("%d/n",process(p,len));return 0; }

總結(jié)

以上是生活随笔為你收集整理的【Programming Clip】06、07年清华计算机考研上机试题解答（个别测试用例无法通过）...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。