算法OJ—回溯专题(一)_穷举n位二进制数
1323.穷举n位二进制数
时限:100ms 内存限制:10000K 总时限:300ms
描述
输入一个小于20的正整数n,要求按从小到大的顺序输出所有的n位二进制数,每个数占一行。
输入
输入一个小于20的正整数n。
输出
按从小到大的顺序输出所有的n位二进制数,每个数占一行。
输入样例
3
输出样例
000
001
010
011
100
101
110
111
从本题开始都是回溯的问题进行的总结,以本题为例:
两位二进制数可以通过循环表示为:
for(int i = 0; i < 2; i++) cout << i;
for(int j = 0; j < 2; j++) cout << j;
三位二进制数可以通过循环表示为:
for(int i = 0; i < 2; i++) cout << i;
for(int j = 0; j < 2; j++) cout << j;
for(int k = 0; k < 2; k++) cout << k;
显然是可以通过增加for循环的层数来完成不同数字的穷举,但是这样的话不能够输出任意个数的二进制数,同样代码也显得很复杂,通过回溯思想的使用,可以完成生成N位二进制数的操作
#include<iostream>
using namespace std;
int a[20], n;
//a为二进制数的位数
void search(int m);
int main(){
cin >> n;
search(0);
}
void search(int m){
int i;
if(m == n){
for(i = 0; i < n; i++){
cout << a[i];
}
cout << endl;
}else{
a[m] = 0; //第m位 为0;
search(m+1);//回溯生成 m+1位
a[m] = 1; //第m位 为1;
search(m+1);//回溯生成 m+1位
}
上一篇: 三道POJ中的回溯问题
下一篇: [Wc2007]剪刀石头布 迭代