Генерация всех строк только двумя буквами длиной от 1 до 10?

Question

Генерация всех строк только двумя буквами длиной от 1 до 10?

Я хочу сгенерировать все строки длиной от 1 до 10 только словами «4» и «7» в отсортированном порядке

  example-> 1)4 //first string

2)7 //second string

3)44 //third,because next after 7 should be 44

4)47 //fourth,after 44

. . .

. . .

. . .

This way till length <=10

Я попробовал себя, и мой код возврата выглядит примерно так

        #include<bits/stdc++.h>
using namespace std;
vector<string>v;                // for storing intermediate string in backtracking
void generate(string s,char ch)
{
if(s.length()>=9)return;    //length > 10 returning
s+=ch;                      //adding to string a new character
v.push_back(s);                    //storing strings
generate(s,'4');            //first backtracking
generate(s,'7');            //second backtracking
}
int main()
{
generate("",'4');
sort(v.begin(),v.end());     //sorting  to get ascending order string
string thisfind;             //to find postion of string thisfind in vector...like postion of '4' is 1
cin>>thisfind;
int l=find(v.begin(),v.end(),thisfind)-v.begin();  //just usual find function
cout<<l+1<<endl;            //output
return 0;
}

Это не правильно, пожалуйста, предложите алгоритм возврата, чтобы сделать то же самое

Примечание: — Не беспокойтесь о сложности времени

0

c++recursion recursive-backtracking string

Решение

Другие решения

Я пишу ответ на свой вопрос. Я нашел решение, потратив некоторое время на него.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define ll long long int
vector<ll> v;
void recurse(ll num)
{
v.push_back(num);
if (num > ((ll)10e10))
return;
recurse(num * 10 + 4);
recurse(num * 10 + 7);
}

int main()
{
recurse(0);
sort(v.begin(), v.end());
ll n;
cin >> n;
cout << find(v.begin(),v.end(),n)-v.begin()<< endl;
return 0;
}

Лучшие алгоритмы уже предложены, но, хотя я поделюсь этим, было бы хорошо.

1

Источник

Accepted Answer

Возврат не требуется, так как существует очень простой алгоритм, который всегда делает правильные вещи:

Начните с пустого слова. (Поскольку вам требуется длина> 0, это не должно быть напечатано)
Сделав работу для размера n — 1, вы можете сделать это для размера n:
- Печать каждого слова размером n — 1 с префиксом «4»
- Затем следует печать каждого слова размером n — 1 с префиксом «7».

Поскольку каждое ваше движение гарантированно будет двигаться в правильном направлении (даже в рекурсивной реализации, которая на самом деле ничего не хранит в явном виде), это на самом деле не будет возвращаться назад, но зачем вам возвращаться в любом случае?

P.S .: Этот алгоритм является оптимальным: он тратит O (1) время на каждый символ, который печатает.

2