Problem collatza

Question

Witam mam problem nie tak bardzo ze samym zadaniem jak ze zrozumieniem dlaczego nie mogę tak zrobić(słabo idą mi funkcje), dlatego kategoria c i c++.

#include <iostream>

int x(int n)
{
    if(x(n)==1)
        return n;

    else
        return x(n+1);

}
int n=0;
using namespace std;
int main()
{
    if(x(n)%2==0)
    {
        x(n+1)=x(n)/2;
    }
    if(x(n)%2!=0)
    {
        x(n+1)=(3*(n))+1;
    }
    return 0;
}

 

Answer 1

W funkcjach rekurencyjnych powinieneś zawsze zastanowić się co będzie warunkiem stopu. W przypadku podanym w zadaniu jest to osiągnięcie przez zmienną wartości 1. Jak ta wartość zostanie osiągnięta, należy zwrócić wartość licznika.

Na razie pseudokod:

unisgned collatz(unsigned s, ...) {
    if( s == 1 ) {
        return counter;
    }
}

Jak widać na razie nie ma żadnej informacji skąd wziął się counter i co ma się z nim dziać. Jeśli chcesz by był inkrementowany w każdym wywołaniu, możesz go przekazać jako kopię w 2 argumencie. Aby było wygodniej, ten argument ustaw domyślnie na 0:

unisgned collatz(unsigned s, unsigned counter = 0) {
    if( s == 1 ) {
        return counter;
    }
}

Oczywiście funkcja dalej jest nieprawidłowa bo nie posiada wywołania rekurencyjnego oraz będzie zwracała (jakie zwracała? przecież dla s != 1 nie ma nic zwracanego !) nieprawidłowe wartości.

Należy więc dodać wywołania rekurencyjne. Za każdym razem wywołanie będzie wymagało inkrementowania licznika wywołań (stąd pojawi się ++counter w następnym wywołaniu). Pojawi się także test "jak liczyć gdy s jest parzyste" oraz "jak liczyć gdy nie jest parzyste". Nie chcę Cię pozbawiać przyjemności rozwiązania, więc podam tylko szkielet:

unisgned collatz(unsigned s, unsigned counter = 0) {
    if( s == 1 ) {
        return counter;
    }
    if( s jest nieparzyste) {
        return collatz(oblicznie s dla wywołania nieparzystego, ++counter);
    } else { // wiadomo że jest parzyste.. 
        return collatz(oblicznie s dla wywołania parzystego, ++counter);
    }
    // Tu program nigdy nie dojdzie bo liczba będzie parzysta lub nie :-)
}

Pozostanie dopisanie tylko funkcji main(). Taka rekurencja w której wszystkie argumenty wysyłasz przez wywołanie i "sam return jest wywołaniem funkcji z argumentami", będzie potraktowana przez dobry kompilator jako tzw. rekurencja ogonowa (https://pl.wikipedia.org/wiki/Rekurencja_ogonowa ). Taka rekurencja nie spowoduje przeciążenia stosu wywołań. Wprawdzie standard C++ tego nie wymaga, ale tak to implementują szanujące się kompilatory :-)

Poniżej umieszczę już "podrasowaną wersję". Zerkaj tylko jeśli już rozwiążesz samodzielnie żebyś wiedział skąd biorą się inaczej zapisane wywołania :-)

#include <iostream>

unsigned collatz(unsigned s, unsigned count = 0) {
    return s == 1 ? count : collatz(s % 2 ? 3 * s + 1: s / 2, ++count);
}

int main() {
    unsigned s;
    unsigned n;
    std::cin >> n;
    while(n--> 0) {
        std::cin >> s;
        std::cout << collatz(s) << '\n';
    }
}

 

Answer 2

Tu raczej powinieneś poczytać coś o funkcji rekurencyjnej.

Nie możesz zrobić tak jak napisałeś ponieważ nie masz przypadku podstawowego i de facto cały czas w nieskończoność wywołujesz funkcje x(n).

Myślę, że chyba chciałeś napisać tak:

int x(n){
   if( n == 1)
        return n;
    else
       return x(n-1);

}

 

Comments

Tu raczej chodzi o operandy. 

x(n+1)=x(n)/2;

Lewy operand to funkcja, czyli coś przypisujesz do funkcji. Co to miałoby niby znaczyć ?

---

Chciałem przez to określić jak określony jest wyraz ciągu, parzysty i nieparzysty. Jak miałbym to inaczej zrobić przy funkcji?

---

@Munvik tu też masz racje, napisał o problemie z funkcja więc zajrzałem tam na szybko i to co powiedziałem jest również prawdą

---

Rzecz w tym, że pisząc ten kod właśnie chciałbym lepiej zrozumieć rekurencje, z zadaniem ze spoja "Problem collatza".

Poniżej przyblizyłem mój tok myślenia

int x(int n)
{
    if(x(n)==1)// w tym miejscu chcialem sprawdzic czy n-ty wyraz ciagu rowna sie 1 
        return n;
 
    else
        return x(n+1);// jesli nie rozpratruje kolejny wyraz
 
}

/////////////////////////

if(x(n)%2==0)
    {
        x(n+1)=x(n)/2;//dla parzystego parzystego wyrazu ciagu kolejny wyraz okreslam wlasnie takim wzorem
    }
    if(x(n)%2!=0)
    {
        x(n+1)=(3*(n))+1;// to samo dla nieparzystego
    }

 

---

w miejscu 

    if(x(n)==1)

nie sprawdzasz czy wyraz ciągu równa się jeden a wywłujesz funkcje x.

Myślę, że lepiej zacząć od podstaw ponieważ mylisz wywołanie funkcji z odwołaniem sie do tablicy