清华机试题目.doc

清华机试题目 2012年 题目1483：求最大最小数 输入N个（N=10000）数字，求出这N个数字中的最大值和最小值。每个数字的绝对值不大于1000000。 #includestdio.h #includestdlib.h #includelimits.h int FindMinMax(long long int A[],int size,long long int min,long long int max) { min = A[0]; max = A[0]; for(int i = 1;i size;i++) { if(A[i] max){ max = A[i]; } if(A[i] min){ min = A[i]; } } return 0; } int main () { int i,N; long long int min,max; long long int Array[10001]; while(scanf(%d,N) != EOF){ for(i = 0;i N;i++){ scanf(%lld,Array[i]); } FindMinMax(Array,N,min,max); printf(%lld %lld\n,max,min); }//while return 0; } 题目1482：玛雅人的密码 玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=N=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。 #include iostream #include cstring #include queue using namespace std; const int N = 1600000; bool used[N]; int n; typedef struct Node{ int num , cnt ; char arr[14]; }Node; queueNode Q; void swap(char *str , int i , int j){ int temp = str[i]; str[i] = str [j]; str[j] = temp; } bool test(char *str){ for(int i = 0 ; i = n- 4 ; i ++){ if(str[i] == 2 str[i + 1] == 0 str[i + 2] == 1 str [i + 3] == 2) return true; } return false; } int stringToInt(char *str){ int res = 0; for( int i = 0 ;str[i] ; i ++){ res = 3 * res + str[i] - 0; } return res; } int bfs(){ while( !Q.empty()){ Node temp = Q.front(); int cnt = temp.cnt; Q.pop(); if(test(temp.arr)){ return temp.cnt; } for(int i = 0 ;i n - 1 ; i ++){ swap(temp.arr,i,i+1); int num = stringToInt(temp.arr); if(!used[num]){ used[num] = true; No