pat 甲级 A1042 Shuffling Machine (20分)

最新推荐文章于 2022-03-07 12:09:04 发布

dutmathjc

最新推荐文章于 2022-03-07 12:09:04 发布

阅读量121

点赞数

分类专栏： PAT甲级文章标签：算法数据结构

本文链接：https://blog.csdn.net/dutmathjc/article/details/105457399

版权

PAT甲级专栏收录该内容

58 篇文章

订阅专栏

本文详细解析了一种洗牌机算法，旨在通过特定的随机序列对一副54张的扑克牌进行洗牌，实现了扑克牌的随机化。文章介绍了算法的具体实现过程，包括初始化序列、置换操作以及最终输出洗牌后的序列。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接：

https://pintia.cn/problem-sets/994805342720868352/problems/994805442671132672

题目大意：

首先，得知道洗牌机（shuffling machine）要达到的目的：一种将一副扑克牌随机化的机器。

然后，题目要求洗牌器按照给定的随机顺序洗一副54张牌，并重复一定的次数。初始序列：S1~S13，H1~H13，C1~C13，D1~D13，J1，J2（其中S代表黑桃，H代表红心，C代表方片，D代表菱形，J代表王）。值得注意的是，题目给出的输入序列是1~54的一个排序，那么如果第i的位置为j，表示将这轮洗牌过程中将第i号位置的元素移至第j号位置，显然，i，j范围都是从1到54。

输入要求：给出两行，第一行输入重复操作的次数，第二行给出洗牌的一个序列。输出要求：将经过洗牌后的序列按牌面输出，中间用空格隔开。

思路分析：

本题的难点在于如何实现将一个初始序列经过给定次数的置换操作，得到新序列的过程。其中，置换这一概念来自群论，即，一个有限集X的置换T是从该有限集映至自身的双射。为此，我们需要开辟两个数组存放操作前后的排列，同时，也需要开辟一个数组存放置换T。对于数字与花色字符的转换，不难看出，可以利用（n -1）/ 13得出。注明：部分参考算法笔记。

参考代码：

#include <cstdio>

const int N = 54;

char map[5] = {'S', 'H', 'C', 'D', 'J'};
int s[N+1], e[N+1], n[N+1];


int main(){
    int k;
    scanf("%d", &k);
    for(int i = 1; i <= N; i++){ //得到轮换序列，以及初始序列
        scanf("%d",&n[i]);
        s[i] = i;
    }
    for(int i = 0; i < k; i++){  //k次循环，每次置换根据初始序列和置换序列得到新序列，同时，
        for(int j = 1; j <= N; j++){  //将新序列作为下一次置换的初始序列。
            e[n[j]] = s[j];
        }
        for(int j = 1; j <= N; j++){
            s[j] = e[j];
        }
    }
    for(int i = 1; i <= N; i++){
        if(i != 1) printf(" ");
        e[i]--;
        printf("%c%d", map[e[i]/13], e[i]%13+1); //(e[i]-1)/13作为区分纸牌花色的依据
    }
}