Tuesday, December 18, 2018

算法题-矩阵排序

admin    December 18, 2018    No comments

题目描述

编写函数
void order(int m, int n, int *matrix);
将 m × n 维的矩阵按照如下规则排序：
（1）首先将矩阵内每一列的元素值，按照从小到大的顺序排列；
（2）然后将矩阵各列按照该列元素之和的顺序从小到大排列，并将排序后的矩阵输出。
使用指针方法编程。

输入形式为：
m（行数 0 < m < 100）
n（列数 0 < n < 100）
矩阵元素 m 行 n 列（同一行的元素以空格隔开）
输出排序后的矩阵。若输入m,n不符合要求，则输出 “ERROR”。

输入

共 m+2 行整数：
m（行数 0 < m < 100）
n（列数 0 < n < 100）
矩阵元素 m 行 n 列（同一行的元素以空格隔开）

输出

排序后的矩阵元素 m 行 n 列（同一行的元素以空格隔开）

样例输入

3
3
1 2 9
4 8 6
7 5 3

样例输出

1 2 3
4 5 6
7 8 9

我的代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>

typedef struct {
    int prev, val;
} pos;

int data[105][105];
pos sum[105];

int compare_ints(const void* a, const void* b) {
    int arg1 = *(const int*)a;
    int arg2 = *(const int*)b;

    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;

    // return (arg1 > arg2) - (arg1 < arg2); // possible shortcut
    // return arg1 - arg2; // erroneous shortcut (fails if INT_MIN is present)
}

int compare_pos(const void* a, const void* b) {
    int arg1 = ((const pos*)a)->val;
    int arg2 = ((const pos*)b)->val;

    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;

    // return (arg1 > arg2) - (arg1 < arg2); // possible shortcut
    // return arg1 - arg2; // erroneous shortcut (fails if INT_MIN is present)
}


int main() {
    int m, n;
    scanf("%d%d", &m, &n);

    memset(sum, 0, sizeof(sum));

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int r = scanf("%d", &data[j][i]);
            if (r == EOF) {
                printf("ERROR");
                return 0;
            }
            sum[j].val += data[j][i];
        }
    }

    /* save as 
     * n row, m col 
     */

    for (int i = 0; i < n; ++i) {
        qsort(&data[i], m, sizeof(int), compare_ints);
        sum[i].prev = i;
    }

    qsort(sum, n, sizeof(pos), compare_pos);

    /* for (int i = 0; i < n; ++i) { */
    /*     printf("%d ", sum[i].val); */
    /* } */
    /* printf("\n"); */

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j) printf(" ");
            int k = sum[j].prev;
            printf("%d", data[k][i]);
        }
        printf("\n");
    }



    return 0;
}

算法题-接龙循环移位

admin    December 18, 2018    No comments

题目描述

编写函数
void shift_solit_matrix(int m, int n, int *matrix, int number);
将 m × n 维的矩阵进行一条龙循环移位。移位过程中，矩阵的相邻行相接，构成 “一条龙”（第一行与第二行尾相连，第二行与第三行首相连，依此类推）。使用指针方法编程。
输入形式为：
m（行数 0 < m < 100）
n（列数 0 < n < 100）
matrix 矩阵元素 m 行 n 列（同一行的元素以空格隔开）
number（位移大小，负数表示向左循环移位，正数表示向右循环移位）
输出移位后的矩阵。若输入m,n不符合要求，则输出 “ERROR”。

输入

共 m+3 行：
m（行数 0 < m < 100）
n（列数 0 < n < 100）
matrix 矩阵元素 m 行 n 列（同一行的元素以空格隔开）
number（位移大小，负数表示向左循环移位，正数表示向右循环移位）

输出

移位后的矩阵。若输入m,n不符合要求，则输出 “ERROR”。

样例输入

3
3
1 2 3
4 5 6
7 8 9
1

样例输出

9 1 2
5 6 3
4 7 8

我的代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>

void reverse(int *p, int len) {
    int *begin = p;
    int *end = p + len - 1;

    while (begin < end) {
        int t = *begin;
        *begin = *end;
        *end = t;

        begin++;
        end--;
    }
}

int main() {
    int data[30000];
    int m, n, k, *p = data+10000, p_idx = 0;
    scanf("%d%d", &m, &n);

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j, p_idx++) {
            int r = scanf("%d", p+p_idx);
            if (r == EOF) {
                printf("ERROR");
                return 0;
            }
        }
        if (i % 2) {
            reverse(p+(i*n), n);
        }
    }
    scanf("%d", &k);
    k %= (m * n);

    memcpy(p - (m*n), p, m*n*sizeof(int));
    memcpy(p + (m*n), p, m*n*sizeof(int));

    /*
    for (int i = 0; i < 3*n*m; i++) {
        printf("%d ", (p - (m*n))[i]);
    }

    printf("\n");
    */

    p -= k;
    p_idx = 0;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j, p_idx++) {
            if (j)
                printf(" ");

            if (i % 2)
                printf("%d", p[n*(i+1) - j - 1]);
            else
                printf("%d", p[p_idx]);
        }
        printf("\n");
    }






    return 0;
}

// vim: et:ts=4:sw=4:

算法题-最长共同子串

admin    December 18, 2018    No comments

题目描述

利用指针实现如下函数：
int Lsubstring(char s1[256], char s2[256], char s3[256], char *buffer)
函数功能为：将s1,s2,s3中的最长共同子串(子串之间用空格分隔)存在buffer指向的地址中，函数返回为最长子串的长度。在主函数中输出最长共同子串及其长度。若存在多个最长共同子串，则全部输出后（空格分隔），再输出长度。若无最长共同子串，则输出”NULL”。

输入

输入三行，分别是s1,s2,s3（每一行内的多个子串用空格隔开，每个字串长度不超过15）

输出

输出最长共同子串及其长度。如果有多个相同长度的最长共同子串，则依次输出，中间空格隔开；如果没有最长共同子串，则输出”NULL”

样例输入

aabb ccdd ee
aabb ee
ccdd aabb

样例输出

aabb 4

我写的代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <string.h>

int main() {
    char s[3][256][256];
    memset(s, 0, sizeof(s));
    int i = 0, j = 0, k = 0;

    for (char c; ~(c = getchar()); ) {
        if (c == '\n') {
            ++i;
            j = 0;
            k = 0;
        } else if (c == ' ') {
            ++j;
            k = 0;
        } else {
            s[i][j][k++] = c;
        }
    }

    int max = 0;
    for (int i = 0; s[0][i][0]; ++i) {
        for (int j = 0; s[1][j][0]; ++j) {
            for (int k = 0; s[2][k][0]; ++k) {
                if (!strcmp(s[0][i], s[1][j]) && !strcmp(s[0][i], s[2][k])) {
                    printf("%s ", s[0][i]);
                    max = strlen(s[0][i]);
                }
            }
        }
    }

    if (max) {
        printf("%d", max);
    } else {
        printf("NULL");
    }





    return 0;
}

// vim: et:ts=4:sw=4:

算法题-字符查找

admin    December 18, 2018    No comments


题目描述

现有如下计算机编程语言列表：
C, C++, Python, Java, Basic, C#, PHP, Javascript, SQL, Ruby, Matlab, Go, Perl, R, Fortran, Pascal, Swift；
请你根据用户输入的若干个字符，显示所有相匹配（包含该子串）的计算机语言。
例如：输入”Ba”，显示”Basic”；输入”C”，显示”C”, ”C++”, “C#”；输入”o”，显示”Python”, “Go”, “Fortran”。

输入

输入匹配字符串

输出

输出匹配结果，每个结果占一行，顺序按原始列表顺序

样例输入

C

样例输出

C
C++
C#

我写的代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <string.h>

int main() {
    char chs[] = ",C,C++,Python,Java,Basic,C#,PHP,Javascript,SQL,Ruby,Matlab,Go,Perl,R,Fortran,Pascal,Swift,";
    char s[1024];
    scanf("%s", s);

    int pos[1024], pos_idx = 0;
    
    for (int i = 0; i < strlen(chs); ++i) {
        if (chs[i] == ',')
            pos[pos_idx++] = i;
    }
    for (int i = 1; i < pos_idx; ++i) {
        int r = -1;
        for (int j = pos[i-1]+1; j < pos[i]; ++j) {
            r = strncmp(chs+j, s, strlen(s));
            if (r == 0)
                break;
        }
        if (r == 0) {
            for (int j = pos[i-1]+1; j < pos[i]; ++j) {
                printf("%c", chs[j]);
            }
            printf("\n");
        }
    }



    return 0;
}

Wednesday, December 12, 2018

求解三对角矩阵线性方程组

admin    December 12, 2018    No comments





求解三对角矩阵线性方程组
时间限制: 1000 ms 内存限制: 1600 KB
by Kailai Zhang

问题描述

三对角矩阵是指除主对角线和其相邻的上下两条对角线之外，其他所有元素都为0的矩阵。
本次实验给定一个三对角矩阵A和右端矩阵B，求解矩阵方程AX=B。
可以认为B=[b1,b2,…,bn]为一些列向量的组合，从而解出的矩阵X=[x1,x2,…,xn]为一些解向量的组合。
本次实验给出的矩阵A均为三对角非奇异方阵，解的准确程度由残差值 ||Axi - bi||2给出，这里i从1到n，要求对所有i，残差值都小于 0.1。

输出格式

输出一共为n行，每行m个浮点数，依次表示X矩阵从第1列到第n列的m个元素的值。
根据以上定义，输出的每一行必须满足对应的残差值小于0.1。

输入样例






1
2
3
4
5
6
5 2 \\表示A为5乘5的矩阵，B为5乘2的矩阵
1.0 2.0 3.0 4.0 5.0 \\表示主对角线上的五个数
1.0 1.0 1.0 1.0 \\表示主对角线上方对角线的四个数
6.0 5.0 4.0 3.0 \\表示主对角线下方对角线的四个数
3.0 13.0 23.0 33.0 37.0 \\表示B的第一列的值
2.0 9.0 9.0 9.0 8.0 \\表示B的第二列的值

输出样例






1
2
1.0 2.0 3.0 4.0 5.0 \\表示X矩阵第一列的值
1.0 1.0 1.0 1.0 1.0 \\表示X矩阵第二列的值

提示

输出结果并不唯一，只需要使X矩阵的所有列都满足残差小于0.1即可。
C++默认的输出精度可能不满足残差要求，同学们需要显式提高输出精度。

我写的代码

算法参考: https://en.wikipedia.org/wiki/Tridiagonal_matrix
跟着算法写就可以了, 最后提高下输出位数





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    double a[n+2], b[n+2], c[n+2], d[n+2], x[n+2];
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }
    for (int i = 1; i <= n-1; ++i) {
        cin >> c[i];
    }
    for (int i = 2; i <= n; ++i) {
        cin >> a[i];
    }

    // calc c'[i]
    c[1] /= b[1];
    for (int i = 2; i <= n-1; ++i) {
        c[i] /= (b[i] - a[i]*c[i-1]);
    }

    for (int j = 0; j < m; ++j) {
        for (int i = 1; i <= n; ++i) {
            cin >> d[i];
        }

        // calc d'[i]
        d[1] /= b[1];
        for (int i = 2; i <= n; ++i) {
            d[i] = (d[i] - a[i]*d[i-1]) / (b[i] - a[i]*c[i-1]);
        }

        // calc x[i]
        x[n] = d[n];
        for (int i = n-1; i >= 1; --i) {
            x[i] = d[i] - c[i]*x[i+1];
        }

        // print
        for (int i = 1; i <= n; ++i) {
            cout << fixed << setprecision(50)
                 << x[i] << " ";
        }
        cout << endl;

    }

    return 0;
}
Subscribe to: Posts (Atom)