Metody Programowania - Lista 1

Zadanie 1

Mamy następujące deklaracje struktur: 

struct { char c; long l; short s; int i;} st1;

struct { long l; short s; char c;} st2;
ile zajmują one miejsca zakładając 2-bajtowe short i 4-bajtowe int i long. Ile jeśli długość short, int i long wynoszą odpowiednio 2, 4 i 8 lub 2, 8, 8 bajtów. Podać wynik zarówno w przypadku rozmieszczenia upakowanego, jak i wyrównywania (tzn, gdy liczby są rozmieszczane pod adresami podzielnymi przez ich wielkość).

Zadanie 2

Nastepujący program kopiuje wejście na wyjście blokami 

int
main(void)
{
    char bufor[1024];
    int dlugosc;
    while((dlugosc = read(0,bufor,1024)) > 0) {
                write(1, bufor, dlugosc);
    }
    return 0;
}
Napisać wersję wykonującą kopiowanie znak po znaku (przy użyciu 'getchar' i 'putchar'). Zmierzyć czas wykonania przy pomocy polecenia 'time' do obu wersji i kilku wielkości pliku (np. 1MB, 10MB, 100MB). Każdy pomiar powtarzać kilkakrotnie. Powtórzyć pomiary kompilując programy przy pomocy opcji '-O0', '-O', '-O2' i '-O3' (spróbować na kilku _różnych_ komputerach). Przedyskutować wyniki.

Zadanie 3

Poniższa funkcja oblicza sumę sinusów liczb od 1 do n: 

#include 

double
sumuj_sinusy(int n)
{
    int i;
    double suma = 0;
    for(i=1; i <= n; i++) {
        suma += sin(i);
    }
    return suma;
}

Napisać program główny który wywoła tą funkcję w pętli 100000 (chodzi
o to by sztucznie wydłużyć czas wykonania tak, by było go łatwo
zmierzyć) z argumentem 1000. Następnie zrobić wersję która oblicza
sinusy kolejnych kątów przy pomocy wzorów na sinus i kosinus sumy kątów
korzystając ze wstępnie obliczonych (przy pomocy funkcji bibliotecznej)
wartości 'sin(1)' i 'cos(1)'. Porównać czasy wykonania (dla różnych
opcji kompilatora) i przedyskutować wyniki.


W następnych zadaniach zakładamy że listy są zadane (reprezentowane
poprzez wskaźnik do pierwszego elementu, zaś ostatni element
ma zerowy wskaźnik do następnego). Listy są jednokierunkowe,
chyba że napisano inaczej.




 Zadanie 4 


 Zadeklarować strukturę, odpowiednią jako typ węzła
dla:

    

  •  listy punktów na płaszczyźnie

  •  listy par nazwa, numer

  •  listy mieszkańców domu




 Zadanie 5 


 Napisać funkcję, która mając daną listę liczb całkowitych
znajdzie maksymalny element (albo obliczy sumę elementów).


 Zadanie 6


 Zakładamy że elementy list mają całkowite pole 'licznik'.
Dla dwu zadanych list (równej długości) stworzyć nową listę, której
pola 'licznik' są sumami pól 'licznik' z list wejściowych
(n-ty element wyniku zawiera sumę z n-tych elementów obu
list wejściowych).


 Zadanie 7


 Zakładamy że elementy listy mają całkowite pola 'klucz'
i 'licznik'.  Powiększyć pole 'licznik' o 1 dla tych
elementów listy które mają zadaną wartość klucza.


 Zadanie 8


 Napisać funkcję, która mając daną listę liczb całkowitych
i liczbę, usunie pierwsze (albo każde) wystąpienie tej liczby
na liście.


 Zadanie 9


 Napisać funkcję, która mając daną listę, (taką jak któraś
z list z zadania 4) i wskaźnik do elementu na liście znajdzie
poprzedni element.


 Zadanie 10 


 Rozdzielić zadaną listę na dwie,

    

  •  pierwsza z nieparzystych elementów, druga z parzystych

  •  zakładamy że elementy mają całkowite pole klucz. Pierwsza
lista ma mieć elementy z kluczem większym od zadanej wartości, druga
pozostałe

  •  to samo, ale dla list dwukierunkowych

  •  to samo co w poprzednich punktach, ale kopiując listy zamiast
modyfikacji




 Zadanie 11 


 Napisać funkcję, która odwróci daną listę dwukierunkową (tzn.
zmieni wskaźniki tak by elementy były w odwrotnej kolejności).


 Zadanie 12 


 Napisać funkcję:

    

  •  która wypisze elementy zadanej listy

  •  zbuduje listę zadanej długości wypełniając pola 'klucz'
kolejnymi (albo losowymi) wartościami


Jak można użyć takie funkcje do sprawdzenia czy funkcje 
z poprzednch zadań działają poprawnie.