summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--inf/rtkš/1.c46
-rw-r--r--inf/rtkš/2.c58
-rw-r--r--inf/rtkš/3.txt17
-rw-r--r--inf/rtkš/4.c33
-rw-r--r--inf/rtkš/5.txt25
5 files changed, 179 insertions, 0 deletions
diff --git a/inf/rtkš/1.c b/inf/rtkš/1.c
new file mode 100644
index 0000000..8b97d69
--- /dev/null
+++ b/inf/rtkš/1.c
@@ -0,0 +1,46 @@
+#include <stdio.h>
+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š/2.c b/inf/rtkš/2.c
new file mode 100644
index 0000000..63f0953
--- /dev/null
+++ b/inf/rtkš/2.c
@@ -0,0 +1,58 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#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š/3.txt b/inf/rtkš/3.txt
new file mode 100644
index 0000000..0800780
--- /dev/null
+++ b/inf/rtkš/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š/4.c b/inf/rtkš/4.c
new file mode 100644
index 0000000..cff67ca
--- /dev/null
+++ b/inf/rtkš/4.c
@@ -0,0 +1,33 @@
+#include <string.h>
+#include <stdio.h>
+#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š/5.txt b/inf/rtkš/5.txt
new file mode 100644
index 0000000..ed9ac28
--- /dev/null
+++ b/inf/rtkš/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.
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-02 08:06:17 +0100