补作业6

2021-11-12

字数统计: 1.1k字 | 阅读时长≈ 4分

XTU-oj-作业06补题解

作业六题解还差两题，补充一下。

B ：Robb’s Problem

这道题比较有意思，一般思路：算就完了！但我们粗略的算一下，20!=2432902008176640000一共19位…更别说100甚至1000的阶乘了。

所以咋办呢，这个时候我们就要考虑一下，怎么把这么大的数储存。这里就需要灵活的运用我们的数组这种顺序储存结构。也就是我们以数组中的每一个储存单元储存一部分的数字，然后以整个一行的数组代表乘完的数字，设每个存储单元存储的大小为R个数字，则每个储存单元的权重就是10×R,用Σa[i]*(10×R)^(i-1)表示结果。

既然解决了数字太大没法存的问题，如何去乘，就成了新的问题。正常来说我们直接数乘数就好了，那对于这种把数字都储存在了数组里面我们如何乘呢？回想我们的乘法竖式，我们应该是用第二个数的每一位去乘以第一个数，同理我们也可以把已经储存在数组里面的数字的每一个储存单元看作一位然后去乘下一个数就好。

这样成就可以了吗？当然不是！我们还要考虑进位的问题，那进位进啥呢？我们在储存结果的时候是按照R位来储存的，那么我们就把超过R位的作为进位，加到下一位相乘后的结果就好了！也就是用到了取余的运算来保证结果是R位，除以R向下取整就是进位的值。

但过做到这一点恐怕还是不行！因为会超时！那我们该咋办呢？打表！用一个二位数组来搞，整个i行储存的就是i!

这样的结果是储存在数组里面，我们要去m位就可以对让i = m/R，k = m%R，然后各种逻辑思路就能找到了！

（敲了好久累了直接上代码）：

/*
为了让进位更好实现，我们让R=4，数组中每个储存单元储存4位，为了不会重复进位，如果是1位的话，可能需要进行连续多次进位，4位的话正好一次就够了。
*/

# include <stdio.h>
int number[1011][670];
int f(int x){	// 求10的x次方
    int i=1;
    while(x>0){
        x--;
        i=i*10;
    }
    return i;
}
int main(){
    int n,m;
    int c; // 进位
    number[0][0]=1; //初始0的阶乘是1
    int cnt = 1; // 标记有多少位
    for(int i=1; i<=1000; i++){
        c = 0;
        for(int j = 0; j < cnt; j ++){
            number[i][j] = number[i-1][j]*i + c; // 计算过程
            c = number[i][j]/10000; // 进位
            number[i][j] = number[i][j]%10000; // 得到四位
            if(j == cnt-1&& c>0) cnt ++; // 发现位数不够就加一位
        }
    }
    int N;
    scanf("%d",&N);//样例个数
    while(N>0){
        N--;
        scanf("%d%d",&n,&m);//n为要阶乘的值 ，m为第几位数码
        int offset = (m -1) / 4; // 第几个储存单元
        int pos = (m -1) % 4; // 存储单元的第几位；
        int y=(number[n][offset]/f(pos))%10;
        printf("%d\n",y);
    }
    return 0;
}

H 字符矩阵

这道题找规律。

看代码吧！

# include <stdio.h>

int main(){
    
    char chr;
    while(scanf("%c",&chr)&&chr!='#'){
        
        int a=chr-64; // 中间的位置从0开始计算
        int k=2*a-1; // 最大的位置序号
        char A[55][55]; // 输出矩阵
        
        // 对第一行从第0个数进行赋值一致到第k个数。第一个循环是+1，第二个是-1
        for(int i=0; i<a; i++){
            char t='A'+i;
            A[0][i]=t;
        }
        for(int i=0; i<a-1; i++){
            char t=chr-i-1;
            A[0][a+i]=t;
        }
        
        // 对角线折叠赋值
        for(int K=1; K<a; K++){
            for(int j=0; j<a; j++){
                if(j<=K) A[K][j]=A[0][K];
                else A[K][j]=A[0][j];
            }
            for(int j=0; j<a-1; j++){
                A[K][a+j]=A[K][k-(a+1+j)];
            }
        }
        
        // 横向对折赋值
        for(int K=a; K<k; K++){
            for(int j=0; j<k; j++){
                A[K][j]=A[k-(K+1)][j];
            }
        }
        
        
        // 输出
        for(int i=0; i<k; i++){
            for(int j=0; j<k; j++){
                printf("%c",A[i][j]);
            }
            printf("\n");
        }
            
    }
    
    
    return 0;
}

本文作者： Doted Wood
本文链接： http://example.com/2021/11/12/XTU oj/补作业6/
版权声明： 版权归博主所有，转载请说明来源