算法训练 s01串
时间限制：1.0s 内存限制：256.0MB
问题描述
s01串初始为"0" 按以下方式变换 0变1，1变01
输入格式
1个整数(0~19)
输出格式
n次变换后s01串
样例输入
3
样例输出
101
数据规模和约定
0~19
思路：1.判断满足输出的条件
2.定义字符数组，将
3.for（）循环，遍历字符数组，'0'直接换为‘1’，‘1’先换为‘0’，再插入‘1’，遍历是跳过插入的一位。
4.调用递归
方法： 注意输入格式，n>0 else cout<<'0'
代码：
#include<iostream> using namespace std; int n; char s[10000010]; void dfs(char s[],int len,int cnt) { if(cnt==n)//递归次数cnt==n时，变换完成 { for(int i=0;i<len;i++) { cout<<s[i]; } return; } for(int i=0;i<len;i++) { if(s[i]=='0') s[i]='1'; else { s[i]='0'; for(int j=len;j>i;j--) { s[j]=s[j-1]; } s[i+1]='1'; len++; i++;//跳过当前插入的这一位 } } dfs(s,len,cnt+1);//调用递归 } int main() { while(cin>>n&&n!=0)//可多次输入 { s[0]='0'; dfs(s,1,0); } return 0; }
实例 ：输入 00， 输出0
评测结果错误得分95CPU使用31ms内存使用10.48MB
#include<iostream> using namespace std; int n; char s[10000010]; void dfs(char s[],int len,int cnt) { if(cnt==n) { for(int i=0;i<len;i++) { cout<<s[i]; } return; } for(int i=0;i<len;i++) { if(s[i]=='0') s[i]='1'; else { s[i]='0'; for(int j=len;j>i;j--) { s[j]=s[j-1]; } s[i+1]='1'; len++; i++; } } dfs(s,len,cnt+1); } int main() { while(cin>>n) { if(n>0) { s[0]='0'; dfs(s,1,0); } else { cout<<"0"; } } return 0; }
评测结果正确得分100CPU使用31ms内存使用10.48MB
