почему этот код выдает ошибку переполнения стека, когда длина слова превышает 4? - PullRequest
Новая
       31

почему этот код выдает ошибку переполнения стека, когда длина слова превышает 4?

1 голос
/ 18 мая 2019

Я написал код для генерации всех возможных комбинаций букв слова без какого-либо повторения какой-либо буквы или какого-либо конкретного слова. код выглядит следующим образом 

static boolean redcheck(int array[])// checks if letters are repeated
{
    boolean check=true;
    for(int i=0;i<array.length-1;i++)
    {
        for(int j=i+1;j<array.length;j++)
        {
            if(array[i]==array[j])
            {
                check=false;
                break;
            }
        }
    }
    return check;
}

static void repeat(char arr2[],int arr1[],int p)// creates and prints the word
{
    if(redcheck(arr1))
    {
        for(int i=0;i<p;i++)
            System.out.print(arr2[arr1[i]]);
        for(int i=0;i<p;i++)
            System.out.print(arr1[i]);
        System.out.println();
    }
    arr1[p-1]+=1;
    for(int ini=p-1;ini>0;ini--)
    {  
        if(arr1[ini]>p-1)
        {
            arr1[ini-1]+=1;
            arr1[ini]=0;  
        }
    }
    if(arr1[0]>p-1)
        return;

    repeat(arr2,arr1,p);
}

public static void main()
{
    Scanner sc=new Scanner(System.in);
    System.out.println("enter word");
    String a=sc.nextLine();
    int num=a.length();
    char arr[]=new char[num];
    for(int c=0;c<a.length();c++)
        arr[c]=a.charAt(c);

    int arr1[]=new int[num];
    for(int i:arr1)
        arr1[i]=0;
    repeat(arr,arr1,num);

}

код работает нормально до любого слова длиной до 4, но когда его значение больше четырех, он выдает ошибку переполнения стека. после некоторой проверки основной частью кода, который создает проблему, является сама часть печати, которая является 

for(int i=0;i<p;i++)
            System.out.print(arr2[arr1[i]]);

Я действительно не могу найти, где я иду не так. оператор print ниже указанного выше печатает индексы слов в том порядке, в котором они будут напечатаны, и не выдает никакой ошибки. я использую редактор bluej, и кажется, у меня есть 512 МБ в памяти стека. Пожалуйста, помогите. Спасибо заранее.

РЕДАКТИРОВАТЬ: код ошибки java.lang.StackOverflowError: нуль

1 Ответ

4 голосов
/ 18 мая 2019

С 4 буквами (при условии, что ни одно из них не совпадает) существует 4 ^ 4 = 256 возможных комбинаций этих букв.Поскольку ваш код в настоящее время настроен, вы будете выполнять рекурсию как минимум 256 раз, прежде чем возвращать значение, которое будет иметь большую стоимость памяти в вашем стеке.Если вы попытаетесь увеличить до 5 букв (опять же, если предположить, что ни одна из них не совпадает), у вас будет 5 ^ 5 = 3125 возможных комбинаций и т. Д. ... Ошибка переполнения стека возникает из-за количества времени, которое вы повторяете.

Моя рекомендация: разделите ваш метод повторения на две части: 

static void printWord(char arr2[],int arr1[],int p) {
    if(redcheck(arr1))
    {
        for(int i=0;i<p;i++)
            System.out.print(arr2[arr1[i]]);
        for(int i=0;i<p;i++)
            System.out.print(arr1[i]);
        System.out.println();
    }
}

, а затем метод повторения: 

static void repeat(char arr2[],int arr1[],int p)// creates and prints the word
{
    while(arr1[0] < p-1){
        printWord(char arr2[],int arr1[],int p);
        arr1[p-1]+=1; // your looping logic
        for(int ini=p-1;ini>0;ini--)
        {  
            if(arr1[ini]>p-1)
            {
                arr1[ini-1]+=1;
                arr1[ini]=0;  
            }
        }
    }
}

, сделав его нерекурсивным, поможет вам избежать стекаошибка переполнения.

Дополнительные рекомендации: прежде чем выполнять какую-либо логику, убедитесь, что во входном слове нет двух одинаковых букв, ваш код не найдет никаких комбинаций, если я введу слово «видеть», поскольку комбинаций нет.таким образом, что трехбуквенное слово может быть создано с буквами {'s', 'e', ​​'e'} без повторения любой из них.Ваш redcheck метод использует слишком много переменных: 

static boolean redcheck(int array[])// checks if letters are repeated
{
    for(int i=0;i<array.length-1;i++)
    {
        for(int j=i+1;j<array.length;j++)
        {
            if(array[i]==array[j])
            {
                return false;
            }
        }
    }
    return true;
}
...