MÁRTON Gyöngyvér

Labor 1

Algoritmusok időmérése I

Feladatok:
1. Egy n>1000000 elemű tömböt töltsünk fel véletlenszerűen generált számokkal. A tömböt kezeljük dinamikusan. Vizsgáljuk meg, hogy a tömb elemei közül hány szám prím. Határozzuk meg az algoritmus időigényét, használva a clock() könyvtárfüggvényt

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10000000

int primek(int * tomb, int n);

int main(){
    clock_t start, finish;
    int *tomb;
    tomb = (int*)malloc(N*sizeof(int));
    int i;
    srand(time(0));
    for (i=0; i<N; ++i){
        tomb[i] = rand();
    }
    int nr;
    start = clock();
    nr = primek(tomb, N); // ezt a fuggvenyt meg kell irni!!!
    finish = clock();
    printf("ido: %f\n", (float)(finish - start)/CLOCKS_PER_SEC);
    printf("Result: %i\n\n", nr);
    system("pause");
    return 0;
}

2. Egy nxn-es négyzetes mátrixot inicializáljunk véletlenszerűen generált számokkal, ahol n>1000. A tömböt kezeljük dinamikusan. Írjunk programot, ami meghatározza a főátlón és mellékátlón levő elemek közül a maximumot. Oldjuk meg kétféleképpen a feladatokat, első esetben használjunk 2 for ciklust, másodszor próbáljuk 1 for ciklussal. Hasonlítsuk össze a két eset futási idejét, majd határozzuk meg a futási időket, ha a mátrix elemszámát fokozatosan növeljük.

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

#define N 10000
int my_max(int **tomb, int n);

int main(){
    clock_t start, finish;
    int m, i, j;
    int **tomb;
    tomb = (int**)malloc(N*sizeof(int*));
    for (i=0; i<N; ++i)
        tomb[i] = (int*)malloc(N*sizeof(int));
   srand(time(0));
    for (i=0; i<N; ++i){
         for(j=0; j<N; ++j){
            tomb[i][j] = rand();
            printf("%4i", tomb[i][j]);
        }
         printf("\n");
    }
    start = clock();
    m = my_max(tomb, N); // ezt a függvényt kétféleképpen kell megírni!!!
    finish = clock();
    printf("ido: %f\n", (float)(finish - start)/CLOCKS_PER_SEC);
    printf("Result: %i\n\n", m);
    system("pause");
    return 0;
}

3. Határozzuk meg x egy adott n értéken vett hatványát a következő algoritmusok szerint határozzuk meg. Hasonlítsuk össze az algoritmusok időigényét.

xⁿ meghatározásához n darab szorzást végzünk
meghívjuk a pow könyvtárfüggvényt:

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

#define N 1000000

int main(){
    clock_t start, finish;
    int i;
    double res;
    start = clock();
    for(i=0; i<N; ++i)
        res = pow(2, i);
    finish = clock();
    printf("ido: %f\n", (double)(finish - start)/CLOCKS_PER_SEC);
    printf("Result: %.0lf\n\n", res);
    system("pause");
    return 0;
}

xⁿ meghatározásához a gyorshatványozás algoritmusát alkalmazzuk:

ered = 1;
ameddig (n > 0)
    ha (n == 'paratlan')
       ered = x * ered;
    vege ha
    x = x * x;
    n= n / 2;
vege ameddig
return ered;