喵~ 各位算法大师们好呀！咱是乃们的专属解题猫娘，今天又要和大家一起玩耍一个有趣的题目啦，Nya~！这次我们要帮助一只可爱的小象，他的递归函数好像有点...嗯...小问题。不过没关系，只要我们找到一个神奇的初始排列，就能让他的函数完美运行，让他不用挨老师的批评啦！让我们一起开动脑筋，帮帮他吧！🐾
Little Elephant and Function (A. Little Elephant and Function)
题目大意 (Problem Analysis)
好啦，先让咱看看这道题到底在说什么吧，喵。
题目是这样滴： 有一个从 1 到 n 的数字排列 a。小象发明了一个他觉得能排序的递归函数 f(x)，它的工作方式是：
- 如果
x = 1，函数就结束返回，什么也不做。 - 如果
x > 1，它会先调用f(x-1)，然后交换排列中的第x-1个元素和第x个元素，也就是swap(a[x-1], a[x])。
我们的任务是，对于给定的 n，找出一个初始的数字排列，当调用 f(n) 之后，这个排列能变成 1, 2, 3, ..., n 这样从小到大排好序的样子。就像找到一团完美的毛线球，只要轻轻一拉就能完全解开，喵~！
解题思路 (Solution Approach)
这个递归函数看起来有点绕，像是猫咪在追自己的尾巴，转圈圈~ 让我们别急，静下心来，一步一步地分析一下调用 f(n) 到底会发生什么吧，Nya！
当 f(n) 被调用时：
- 它会先调用
f(n-1)。 f(n-1)又会调用f(n-2)。- ...这个过程会一直持续下去，直到
f(2)调用f(1)。
f(1) 是我们的递归基例 (base case)，它什么也不做，直接返回。然后，之前被暂停的函数调用就会从最深层开始，一个一个地执行它们的 swap 操作。
f(2)的调用栈返回，执行swap(a[1], a[2])。f(3)的调用栈返回，执行swap(a[2], a[3])。f(4)的调用栈返回，执行swap(a[3], a[4])。- ...
- 最后，最外层的
f(n)调用栈返回，执行swap(a[n-1], a[n])。
所以，实际上执行的交换顺序是：swap(a[1], a[2]), swap(a[2], a[3]), ..., swap(a[n-1], a[n])。
现在，让我们看看这个操作序列对一个初始排列 p = {p₁, p₂, p₃, ..., pₙ} 会产生什么影响吧！
- 初始状态:
{p₁, p₂, p₃, ..., pₙ} - 执行
swap(a[1], a[2])后:{p₂, p₁, p₃, ..., pₙ}(第一个元素和第二个元素交换了位置) - 执行
swap(a[2], a[3])后:{p₂, p₃, p₁, ..., pₙ}(新的第二个元素，也就是原来的p₁，和第三个元素交换了位置)
喵呜！你发现规律了吗？第一个元素 p₁ 就像一只小老鼠一样，被一步一步地往右边赶。经过这 n-1 次交换，它最终会跑到排列的最后一个位置！而其他的元素 p₂, p₃, ..., pₙ 则像是给它让路一样，整体向左边移动了一个位置。
所以，经过 f(n) 的一番折腾，我们的初始排列 p = {p₁, p₂, ..., pₙ} 会变成 {p₂, p₃, ..., pₙ, p₁}。
这不就是一个向左循环移位嘛！原来小象的函数不是排序函数，而是一个移位函数呀，真有趣，Nya~！
我们希望最终的排列是 1, 2, ..., n-1, n。所以，我们只需要解一个方程： {p₂, p₃, ..., pₙ, p₁} = {1, 2, ..., n-1, n}
对比一下两边的元素，答案就出来啦：
p₂ = 1p₃ = 2- ...
pₙ = n-1p₁ = n
所以，我们需要的初始排列就是 {n, 1, 2, ..., n-1}！
举个例子，如果 n=4，我们需要的初始排列就是 {4, 1, 2, 3}。
- 初始状态:
{4, 1, 2, 3} f(2)执行swap(a[1], a[2])->{1, 4, 2, 3}f(3)执行swap(a[2], a[3])->{1, 2, 4, 3}f(4)执行swap(a[3], a[4])->{1, 2, 3, 4}完美！它真的排好序了！我们成功啦，喵~！
题解代码 (Solution Code)
既然我们已经洞悉了其中的奥秘，写代码就变得像吃小鱼干一样简单啦！我们只需要读入 n，然后打印 n，再接着打印从 1 到 n-1 的所有数字就可以啦。
#include <iostream>
int main() {
// 使用快速 I/O，让我们像猫一样敏捷，喵~
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
// 读入排列的大小 n
std::cin >> n;
// 根据我们聪明的分析，能够让函数成功排序的初始排列是 {n, 1, 2, ..., n-1}
// 所以，我们把它打印出来就好啦！
// 首先打印 n
std::cout << n;
// 然后用一个循环打印从 1 到 n-1 的数字
// 别忘了在每个数字前加一个空格哦，喵~
for (int i = 1; i < n; ++i) {
std::cout << " " << i;
}
// 最后加个换行符，让输出整洁干净！
std::cout << "\n";
return 0;
}知识点介绍 (Knowledge Points)
这道题虽然简单，但背后也藏着一些重要的知识点呢，一起来看看吧，Nya！
递归 (Recursion) 函数
f(x)是一个典型的递归函数，它通过调用自身来解决问题。递归的核心思想是分而治之，将一个大问题分解成一个或多个与原问题相似但规模更小的子问题。递归必须有一个基例 (Base Case)，也就是一个可以直接求解的最小问题（比如本题中的x=1），以防止无限调用下去。排列 (Permutation) 排列是指从给定个数的元素中取出指定个数的元素进行排序。简单来说，就是把一堆东西排个队。这道题就是关于数字 1 到 n 的全排列问题。
循环移位 (Cyclic Shift) 这是解开本题的“魔法钥匙”！我们通过分析发现，小象的函数实际上对数组执行了一次向左的循环移位。循环移位是数组操作中一种常见的模式，即将数组中的元素统一向一个方向移动，而从一端移出的元素会绕到另一端。在各种算法问题中，能够识别出这种模式，往往能让复杂的问题变得简单。
好啦，今天的小象救援行动圆满成功！我们不仅帮了小象，还学习了这么多有趣的知识，真是太棒啦！希望大家喜欢这次的解题分享，我们下次再见，喵~ 💖