Zadanie 1
int is_permutation(int array[], int size) {
for (int i = 0; i < size; i++) { // dla każdej liczby od 0 do size-1 sprawdzamy, czy jest w naszej tablicy
int found = 0; // na początku nie wiemy, czy dana liczba `i` jest w tablicy, stąd początkowa wartość 0 (false)
for (int j = 0; j < size; j++) { // przechodzimy po tablicy w poszukiwaniu liczby `i`
if (array[j] == i) { // jesli znaleźliśmy liczbę `i`, to zapisujemy tą informację
found = 1;
}
}
if (!found) { // jesli nie znaleźliśmy liczby `i`, to wiemy, że w tablicy nie ma poprawnej permutacji
return 0; // w takimy wypadku możemy od razu zwrócić 0 (false)
}
}
// w naszej tablicy znaleźliśmy wszystkie liczby od 0 do size-1, a sama tablica ma rozmiar size, czyli wiemy, że jest to poprawna permutacja
return 1; // możemy zatem zwrócić 1 (true)
}
void compose_permutation(int a[], int b[], int result[], int size) {
for (int i = 0; i < size; i++) {
result[i] = b[a[i]];
}
}Zadanie 2
#include <stdio.h>
#define MAX_ARRAY_SIZE 1000
int scan_number() {
int x;
scanf("%d", &x);
return x;
}
void print(int x) {
printf("%d\n", x);
}
void swap(int tab[], int i, int j) {
int tmp = tab[i];
tab[i] = tab[j];
tab[j] = tmp;
}
void sort(int array[], int size) {
for (int i = 0; i < size; i++) {
int current_candidate = i;
for (int j = i + 1; j < size; j++) {
if (array[current_candidate] > array[j]) {
current_candidate = j;
}
}
if (current_candidate != i) {
swap(array, i, current_candidate);
}
}
}
void sorting() {
int array[MAX_ARRAY_SIZE]; // wiemy, że będziemy mieli co najwyżej 1000 elementów do posortowania, dlatego możemy zaalokować tak dużą tablicę od razu
int x = scan_number(); // wczytujemy `x`
for (int i = 0; i < x; i++) { // wczytujemy jedynie `x` liczb do tablicy, być może nie wypełnimy całej, ale to nie jest problem
array[i] = scan_number();
}
sort(array, x); // sortujemy tablicę o długości `x`
for (int i = 0; i < x; i++) { // wypisujemy posortowane liczby
print(array[i]);
}
}
int main() {
sorting();
return 0;
}Zadanie 3
/*
* To jest zmodyfikowana funkcja sprawdzająca, czy w tablicy `array` między indeksami `begin` oraz `end` znajduje się palindrom
*/
int is_palindrome(char array[], int begin, int end) {
int length = end - begin; // długość napisu
for (int i = 0; i < length / 2; i++) {
if (array[begin + i] != array[end - i - 1]) {
return 0;
}
}
return 1;
}
int is_double_palindrome(char t[], int size) {
for (int i = 1; i < size; i++) { // sprawdzamy każdy możliwy punkt podziału napisu na dwa potencjalne palindromy
if (is_palindrome(t, 0, i) && is_palindrome(t, i, size)) {
return 1;
}
}
return 0;
}Zadanie 4
Poprawiony kod:
#include <stdio.h>
void tree_leaves(int n) {
/*
* liście mają n poziomów, czyli używamy pętli, której jeden obrót narysuje jeden poziom
* tutaj możemy iterować się i=0, 1, 2, ..., n-1 albo i=1, 2, 3, ..., n - nie ma to dużego znaczenia, ja akurat wybrałem pierwszą opcję
* przyjrzyjmy się dwóm najistotniejszym z naszego punktu widzenia obrotom pętli - pierwszemu i ostatniemu
* pierwszy obrót musi wypisać X spacji i 1 gwiazdkę, a ostatni obrót ma wypisać 0 spacji i Y gwiazdek
* najpierw liczba gwiazdek - każdy kolejmy poziom ma dwie gwiazdki więcej niż poprzedni, a pierwszy poziom ma 1 gwiazdkę
* skoro na pierwszym poziomie `i=0`, to mamy proste równanie opisujące liczbę gwiazdek na i-tym poziomie - `2 * i + 1`
* teraz spacje - wiemy, że na ostatnim poziomie `i=n-1` mamy `2 * n - 1` gwiazdek, i to jest szerokość obrazka
* szerokość obrazka na pierszym poziomie musi wynosić X + 1 + X (spacje z lewej, 1 gwiazdka i spacje z prawej)
* dostajemy więc `2 * X + 1 = 2 * n - 1` => `X = (2 * n - 2) / 2 = n - 1` - czyli na pierwszym poziomie musi być `n - 1` spacji z lewej strony
* na drugim poziomie ostatnia spacja z lewej jest zastępowana przez gwiazdkę, czyli możemy zgadnąć wzór na liczbę spacji: `n - 1 - i`
*/
for (int i = 0; i < n; i++) { // poprzednim warunkiem pętli było `i <= n`, ale to powodowało że i=0, 1, 2, ..., n - czyli rysowaliśmy n+1 poziomów
for (int j = 0; j < n - i - 1; j++) { // wypisujemy `n - 1 - i` spacji
printf(" ");
}
for (int j = 0; j < 2 * i + 1; j++) { // wypisujemy `2 * i + 1` gwiazdek
printf("*");
}
printf("\n"); // nie musimy pisać spacji z prawej strony, bo ich i tak nie widać - zatem przechodzimy do kolejnej linii
}
}
void tree_trunk(int n) {
/*
* pień ma 3 poziomy, z których każdy będzie identyczny - najpierw X spacji, a potem 3 gwiazki
* żeby policzyć, ile tych spacji musimy wypisać, można się przyjrzeć na najszerszy poziom liści
* i-ty (licząc od i = 0) poziom liści ma szerokość `2 * i + 1`, zatem najszerszy ma szerokość `2 * (n - 1) + 1 = 2 * n - 1`
* wiemy, że szerokość całej linii to X + 3 + X, bo odstęp pnia do lewej i do prawej krawędzi musi być identyczny
* dostajemy `2 * n - 1 = 2 * X + 3`, czyli `X = (2 * n - 4) / 2 = n - 2`
*/
for (int i = 0; i < 3; i++) { // pień ma wysokość 3, więc każdy obrót pętli rysuje jeden wiersz - a mamy 3 obroty pętli
for (int j = 0; j < n - 2; j++) { // rysujemy spacje z lewej strony, tych spacji musi być X, czyli `n - 2`
printf(" ");
}
printf("***\n"); // tutaj brakowało przejścia do nowej linii, czyli wypisania `\n`
}
}
void tree(int n) {
if (n < 3)
return; // to jest poprawne, nie chcemy rysowac choinek o wysokosci mniejszej niż 3
tree_leaves(n);
tree_trunk(n);
}
int main() {
int n;
printf("Podaj wysokosc choinki: ");
scanf("%d", &n);
tree(n);
return 0;
}Rysowanie ramki:
#include <stdio.h>
void tree_leaves(int n) {
for (int i = 0; i < n; i++) {
printf("|"); // każdy wiersz liści zaczynamy ramką z lewej strony
for (int j = 0; j < n - i - 1; j++) {
printf(" ");
}
for (int j = 0; j < 2 * i + 1; j++) {
printf("*");
}
for (int j = 0; j < n - i - 1; j++) { // wypisujemy tyle samo spacji z prawej strony liści, co z lewej
printf(" ");
}
printf("|\n"); // teraz wypisujemy ramkę tego wiersza z prawej strony i przechodzimy do nowej linii
}
}
void tree_trunk(int n) {
for (int i = 0; i < 3; i++) {
printf("|"); // każdy wiersz pnia zaczynamy ramką z lewej strony
for (int j = 0; j < n - 2; j++) {
printf(" ");
}
printf("***"); // teraz jeszcze nie możemy przejść do nowej linii
for (int j = 0; j < n - 2; j++) { // wypisujemy tyle samo spacji z prawej strony pnia, co z lewej
printf(" ");
}
printf("|\n"); // teraz wypisujemy ramkę tego wiersza z prawej strony i przechodzimy do nowej linii
}
}
void frame_horizontal(int n) { // mamy jedną funkcję rysującą górę i dół ramki
/*
* szerokość ramki to szerokość najszerszego rzędu liści plus 2 (bo musi też obejmować pionową ramkę z lewej i z prawej strony)
* zatem musimy wypisać `(2 * n - 1) + 2 = 2 * n + 1` znaków, a potem przejść do nowej linii
*/
for (int i = 0; i < 2 * n + 1; i++) {
printf("-");
}
printf("\n");
}
void tree(int n) {
if (n < 3)
return; // to jest poprawne, nie chcemy rysowac choinek o wysokosci mniejszej niż 3
frame_horizontal(n); // zaczynamy obrazek od ramki górnej
tree_leaves(n);
tree_trunk(n);
frame_horizontal(n); // kończymy obrazek ramką dolną
}
int main() {
int n;
printf("Podaj wysokosc choinki: ");
scanf("%d", &n);
tree(n);
return 0;
}Zadanie 5
Rozwiązanie jest dostępne tutaj. Brakuje tam części obliczeń, a niektóre zwroty są wskazówkami dla Was a nie częścią dowodu, dlatego traktujcie to raczej jako szkic.
Zadanie 6
double triangle_area(double triangle[]) {
double area = (triangle[2] - triangle[0]) * (triangle[5] - triangle[1]) - (triangle[3] - triangle[1]) * (triangle[4] - triangle[0]);
if (area < 0.0)
area = -area;
return area / 2.0;
}Zadanie 7
Niech n będzie liczbą elementów w słowniku (czyli n=dict_fill).
dict_init- rząd złożonościO(1)- stały. Niezależnie oddict_fill, wykonujemy stałą liczbę operacji.dict_contains- rząd złożonościO(n)- liniowy. W pesymistycznym przypadku przeszukujemy całą tablicę o długościdict_fill.dict_add- rząd złożonościO(n)- liniowy. Wykonujemydict_containso złożonościO(n)plus stałą liczbę operacji.dict_get- rząd złożonościO(n)- liniowy. W pesymistycznym przypadku przeszukujemy całą tablicę o długościdict_fill.dict_remove- rząd złożonościO(n)- liniowy. W pesymistycznym przypadku przeszukujemy całą tablicę o długościdict_filla potem wykonujemy stałą liczbę operacji.
Zadanie 8
9 10 12 4 5 11 8 2 1 3 6 7 13
9 10 12 4 5 13 8 2 1 3 6 7 11
9 10 12 4 6 13 8 2 1 3 5 7 11
9 10 13 4 6 12 8 2 1 3 5 7 11
13 10 9 4 6 12 8 2 1 3 5 7 11
13 10 12 4 6 9 8 2 1 3 5 7 11
13 10 12 4 6 11 8 2 1 3 5 7 9
// teraz mamy poprawny kopiec
9 10 12 4 6 11 8 2 1 3 5 7 13
12 10 9 4 6 11 8 2 1 3 5 7 13
12 10 11 4 6 9 8 2 1 3 5 7 13
7 10 11 4 6 9 8 2 1 3 5 12
11 10 7 4 6 9 8 2 1 3 5 12
11 10 9 4 6 7 8 2 1 3 5 12
5 10 9 4 6 7 8 2 1 3 11
10 5 9 4 6 7 8 2 1 3 11
10 6 9 4 5 7 8 2 1 3 11
3 6 9 4 5 7 8 2 1 10
9 6 3 4 5 7 8 2 1 10
9 6 8 4 5 7 3 2 1 10
1 6 8 4 5 7 3 2 9
8 6 1 4 5 7 3 2 9
8 6 7 4 5 1 3 2 9
2 6 7 4 5 1 3 8
7 6 2 4 5 1 3 8
7 6 3 4 5 1 2 8
2 6 3 4 5 1 7
6 2 3 4 5 1 7
6 5 3 4 2 1 7
1 5 3 4 2 6
5 1 3 4 2 6
5 4 3 1 2 6
2 4 3 1 5
4 2 3 1 5
1 2 3 4
3 2 1 4
1 2 3
2 1 3
1 2Zadanie 9
void merge_two_sorted_arrays(int tab[], int dest[], int size, int middle) {
int i = 0, j = middle, k = 0;
while (i < middle && j < size) {
if (tab[i] <= tab[j]) {
dest[k] = tab[i];
k++;
i++;
} else {
dest[k] = tab[j];
k++;
j++;
}
}
while (i < middle) {
dest[k] = tab[i];
k++;
i++;
}
while (j < size) {
dest[k] = tab[j];
k++;
j++;
}
}Projekt zaliczeniowy
#include <stdio.h>
#define MAX_DATA_SIZE 1000
#define MAX_BUCKETS_COUNT 100
int read_number() {
int x;
scanf("%d", &x);
return x;
}
int main() {
int numbers[MAX_DATA_SIZE];
int buckets[MAX_BUCKETS_COUNT];
int size = read_number();
int number_of_buckets = read_number();
for (int i = 0; i < number_of_buckets; i++)
buckets[i] = 0;
for (int i = 0; i < size; i++) {
numbers[i] = read_number();
}
int min = numbers[0], max = numbers[0];
for (int i = 1; i < size; i++) {
if (numbers[i] < min)
min = numbers[i];
if (numbers[i] > max)
max = numbers[i];
}
int bucket_width = (max - min + 1) / number_of_buckets;
for (int i = 0; i < size; i++) {
int x = numbers[i];
buckets[(x - min) / bucket_width]++;
}
for (int i = 0; i < number_of_buckets; i++) {
printf("bucket %d: [%d, %d], count: %d\n", i, min + i * bucket_width, min + (i + 1) * bucket_width - 1,
buckets[i]);
}
return 0;
}