Problem Solving►UVa

UVa 306 - Cipher

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

將在每個位置轉換的過程記錄下來，會形成一個循環，且回到一開始的位置。(因為其 key 為 1~n )
order[i][0] 為第 i 個字元一開始的位置，order[i][k+1] 為在第 k 次轉換後的位置， order[i][0] 拿來存循環的週期。
接著只要將原先的字元存進對應的結果即可:

m = k%order[i][0];//週期
ans[order[i][m + 1]] = str[i - 1];

注意 index 的處理。

Code

UVa 306
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
#include<cstdio>
#include<cstring>
#define N 201

int main()
{
    int n;
    int key[N], order[N][N];
    char str[N], ans[N];
    while (scanf("%d", &n) && n)
    {
        int i, k;
        for (i = 1; i <= n; i++) 
            scanf("%d", &key[i]);

        for (i = 1; i <= n; i++)
        {
            int temp = i, j = 0;

            do
            {
                order[i][++j] = temp;
                temp = key[temp];
            } while (i != temp);

            order[i][0] = j;//存它的週期
        }

        while (scanf("%d", &k) && k)
        {
            getchar();
            gets(str);
            
            for (i = 1; i <= n; i++)
                ans[i] = ' ';
            int len = strlen(str), m;

            for (i = 1; i <= len; i++)
            {
                m = k%order[i][0];
                ans[order[i][m + 1]] = str[i - 1];
            }

            for (i = 1; i <= n; i++)
                putchar(ans[i]);
            putchar('\n');
        }

        putchar('\n');
    }

    return 0;
}