-4

当我有 20 个作为密码长度（字符串行）和这些字符串中有 26 个字母时，我遇到了问题。现在它会打印 acaaaaaaaaaaaaaaaaaa，这 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 回答