Rekursiv rechnen!

Hallo zusammen,

Ich bin ein C Anfänger und hätte eine Frage zu einer Aufgabe.
Ich soll x_n= n - x_n-1 mit x₁= 1 und n>1 rekursiv berechnen.
n soll von der Kommandozeile abgelesen werden. Für Testzwecke habe ich n einen Wert zu gewiesen.

#include <stdio.h>

int main (void)
{
    int n = 5;
    int x;
 //   printf("Geben Sie eine Zahl ein\n");
 //   scanf("%d", &n);

    for (x = 1; n > 1; n--)
    {
        x = n - x;
    }

    printf("%d", x);
    return 0;
}

Meine Frage ist jetzt, inwiefern ich x korrekt ausgebe? Bzw. ob die for schleife für mein Vorhaben korrekt ausgelegt ist?

Viele Grüße
Ben

knivil

Wenn die Aufgabe 'rekursiv' lautet, dann sollte vielleicht auch Rekursion benutzt werden.

Swordfish

...

volkard

BenJohn schrieb:

Ich soll

Da Du so weit weg bis vom Ziel hier mal eine Komplettlösung:

#include <stdio.h>

int f(int n)
{
    if(n==1)
    {
        return 1;
    }
    else
    {
        int xn=n-f(n-1);
        return xn;
    }
}

int main(void)
{
    int n = 20;
 //   printf("Geben Sie eine Zahl ein\n");
 //   scanf("%d", &n);

    printf("%d\n",f(n));

    return 0;
}

BenJohn schrieb:

x_n= n - x_n-1 mit x₁= 1

Och, das ist soo schade.
Also

int xn=n-f(n-1);//supi langweilig, f(n)=floor(n/2)

statt

int xn=n-f(f(n-1));//Schönen Gruß von Hofstadter

volkard schrieb:

Da Du so weit weg bis vom Ziel hier mal eine Komplettlösung:
int f(int n)
{
    if(n==1)
    {
        return 1;
    }
    else
    {
        int xn=n-f(n-1);
        return xn;
    }
}
....

Oder ein bisschen eleganter:

int f(int n)
{
  int xn;
  return (n==1) ? 1 : xn=n-f(n-1);
}

Was genau ist daran eleganter?

knivil

Tim schrieb:

Was genau ist daran eleganter?

Ohne auf Korrektheit geprueft zu haben: kuerzer, keine temporaeren Variablen. Warum dann aber int xn noch dasteht, k.A. .

Das mit dem xn macht natürlich keinen Sinn, ich denke mal er mal eben "auf die schnlle" umgeschrieben. Also wäre es so in der Tat eleganter:

int f(int n)
{
  return (n==1) ? 1 : n-f(n-1);
}

Tim schrieb:

Was genau ist daran eleganter?

- kürzer
- keine unnötigen Variablen

Aber das wichtigste:

Der geübte Informatiker kann so viel einfacher die Rekursion nachvollziehen und erkennen. In der if-else Kaskade oben wird die schnell mal übersehen.

Ich bin wohl nicht geübter Informatiker genug um Eleganzunterschiede zweier identischer Implementierungen, die sich lediglich durch Syntaxzucker (oder Salz) unterscheiden, zu erkennen. Damit kann ich leben

volkard

Peterson W. schrieb:

Der geübte Informatiker kann so viel einfacher die Rekursion nachvollziehen und erkennen. In der if-else Kaskade oben wird die schnell mal übersehen.

Tja. Neulich die Aufgabe TGGC5, da schrieb ich

void erzeugeTeilerSub(vector<uint32_t> & result,
//...und dann wird hier der Teilerverband aufgespannt. 
    map<uint32_t,size_t>::iterator begin,
    map<uint32_t,size_t>::iterator end,
    uint32_t p){
    if(begin==end){
        result.push_back(p);
        return;
    }
    for(size_t i=0;i<=begin->second;++i){
        ++begin;
        erzeugeTeilerSub(result,begin,end,p);
        --begin;
        p*=begin->first;
    }
}

vector<uint32_t> erzeugeTeilerSub(uint32_t n){
//Zählt Primfaktoren und dann...
    vector<uint32_t> result;
    map<uint32_t,size_t> primfaktoren;
    while(n%2==0){
        ++primfaktoren[2];
        n/=2;
    }
    for(uint32_t t=3;t*t<=n;t+=2){
        while(n%t==0){
            n/=t;
            ++primfaktoren[t];
        }
    }
    if(n!=1)
        ++primfaktoren[n];
    erzeugeTeilerSub(result,primfaktoren.begin(),primfaktoren.end(),1);
    sort(result.begin(),result.end());
    return result;
}
vector<uint32_t> erzeugeTeiler(int32_t n){
//Aufruf-Wrapper mit Cache
//    cout<<"ask "<<n<<'\n';
    static unordered_map<uint32_t,vector<uint32_t>> cache;
    vector<uint32_t>& result=cache[n];
    if(result.empty())
        result=erzeugeTeilerSub(n);
    return result;
}

Jo, rekursiv halt. Wie soll ich sonst einen Teilerverband aufspannen? Gut, es geht auch anders, aber so war es am schnellste eingeklimpert.
Als geübter Informatiker baue ich Rekursionen immer mit if.
Triviale Fälle würden zu ?: zerfallen können. Aber das gebe ich mir nicht, um die Sache einheitlich zu lassen.

Und dann geschah

uint32_t z[32];
uint32_t bestValue=120;
uint32_t auco=0;
void run(uint32_t n,uint32_t produkt,uint32_t value,size_t count,uint32_t minTeiler){
    if(n==1){
        ++auco;
        if(value<=bestValue){
            bestValue=value;
            cout<<produkt<<": ";
            for(size_t i=0;i<count;++i)
                cout<<z[i]<<' ';
            cout<<"-> "<<value;
            cout<<'\n';
        }
        return;
    }
    for(auto t:erzeugeTeiler(n)){
        if(t<minTeiler) continue;
//        cout<<t<<'\n';
        z[count]=t;
        if(t==2)
            run(n/2,produkt*2,value+t%27,count+1,t);
        else
            run(n/t,produkt*t,value+t%27,count+1,t);
    }
}
void run(uint32_t n){
    run(n,1,0,0,2);
}

und alle Lösungen für ein Produkt werden durchprobiert. Schon wieder rekursiv. Schon wieder mit if.

Nö, die Version mit ?: halte ich nicht für eleganter. Sie trägt eigentlich nur bei Schulaufgaben, fürchte ich.

Meine Version oben mit der Zwischenvariablen war nur, um sicherzustellen, daß BenJohn den Code noch besser nachvollziehen kann.

Für mich würde ich schreiben

nt f(int n)
{
    if(n==1)
        return 1;
    return n-f(n-1);
}

Wohl die uneleganteste Version.
Aber ich mag es nicht, den Haupt-Zweig einzurücken, daher hüpft die Abbruchbedingung, die auch vorher zu stehen hat, mit return raus.

Swordfish

...