2

辞書順列を生成するためのこのコードがあります。次のロジックが使用されます。

  1. 特定のテスト文字列内の文字の昇順の配置から開始します。
  2. 次の辞書順列を生成するには:

a) 次の文字よりも小さい右端の文字を見つけます。Aと言ってください。

b) A の右側で、次に大きい文字を見つけます。B と言って、A と B を入れ替えます。

c) A の元の位置の右側で、文字を昇順で並べ替えます。

最後の順列を取得すると、アルゴリズムは終了します。つまり、指定されたテスト文字列の逆。私のテスト文字列s = "0123456789"

編集: プログラムを実行するたびに、セグメンテーション違反の別の位置を取得します。

A を取得するには:

int firstchar(string s){
int pos = s.length()-2;
for(int i=pos;i>=0;i--){
    if(s[i]<s[i+1]){
        pos = i;
        break;
    }
}
return pos;}

B を取得してから再帰的アプローチを取得するには (qsort は の関数です<cstdlib>):

int ceilchar(string s, int fc){
int ceil = fc+1;
int diff=27;
for(int i=ceil;i<s.length();i++){
    if(s[i]>s[fc] && s[i]-s[fc]<diff){
        ceil = i;
        diff  = s[i]-s[fc];
    }
}
return ceil;}

開始機能:

void nextpermute(string& s){
int fc = firstchar(s);
int cc = ceilchar(s,fc);
swap(s,fc,cc);
sort(&s[fc]+1,&s[fc]+s.length()-fc);
if(s!="9876543210"){
    cout<<s<<"\n";
    nextpermute(s);
}
else
    cout<<s<<"\n";}

メインからの呼び出し:nextpermute(test);

テスト文字列が"01234567"0 またはそれより小さい場合、問題なく動作します。"012345678"しかし、またはのような文字列の 場合"0123456789"、セグメンテーション違反が発生します。助けてください！！

4

1 に答える 1

1

スタック サイズが限界を超えていると思われます。Linuxで実行している場合は、「制限」を実行してスタックサイズを確認してください。この状況を回避する方法は 2 つあります

1) (非推奨) 「スタックサイズを無制限に制限」を実行します (UNIX ベースのシステムを使用している場合のみ)。そして、プログラムを再度実行します。

2) (推奨)。

変化する

void nextpermute(string& s){
    int fc = firstchar(s);
    int cc = ceilchar(s,fc);
    swap(s,fc,cc);
    sort(&s[fc]+1,&s[fc]+s.length()-fc);
    if(s!="9876543210"){
        cout<<s<<"\n";
        nextpermute(s);
    }
    else
        cout<<s<<"\n";
}

に

void nextpermute(string& s){
    int fc = firstchar(s);
    int cc = ceilchar(s,fc);
    swap(s,fc,cc);
    sort(&s[fc]+1,&s[fc]+s.length()-fc);
    cout <<s<<"\n";
}

メイン関数を次のように変更します

int main()
{
    string s = "0123456789";
    while (s != "9876543210")
    {
        nextpermute(s);
    }
}

上記の変更により、「nextpermute」の再帰がなくなるため、スタックサイズの制限を超えることはありません

于 2013-08-11T12:26:09.687 に答える