-4

passlength (文字列の行) が 20 で、それらの文字列に 26 文字があると問題が発生します。現在、そのインスタンスに対して acaaaaaaaaaaaaaaaaaaa が出力されます。26 文字はアルファベットです。順列の量が多すぎて保存できません。彼が 1048576 の順列を要求する最高の順列。n番目(強さ)の順列を出力したいと思っています。

スキップ数が大きすぎるというスタックオーバーフローの問題を回避するにはどうすればよいですか??? int を long long に変更してみました。私はprintfを使用して順列の数を確認しましたが、intの場合と同じ数が長い間得られます。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define ALPHA 28

typedef struct {
    int yourpass;
    char letters[ALPHA];
    int temp;
    int skips;
} password;

//declare functions
void FindVariations(int passlength, int strength, password *combo, int j, int x);
void magical(password *combo, int passlength);

int main() {

    int i, j, d, cases, passlength;
    int strength;
    password* combo;

    combo = malloc(ALPHA*sizeof(password));

    // enter number of passwords to compute
    scanf("%d", &cases);

    for (i=0; i<cases; i++) {

        //enter number of strings/length of password
        scanf(" %d ", &passlength);

        // input the letters for password
        for (j=0; j<passlength; j++) {

        scanf(" %s ", combo[j].letters);

        combo[j].temp = strlen(combo[j].letters);
        }

        scanf("%d", &strength);

        // find the total nnumber of permutations
        magical(combo, passlength);

        // find the permutation to print
        FindVariations( passlength, strength, combo, 1, 0);

        // print the wanted password
        for(d=0; d<passlength; d++) {

            printf("%c", combo[d].letters[combo[d].yourpass]);

        }

        printf("\n");
    }
    free(combo);
    return 0;
}

void magical(password *combo, int passlength) {

    int i;
    int total=0;

    for(i=(passlength-1); i>=0; i--) {

        if(i==(passlength-1)) {
            combo[i].skips=1;
            total=combo[i].temp;

        }
        else {
            combo[i].skips=total;
            total*= combo[i].temp;
        }
    }

}

void FindVariations(int passlength, int strength, password *combo, int j, int x) {

    combo[x].yourpass = 0;

    if(x==passlength){
        return;
    }

    if (x<passlength)  {
        while(j<=strength-combo[x].skips) {
            combo[x].yourpass+=1;
            j+=combo[x].skips;
        }
    }

    FindVariations( passlength, strength, combo, j, x+1);
}
4

1 に答える 1

3

スタックオーバーフローとは何か理解していますか? あなたの場合、大きな数を格納することは問題ではありません。膨大な数の再帰関数呼び出しを使用して、大量のメモリを使用するのは問題です。

関数呼び出しを行うたびに、コンパイラは関数のパラメーターと内部変数用のスペースをプログラムのスタック メモリに追加します。関数呼び出し内で多くの関数呼び出しを行うと、プログラムのスタック メモリが許容範囲を超えて増加し、スタック オーバーフロー エラーが発生します。

ただし、プログラムの場合、FindVariations関数呼び出しを行うと、変数の以前の値は必要ないため、再帰的な関数呼び出しによって引き起こされるメモリ オーバーヘッドは実際には必要ありません。これは末尾再帰と呼ばれます。

スタックのオーバーフローを防ぐ最も簡単な解決策は、再帰的な解決策を反復的な解決策に変えることです。

void FindVariations(int passlength, int strength, password *combo, int j, int x) 
{
    for (combo[x].yourpass = 0; x < passlength; x++) 
    {
        while(j <= strength-combo[x].skips) 
        {
            combo[x].yourpass+=1;
            j+=combo[x].skips;
        }
    }
}
于 2013-09-24T00:27:46.283 に答える