简易版TGU算法课程：递归与分治方法下的Test1问题E - 组合数学详解题解

题目描述

龙龙学姐很喜欢学数学，而在数学问题里他最喜欢研究的就是排列组合问题了。想得到龙龙学姐的青睐就要通过他的考验！现在他想考考你前n个正整数不同的排列组合方案有多少，请你写一个程序按字典序, 列出1~n所有的排列组合方法。

输入描述

输入数据只有一行，包括一个整数 n（1 <= n <= 7）

输出描述

按字典序输出1~n的所有可能的排列组合方案, 每个方案占一行
关于何为"字典序", 请参考下面的样例

输入样例1

3

输出样例1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

题目解析

最经典的递归问题，也可以说是搜索问题，注意递归进入和退出时数据的复原。每次将1，2，3，赋值给不同位置即可。

参考代码

/*
Pro.E 标程
E_std.cpp
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 10;
int a[N], vis[N], n;

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++)
        {
            printf("%d ", a[i]);
        }
        puts("");
    }
    
    for (int i = 1; i <= n; i ++)
    {
        if (!vis[i])
        {
            a[u] = i;
            vis[i] = 1;
            dfs(u + 1);
            vis[i] = 0;
        }
    }
}


void solve()
{
    cin >> n;
    
    dfs(0);
}

int main(void)
{ 
    solve();
    
    return 0;
}

问题分析

1. 题目背景过于简单，代码相似度过高。
2. 自己做的同学，会对字典序的排列产生问题，这里要注意如果使用交换的做法，注意交换的位置不要写错。
3. 可以学习使用C++的next_permutation函数，更便于处理这道题。
4. 出题的时候没有考虑行末的空格问题，之后可以修改一下题面。
   
   

写在最后

骗赞