01序列

id: 01_seq

[[toc]]

教学目标

  • 排列组合的入门题目
  • 理解最基本的球放入盒子的模型

题目

题目描述

有一个盒子,盒子有两种数字,0和1每种数字有无限个, 现在有n( 1<= n <= 20)个人取数字,这n个人排成一排,先第一个人拿,然后依次去取.

问:一共有多少人可能性.按字典序从大到小输出所有的可能性

输入样例

3

输出样例

000
001
010
011
100
101
110
111

小朋友法

有nn个小朋友,每个小朋友,手上有两个球.分别编号为0,10,1,还有nn个盒子,

  • 每个小朋友按从小到大的模式把球放到对应编号的盒子里
  • 一次只能放一个球
  • 回溯的时候把球拿回来
  • 只能左边的小朋友通知自己的时候,才能放球

解析

每个位置有两种可能性,0,1,所以最终有2^2行结果

针对样例,我们可以使用3层for来解,

//Author by [Rainboy](https://github.com/rainboylvx) 
//date: 2024-05-03 16:38:43
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,m;

int b[maxn]; //桶
void dfs(int dep) {
    if( dep > n) {
        for(int i = 1;i <= n ;++i ) // i: 1->n
        {
            cout << b[i] << " ";
        }
        std::cout << "\n";
        return;
    }
    for(int i = 0;i <= 1 ;++i ) // i: 0->1
    {
        b[dep] = i;
        dfs(dep+1);
    }
}

int main () {
    std::cin >> n;
    dfs(1);
    return 0;
}

但是针对题目的n是变化的,所以不能使用for

想一想,前面,如果使用来dfs来解呢?

首选是原问题A是什么

如果分解子问题B_i

当第1个人放了数字后,后面2 3 4 5就和第一个人没有关系了

1 2 3 4 5
  |-----|

游戏设计:找三个人拿数字的游戏

  • 随机拿
  • 最小的可能性是?
  • 最大的可能性是?
  • 第一个人的可能取?
  • 怎么用for循环来写三个人的问题?
  • 能不能用for来解n个人的问题?不能用dfs
  • 原问题是什么?
  • 第一个人怎么保证尽可能小?如果
  • 整体怎么保证小的先输出?如果每个人都像第一个人一样,就进可能小

进一步的抽象: 有n个人,第depdep个人把它先放0,然后让后面的去做这个问题

也可以用集合的思想来思考这个问题

第一个人只可能有0,1有种情况,所以分成两种类的集合

总结

📝:递归就是在树上行走

练习题目

暂无题目