Rest beim Teilen ausgeben(rekursiv)

Hallo,

ich komme bei einer Aufgabe nicht weiter und zwar weiss ich nicht wie ich bei folgender Aufgabe den Rest ausgeben soll.

Aufgabenstellung:
Schreiben Sie eine Funktion, die zwei ganze Zahlen dividiert und das Ergebnis sowie den ganzzahligen Rest ausgibt. Das Programm darf nicht die Operatoren / und % verwenden und soll rekursiv sein.

hier mein code bisher:
Das teilen funktioniert einwandfrei, nur weiss ich nicht wie ich den Rest ausrechnen soll also z.b. wenn ich 13 und 5 eingebe dass 2 "REST 3" rauskommt.

#include <stdio.h>
#include <stdlib.h>

int teilen(int x, int y)
{
    int ret=0;

    if(x>=y)
    {
        ret=(1+teilen(x-y, y));
    }

    return ret;
}

int main()
{
    int a,b;
    int tmp;

    printf("Erste Zahl eingeben: ");
    scanf("%d", &a);
    printf("\nZweite Zahl eingeben: ");
    scanf("%d", &b);

    tmp=teilen(a,b);

    printf("%d", tmp);

}

danke

Swordfish

Sind statische Variablen erlaubt? (hint, hint)

hmm... ka

ich habe nur die obenstehende Aufgabenstellung und unser Prof. ist diese Woche nicht mehr erreichabar - kann ihn also auch nicht mehr fragen.

Wutz

Du musst dir überlegen, wie du statt ein jetzt zwei Werte aus der Funktion an den aufrufenden Kontext übergibst.
Deppen verwenden hier globale Variablen.
Man könnte statt 1x int eine struct (mit 2x int) rückgeben, oder einen extra Parameter spendieren:

int teilen(int x, int y, int *r)
{
    int ret=0;
    *r = x;

    if(x>=y)
    {
        ret=(1+teilen(x-y, y, r));
    }

    return ret;
}

int main(void) {
	int r, d = teilen(13,5,&r);
	printf("%d REST %d",d,r);
	return 0;
}

http://ideone.com/3XTdms

Dein Algorithmus funktioniert nicht für negative Zahlen.

Swordfish

Da die Funktion das Ergebnis selbst ausgeben soll glaube ich nicht, daß es um das Zurückgeben von zwei Werten geht.

//edit: Andreaseits wirds anders wohl nicht gehn

camper

Swordfish schrieb:

//edit: Andreaseits wirds anders wohl nicht gehn

Gehen schon, aber ob's schön ist...

#include <stdio.h>
int teilen(int x, int y, int *r, int marker)
{
    int ret=0;
    *r = x;

    if(x>=y) {
	    marker++;
        ret=(1+teilen(x-y, y, r, marker));
	    marker--;
        if (! marker) {
	        printf("%d REST %d\n\r",ret,*r);
        }
    }
    return ret;
}

int main(void) {
    int r, d = teilen(23,7,&r,0);
    return 0;
}

SeppJ

Wenn man schon div nach programmiert, dann kann man ja auch die gleiche Schnittstelle nutzen.

SeppJ

Wenn wir hier schon Division machen, dann doch bitte mit Divide & Conquer! Ohne D&Q ist Rekursion schließlich lahm. Bloß sind in diesem Fall die beiden Seiten gleich, so dass man auch einfach 2x das Ergebnis einer Hälfte nehmen kann . Nichtsdestotrotz kommt man so von einem Aufwand O(Quotient) zu einem Aufwand O(log(Quotient)).

typedef struct
{
  int quot;
  int rem;
} division_result;

division_result division(int numer, int denom)
{
  division_result res = {0, numer};
  if (numer >= denom)
    {
      division_result sub_res;
      int quot;
      sub_res = division(numer >> 1, denom);  // Hier könnte man der Schönheit wegen auch noch eine zweite Division mit numer - (numer >> 1) machen
      res.rem = (numer & 1) + sub_res.rem + sub_res.rem; // Und dann hier das (numer & 1) weglassen und die beiden Ergebnisse addieren
      quot = sub_res.quot + sub_res.quot;
      if (res.rem >= denom) 
        {
          quot += 1;
          res.rem -= denom;
        }
      res.quot += quot;
    }  
  return res; 
}

Auch dieser Code geht nicht mit negativen Zahlen, ich will dem TE schließlich nicht die Hausaufgaben komplett machen.

Swordfish

@SeppJ: clever one