[PAT] 00-自测5. Shuffling Machine

题目链接:

---

这道题目是通过题中给出的小例子，通过归纳法推导出来的。

首先，这个方法不能通过将存放扑克牌的数组移动题目中要求的次数来得到结果，
        而是从每个扑克牌的初始位置入手通过得知变换序列以及变换的次数求出扑克牌，
         移动题目中给定的次数之后，在数组中终止位序，按照求出的位序输出数组。
然后，可得知，上述操作共需要 3 个数组：
          数组 1 ： 用来存放扑克牌花色+扑克牌顺序坐标的数组 : poker，这里如果使用 STL 的话，
         可以通过 map 来实现，我这里通过定义一个含有两个字段的结构体来实现
        struct node
        {
            int pos ; // 记录了poker 牌当前在全套扑克牌中的位置
            int name ; // 通过一个整型的变量来存放扑克牌的花色，
                          // 这种方法远比自己创建字符串数组使用的要方便 (name-1)/13 得出的范围是 [0...4]
         } ;            // 其中name 的取值范围为 [1...54] , 创建 char name [4] = {S ,H ,C ,D ,J} 这样便可以实现映射
                        // 然后花色之后的数值便可以通过 name % 13 计算获得，其中当 name = 13 , 26 , 39 , 52 
                        // 的时候， name %13 = 0 , 此时对应让其数值为 13 这样便得到了  S13 , H13 , C13 , D13 扑克

数组2 : modify[1..54] 
            该数组是用来存放每次扑克牌位置变换对应的映射的数值，通过推到题中给定的特例可以得到如下的公式：
            第 k 次 映射中， 第 i 张扑克牌映射到新的位置, poker 中的花色是不随位置变换而变的
            poker[i].pos = modify[poker[i].pos] ;
            如果第 i 次映射为最后一次变换，那么，poker[i].name 花色的扑克牌便位于输出序列的 第 poker[i].pos 个
            被打印出来， 不过输出的时候，总不能每次执行一个循环，首先从 poker[1..54] 中找到 poker[i].pos = 1
      的花色的扑克牌进行输出， 这样十分的浪费时间。为了节省时间，所以在空间上做出牺牲，申请了第三个数组。

数组3： result [1..54]
          后来仔细分析一下， result 角色的数组完全可以使用 modify 来替代， 但是为了直观，再次申请一个数组作为
            存放结果的数组。通过下列的循环，将 poker[i].name 按照 poker[i].pos 的顺序存放到 result 中，
            这样在每次输出结果的时候，执行一个 1 .. 54 的循环将result 中的元素按照顺序输出便是结果
            for ( i -> 1.. 54 )
            result [ poker[i].pos ]  = poker[i].name 
            

---

#include <stdio.h>
#include <stdlib.h>

#define N 55

char name[] = {'S', 'H', 'C','D','J'} ;

char getName ( int pos )
{
    return name [(pos-1)/13] ;
}

int getPos ( int pos )
{
    int rs = pos %13 ;
    if ( rs == 0 )
        rs = 13 ;
    return rs ;
}

struct node
{
     int pos ;
     int name ;
}poker[N] ;


void initPoker ()
{
    for ( int i = 1 ; i < N ; i++ ) // 1.. 54
    {
        poker[i].name = poker[i].pos = i ;
    }
}

void shuffPoker ( int *modify ,int *result, int times )
{
    for ( int j = 0 ; j < times ; j++ )
     for ( int i = 1 ; i < N ;i++)
     {
          poker[i].pos = modify[poker[i].pos] ;
     }

    for ( int k = 1 ; k < N ; k++ )
    {
        result[ poker[k].pos] = poker[k].name ;
    //    printf ("result [%d  %d] = %c%d  \n" ,poker[k].pos , poker[k].name , getName(poker[k].name) , getPos (poker[k].name) ) ;
    }
}

int main ( void )
{
    int modify [N]={0};
    int result [N] = {0} ;
    int timer ;
    scanf ("%d", &timer ) ;

    for ( int i = 1 ; i < N ; i++ )
        scanf ("%d" , &modify[i]) ;

        initPoker() ;
    shuffPoker(modify , result ,timer ) ;

    for ( int k = 1 ; k < N ; k++ )
        {
        printf("%c%d", getName(result[k]) , getPos(result[k])) ;
        if ( k != N-1)
                  printf (" ") ;
        }
    return 0 ;
}

改程序通过全部测试点