【Programming Clip】06、07年清华计算机考研上机试题解答（个别测试用例无法通过）...-白红宇

【Programming Clip】06、07年清华计算机考研上机试题解答（个别测试用例无法通过）...

阅读量：5327 次

发布时间：2019-06-14

本文共 5988 字，大约阅读时间需要 19 分钟。

作者：

出处：

1.清华计算机系研究生考试上机07年试题解答（自己今天上午做的，有一个不能完成所有测试用例～）

清华大学计算机科学与技术系

2007 年硕士研究生招生复试

2007 年 3 月 24 日

注意事项：

1. 试题共三题，总计 100 分，考试时间为一个半小时。

2. 不得使用自带的电子设备，包括笔记本、 U 盘、手机等；不得使用参考书籍和资料。

3. 编程环境为 Windows 2000 Professional + Visual Studio 6.0 ，只能使用 C/C++ 语言。

4. 每一题的输入数据都从文件 input.txt 中读取，将结果输出至文件 output.txt ，请严格按照每一题的输入输出格式 。在考试过程中，我们恕不提供除试题中样例以外的测试数据，请自行生成输入数据以对程序进行自测。

5. 在考试结束之前自行设置编译环境和配置编译参数，将所写的程序编译成可执行文件，文件名在每一题中都有规定。生成的可执行文件将作为最终测试的唯一依据，若无法运行您的可执行文件，最终成绩将记为零分。

6. 程序对每个测试数据的可用运行时间上限 1 秒，若超时或结果错误，则该测试用例不能得分。

7. 在考试过程中，若计算机出现故障，请及时通知工作人员，以免耽误您的考试时间。

8. 上机考试结束后，请勿马上离开，工作人员将会直接进行现场测试，需要您的合作。

第一题（可执行文件名 program1.exe ）

求正整数 N(N>1) 的质因数的个数。注意： 1 不是 N 的质因数：若 N 为质数， N 是 N 的质因数。相同的质因数需要重复计算。

如 120=2*2*2*3*5 ，共有 5 个质因数。

输入：

正整数N ，1<N<10⁹

输出：

N 的质因数的个数

样例输入：

120

样例输出

#include
     
      #include
      
       #include
       
         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;}

第二题（可执行文件名：program2.exe ）

对于一个十进制数A ，将A 转换为二进制数，然后按位逆序排列，再转换为十进制数B ，我们乘B 为A 的二进制逆序数 。

例如对于十进制数173 ，它的二进制形式为101011101 ，逆序排列得到10110101 ，其十进制数为181 ，181 即为173 的二进制逆序数

输入：

一个1000 位( 即2⁹⁹⁹ ) 以内的十进制数。

输出：

输入的十进制数的二进制逆序数。

样例输入：

173

样例输出：

181

（下列程序只能忍受部分测试用例）

#include 
     
      #include 
      
       #include 
       
        #include 
        
          #define MAX 100#define LEN 1000 long 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

第三题（可执行文件名program3.exe ）

有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。

如，有1 分，3 分，3 分，3 分，4 分五张邮票，要求凑成10 分，则使用3 张邮票：3 分、3 分、4 分即可。

输入：

首先是要求凑成的邮票总值M ，M<100

然后是一个数N ，N 〈20 ，表示有N 张邮票。接下来是N 个正整数，分别表示这N 张邮票的面值，且以升序排列。

输出：

能够凑成总值M 的最少邮票张数。若无解，输出0 。

样例输入：

10 5 1 3 3 3 4

样例输出：

分析：这是最简单的背包问题，动态规划的方法，写得不是很规范，不过结果很不错，线形复杂度 ~~

#include 
     
      #include 
      
       #include 
       
        #include 
        
          #define MAX 100#define LEN 1000 void 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

2.清华计算机系研究生考试上机06年试题解答（自己今天下午做的，郁闷之中。。。做的时间太长）

一、输入：两行

第一行：M和N

第二行：X

M和N是一个十进制数，M和N都在[2-36]之间，X是一个M进制数，X在[1-2*10^19]

输出：一行

第一行：现在要求你将M进制数X转换成N进制数输出

输入一：

16 10

输出一：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #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; }}/* 数制转换函数 */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); /* 数值的长度 */  ibase1 = base1; /* 数基1 */ if ((ibase1<2) || (ibase1>36))  printerror(2,"",base1); /* 有效吗? */ ibase2 = base2; /* 数基2 */ if ((ibase2<2) || (ibase2>36))  printerror(2,"",base2); /* 有效吗? */ for (j=0;j
         
          =48) && (num[j]<=l)) /* 求每位数字的十进制值 */   k = num[j]-48;  else if (ibase1>10)  {   /* 求每个字母所代表的十进制值 */   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);  }  else   printerror(1,num,base1);   /***************************************************/  inum += k * (int) r; /* 累加计算结果 */  } /* 输出转换结果 */ 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进制转为n进制，请输入m和n：/n"); scanf("%d %d", &m, &n); if(m<2||n<2) {  printf("非法输入！");  return 1; } getchar(); printf("万能进制转换程序。请输入欲转换的数：/n"); gets(number);/*将输入的m进制数作为一个字符串接收*/  strcpy(num,number); base1=m; base2=n; transnum(num,base1,base2);}

二、按照手机键盘输入字母的方式，计划所花费的时间

如：a,b,c都在“1”键上，输入a只需要按一次，输入c需要连续按三次。

如果连续两个字符不在同一个按键上，则可直接按，如：ad需要按两下，kz需要按6下

如果连续两字符在同一个按键上，则两个按键之间需要等一段时间，如ac，在按了a之后，需要等一会儿才能按 C。

现在假设每按一次需要花费一个时间段，等待时间需要花费两个时间段。

现在给出一串字符，需要计划出它所需要花费的时间。

输入一：bob

输出一：7

输入二：www

#include 
     
      #include 
      
       #include 
       
        #define MAX 100int 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
        
         0)  {    for(j=number[i+1];j