还是三道题。粗略地测试了一下，貌似没有大问题。
贴上来。
2008年的复试上机题目：
1.素数
输入一个整数，要求输出所有从1到这个整数之间个位为1的素数，如果没有则输出-1（30分）（水题吗）
#include <stdio.h> #include <math.h> bool judge(int n) { bool flag=true; for(int i=2;i<=sqrt(n);i++) { if(n%i==0) { flag=false; break; } } return flag; } void main() { int n; scanf("%d",&n); if(n<=11) { printf("%d",-1); } else { for(int i=11;i<n;i=i+10) { if(judge(i)) { printf("%d ",i); } } } } |
2.旋转矩阵
任意输入两个9阶以下矩阵，要求判断第二个是否是第一个的旋转矩阵，如果是，输出旋转角度（0、90、180、270），如果不是，输出-1。
要求先输入矩阵阶数，然后输入两个矩阵，每行两个数之间可以用任意个空格分隔。行之间用回车分隔，两个矩阵间用任意的回车分隔。（60分）
#include <stdio.h> void printMatrix(int** a,int n) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { printf("%d ",a[i][j]); } printf("%s","\n"); } } void initMatrix(int** a,int n) { for(int i=0;i<n;i++) { a[i]=new int [n]; for(int j=0;j<n;j++) { scanf("%d",&a[i][j]); } } } bool zero(int** a,int** b,int n) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(a[i][j]==b[i][j]) continue; else return false; } } return true; } bool ninety(int** a,int** b,int n) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(a[i][j]==b[j][n-1-i]) continue; else return false; } } return true; } bool reverse(int** a,int** b,int n) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(a[i][j]==b[n-1-i][n-1-j]) continue; else return false; } } return true; } bool counterninety(int** a,int** b,int n) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(a[i][j]==b[n-1-j][i]) continue; else return false; } } return true; } void main() { int m=0,n=0; scanf("%d",&n); scanf("%d",&m); int** m1=new int* [n]; int** m2=new int* [m]; initMatrix(m1,n); initMatrix(m2,m); if(m!=n) { printf("%d",-1); } else if(zero(m1,m2,n)) { printf("%d",0); } else if(ninety(m1,m2,n)) { printf("%d",90); } else if(reverse(m1,m2,n)) { printf("%d",180); } else if(counterninety(m1,m2,n)) { printf("%d",270); } else { printf("%d",-1); } } |
3.字符串匹配
从string.in中读入数据，然后用户输入一个短字符串。要求查找string.in中和短字符串的所有匹配，输出行号、匹配字符串到string.out文件中。匹配时不区分大小写，并且可以有一个用中括号表示的模式匹配。如“aa[123]bb”，就是说aa1bb、aa2bb、aa3bb都算匹配。（60分）
#include <stdio.h> #include <string.h> #include <ctype.h> //认为[]只能匹配一个字符 char getNewStarter(char *t,int j) { while(t[j]!=']') j++; return t[j+1]; } bool find(char *s,char *t,int start,int& end) { int i=start,j=0; end=start; while(t[j]&&s[i]) { if(tolower(s[i])==tolower(t[j])) { i++; j++; } else if(t[j]=='[') { if(tolower(s[i])==tolower(getNewStarter(t,j)))//fanjunishere fan[89]jun和[89]fanjun { while(t[j]!=']') j++; i++; j=j+2; } else if(getNewStarter(t,j)=='\0')//fanjunishere fanjun[89] { end=i; return true; } else{//普通情况 bool flag=false; do { j++; if(tolower(t[j])==tolower(s[i])) { flag=true; } }while(t[j]!=']'); if(!flag) { return false; } else { i++; j++; } } } else { return false; } } if(t[j]=='\0'||t[j]=='[')//doyouknowfanjun fanjun[89] { end=i; return true; } else { return false; } } void main() { char input[50]; scanf("%s",input); FILE *fp1,*fp2; if ((fp1=fopen("string.in","r"))==NULL) { printf("cannot open file\n"); return; } fp2=fopen("string.out","w"); char buff[50]; int line=1; while(fgets(buff,50,fp1)>0) { for(unsigned int i=0;i<strlen(buff);i++) { int end; if(find(buff,input,i,end)) { fprintf(fp2,"%d ",line); for(int j=i;j<end;j++) fprintf(fp2,"%c",buff[j]); fprintf(fp2,"%s","\n"); } } line++; } } |
总结一下，字符串是重点。
考研的复试需不需要对这些题目进行一些算法优化？
比如第一题可以用筛法求素数之类的？这样会不会得到一些加分？
小弟明年也要考研，特地求教求教
我感觉评分应该和acm评测那个差不多，就是给出具有一些区分度的测试数据看程序能否通过。优化算法对通过那些“边缘数据”是有帮助的
错误了。。。我是后年考。。。最近脑子比较呆
其实感觉最后一题可以用字典树来做，速度会快很多，我感觉60分的题目，直接这样暴力跑会不会太简单了？
你的意思是用带有[]的字符串生成字典树，然后再用原串在字典树中查找字符串吗？
只看了第三题，感觉用trie树做比较好。
先把string.in中的数据生成trie树，然后根据输入进行遍历，效率会高些
我怎么感觉是用输入的串生成trie树，然后用string.in中的数据来遍历这个树呢?
你是不是认为输入的字符串中没有中括号，而中括号在string.in的数据中？
好定西