【机试】2013华科机试题【纯C实现】.md

2013年华科机试题

pro01, 孪生素数

/**
1.孪生素数（30 分）
如果n 和n+2 都是素数，则称它们是孪生素数。输入m，输出2 个均不超过m 的最大孪生
素数。5<=m<=1000。例如m=20 时候，答案为17、19
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000+5
#define LL_MAX ((1LL<<63)-1)
#define ll long long
#define mem(a, n) memset(a, n, sizeof(a))

//int is_pri[MAXN];
//int cnt, primes[MAXN];
//int is_prime() {
//    cnt=0;
//    mem(is_pri, 0);
//    int i, j;
//    for(i=2; i*i<MAXN; i++) {
//        if(!is_pri[i]) {
//            for(j=i*i; j<MAXN; j+=i) {
//                is_pri[j]=1;
//            }
//        }
//    }
//    for(i=2; i<MAXN; i++){
//        if(!is_pri[i]) {
//            primes[cnt++] = i;
//        }
//    }
//}
int is_prime2(int x) {
    int i;
    for(i=2; i*i<=x; i++) {
        if(x%i==0) {
            return 0;
        }
    }
    return 1;
}

int main() {
//    is_prime();
    int m;
    while(~scanf("%d", &m)) {
        int i;
        for(i=m; i>=2; i--) {
            if(is_prime2(i) && is_prime2(i-2)) {
                printf("%d %d\n", i-2, i);
                break;
            }
        }
    }
    return 0;
}

pro02，顺转数组

#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000+5
#define LL_MAX ((1LL<<63)-1)
#define ll long long
#define mem(a, n) memset(a, n, sizeof(a))

/**
2.顺转数组（30 分）
输入一个数字n，输出一个n 阶顺转数组
如输入：5
输出：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
*/
/// 思路：按照一圈一圈来分析知，定四个角的位置来填充数字

int cnt=0;
int **matrix;
void solve(int l, int r, int u, int d) {
    if(l > r || u > d) {
        return ;
    }
    int i;
    for(i=l; i<=r; i++) {
        matrix[u][i] = cnt++;
    }
    for(i=u+1; i<=d; i++) {
        matrix[i][r] = cnt++;
    }
    for(i=r-1; i>=l; i--) {
        matrix[d][i] = cnt++;
    }
    for(i=d-1; i>u; i--) {
        matrix[i][l] = cnt++;
    }
    solve(l+1, r-1, u+1, d-1);
}
int main() {

    int n;
    while(~scanf("%d", &n)) {
        matrix = (int**) malloc(sizeof(int*)*n);
        int i, j;
        for(i=0; i<n; i++) {
            matrix[i] = (int*) malloc(sizeof(int)*n);
        }
        solve(0, n-1, 0, n-1);
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                printf("%4d ", matrix[i][j]);
            }
            puts("");
        }
    }
    return 0;
}

pro03，最长回文子串

/**
3.最长子回文串（40 分）、
输入一个字符串，求出其中最长的回文子串。子串的含义是：在原串连续出现的字符串片段。
回文的含义是：正着看和倒着看是相同的，如abba 和abbebba。在判断是要求忽略所有的
标点和空格，且忽略大小写，但输出时按原样输出（首尾不要输出多余的字符串）。输入字
符串长度大于等于1 小于等于5000
样例输入
She say:Madam,I'm Adam.
样例输出
Madam,I'm Adam
*/
/// 思路：判断回文子串时，忽略大小写，需要原样输出，那么需要使用一个临时字符串tmpstr存储原串；判断回文字串可以用暴力。 复杂度0(n^2)，还可以KMP或者更快的算法Manacher算法 O(n)。 若不要求复杂度就暴力，不然学下manacher