Stefan Sokołowski, Podstawy programowania
LABORATORIUM 8

Zadanie 1:

Napisać program na poszukiwanie liczby całkowitej w tablicy: wczytać tablicę (czyli najpierw jej długość, następnie jej elementy), potem liczbę i wydrukować

albo numer indeksu pod którym w tablicy znajduje się poszukiwana liczba;
albo komunikat, że takiej liczby w tablicy nie ma.

Ile porównań liczb wykonuje ten algorytm w najgorszym razie dla tablicy o długości n?

Zadanie 2:

Rysunek obok ilustruje niepoprawny oraz poprawny sposób zamieniania dwóch elementów tablicy.

Dla rozgrzewki proszę napisać prosty program, który

spyta użytkownika o liczbę n liczb rzeczywistych,
wczyta do tablicy n liczb rzeczywistych podanych przez użytkownika,
zamieni w tablicy liczbę zerową z ostatnią,
wydrukuje liczby z poprawionej tablicy.

Zadanie 3:

Teraz proszę o

program, który we wczytanej tablicy liczb rzeczywistych zamieni liczbę ostatnią z liczbą największą; to znaczy największa liczba ma pójść na koniec tablicy, przy tym żadna liczba z tablicy nie może zginąć;

program, który wykorzysta punkt A dla uporządkowania całej tablicy wg wielkości liczb; czyli najpierw postawi największą liczbę na końcu, potem największą z pozostałych na końcu tych pozostałych, itp.

Program stanowiący rozwiązanie punktu B proszę przetestować na tym zbiorze 30 tys. liczb rzeczywistych.

Wskazówka:
Oczywiście 30 tys. liczb nie można wpisać z klawiatury; nie ma też sensu wyświetlania tak dużego wyniku na konsoli. Należy to zrobić na plikach — podaję niżej przydatne komendy systemu Linux:

ściągnięcie pliku z danymi do własnego aktualnego katalogu:
wget http://iis.ans-elblag.pl/~stefan/Dydaktyka/PodstProg/Lab08/liczby
wykonanie skompilowanego programu z danymi branymi z pliku dane zamiast z klawiatury oraz z wynikami na (dotąd nieistniejącym) pliku wyniki zamiast na ekranie:
./a.out < dane > wyniki
(oczywiście oba pliki można nazwać inaczej).

Plik wynikowy powinien zajmować ok. 460kB — proszę to sprawdzić. I proszę zajrzeć do środka i ocenić ,,na oko'', czy liczby są uporządkowane.

Zadanie 4:

Zad.3B może być traktowane jako wstęp do ważnej kategorii algorytmów komputerowych: sortowania. Ważnym zagadnieniem z dziedziny analizy algorytmów jest ocena, ile razy zostają w nich użyte konkretne operacje.

Proszę ustalić, ile

porównań liczb rzeczywistych, oraz
zamian liczb rzeczywistych

wykonuje w najgorszym razie program z zad.3B dla tablicy zawierającej n liczb.

Wskazówka:
Ostateczną odpowiedź powinna stanowić jakaś funkcja od n (funkcja o argumencie n i wartości równej liczbie porównań/zamian). Pomocne może być wzbogacenie algorytmu o liczniki porównań i zamian. Pozwolą one sprawdzić zgadnięty wzór funkcji na liczbach podanych przez te liczniki.

Zadanie 5 domowe:

Napisać program, który

wczytuje liczbę naturalną n≥2;
do tablicy o n miejscach wczytuje n−1 liczb rzeczywistych już uporządkowanych ręcznie przez użytkownika — pozostaje więc jedno wolne miejsce na końcu tablicy;
wczytuje jakąś dodatkową liczbę rzeczywistą na to ostatnie wolne miejsce w tablicy — w wyniku tego wstawienia tablica na ogół przestaje być uporządkowana;
za pomocą zamian elementów sąsiednich przestawia tą ostatnią liczbę z liczbami poprzedzającymi ją w tablicy, aż znajdzie się na takim miejscu, żeby cała tablica była uporządkowana.

Zastanowić się, jak taki program można wykorzystać do sortowania dowolnej tablicy liczb rzeczywistych.

Do mojej głównej witrynki