From e1ca97ded1258fea7c5cef33b35a318c72b41836 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= Date: Fri, 27 Jan 2023 15:55:37 +0100 Subject: =?UTF-8?q?rtk=20=C5=A1olsko=202023?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- "inf/rtk\305\241/1.c" | 46 +++++++++++++++++++++++++++++++++++++++ "inf/rtk\305\241/2.c" | 58 +++++++++++++++++++++++++++++++++++++++++++++++++ "inf/rtk\305\241/3.txt" | 17 +++++++++++++++ "inf/rtk\305\241/4.c" | 33 ++++++++++++++++++++++++++++ "inf/rtk\305\241/5.txt" | 25 +++++++++++++++++++++ 5 files changed, 179 insertions(+) create mode 100644 "inf/rtk\305\241/1.c" create mode 100644 "inf/rtk\305\241/2.c" create mode 100644 "inf/rtk\305\241/3.txt" create mode 100644 "inf/rtk\305\241/4.c" create mode 100644 "inf/rtk\305\241/5.txt" (limited to 'inf') diff --git "a/inf/rtk\305\241/1.c" "b/inf/rtk\305\241/1.c" new file mode 100644 index 0000000..8b97d69 --- /dev/null +++ "b/inf/rtk\305\241/1.c" @@ -0,0 +1,46 @@ +#include +enum stanje { + nedefinirano, + cikcakast, + necikcakast_isti, + necikcakast_1, + necikcakast_2 +}; +enum stanje preveri (const char * n) { + int prevl = -1; + int prevprevl = -1; + int l = 1; + char c = *n++; + if (!c) + return nedefinirano; + while (1) { + if (*n != c) { + fprintf(stderr, "*n je %c, c je %c\n", *n, c); + if (l == prevl) + return necikcakast_isti; + if (prevprevl != -1 && prevl != -1) { + if (prevprevl < prevl) + if (l > prevl) + return necikcakast_1; + if (prevprevl > prevl) + if (l < prevl) + return necikcakast_2; + } + prevprevl = prevl; + prevl = l; + l = 1; + c = *n; + if (!*n) + return cikcakast; + n++; + } else { + l++; + n++; + } + } +} +int main (int argc, char ** argv) { + if (argc == 2) + return preveri(argv[1]); + return 255; +} diff --git "a/inf/rtk\305\241/2.c" "b/inf/rtk\305\241/2.c" new file mode 100644 index 0000000..63f0953 --- /dev/null +++ "b/inf/rtk\305\241/2.c" @@ -0,0 +1,58 @@ +#include +#include +#include +#define MIN(a,b) ((a) > (b) ? (b) : (a)) +#define MAX(a,b) ((a) < (b) ? (b) : (a)) +struct stolpec { + int položaj; + int višina; + int izmeril; +}; +int primerjaj_stolpca (const void * a, const void * b) { + const struct stolpec * c = (const struct stolpec *) a; + const struct stolpec * d = (const struct stolpec *) b; + return d->višina - c->višina; +} +void natisni (int n, const struct stolpec * s) { + for (int i = 0; i < n; i++) { + printf("%d: ", s[i].položaj); + for (int j = 0; j < s[i].višina; j++) + printf("@"); + printf("\n"); + } +} +int voda (int n, struct stolpec * s) { + struct stolpec razv[n]; + memcpy(razv, s, n*sizeof *s); + qsort(razv, n, sizeof *s, primerjaj_stolpca); + natisni(n, s); + printf("---------\n"); + natisni(n, razv); + int povr = 0; + for (int i = 0; i < n-1; i++) { + int max_pol = MAX(razv[i].položaj, razv[i+1].položaj); + int min_pol = MIN(razv[i].položaj, razv[i+1].položaj); + if (max_pol - min_pol > 1) { + printf("med stoplcema z indeksoma %d in %d\n", min_pol, max_pol); + for (int j = min_pol+1; j < max_pol; j++) { + if (s[j].izmeril) + continue; + int tapovr = razv[i+1].višina - s[j].višina; + if (tapovr > 0) + povr += tapovr; + s[j].izmeril++; + printf("izmeril stoplec indeks %d - povr je %d ... min_viš je %d, s[j].višina je %d\n", j, povr, razv[i+1].višina, s[j].višina); + } + } + } + return povr; +} +int main (int argc, char ** argv) { + int n = argc-1; + struct stolpec * stolpci = calloc(n, sizeof *stolpci); + for (int i = 0; i < n; i++) { + stolpci[i].položaj = i; + stolpci[i].višina = atoi(argv[i+1]); + } + return voda(n, stolpci); +} diff --git "a/inf/rtk\305\241/3.txt" "b/inf/rtk\305\241/3.txt" new file mode 100644 index 0000000..0800780 --- /dev/null +++ "b/inf/rtk\305\241/3.txt" @@ -0,0 +1,17 @@ +Inicializacija: + Vsem urnim komponentam časa, torej h_i, odštejemo 7 in čase spremenimo v skalarje - sekunde: č_i := h_i*3600+m_i*60. + Nato seznam č uredimo po velikosti od najmanjšega do največjega. + Izdelamo seznam testirnih točk, ki je vedno urejen po velikosti, recimo binarno drevo. + Vrednost vsake točke je čas konca zadnjega testiranja. Najprej imamo eno točko s časom 0 - čas je v formatu sekund od 7:00, kot urejeni seznam č. +Zanka po urejenem seznamu časov ljudi z lokalno spremenljivko č_i: + Zanka po časih zadnjega testiranja testirnih točk z lokalno sprem. t_j: + Če je t_j+T manjše ali enako od č_i, kjer je T čas enega testiranja v sekundah: + Spremenimo t_j na t_j+T in poskrbimo, da je podatkovna struktura t spet urejena ter nato nadaljujemo z naslednjim časom testiranca. + Konec zanke časov testirancev, ampak nismo nadaljevali z naslednjim testirancem, torej ustrezne testirnice nismo našli: + Dodamo novo testirnico v t, ki nosi vrednost T. +Konec zanke časov testirancev: + Število testirnic je enako številu elementov v podatkovni strukturi t, vsak element nosi vrednost, kdaj se testirnica zapre. Vse testirnice neprestano obravnavajo testirance. + +Razlaga: + Najprej smo našli testirnice za osebe, ki se jim najbolj mudi; imajo najmanjši č. + Novo testirnico izdelamo le, če ima ota oseba tak č_o, da ima vsaka obstoječa testirnica večji t_i+T kot č_o. diff --git "a/inf/rtk\305\241/4.c" "b/inf/rtk\305\241/4.c" new file mode 100644 index 0000000..cff67ca --- /dev/null +++ "b/inf/rtk\305\241/4.c" @@ -0,0 +1,33 @@ +#include +#include +#define MIN(a,b) ((a)>(b)?(b):(a)) +int palind (const char * c) { + int p = 0; + int l = strlen(c); + for (int i = 0; i < l; i++) { + if (c[i] == c[i+1]) { + printf("sodi\n"); + p++; + for (int j = 1; j <= MIN(i, l-i-2); j++) + if (c[i-j] == c[i+1+j]) { + printf("nadaljevanje\n"); + p++; + } + } + if (i && c[i-1] == c[i+1]) { + p++; + printf("lihi\n"); + for (int j = 2; j < MIN(i, l-i-1); j++) + if (c[i-j] == c[i+j]) { + printf("nadaljevanje\n"); + p++; + } + } + } + return p; +} +int main (int argc, char ** argv) { + if (argc != 1+1) + return 255; + return palind(argv[1]); +} diff --git "a/inf/rtk\305\241/5.txt" "b/inf/rtk\305\241/5.txt" new file mode 100644 index 0000000..ed9ac28 --- /dev/null +++ "b/inf/rtk\305\241/5.txt" @@ -0,0 +1,25 @@ +Inicializacija: + Omrežje jam si predstavljamo kot graf, predstavljen v 2D tabeli enobitnih podatkov (drži=1/ne drži=0) --- omrežje[i][j]. Ta tabela je velikosti n*n, omrežje[i][j] v tej tabeli pa pove, da je med jamama i in j prehod. Začnemo s tabelo, polno ničel. + Tabelo jamskega omrežja izpolnimo z zanko z lokalno spremenljivko i, ki gre od 0 do m: + omrežje[a[i]][b[i]] := 1 in omrežje[b[i]][a[i]] := 1 + Nastavimo tudi 1D tabelo obiskanih jam dolžine n, torej obiskane[n]. Inicializiramo ga na 0, prav tako vsebuje dvojiške podatke v celicah. + obiskane[s] := 1 + Definiramo podprogram išči(referenca na omrežje, referenca na obisakane), ki na koncu vrne skalarno stanje iskanja izmed neuspel, novo ali cilj. Postopek podprograma: + stanje := neuspel + Zanka od 1 do n z lokalno spremenljivko obiskana: + Če drži obiskane[obiskana]: + Zanka od 1 do n z lokalno spremenljivko nova: + Če drži bodisi omrežje[jama][nova] bodisi omrežje[nova][jama]: + obiskane[nova] := 1 + stanje := novo + Če c[obiskana] != -1: + omrežje[c[obiskana]][d[obiskana]] := 1 + omrežje[d[obiskana]][c[obiskana]] := 1 + stanje := novo + Če je obiskana enako t: + stanje := cilj +Neskončna zanka: + Dokler funkcija išči vrača novo, jo neprestano kličemo, s čimer odpremo vse možne skrinje in pogledamo po omrežjem grafu vse možne jame, če so slučajno ciljne in dostopne. Ko funkcija ne vrne novo, je ali našla t (stanje == cilj), kar pomeni, da je pot mogoča, ali pa ne dostopala do nobenih novih jam ali odprla nobenih novih skrinj, kar pomeni, da se bo isto zgodilo v naslednjem potencialnem ciklu, zato iskanje prekinemo, saj pot od s do t ni možna. + +Prostorska zahtevnost je polinomska s številom jam --- S(n^2). Teoretično manj, ker lahko hranimo le tabelo velikosti n*n/2 trikotniške oblike. +Časovna zahtevnost je v najslabšem primeru O(n*globina), kjer je globina število prehodov od s do najbolj oddaljene jame, ko so vse dosegljive skrinje že odprte, in v najboljšem O(n), ko je s enak t. -- cgit v1.2.3