Vissza

Rekurzió II

1. Írjunk rekurzív függvényt, mely meghatározza xn értékét. Az algoritmus iteratív változata, unsigned long long típus esetében itt található.

2. Írjunk rekurzív függvényt, mely meghatározza két szám legnagyobb közös osztóját

3. Írjuk meg a bináris keresés rekurzív változatát.

4. Számrendszerek közötti átalakítások, rekurzívan:

  • adott tízes számrendszerbeli számot alakítsunk át tetszőleges b számrendszerbe és fordítva is, (az algoritmusok különböző változatainak forráskódja itt található)
  • adott 2-es számrendszerbeli számot alakítsunk át 2k számrendszerbe és fordítva is,
  • adott b-es számrendszerbeli számot alakítsunk át bk számrendszerbe és fordítva is.

5. Hanoi tornyai: adott 3 rúd, melyeket jelöljünk rendre a, b, c-vel. Az a rúdon n különböző méretű korong található, méretük szerint csökkenő sorrendben (legalul található a legnagyobb átmérőjű). Írjunk rekurzív függvényt, mely szimulálja az n korong áthelyezését az a rúdról a b rúdra, a c rúd segítségével, figyelembe véve a következőket:

  • egy lépésben egyetlen korong mozdítható el
  • tilos nagyobb átmérőjű korongot, kisebb átmérőjűre helyezni.
A feladat pseudokódja a következő:
hanoi( korong, elso, masodik, harmadik )
    ha egy korong van akkor elso -> masodik
    maskepp
       hanoi(korong-1, elso, harmadik, masodik)
       elso -> masodik
       hanoi(korong-1, harmadik, masodik, elso)

1. feladat

#include <stdio.h>
typedef unsigned long long UL;

UL hatvany(UL x, UL n);

int main(){
    UL x, n, res;
    printf("alap: ");
    scanf("%llu", &x);

    printf("kitevo: ");
    scanf("%llu", &n);

    res = hatvany(x, n);
    printf("eredmeny: %llu\n", res);
}

UL hatvany(UL x, UL n){
    UL ered = 1;
    while( n > 0){
        if (n % 2 == 1) ered = x * ered;
        x = x * x;
        n = n / 2;
    }
    return ered;
}

2. feladat:

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

int * alakit(int *, int, int);
int * alakitR(int *, int, int);
void alakitP(int *, int **, int, int);

int main(){
    int nr=27, b=2, n, i;
    int * new_nr = (int*)malloc(sizeof(int));
   
    new_nr = alakit(&n, nr, b);
    printf("Iterativan:\n%i\t", nr);
    for(i = 0; i < n; ++i)
        printf("%i ", new_nr[i]);
    printf("\n\n");
   
    new_nr = alakitR(&n, nr, b);
    printf("Rekurzivan:\n%i\t", nr);
    for(i = 0; i < n; ++i)
        printf("%i ", new_nr[i]);
    printf("\n\n");
   
    alakitP(&n, &new_nr, nr, b);
    printf("Iterativan, cim szerint:\n%i\t", nr);
    for(i = 0; i < n; ++i)
        printf("%i ", new_nr[i]);
    printf("\n\n");
   
    free (new_nr);
    return 0;
}

int * alakit(int *n, int nr, int b){
    int *t_nr = NULL;
    *n = 0;
    while(nr != 0){
            t_nr = (int*)realloc(t_nr, (*n+1) * sizeof(int));
            t_nr[*n] = nr % b;
            nr = nr/b;
            (*n)++;
    }
    return t_nr;
}

int * alakitR(int *n, int nr, int b){
    int * t_nr;
    if (nr == 0) {
        t_nr = NULL;
        *n = 0;
        return t_nr;
    }
    t_nr = alakitR(n, nr/b, b);
    t_nr = (int*)realloc(t_nr, (*n+1) * sizeof(int));
    t_nr[*n] = nr % b;
    (*n)++;
    return t_nr;
}

void alakitP(int *n, int ** tomb_nr, int nr, int b){
    int * t_nr = NULL;
    int i = 0;
    while(nr != 0){
            t_nr = (int*)realloc(t_nr, (i+1) * sizeof(int));
            t_nr[i] = nr % b;
            nr = nr/b;
            (i)++;
    }
    *n = i;
    *tomb_nr = t_nr;
}