Programy C (pt. 4)

Kolejny zestaw programów:

5 stycznia 09 (przeniesione z 22 grudnia 08) – szybkie sortowanie rekursywne

http://www.ipipan.gda.pl/~stefan/Dydaktyka/WstepDoProg/lab-12-22/

Pliki potrzebne do zadania:

dane1 – plik ze 100 000 liczbami nieposortowanymi, czas – program mierzący czas wykonywania.
Odpalamy programy w ten sposób: ./czas sort dane1 wynik .

Zadanie 1: uporządkować dane za pomocą rekursywnej funkcji mergesort omówionej na wykładzie:

#define N 100000
float a[N];

void merge (int p, int r, int q)
{
    int i,j,k;
    float pom[N];
    i=p;
    j=r;
    k=p;
    while (i<r && j<q)
    {
        if (a[i] <= a[j])
        {
            pom[k] = a[i]; i++; k++;
        }
        else
        {
            pom[k]=a[j]; j++; k++;
        }
    }
    while (i<r) { pom[k]=a[i]; i++; k++;}
    while (j<q) { pom[k]=a[j]; j++; k++;}
    for (k=p; k<q; k++) a[k]=pom[k];
}

void mergesort (int p,int q)
{
    int r;
    if (p+1 < q)
    {
        r = (p+q)/2;
        mergesort(p,r);
        mergesort(r,q);
        merge(p,r,q);
    }
}

main ()
{
    int i;

    for (i=0; i<N; i++)
    {
        scanf("%f",&a[i]);
    }

    mergesort(0,N);

    for(i=0; i<N; i++)
    {
        printf("%f\n",a[i]);
    }
}

Zadanie 2: Jak wyżej, ale tym razem za pomocą programu quicksort (brakująca część programu została podana na laboratorium).

#define N 100000

float a[N];

void quicksort(int p, int q)
{
    int j,k,l;
    float r,x;
    if (p+1 < q)
    {
        r = a[(p+q)/2];

        // sth

        k = p;
        l = q;
        j = q;

        while(j>k)
        {
            if (a[j-1]==r) j--;
            else if (a[j-1]<r)
            {
                x = a[j-1];
                a[j-1]==a[k];
                a[k]=x;
                k++;
            }
            else
            {
                x = a[j-1];
                a[j-1] = a[l-1];
                a[l-1]=x;
                l--;
                j--;
            }
        }

        quicksort(p,k);
        quicksort(l,q);

    }
}

main ()
{
    int i;

    for (i=0; i<N; i++)
    {
        scanf("%f",&a[i]);
    }

    quicksort(0,N);

    for(i=0; i<N; i++)
    {
        printf("%f\n",a[i]);
    }
}

12 stycznia 09, reprezentacja komputerowa liczb (cecha i mantysa)

http://www.ipipan.gda.pl/~stefan/Dydaktyka/WstepDoProg/lab-01-12/

Zadanie 1: Obliczyć ile bitów zajmuje INT, poprzez potęgowanie liczby 2:

main(){

int liczba,ile;

liczba = 1;
ile =0;

while (liczba > 0 )
{
    liczba = liczba *2;
    ile ++;
}

printf("Jest %i bitow\n",ile+1);
}

Zadanie 2: Obliczanie cechy i mantysy dla typu FLOAT:

//zad 2, lab 01-12

main ()
{
    float liczba,last;
    int cecha,mantysa;

    liczba = 1;
    last = 0;

    cecha = 0;
    mantysa = 0;

    while (liczba != last)
    {
        last = liczba;
        liczba = liczba * 2;
        cecha ++;
    }

    cecha = cecha - 2;
    printf("Maksymalna cecha wynosi %i \n",cecha);

    liczba = 1;
    do
    {
        liczba = liczba / 2;
        mantysa ++;
    }
    while (liczba != 0);

    printf("Mantysa wynosi %i \n",mantysa - cecha);

}

Zadanie 3: tak jak w punkcie 2, ale float liczba,last zamieniamy na double liczba, last.

main ()
{
    double liczba,last;
    int cecha,mantysa;
    // ... i tak dalej, jak w zadaniu 2

Zadanie 4: Wykonać program, który dzieli a/2 tak długo aż: 1 + a = 1, (a będzie tak małą liczbą float, że zostanie zaokrąglone do zera).

main()
{
    float a;
    int ile;

    a = 1;
    ile = 0;

    while (1 + a != 1)
    {
        a = a / 2;
        ile --;
    }

    printf("Ostatnia potega to %i\n",ile);
}

.
Kilka innych programów z rekursją:

1.  Program prosi usera o podanie rozmiaru tablicy ( 0 < n <= 100 ). User wpisuje dowolne liczby, a program je sortuje.

float a[100];

void sort(int n)
{
    int index,i;
    float pamietaj;

    index = 0;
    for (i=1; i<n; i++)
    {
        if (a[i]>a[index]) index = i;
    }

    pamietaj = a[index];
    for (i=index; i<n-1; i++)
    {
        a[i]=a[i+1];
    }
    a[n-1] = pamietaj;

    if (n>2) sort(n-1);
}

main()
{
    int n,i;

    printf("Podaj n:");
    scanf("%i",&n);
    if ( n<1 || n>100 )
    {
        printf("Zly zakres");
        return;
    }

    //skanuj tablice
    for (i=0; i<n; i++)
    {
        scanf("%f",&a[i]);
    }

    if (n > 1) sort(n);

    // drukuj tablice
    for (i=0; i<n; i++)
    {
        printf("%f\n",a[i]);
    }
}

2. Permutacje. Podać n ( 0 < n <= 20). Program wyświetla wszystkie permutacje dla liczb od 0 do n-1. np.: dla n = 2:

01
10

dla n = 3:

012
021
102
120
201
210

//permutajce
//te zmienne sa dostepnie globalnie, tzn. jezeli gdziekolwiek je zmienimy, to zmieniaja sie dla !calego! programu
int a[20],n;

//ta funkcja drukuje tablice a dla wartosci n od tylu, tak po prostu wyglada ladniej
void drukuj()
{
    int i;
    for ( i=n; i>0; i-- )
    {
        printf( "%i" , a[i-1] );
    }
    printf( "\n" );
}

//permutacje
void permute( int k )
{
    int i,t;

    if ( k==0 ) drukuj();
    else
    for ( i=0; i<k; i++ )
    {
        t = a[i];
        a[i] = a[k-1];
        a[k-1] = t;

        permute( k-1 );

        t = a[i];
        a[i] = a[k-1];
        a[k-1] = t;
    }
    return;
}

//glowna czesc programu
main()
{
    int i;
    //nie potrzebujemy int n, poniewaz jest zdefinionwane na poczatku

    printf( "Podaj n: " );
    scanf( "%i" , &n );
    if ( n<1 || n>20 )
    {
        printf( "Zly zakres" );
        return;
    }

    //zapychamy tablice a kolejnymi liczbami naturalnymi od 0 do n-1
    for ( i=0; i<n; i++ )
    {
        a[i] = i;
    }

    //permutujemy
    permute( n );

    //to jest juz wszystko
    return;
}

.

Dodaj komentarz