Podstawy programowania - ćwiczenia



Forma zaliczenia

W ramach ćwiczeń można uzyskać 15 punktów (sprawdzian z teorii (8 pkt) + kolokwium (7pkt)).

liczba uzyskanych punktów

ocena z ćwiczeń

<14,15>

5.0

<13,14)

4.5

<12,13)

4.0

<10,12)

3.5

<8,10)

3.0

(0,8)

2.0



Plan zajęć:

1. Struktura programu w języku C. Podstawowe typy danych. Definiowanie zmiennych. Instrukcje wejścia- wyjścia. Instrukcje warunkowe i wyboru. Wprowadzenie do tworzenia schemtów blokowych. 

2. Instrukcje iteracyjne. Tworzenie schematów blokowych z wykorzystaniem pętli.
Do każdego z poniższych zadań należy sporządzić schemat blokowy.
Zadanie 2.1
Wprowadzić n liczb typu rzeczywistego, obliczyć dla każdej z nich kwadrat i sześcian oraz wyprowadzić numer liczby, samą liczbę, oraz jej kwadrat i sześcian. Program ma zapraszać użytkownika komentarzem do podania kolejnej liczby i wyprowadzać dane oraz wyniki związane z jedna liczbą w jednym wierszu.
Zadanie 2.2
Wprowadzić ciąg znaków zakończony znakiem '*', policzyć i wyprowadzić liczbę znaków w ciągu.
Zadanie 2.3
Podczas wprowadzania ciągu n liczb wyszukać liczbę o maksymalnej wartości i podać jej numer w ciągu.
Zadanie 2.4
Dla podanego n oblicz następują wartość:
1/2+2/3+3/4+...+n/(n+1)
Zadanie 2.5
Napisz program, który pyta się o pewną stałą liczbę tak długo, aż zostanie odgadnięta. Po każdej nieudanej próbie informuje, czy szukana liczba jest większa, czy mniejsza od podanej.
Zadanie 2.6
Napisz program wyznaczający iteracyjnie (numerycznie) sumę szeregu:
1/x + 1/x 2 + 1/x3 + 1/x4 + ... + 1/xn
Zadanie 2.7
Napisać program obliczający silnię.
Zadanie 2.8
Napisać program wyznaczający sumę liczb podawanych z klawiatury tak długo, aż użytkownik nie wprowadzi liczby zero.

3. Dynamiczna alokacja pamięci. Tablice jednowymiarowe.
Do każdego z poniższych zadań należy sporządzić schemat blokowy.
Zadanie 3.1
Napisz program, który wczyta dane z klawiatury do 10-cio elementowej tablicy liczb double, a następnie sprawdzi:
- czy te liczby są uporządkowane rosnąco lub malejąco,
- czy elementy tablicy mają symetryczną zawartość (tzn. pierwszy element równy ostatniemu, drugi równy przedostatniemu, itd. )
- czy w tablicy występuje chociaż jedno powtórzenie wartości.
Zadanie 3.2
Napisz program, który przesunie zawartość N-elementowej tablicy (rozmiar tablicy podawany jest przez użytkownika) cyklicznie o jedną pozycję „w górę”. (tzn. pierwszy element na miejsce drugiego, drugi na trzeci, ..., ostatni na pierwszy).
Zadanie 3.3
Napisać program wyznaczający iloczyn skalarny dwóch wektorów N-elementowych o wartościach rzeczywistych.  Rozmiar wektorów podawany jest przez użytkownika.
Zadanie 3.4
Napisać program, który na podstawie tablicy liczb całkowitych tabA (rozmiar i wartości podawane są przez użytkowika) stworzy tablicę tabB wg następującego wzoru: tabB[i] = tabA[0]-tabA[1]+tabA[2]-...tabA[i].
Zadanie 3.5
Napisać program, który wczytuje ze standardowego wejścia napis do tablicy i sprawdza, czy jest on palindromem. Wczytany napis ma mieć maksymalnie 40 znaków.
Zadanie 3.6
Napisać program, który wczytuje od użytkownika łańcuch znaków a następnie pojedynczy znak i podaje indeks ostatniego wystąpienia tego znaku w zadanym łańcuchu. Indeksy mają być liczone od jedynki. Wczytany napis ma mieć maksymalnie 20 znaków.
Przykład:
znak: 'o',
łańcuch: ”Ola ma kota”
wynik: 9
Zadanie 3.7
Napisać program, który wylosuje do tablicy N liczb z przedziału 1...M (N i M podawane są przez użytkownika) i wypisze na ekran wylosowane elementy oraz policzy liczność każdego z nich.
Przykład:
N=10, M=5,
tablica: 1 4 2 4 5 3 1 2 2 1
wynik: 1–3 razy; 2-3 razy; 3-1 raz; 4-2 razy; 5-1 raz

4. Tablice dwuwymiarowe.
Zadanie 4.1
Napisz program, który wczyta od użytkownika wymiary (n i m) i wypełni dwuwymiarową tablicę liczb całkowitych t[N][M] wartościami wczytanymi od użytkownika, a następnie wyznaczy ile jest elementów parzystych dla każdej kolumny osobno.
N i M są zdefniowane w programie za pomoc¡ dyrektywy #define i oznaczają maksymalny możliwy rozmiar tablicy.
Wartości n i m to liczba elementów w tablicy (n<=N, m<=M).
Zadanie 4.2
Napisz program, który wczyta od użytkownika wymiary (n i m) i wypełni losowymi wartościamy dwywumiarową tablicę liczb całkowitych t[N][M] a następnie znajdzie numer wiersza, dla którego średnia elementów jest największa.
N i M są zdefniowane w programie za pomoc¡ dyrektywy #define i oznaczają maksymalny możliwy rozmiar tablicy.
Wartości n i m to liczba elementów w tablicy (n<=N, m<=M).
Zadanie 4.3
Napisz program, który wczyta od użytkownika wymiary (n i m) i wypełni losowymi wartościamy dwywumiarową tablicę liczb rzeczywistych t[N][M] a następnie w każdej kolumnie zamieni elementy, które są mniejsze od średniej danej kolumny wartością wczytaną od użytkownika.
N i M są zdefniowane w programie za pomoc¡ dyrektywy #define i oznaczają maksymalny możliwy rozmiar tablicy.
Wartości n i m to liczba elementów w tablicy (n<=N, m<=M).
Zadanie 4.4
Napisz program, który utworzy dynamiczną dwuwymiarową tablicę liczb całkowitych (rozmiar i wartości podawane są przez użytkowika) a następnie zamieni miejscami dwa wiersze, których numery podaje użytkownik.
Nie przepisuj elementów, wykorzystaj fakt, że tablica dwuwymiarową składa się z dwuwymiarowej tablicy wskaźników.
Zadanie 4.5
Napisz program, który utworzy dynamiczną dwuwymiarową tablicę liczb całkowitych (liczbę wierszy i wartości podawane są przez użytkowika) w taki sposób, że w pierwszym wierszu znajduje się tylko jeden element a liczba elementów w każdym następnym wierszu jest dwa razy większa niż w wierszu poprzednim.
Zadanie 4.6
Napisz program, który utworzy dynamiczną dwuwymiarową tablicę liczb całkowitych (rozmiar i wartości podawane są przez użytkowika) a następnie stworzy druga tablicę w taki sposób, że liczba wierszy jest taka sama jak w tablicy pierwszej a w danym wierszu znajdą się tylko te elementy pierwszej tablicy, któ¶e są większe od średniej arytmetycznej tego wiersza.

5. Funkcje. Przekazywanie parametrów.
Zadanie 5.1
Napisz funkcję polacz(), która przyjmuje dwa argumenty i przekazuje na zewnątrz napis będący ich połączeniem.
Zadanie 5.2
Napisz funkcję odwroc(), która będzie odwracała kolejność znaków w przekazanym jej napisie. Po wykonaniu odwroc(p), ostatni znak p będzie pierwszym, przedostatni – drugim, itd.
Zadanie 5.3
Napisać funkcję znajdującą i wypisującą na ekran wszystkie pary liczb bliźniaczych z danego przedziału liczb naturalnych, podanego jako parametr funkcji. Parą liczb bliźniaczych nazywamy parę kolejnych liczb nieparzystych pierwszych, np. 3 i 5.
Zadanie 5.4
Napisać funkcję, która w tablicy dwuwymiarowej NxM o wartościach typu float wyznaczy dla ilu pierwszych elementów ich suma jest większa od 100.
Zadanie 5.5
Napisać funkcję zwracającą sumę tych elementów leżących na przekątnej tablicy liczb całkowitych o rozmiarze NxN, które są liczbami nieparzystymi.
Zadanie 5.6
Napisać funkcję obracającą tablicę kwadratową o wymiarze N wokół przekątnej, tzn. zamiana elementów tab[i][j] z elementami tab[j][i] (dla i różnego od j).
Zadanie 5.7
Napisać funkcję, która dla dwuwymiarowej tablicy przekazanej jako parametr zwróci numer wiersza o maksymalnej sumie elementów. Jeśli jest kilka wierszy o takiej samej sume elementów, to funkcja ma zwrócić numer ostatniego z nich.
Przykład: dla tablicy o 4 wierszach i 3 kolumnach:
1 5 1
2 3 3
2 2 2
4 3 3
będzie to indeks 3.

6. Funkcje rekurencyjne.
Zadanie 6.1
Napisać funkcję rekurencyjną wypisującą dwójkowe rozwinięcie dodatniej liczby całkowitej danej jako parametr.
Zadanie 6.2
Napisać funkcję rekurencyjną odwracającą napis.
Zadanie 6.3
Korzystając z algorytmu Euklidesa napisać funkcję rekurencyjną obliczającą największy wspólny dzielnik dwóch liczb całkowitych n i m.
Zadanie 6.4
Napisać funkcje rekurencyjną, która sumuje liczby od 1 do n, gdzie n jest dodatnia liczba calkowita przekazywana do funkcji.
Zadanie 6.5
Zaimplementować funkcję rekurencyjną obliczającą n−ty element ciągu zadanego wzorem rekurencyjnym:
p(0) = 0
p(1) = 1
p (k) = p (k − 1) + p (k − 2) + k; dla k >= 2.

7. Typ strukturalny. Operacje na plikach elementowych.
Zadanie 7.1
Napisać funkcję czytającą plik elementowy zawierający koła opisane za pomocą struktury:
struct kolo
{
    double promien, x, y;
};
i zliczającą ile jest kół leżących w całości w drugiej ćwiartce układu współrzędnych.
Zadanie 7.2
Korzystając z pliku z zadania 7.2 napisać funkcję tworzącą plik elementowy zawierający te koła, których pole jest niemniejsze niż zadany parametr.
Zadanie 7.3
Dany jest plik elementowy zawierający dane o studentach w postaci:
struct student
{
    char nazwisko[20], imie[10];
    double srednia;
};
Napisać funkcję, która dla każdego studenta wyliczy wartość stypendium wg algorytmu: średnia>4.0–stypendium w wysokości 200zł, średnia od 4.2 do 4.4-stypednium w wysokości 250 zł, średnia od 4.4 do 4.6-stypednium w wysokości 300 zł, itd. Do pliku wyjściowego zapisze tych studentów, którzy otrzymają stupendium.

8. Pliki tekstowe.
Zadanie 8.1
Napisz fukcję zliczającš ilości wystąpień każdego ze znaków w dokumencie tekstowym o kodach 32-126. Nazwa pliku powinna być przekazana jako parametr funkcji.
Zadanie 8.2
Na podstawie pliku tekstowego liczb całkowitych stworzyć dwa pliki: jeden z elementami parzystymi i drugi z elementami nieparzystymi. Nazwy wszystkich plików powinny być przekazane w parametrach funkcji.
Zadanie 8.3
Dane są dwa pliki tekstowe zawierające macierze liczb rzeczywistych. W pierwszym wierszu każdego pliku znajduje się informacja o ilości wierszy i kolumn macierzy, a następnie w wierszach umieszczone są kolejne wartości. Napisać funkcję mnożącą te dwie macierze i zapisującą wynik do pliku wyjściowego w takiej samej postaci jak czynniki iloczynu. W przypadku, gdy operacji nie da się wykonać w pliku wyjściowym powinna znaleźć się tylko wartość 0. Nazwy wszystkich plików powinny być przekazane w parametrach funkcji.
Zadanie 8.4
Napisać fukcję zamieniającą wszystkie małe litery na wielkie w pliku tekstowym (nazwa pliku przekazana jako paramter funkcji) wybranym przez użytkownika. Funkcja ma zwrócić liczbę dokonanych zamian.
Zadanie 8.5
W pliku tekstowym znajdują się informacje o rachunku z restauracji. Treść składa się zawsze z 3 wierszy. Każdy wiersz zawiera nazwę towaru, dwukropek, cenę w złotych. Nazwa towaru może się składać z dowolnej liczby słów oddzielonych odstępami, a słowa wyłącznie z liter. Napisz funkcję void suma(char *rachunek) obliczający całkowitą należność do zapłaty. Przykładowy plik może wyglądać następująco:
kanapka: 2.50
szarlotka: 1.50
woda mineralna: 1.50
Zadanie 8.6
Plik tekstowy zawiera pewną ilość linii. Napisać funkcję, która do drugiego pliku tekstowego zapisze długości poszczególnych linii, w takiej kolejności w jakiej wystepuja one w pliku wejściowym. Nazwa plików przekazać jako parametr funkcji.

9-11. Typ wskaźnikowy. Wskaźniki do funkcji. Dynamiczne struktury danych. Listy jednokierunkowe.

We wszystkich poniższych zadaniach Wskaźnik na pierwszy element listy przekazujemy jako parametr funkcji.

Zdefiniowane są struktury i typy:
struct lista
{
int liczba;
struct lista *nast;
};
typedef struct lista ELEMENT;
typedef ELEMENT *LISTA;

Zadanie 9.1
Napisać funkcję zwracającą wartość elementu minimalnego na liście.
Zadanie 9.2
Napisać funkcję, która zwraca ilość liczb parzystych na liście
Zadanie 9.3
Napisać funkcję dodającą liczbę na koniec listy (liczbę przekazujemy jako parametr).
Zadanie 9.4
Napisać funkcję usuwająca pierwszy element listy.
Zadanie 9.5
Napisać funkcję usuwającą ostatni element listy.
Zadanie 9.6
Napisać funkcję dodającą element do listy tak aby lista była uporządkowana malejąco. (Zakładamy, że przed dodaniem elementu lista jest uporządkowana)
Zadanie 9.7
Napisać funkcję sortującą listę algorytmem sortowania przez wybór lub przez wstawianie.
Zadanie 9.8
Zdefiniowane są struktury i typy
struct student
{
char imie[15];
char nazwisko[20];
float ps, cw, ep, e;
};
struct lista
{
struct student s;
struct lista *nast;
};
typedef struct lista ELEMENT;
typedef ELEMENT *LISTA;
Pola ps, cw, ep, e w strukturze student oznaczają liczbę punktów uzyskanych przez studenta odpowiednio na pracowni specjalistycznej ćwiczeniach, egzaminie połówkowym i egzaminie końcowym.
Napisać funkcję która do pliku tekstowego "e.txt" zapisze imiona i nazwiska studentów którzy zaliczyli egzamin, do pliku "ps.txt" zapisze studentów którzy zaliczyli pracownie specjalistyczna, a do pliku "cw.txt", tych którzy zaliczyli ćwiczenia. (Każdy student w oddzielnej linii)
Student zaliczył pracownie jeśli uzyskał co najmniej 16 punktów, ćwiczenia jeśli z ćwiczeń uzyskał co najmniej 8 punktów, a egzamin jeśli w sumie ze wszystkich form uzyskał co najmniej 50 punktów.
Zadanie 9.9
Korzystając z danych z zadania 8 napisać funkcję która utworzy 2 listy. Na pierwszej liście maja znaleźć sie studenci, którzy zaliczyli wszystkie formy (ps, cw i egzamin końcowy), na drugiej pozostali studenci.

12-13. Dynamiczne struktury danych. Listy dwukierunkowe.
Zadanie 12.1
Dany jest plik tekstowy, w którym wg poniższego schematu zapisane są informacje o książkach
char autor[128]
char tytul[256]
int rok
int l_stron
Napisać funkcję wczytującą zawartość pliku na listę dwukierunkową w porządku alfabetycznym wg autora. Jeżeli plik zawiera więcej niż jedną książkę danego autora, to powinny one być również posortowane alfabetycznie. Nazwa pliku oraz wskaźnik na początek listy powinny być przekazane jako parametr funkcji.
Zadanie 12.2
Napisać funkcję, która znajdzie najkrótszą książkę autora, którego książek mamy na liście najwięcej.
Zadanie 12.3
Napisać funkcję usuwającą co k-ty element z dwukierunkowej listy cyklicznej, aż zostanie na liście tylko jeden element. Początek listy należy przekazać jako parametr funkcji.
Zadanie 12.4
Napisać funkcję sortującą listę dwukierunkową algorytmem bąbelkowym.
Zadanie 12.5
Zaimplementować algorytmy sortowania bąbelkowego, sortowania przez wybór oraz sortowania przez wstawianie na listach dwukierunkowych.
alg 

Powtórzenie
Zadanie 1
Sporządź schemat blokowy i napisz funkcję, która wyznaczy sumę n elementów ciągu arytmetycznego o wyrazie początkowym równym 1 i zadanej różnicy r.
Zadanie 2
Sporządź schemat blokowy i napisz funkcję, która znajdzie największą liczbę całkowitą n taką, że 1+2+ ... + n < granica.
Zadanie 3
Dana jest struktura
 struct el_listy
{
char symbol[20];
float wysokosc;
struct el_listy *nast, *poprz;
};
W pliku tekstowym znajduje się opis drzew w szkółce leśnej. Każde drzewo opisane jest pewnym symbolem i swoją wysokością. Napisz funkcję, która wczyta na listę informacje o drzewach, a następnie wyznaczy i wypisze na ekranie jaka wysokość drzewa powtarza się najczęściej.
Zadanie 4
Sporządź schemat blokowy i napisz funkcję obliczającą iloczyn skalarny dwóch wektorów, przekazanych jako jej parametry.
Zadanie 5
Dana jest struktura
 struct student
{
char indeks[10];
float oceny[20];
};
Napisz funkcję, która na podstawie pliku elementowego zawierającego informacje o studentach utworzy plik tekstowy, w którym znajdą się numery indeksów tych studentów, którzy uzyskali średnią powyżej zadanego parametru. Nazwy plików należy przekazać w parametrach.
Zadanie 6
Sporządź schemat blokowy i napisz funkcję, która sprawdzi ile razy w jednowymiarowe tablicy liczb występują liczby podzielne przez X (przekazane jako parametr funkcji).
Zadanie 7
Napisz funkcję, która wypisze na ekran tablicę dwuwymiarową wężykiem.
Przykład:
1 3 5 6
2 4 1 9
8 7 5 1
Wynik:
1 3 5 6 9 1 4 2 8 7 5 1
Zadanie 8
Dana jest następująca struktura:
 struct el_listy
{
int l;
struct el_listy *nast;
};
Napisz funkcję, która zwróci tablicę zawierającą tylko parzyste elementy znajdujące się na liście.
Zadanie 9
Dany jest plik tekstowy zawierający słowa. Napisz funkcję, która rozdzieli zawartość tego pliku w taki sposób, że w pliku „a.txt” znajdą się wyrazy zaczynające się na literę a, w „b.txt” na literę b, itd.
Zadanie 10
Dane są dwa pliki tekstowe utworzone wg schematu: w pierwszym wierszu znajduje się liczba całkowita N wskazująca ile liczb znajduje s to te liczby w pliku, kolejne N linii to te liczby. Napisz funkcję, która wczyta zawartości tych plików do tablic a następnie do nowego pliku tekstowego zapisze te liczby, które występują w obydwu tablicach.
Zadanie 11
W pliku elementowym utworzonym za pomocą struktury
struct prostokat
{
double a, b;
};
znajduje się pewna liczba prostokątów. Napisz funkcję, która do pliku tekstowego zapisze pola i obwody wszystkich prostokątów w takiej samej kolejności w jakiej są umieszczone w pliku wejściowym. Nazwy plików należy przekazać w parametrach funkcji.
Zadanie 12
 Napisz funkcję, która wypełni tablicę 2D daną jako parametr losowymi liczbami wg schematu: w pierwszym wierszy tablicy mogą znaleźć się liczby z przedziału [1; 10], w drugim wierszu z przedziału [min pierwszego wiersza; min pierwszego wiersza+10], w trzecim z przedziału [min drugiego wiersza; min drugiego wiersza+10], etc.
Zadanie 13
Dana jest struktura
struct el_listy
{
float a, b; //długości boków prostokąta
struct el_listy *nast;
};
Napisz funkcję zwracającą informację, którym z kolei na liście jest prostokąt o najkrótszym obwodzie. Jeżeli jest kilka prostokątów funkcja powinna zwrócić położenie ostatniego z nich. Początek listy przekaż jako parametr funkcji.
Zadanie 14
Dana jest struktura
struct el_listy
{
float a, b; //długości boków prostokąta
struct el_listy *nast;
};
Napisz funkcję, która wyznaczy średnie pole prostokątów znajdujących się na liście a następnie usunie z listy te, których pole jest mniejsze od średniej.
Zadanie 15
 Sporządź schemat blokowy i napisz program, który po wylosowaniu liczb z przedziału zadanego przez użytkownika do n-elementowej tablicy liczb całkowitych obliczy i wyświetli na ekranie średnią arytmetyczną elementów większych od k (k wczytaj od użytkownika). Wyliczona wartość powinna być poprzedzona informacją jakie liczby brały udział w jej wyznaczaniu. Rozmiar tablicy podaje użytkownik.
Zadanie 16
Dane jest struktury:
struct drzewo
{
char symbol[20];
float wysokosc, obwod;
};
struct el_listy
{
struct drzewo d;
struct el_listy *nast, *poprz;
};
Napisz funkcję, która znajdzie wymiary (wysokość i obwód) drugiego co do wielkości drzewa na liście i zapisze do pliku elementowego symbole tych drzew, które posiadają wyznaczone wymiary.
Zadanie 17
Dana jest następująca struktura:
struct el_listy
{
int l;
struct el_listy *nast, *poprz;
};
Napisz funkcję, która zmodyfikuje istniejącą listę w taki sposób, że element ostatni znajdzie się na jej początku, element przedostatni będzie drugim, itd.
Zadanie 18
Dana jest następująca struktura:
struct el_listy
{
int l;
struct el_listy *nast;
};
Napisz funkcję, która do pliku tekstowego zapisze elementy listy w odwrotnej kolejności niż są umieszczone na liście. Wskaźnik na początek listy oraz nazwę pliku należy przekazać jako parametr.
Zadanie 19
Napisz funkcję, która zwróci największą sumę spośród sum ćwiartek kwadratowej tablicy dwuwymiarowej.

14. Kolokwium.
15. Kolokwium poprawkowe.