乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT乙级BasicLevelPractice 1008

问题分析

题目给定了一个数组N和一个整数M, 要求:
1. 将数组每个元素向右移动M位
2. 不使用额外的数组

将数组每个元素向右移动M位

这个要求很容易满足, 要求本身给出了操作内容, 第一直觉是模拟法搞定。

1. 建立一个新的数组;
2. 然后算出元素从原先位置向右移动M位之后应该放置的位置;
3. 把元素放入应该目标位置即可。

不使用额外的数组

由于这个要求的存在, 我们就需要重新考虑我们上面的方案.
考虑的目标是, 如果不使用额外的数组.(像极了一句废话)
换句话说, 我们要考虑"之前方案里的数组起到了什么作用", “是否有替代方式实现同样功能”

数组的作用

我们在之前的练习题中提及过"数据的存储"是为了"使用存在的", 如果不需要使用, 可以不存储。
同样的思路, 我们要考虑的是,

• 这个我们希望去掉的数组, 在过程中的每一步是怎么被我们使用
• 这个数据多大程度上被我们使用
• 是否有没有被使用的部分, 这部分是否可以去掉

计算过程中, （我们先考虑移动某一个元素这个基本动作）
数据输入: [1, 2, 3, 4, 5], 3
我们的操作如下:

1. 新建数组. [空, 空, 空, 空, 空]
2. 计算第一个元素该放入的位置. (第一位元素向右移动3位, 应该放入第4位)
3. 将第一个元素放入新数组的第4位, 如下:
   [1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
   [空, 空, 空, 空, 空] -> [空, 空, 空, 1, 空]

将第一个元素放入新数组的第4位的过程中, 数据的使用情况, 以及之后数据可能被使用的情况

1. 使用了原数组里第一个元素
2. 使用了新数组里第四个元素(的位置)
3. 原数组的第一个元素之后不会被使用到.
4. 新数组的第四个元素之后不会被使用到.
5. 新数组里第四个元素之外的位置在这个过程中没有被使用到.

之后不使用的数据是否可以不存, 暂时不使用的空间是否可以不预先建立

1. 原数组的第一个元素要放到新数组的第四个元素
   -> (把数组当格子来看的话) 多使用了一个第四格, 第一格可以不用了
   -> 一个使用需求和一个空余空间, 二者是否可以互相消化?
   -> 把第一个元素取出来, 暂存.
   把第四个元素取出来, 放到第一个元素原本的位置(第一个元素被取出后, 这个位置就是空余位置了)
   把暂存的第一个元素放入第四个元素原本的位置.
   我们完成了一个移动, 期间没有使用到额外的数组, 而是使用了一个存储某元素的空间,
   而且在移动完毕后该空间可以释放.

如果我们把上述步骤完成之后的状态当成初始状态, 然后重复我们的步骤. 则似乎就可以达到要求和目的.

完整地描述过程

我们尝试完整地描述一下过程:

1. (假设) 数据输入[1, 2, 3, 4, 5], 3
2. 建立一个额外空间, 用 “[空]” 表示
3. 移动第一个元素
   • [1, 2, 3, 4, 5], [空]  - 初始状态
   • [1, 2, 3, 4, 5], [1]   - 暂存当前要移动的元素, 使得元素原本的位置变成空闲空间
   • [4, 2, 3, 4, 5], [1]   - 将要移动到的位置上的元素放到空闲空间(就是当前要移动的元素原本的位置)
   • [4, 2, 3, 1, 5], [1]   - 将要移动的元素放到它右移指定步长之后的位置
   • [4, 2, 3, 1, 5], [空]  - 完成, 暂存空间也变成了空闲空间
4. 移动第二个元素
   • [4, 2, 3, 1, 5], [空]  - 初始状态
   • [4, 2, 3, 1, 5], [2]   - 暂存当前要移动的元素, 使得元素原本的位置变成空闲空间
   • [4, 5, 3, 1, 5], [2]   - 将要移动到的位置上的元素放到空闲空间(就是当前要移动的元素原本的位置)
   • [4, 5, 3, 1, 2], [2]   - 将要移动的元素放到它右移指定步长之后的位置
   • [4, 5, 3, 1, 2], [空]  - 完成, 暂存空间也变成了空闲空间
5. 移动第三个元素…
6. …

不过这个过程中引入了一个需要考虑的新问题:
当我要移动原数组的第四个元素时,
第四个元素已经被移动到了原数组的第一个位置,
我们如何直到这件事并且把第一个位置的元素当作移动对象。

完整描述一下我们的此刻的问题:
在要将元素右移3位的问题中, 我们会最先遇到第四个元素暂存到了第一个位置, 我们如何实现从4到1?

• -> 有什么信息可以 把 4 变成 1?
• -> (面对已知信息) 4 % 3 == 1 ✔
• -> 检查一下上面的逻辑是否也可以处理其他情况:
  • 同样在右移3位的问题中, 第5位的元素暂存到第2位, 由 5 % 3 == 2 可以知道这个信息 ✔
  • 在右移4位的问题中, (假设数组长度大于4) 第5位的元素会被暂存到第1位, 由 5 % 4 == 1 可以知道这个信息
  • 在右移4位的问题中, (假设数组长度等于3, 即小于4) 由于移动数组长度后相当于从头开始移动, 所以相当于向右移动1位.
    • 等价于，在右移1位的问题中, (假设数组长度等于3) 第2位的元素会被放到第1位, 由 2 % 1 == 1可以知道这个信息 ✔

所以"如何正确找到我们此次要移动的元素的位置"的方法是: 将"要移动元素在原数组中的位置 % 要求移动的位数"的值作为本次要移动元素的位置

代码实现上的更多细节

1. 检查移动步长, 如果移动的步数是数组长度的整数倍, 那么元素会移动到原位. 原数组就是答案.
2. 假设数组有N个, 则移动N-1次之后, 有N-1个元素已经被我们移动到预期的位置, 而剩下的一个元素也会自然在正确的位置上.
   所以有N个元素时, 只要进行N-1次移动.

完整提交代码

/*
问题分析:
题目给定了一个数组N和一个整数M, 要求:
    1. 将数组每个元素向右移动M位
    2. 不使用额外的数组
    
"将数组每个元素向右移动M位":
这个要求很容易满足, 要求本身给出了操作内容, 第一直觉是模拟法搞定。
1. 建立一个新的数组;
2. 然后算出元素从原先位置向右移动M位之后应该放置的位置;
3. 把元素放入应该目标位置即可。

"不使用额外的数组"
由于这个要求的存在, 我们就需要重新考虑我们上面的方案.
考虑的目标是, 如果不使用额外的数组.(像极了一句废话)
换句话说, 我们要考虑"之前方案里的数组起到了什么作用", "是否有替代方式实现同样功能"

# 数组的作用

我们在之前的练习题中提及过"数据的存储"是为了"使用存在的", 如果不需要使用, 可以不存储。
同样的思路, 我们要考虑的是, 
    这个我们希望去掉的数组, 在过程中的每一步是怎么被我们使用
    这个数据多大程度上被我们使用
    是否有没有被使用的部分, 这部分是否可以去掉

计算过程中, （我们先考虑移动某一个元素这个基本动作）
数据输入: [1, 2, 3, 4, 5], 3
我们的操作如下:
1. 新建数组. [空, 空, 空, 空, 空]
2. 计算第一个元素该放入的位置. (第一位元素向右移动3位, 应该放入第4位)
3. 将第一个元素放入新数组的第4位, 如下:
[1, 2, 3, 4, 5]       -> [1, 2, 3, 4, 5]
[空, 空, 空, 空, 空]    -> [空, 空, 空, 1, 空]

# 将第一个元素放入新数组的第4位的过程中, 数据的使用情况, 以及之后数据可能被使用的情况
1. 使用了原数组里第一个元素
2. 使用了新数组里第四个元素(的位置)
3. 原数组的第一个元素之后不会被使用到.
4. 新数组的第四个元素之后不会被使用到.
5. 新数组里第四个元素之外的位置在这个过程中没有被使用到.


## 之后不使用的数据是否可以不存, 暂时不使用的空间是否可以不预先建立
1. 原数组的第一个元素要放到新数组的第四个元素
    -> (把数组当格子来看的话) 多使用了一个第四格, 第一格可以不用了
    -> 一个使用需求和一个空余空间, 二者是否可以互相消化?
    -> 把第一个元素取出来, 暂存.
        把第四个元素取出来, 放到第一个元素原本的位置(第一个元素被取出后, 这个位置就是空余位置了)
        把暂存的第一个元素放入第四个元素原本的位置.
我们完成了一个移动, 期间没有使用到额外的数组, 而是使用了一个存储某元素的空间, 
    而且在移动完毕后该空间可以释放.

如果我们把上述步骤完成之后的状态当成初始状态, 然后重复我们的步骤. 则似乎就可以达到要求和目的.

我们尝试完整地描述一下过程:

1. (假设) 数据输入[1, 2, 3, 4, 5], 3
2. 建立一个额外空间, 用 "[空]" 表示
3. 移动第一个元素, [1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]  -> [4, 2, 3, 4, 5]  -> [4, 2, 3, 1, 5]  -> [4, 2, 3, 1, 5]
                 [空]            -> [1]              -> [1]              -> [1]              -> [空]
4. 移动第二个元素, [4, 2, 3, 1, 5] -> [4, 2, 3, 1, 5]  -> [4, 5, 3, 1, 5]  -> [4, 5, 3, 1, 2]  -> [4, 5, 3, 1, 2]
                 [空]            -> [2]              -> [2]              -> [2]              -> [空]
5. 移动第三个元素...
6. ......

不过这个过程中引入了一个需要考虑的新问题:
当我要移动原数组的第四个元素时, 
    第四个元素已经被移动到了原数组的第一个位置, 
    我们如何直到这件事并且把第一个位置的元素当作移动对象。

完整描述一下我们的此刻的问题: 
在要将元素右移3位的问题中, 我们会最先遇到第四个元素暂存到了第一个位置, 我们如何实现从4到1?
-> 有什么信息可以 把 4 变成 1?
-> (面对已知信息) 4 % 3 == 1 ✔
-> 检查一下上面的逻辑是否也可以处理其他情况:
    - 同样在右移3位的问题中, 第5位的元素暂存到第2位, 由 5 % 3 == 2 可以知道这个信息 ✔
    - 在右移4位的问题中, (假设数组长度大于4) 第5位的元素会被暂存到第1位, 由 5 % 4 == 1 可以知道这个信息
    - 在右移4位的问题中, (假设数组长度等于3, 即小于4) 由于移动数组长度后相当于从头开始移动, 所以相当于向右移动1位.
        - 在右移1位的问题中, (假设数组长度等于3) 第2位的元素会被放到第1位, 由 2 % 1 == 1可以知道这个信息 ✔

所以"如何正确找到我们此次要移动的元素的位置"的方法是: 将"要移动元素在原数组中的位置 % 要求移动的位数"的值作为本次要移动元素的位置

# 代码实现上的更多细节
1. 检查移动步长, 如果移动的步数是数组长度的整数倍, 那么元素会移动到原位. 原数组就是答案.
2. 假设数组有N个, 则移动N-1次之后, 有N-1个元素已经被我们移动到预期的位置, 而剩下的一个元素也会自然在正确的位置上.
    所以有N个元素时, 只要进行N-1次移动.
*/


#include 

int main()
{
    int numbers_amount;
    int move_pace;
    if (scanf("%d %d", &numbers_amount, &move_pace) != 2)
    {
        printf("Failed To Read numbers_amount and move_pace");
        return 1;
    }

    int numbers[numbers_amount];
    for (int i = 0; i < numbers_amount; i++)
    {
        scanf("%d", &numbers[i]);
    }

    move_pace = move_pace % numbers_amount;

    if (move_pace == 0)
    {
        for (int i = 0; i < numbers_amount; i++)
        {
            printf("%d", numbers[i]);
            if (i + 1 != numbers_amount)
            {
                printf(" ");
            }
        }

        printf("\n");
        return 0;
    }

    int space_to_store_one_value = 0;
    for (int i = 0; i < numbers_amount - 1; i++)
    {
        int index_of_next_element_to_move = i % move_pace;
        int index_of_element_should_move_to = (i + move_pace) % numbers_amount;

        space_to_store_one_value = numbers[index_of_element_should_move_to];
        numbers[index_of_element_should_move_to] = numbers[index_of_next_element_to_move];
        numbers[index_of_next_element_to_move] = space_to_store_one_value;
    }

    for (int i = 0; i < numbers_amount; i++)
    {
        printf("%d", numbers[i]);
        if (i + 1 != numbers_amount)
        {
            printf(" ");
        }
    }

    printf("\n");
}
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146