0

我想按排序顺序仅通过单词“4”和“7”生成长度从 1 到 10 的所有字符串

  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;
    }

这是不正确的，请提出一个回溯算法来做同样的事情

注意：- 不用担心时间复杂性

4

2 回答 2

2

不需要回溯，因为存在一个非常简单的算法，它总是做正确的事情：

  • 从空词开始。（因为您需要长度> 0，所以不需要打印）

  • 在完成尺寸 n - 1 的工作后，您可以通过以下方式对尺寸 n 进行操作：

    • 打印每个大小为 n - 1 的单词，前缀为“4”
    • 然后打印每个大小为 n - 1 的单词，前缀为“7”

由于您所做的每一步都保证朝着正确的方向移动（即使在实际上没有显式存储任何内容的递归实现中），这并不是真正的回溯 - 但您为什么要回溯呢？

PS：这个算法是最优的：它打印每个字符花费 O(1) 时间。

于 2015-09-09T21:39:05.433 回答
1

我正在写我自己问题的答案。我在投入一些时间后找到了解决方案。

#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;
}

已经提出了更好的算法，但尽管我分享这个会很好。

于 2015-09-10T06:53:04.680 回答