C语言习题 | 戊成的BLOG

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

蛇形填数

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

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

代码：

#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的全部数字就行了

代码：

#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范围的数要怎么处理，再看的时候简直不要太简单

#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的字符串，输出其最小周期

代码：

#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来从缓冲区读取字符，配合字符数组来进行操作。

代码：

#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距离数组的下标记录下来，由于题目要求多解时输出最小字典，所以在外部定义一个函数记录字符串的大小。

#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日）

#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语言标准问题浪费好多时间应该可以搞个一等奖的，有点可惜了。