Google2012.9.24校园招聘会笔试题

      代码： ~~~ //转载请标明出处，原文地址：http://blog.csdn.net/hackbuteer1/article/details/8017703 bool IsPrime(int n) { int i; if(n < 2) return false; else if(2 == n) return true; if((n&1) == 0) //n%2 == 0 return false; for(i = 3 ; i*i <= n ; i += 2) //只考虑奇数 { if(n % i == 0) return false; } return true; } /* 考虑到所有大于4的质数，被6除的余数只能是1或者5 比如接下来的5,7,11,13,17,19都满足 所以，我们可以特殊化先判断2和3 但后面的问题就出现了，因为并非简单的递增，从5开始是+2,+4,+2,+4,....这样递增的 这样的话，循环应该怎么写呢？ 首先，我们定义一个步长变量step，循环大概是这样 for (i = 5; i <= s; i += step) 那么，就是每次循环，让step从2变4，或者从4变2 于是，可以这么写： */ bool IsPrime2(int n) { int i, step = 4; if(n < 2) return false; else if(2 == n || 3 == n) return true; if((n&1) == 0) //n%2 == 0 return false; if(n%3 == 0) //n%3 == 0 return false; for(i = 5 ; i*i <= n ; i += step) { if(n % i == 0) return false; step ^= 6; } return true; } void print_prime(int n) { int i , num = 0; for(i = 0 ; ; ++i) { if(IsPrime2(i)) { printf("%d " , i); ++num; if(num == n) break; } } printf("\n"); } ~~~  代码： ~~~ //转载请标明出处，原文地址：http://blog.csdn.net/hackbuteer1/article/details/8017703 void myswap(int a , int b , int* array) { int temp = array[a]; array[a] = array[b]; array[b] = temp; } //利用0和其它数交换位置进行排序 void swap_sort(int* array , int len) { int i , j; for(i = 0 ; i < len ; ++i) //因为只能交换0和其他数，所以先把0找出来 { if(0 == array[i]) { if(i) //如果元素0不再数组的第一个位置 myswap(0 , i , array); break; } } for(i = 1 ; i < len ; ++i) //因为是0至N-1的数，所以N就放在第N的位置处 { if(i != array[i]) //这个很重要，如果i刚好在i处，就不用交换了，否则会出错 { for(j = i + 1 ; j < len ; ++j) { if(i == array[j]) { myswap(0 , j , array); //把0换到j处，此时j处是0 myswap(j , i , array); //把j处的0换到i处，此时i处是0 myswap(0 , i , array); //把i处的0换到0处 } }//for } }//for } ~~~  代码： ~~~ //转载请标明出处，原文地址：http://blog.csdn.net/hackbuteer1/article/details/8017703 int mymin(int a , int b , int c) { int temp = (a < b ? a : b); return temp < c ? temp : c; } int min_edit_dic(char* source , char* target) { int i , j , edit , ans; int lena , lenb; lena = strlen(source); lenb = strlen(target); int**distance = new int*[lena + 1]; for(i = 0 ; i < lena + 1 ; ++i) distance[i] = new int[lenb + 1]; distance[0][0] = 0; for(i = 1 ; i < lena + 1 ; ++i) distance[i][0] = i; for(j = 1 ; j < lenb + 1 ; ++j) distance[0][j] = j; for(i = 1 ; i < lena + 1 ; ++i) { for(j = 1 ; j < lenb + 1 ; ++j) { if(source[i - 1] == target[j - 1]) edit = 0; else edit = 1; distance[i][j] = mymin(distance[i - 1][j] + 1 , distance[i][j - 1] + 1 , distance[i - 1][j - 1] + edit); //distance[i - 1][j] + 1 插入字符 //distance[i][j - 1] + 1 删除字符 //distance[i - 1][j - 1] + edit 是否需要替换 } } ans = distance[lena][lenb]; for(i = 0 ; i < lena + 1 ; ++i) delete[] distance[i]; delete[] distance; return ans; } ~~~