Programming Clip】06、07年清华计算机考研上机试题解答(个别测试用例无法通过)-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

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

简介:

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<109

输出:

N 的质因数的个数

样例输入:

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

第二题(可执行文件名:program2.exe )

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

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

输入:

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

输出:

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

样例输入:

173

样例输出:

181

(下列程序只能忍受部分测试用例)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
#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<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;
}

第三题(可执行文件名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

样例输出:

3

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
#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<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.清华计算机系研究生考试上机06年试题解答(自己今天下午做的,郁闷之中。。。做的时间太长)

一、输入:两行
第一行:M和N
第二行:X
M和N是一个十进制数,M和N都在[2-36]之间,X是一个M进制数,X在[1-2*10^19]
输出:一行
第一行:现在要求你将M进制数X转换成N进制数输出
输入一:
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;
 }
}
/* 数制转换函数 */
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<len;j++) //这个循环是为了将要转换的数字转换为十进制
 { /*******判断字母或者数字,转化为相应的数字******************/
  r = pow(ibase1,len-j-1); /* 计算数基的幂指数 */
  if (ibase1<=10)
   l = '9' - (10 - ibase1); /* 计算有效的数范围 */
  else
  { /* 计算有效的数范围 */
   m = 'a' + (ibase1 - 11);
   l = '9';
  }
  if ((num[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 <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);
 else
  return (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;
}

本文转自gnuhpc博客园博客,原文链接:http://www.cnblogs.com/gnuhpc/archive/2012/01/17/2324785.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章