UVa 3n + 1 Case Рекурсивное переполнение стека

Question

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

к сожалению, когда входное значение представляет собой большое целое число (100000> вход>1000000), часто происходит сбой

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

, пожалуйста, помогите мне, я не знаю, что делать, я пытался изменить тип данных на unsigned long,unsigned int и т. д., но ничего из этого не работает

вот мой код, я использую ANSI C

#include "stdio.h"

int cek(int n) {
    return n % 2;
}

int fung(int n,int c) {
    if (n == 1) {
        return c;
    }
    if (!cek(n)) {
        return fung(n/2,++c);
    }
    else {
        return fung((n*3)+1,++c);
    }
}

int comp(int i,int j,int tmp) {
    int temp;
    if (i == j)
        return tmp;
    temp = fung(i,1);
    if (temp > tmp)
        return comp(++i,j,temp);
    else
        return comp(++i,j,tmp);
}

int main() {
    int i,j,tmp;
    while (scanf("%d %d",&i,&j)) {
        if (i > j) {
            tmp = i;
            i = j;
            j = tmp;
        }
        printf("%d %d %d\n",i,j,comp(i,j,0));
    }
    return 0;
}

PS: извините за мою глупость, я действительно новичок @ _ @

Answer 1

Рекурсия вряд ли будет быстрее, чем итерация, и на самом деле она будет медленнее.

Стек вызовов имеет ограниченный размер, и если ваша рекурсия идет глубже, вы ничего не можете сделатьоб этом.Особенно в проблеме Коллатца, невозможно заранее определить, сколько шагов вам понадобится.Перепишите это, используя итеративный метод.

(Если ваш компилятор выполняет оптимизацию хвостовых вызовов, рекурсия все еще может работать. Но TCO не требуется стандартом, так что это приведет к непереносимому коду. И, очевидно, ваш компиляторв любом случае не оптимизирует этот конкретный хвостовой вызов.)

Answer 2

Не эксперт C, но обычно существует предел глубины стека вызовов , установленный компилятором.Возможно, вы можете изменить это с помощью флага компилятора , но это не решит вашу проблему.Исправив алгоритм итеративно, а не рекурсивно.

Рекурсивные алгоритмы обычно не работают быстрее, чем итерационныеНо они, как правило, лучше понять.(= более элегантно)

Answer 3

Хорошо, ребята, я нашел это !!!

так что это мой код, я все еще использую рекурсию, но только для внутреннего цикла fung (),

я не особо впечатлен этимПоскольку для подсчета входных данных 1 и 1000000 требуется 0,5 секунды, чей-то код может сделать это за 0 секунд, LOL

Я изменяю внешний цикл comp () итерационным методом,

смотри здесь

#include "stdio.h"
/*#include "windows.h"*/

int cek(int n) {
    return n % 2;
}

unsigned int fung(unsigned int n,unsigned int c) {
    if (n == 1) return c;
    if (!cek(n)) return fung(n/2,++c);
    else return fung((n*3)+1,++c);
}

/*
Above recursion will looked like this in iterative method
int func(int n) {
    int c=1;
    while (n != 1) {
        c++;
        if (n % 2 == 0)
            n=n/2;
        else
            n=(n*3)+1;
    }
    return c;
}
*/

/*Outer Loop*/
int iter(int i,int j) {
    int tmp1=0,tmp2;
    while (i <= j) {
        tmp2 = fung(i,1);
        if (tmp1 < tmp2)
            tmp1 = tmp2;
        i++;
    }
    return tmp1;
}

int main() {
    unsigned int i,j,s,f;
    while (scanf("%d %d",&i,&j)) {            /*UVa Standard, infinite loop*/
        /*s = GetTickCount();*/
        printf("%d %d %d",i,j,iter(i,j));
        /*f = GetTickCount();
        printf("%lu\n",f-s);*/
    }
    return 0;
}