戊成的BLOG
C语言习题
Wucheng
  2022-02-19 01:52:19   2024-11-30 17:08:33

由于报了竞赛所以苦逼的在寒假也要写题目，开一篇记录一下寒假写的部分算法题

蛇形填数

在nn的矩形中填入1，2，3，……，nn，要求填成蛇形
如4*4方阵：

1
2
3
4
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4

大致的思路就是将全部值初始化为0，从最右边开始的值为1，开始向下填数
在填数的时候就直接判断在不超过界限的情况下值是否为0
是0就填，不是的话就进入下一个循环开始向左填数，以此类推

代码：

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
#include<stdio.h>
int main()
{
    int array[100][100] = {0};
    int x,y;
    int n,num = 1;

    scanf("%d",&n);
    x = 0, y = n-1;
    array[x][y] = 1;

    while (num < n*n)
    {
        while(array[x+1][y] == 0 && x < n-1) array[++x][y] = ++num;
        while(array[x][y-1] == 0 && y > 0) array[x][--y] = ++num;
        while(array[x-1][y] == 0 && x > 0) array[--x][y] = ++num;
        while(array[x][y+1] == 0) array[x][++y] = ++num;
    }
    
    for (size_t x = 0; x < n; x++)
    {
        for (size_t y = 0; y < n; y++)
        {
            printf("%-5d ",array[x][y]);
        }
        printf("\n");
    }
    
}

排列

用1，2，3，…，9组成3个三位数abc，def和ghi，每个数字恰好使用一次
要求abc：def：ghi＝1：2：3。按照“abc def ghi”的格式输出所有解，每行一个解

排列组合然后判断比值虽然没有什么问题，但是这样实在不大划算（虽然但是不管怎么说其实能用也不用纠结那么多的XD）
所以一开始就直接以a作为基数，b=2a、c=3a，然后再用布尔数组判断是否使用了1-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
#include <stdio.h>
_Bool array(_Bool num[])//判断是否使用了全部的数字
{
    for (size_t i = 1; i < 10; i++)
        if(num[i] == 0) return 1;
    return 0;
}

int main()
{
    int a,b,c;

    for (int i = 111; i < 999; i++)
    {
        _Bool num[10] = {0};
        a = i;
        b = i * 2;
        c = i * 3;

        if(c > 999) break;

        for(; c > 0; a /= 10, b /= 10, c /= 10)//如果使用了那个数字，则将布尔数组的该下标值改为1
        {
            num[a % 10] = 1;
            num[b % 10] = 1;
            num[c % 10] = 1;
        }

        if(array(num) == 1) continue;
        else printf("%d %d %d\n",i,i * 2, i * 3);
    }
    
}

数数字

把整数顺次写在一起，数一数0~9各出现过多少次

这个题是初中学C的时候被难住的一题，当时完全不知道超出long范围的数要怎么处理，再看的时候简直不要太简单

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
int main()
{
    int count[10] = {0};
    char num;

    while ((num = getchar()) != '\n')
        count[num - 48]++;//由于getchar读入的是字符串，所以只要减去0对应的ASCII码就行了

    for (size_t i = 0; i < 10; i++)
        printf("%d",count[i]);
    
}

周期字符串

如果一个字符串可以由某个长度为k的字符串重复多次得到，则称该串以k为周期
例如，abcabcabcabc以3为周期
输入一个长度不超过80的字符串，输出其最小周期

代码：

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
#include<stdio.h>
#include<string.h>

_Bool compared(char ch[100], int len , int i)//历遍数组后面是否与前面重复
{
    for (size_t n = i; n < len; n++)
    {
        if(ch[n] != ch[n % i]) return 0;
    }
    return 1;
}

int main()
{
    char ch[100];
    int len;
    _Bool ok;

    scanf("%s",ch);
    len = strlen(ch);

    for (size_t i = 1; i < len; i++)
    {
        if(len % i == 0)//判断是否为字符串长度的倍数
            ok = compared(ch, len, i);
        else continue;

        if(ok)
        {
            printf("%d",i);
            break;
        }
    }
}

谜题

有一个5*5的网格，其中恰好有一个格子是空的，其他格子各有一个字母。
一共有4种指令：A, B, L, R，分别表示把空格上、下、左、右的相邻字母移到空格中。
输入初始网格和指令序列（以数字0结束），输出指令执行完毕后的网格。如果有非法指令，应输出“This puzzle has no final configuration.”

首先读取文件中的字符，前面用的是fscanf函数一个一个读取祖父，但是遇到后面的换行符就不大好处理，而用fscanf函数读取字符串的话遇到空格就会直接停下，所以最好用的还是fgets函数。
然后用getchar来从缓冲区读取字符，配合字符数组来进行操作。

代码：

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
#include<stdio.h>
#define NUM 5
int main()
{
    char str[10][10];
    char put;
    int x = 2, y = 1;//空字符所处位置
    FILE *fp;
    fp = fopen("test.in","rb");

    for (size_t i = 0; i < NUM; i++)
            fgets(str[i],10,fp);//读取字符串

    while ((put = getchar()) != '0')
    {
        if(put == 'A') str[x][y] = str[x-1][y],x--;
        else if(put == 'B') str[x][y] = str[x+1][y],x++;
        else if(put == 'L') str[x][y] = str[x][y-1],y--;
        else if(put == 'R') str[x][y] = str[x][y+1],y++;
        else {printf("This puzzle has no final configuration\n"); break;}
    }

    str[x][y] = ' ';//再将最后停留的位置变回空字符

    for (size_t i = 0; i < NUM; i++)
    {   for (size_t j = 0; j < NUM; j++)
            printf("%c",str[i][j]);
        printf("\n");
    }
}

DNA序列

输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总Hamming距离尽量小。
两个等长字符串的Hamming距离等于字符不同的位置个数，例如，ACGT和GCGA的Hamming距离为2（左数第1, 4个字符不同）。
输入整数m和n（4≤m≤50, 4≤n≤1000），以及m个长度为n的DNA序列（只包含字母A，C，G，T），输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。
如有多解，要求为字典序最小的解。例如，对于下面5个DNA序列，最优解为TAAGATAC。
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

用三重循环先把每个数组的总hamming距离计数，然后把最小的hamming距离数组的下标记录下来，由于题目要求多解时输出最小字典，所以在外部定义一个函数记录字符串的大小。

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 <stdio.h>

int compare(char a[], char b[], int mark, int last, int n)//在相同的情况下比较字典最小
{
    int count1 = 0,count2 = 0;
    for (size_t i = 0; i < n; i++)
    {
        count1 += a[i];
        count2 += b[i];
    }
    
    if(count1 < count2) return mark;
    else return last;
}

int main()
{
    char dna[50][1000];
    int count[50] = {0};//hamming距离计数
    int m,n;
    
    scanf("%d %d",&m,&n);
    
    for (size_t i = 0; i < m; i++)
        scanf("%s",dna[i]);

    for (size_t x = 0; x < m; x++)//记录对应的Hamming距离
        for (size_t y = 0; y < m; y++)
        {
            if(x == y) continue;
            for (size_t z = 0; z < n; z++)
                if(dna[x][z] != dna[y][z]) count[x]++;
        }

    int min = count[0];//最小值
    int index = 0;//最小值下标
    for (int i = 1,last_min; i < m; i++)
    {
        if(count[i] < min)
        {
            min = count[i];
            last_min = i;
            index = i;
        }
        else if(count[i] == min)//hamming距离相等时比较上一个最小hamming距离的数组
        {
            index = compare(dna[i], dna[last_min], i, last_min, n);
            last_min = index;
        }
    }
    printf("%s\n",dna[index]);
}

八皇后问题

在8*8的宫格中，放置8个皇后，8个皇后之间所占据的位置中八个方位不能有其他皇后

这题要用到回溯算法，在递归中发现错误回退上一步再尝试下一个解法
下面的代码是我从网上找的参考，并不是我自己写的，等写出来后再把自己的放上来（2.19日）

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
81
82
83
84
85
86
87
#include <stdio.h>
#include <stdlib.h>
#define length 8

int count = 0;  // 计数 
int ms[length][length] = {0};

// 判断将皇后放在(a, b)位置上是否合法 
int isTrue(int a, int b)
{
    int t;
    // 向上判断 
    for(t=a-1; t>=0; t--)
    {
        if(ms[t][b] == 1)
            return 0;
    }

    // 向左判断左
    for(t=b-1; t>=0; t--){
        if(ms[a][t] == 1)
            return 0;
    }

    int m, n;
    // 向左上判断 
    for(m=a-1,n=b-1; m>=0&&n>=0; m--,n--)
    {
        if(ms[m][n] == 1)
            return 0;
    }
    // 向右上判 
    for(m=a-1,n=b+1; m>=0&&n<length; m--,n++)
    {
        if(ms[m][n] == 1)
            return 0;
    }
    return 1;
}

// 打印八皇后 
void print(){
    count++;
    printf("%d:\n", count);
    int a, b;
    for(a=0; a<length; a++) // 行 
    {
        for(b=0; b<length; b++) // 列 
        {
            if(ms[a][b] == 0)
            {
                printf("* ");
            }
            else if(ms[a][b] == 1)
            {
                printf("# ");
            }
        }
        printf("\n");
    }
    printf("\n\n");
}

// 递归调用 m表示层数 
void fun(int m){
    if(m == length)  
    {
        print();    // 输出 
        return;     // 递归出口
    }
    int i;
    for(i=0; i<length; i++)
    {
        if(isTrue(m, i))    // 回溯算法 
        {
            ms[m][i] = 1;   // 10表示此位置有皇后
            fun(m+1);       // 递归调用 
            ms[m][i] = 0;   // 0表示此位置无皇后 
        }
    }
}

int main(void)
{
    fun(0);
    return EXIT_SUCCESS;
}

最后

十三届蓝桥杯二等奖

没想到我这么摸也能拿个二等奖，不过如果不是因为c语言标准问题浪费好多时间应该可以搞个一等奖的，有点可惜了。

  1. 蛇形填数
  2. 排列
  3. 数数字
  4. 周期字符串
  5. 谜题
  6. DNA序列
  7. 八皇后问题
  8. 最后
  1. 蛇形填数
  2. 排列
  3. 数数字
  4. 周期字符串
  5. 谜题
  6. DNA序列
  7. 八皇后问题
  8. 最后