B3688 [语言月赛202212] 旋转排列 题解

· · 题解

B3688 [语言月赛202212] 旋转排列 题解

Source & Knowledge

2022 年 12 月语言月赛，由洛谷网校入门计划/基础计划提供。

本题考察循环结构。

文字题解

题目大意

给出一个排列 p，按如下规定循环操作：

现在，给定一个长度为 n 的排列 p，请你按照如下规定循环操作：

  1. 对当前的排列 p 做一次“shift”操作；
  2. 输出本次“shift”以后的排列 p；
  3. 判断排列 p 的最后一个数字是否是 n，如果是，则结束循环操作；否则回到 1 继续操作。

一次“shift”操作是指：将 p 里的每一个数字都依次向后移动一位，并把 p 的最后一个数字移动到开头去。

解析

shift 操作

考虑一次 shift 操作如何完成：可以令 i := n 到 2 进行倒序枚举，每次令 p[i] := p[i - 1]，这样可以把第 1 \sim (n-1) 的数字都向后移一位。但是此时原有的 p[n] 的值会被抹去， 需要新建一个变量 temp 来存储 p[n] 的值，再枚举结束后直接令 p[1] := temp。

核心代码为：

int temp = p[n];
for (int i = n; i >= 2; --i) p[i] = p[i - 1];
p[1] = temp;

输出操作

需要输出一行 n 个数，两两之间用空格隔开，行末输出空格。可以采用如下的输出形式：

for (int i = 1; i <= n; ++i) {
  cout << p[i] << " \n"[i == n];
}

在上文的代码中，" \n" 是一个长度为 2 的字符串，其第 0 位为空格，第 1 位为换行。我们可以用 [] 运算符来访问其某一位。

当 i \neq n 时，语句 i == n 的值为 0，此时相当于 " \n"[0]，则输出一个空格；
当 i = n 时，语句 i == n 的值为 1，此时相当于 " \n"[1]，则输出换行符。

循环操作

注意到循环操作的要求：先执行循环体，再进行判断。这提示我们使用 do - while 语句。

do - while 语句的结构是 do A while (B)，代码会先执行语句（块） A（无论 B 是否为真），再执行判断语句 B，如果 B 为假，则终止执行，否则反复执行语句（块）A 直到 B 为假。

结合上面的分析，我们可以写出循环部分的核心代码：

do {
  int temp = p[n];
  for (int i = n; i >= 2; --i) p[i] = p[i - 1];
  p[1] = temp;
  for (int i = 1; i <= n; ++i) {
    cout << p[i] << " \n"[i == n];
  }
} while (p[n] != n);

视频题解

完整代码请在视频中查看。