summaryrefslogtreecommitdiffstats
path: root/inf/rtk/šolsko
diff options
context:
space:
mode:
Diffstat (limited to '')
-rwxr-xr-xinf/rtk/šolsko/1bin0 -> 18120 bytes
-rw-r--r--inf/rtk/šolsko/1.c24
-rw-r--r--inf/rtk/šolsko/1.txt6
-rwxr-xr-xinf/rtk/šolsko/2bin0 -> 18196 bytes
-rw-r--r--inf/rtk/šolsko/2.c30
-rw-r--r--inf/rtk/šolsko/2.txt5
-rwxr-xr-xinf/rtk/šolsko/3bin0 -> 19740 bytes
-rw-r--r--inf/rtk/šolsko/3.c106
-rw-r--r--inf/rtk/šolsko/3.txt4
-rw-r--r--inf/rtk/šolsko/4.c27
-rw-r--r--inf/rtk/šolsko/5.c22
-rw-r--r--inf/rtk/šolsko/Makefile15
12 files changed, 239 insertions, 0 deletions
diff --git a/inf/rtk/šolsko/1 b/inf/rtk/šolsko/1
new file mode 100755
index 0000000..e8daf5b
--- /dev/null
+++ b/inf/rtk/šolsko/1
Binary files differ
diff --git a/inf/rtk/šolsko/1.c b/inf/rtk/šolsko/1.c
new file mode 100644
index 0000000..f93eb94
--- /dev/null
+++ b/inf/rtk/šolsko/1.c
@@ -0,0 +1,24 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+int main (void) {
+ char buf[1024];
+ double z = 0;
+ fgets(buf, 1024, stdin); /* prva vrstica ni potrebna */
+ fgets(buf, 1024, stdin);
+ while (!feof(stdin)) { /* gremo čez vsako vrstico */
+ int i = 0; /* indeks */
+ int m = 1; /* trenutni imenovalec */
+ do {
+ m *= 2; /* povečamo trenutni imenovalec */
+ if (buf[i] == 'S') {
+ z += 1 / (double) m; /* povečamo za trenutno velikost kosa */
+ /* fprintf(stderr, "sadi, %d, %f\n", m, z); */
+ }
+ i++;
+ } while (buf[i-1] != '\n' && buf[i-1] != 0 && buf[i-1] != '\r'); /* konec vhoda */
+ fgets(buf, 1024, stdin); /* poberemo novo vrstico */
+ }
+ printf("%d\n", (int) ceil(z)); /* izpišemo vrednost, zaokroženo navzgor */
+ return 0; /* končamo program */
+}
diff --git a/inf/rtk/šolsko/1.txt b/inf/rtk/šolsko/1.txt
new file mode 100644
index 0000000..6a912d3
--- /dev/null
+++ b/inf/rtk/šolsko/1.txt
@@ -0,0 +1,6 @@
+5 4
+SJSJ
+SSJJ
+JSJJ
+JJJJ
+JJSJ
diff --git a/inf/rtk/šolsko/2 b/inf/rtk/šolsko/2
new file mode 100755
index 0000000..58228cb
--- /dev/null
+++ b/inf/rtk/šolsko/2
Binary files differ
diff --git a/inf/rtk/šolsko/2.c b/inf/rtk/šolsko/2.c
new file mode 100644
index 0000000..3c7f97d
--- /dev/null
+++ b/inf/rtk/šolsko/2.c
@@ -0,0 +1,30 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+int main (int argc, char ** argv) { /* vzorec je prvi argument, slovar je standardni vhod */
+ if (argc != 2) {
+ fprintf(stderr, "uporaba: %s vzorec < slovar.txt\n", argv[0] ? argv[0] : "pwnkit");
+ return 1; /* slovar so besede v cevovodu, ločene z novo vrstico tipa POSIX */
+ }
+ int l = strlen(argv[1]); /* dolžina vzorca, daljše besede avtomatsko izključimo */
+ char * buf = alloca(l+2); /* prostor za vrstico vnosa slovarja */
+#define NASLEDNJI() while (!fgets(buf, l+2, stdin) && !feof(stdin)) /* predolgi grejo takoj stran */
+ NASLEDNJI();
+ while (!feof(stdin)) { /* beremo vsako besedo slovarja */
+ for (int i = 0; 1; i++) { /* gremo čez vsak znak besede iz slovarja in znak vzorca */
+ if (buf[i] == '\n' && !argv[1][i]) { /* če je hkrati konec besede & vzorca */
+ printf("%s", buf); /* itak je nova vrstica že v buf */
+ break; /* natisnemo besedo in gremo na naslednjo besedo */
+ }
+ if (buf[i] == '\n' || (buf[i] != argv[1][i] && argv[1][i] != '*'))
+ break; /* če je konec besede in ni konec vzorca ali obratno */
+ } /* potem ne izpišemo */
+ NASLEDNJI();
+ }
+ return 0; /* končamo program */
+}
+
+/*
+podprimer b:
+Vse besede bi shranili v delovni pomnilnik v drevesno strukturo s primerjalno funkcijo strcmp, vendar bi imeli za vsako dolžino besede svojo drevesno strukturo. Z drevesno strukturo smo olajšali kompleksnost iskanja besed, kjer je pri vzorcu na začetku veliko določenih znakov in ne zvezdic. Ko pri vzorcu pridemo do prve zvezdice, bo itak treba iskati po vsej veji v drevesu. Dodajanje dreves še od zadaj naprej bi samo povečalo spominsko zahtevnost. S ločevanjem po dolžini nizov pa smo zmanjšali kompleksnost, ko vzorec blizu začetka če vsebuje zvezdico a ni iste dolžine (takoj bo zavrnjen, če te dolžine v slovarju ni in zmanjša iskalno polje), nismo pa bistveno vplivali na spominsko zahtevnost.
+*/
diff --git a/inf/rtk/šolsko/2.txt b/inf/rtk/šolsko/2.txt
new file mode 100644
index 0000000..d35a736
--- /dev/null
+++ b/inf/rtk/šolsko/2.txt
@@ -0,0 +1,5 @@
+miza
+zima
+riba
+mirta
+prva
diff --git a/inf/rtk/šolsko/3 b/inf/rtk/šolsko/3
new file mode 100755
index 0000000..5756a55
--- /dev/null
+++ b/inf/rtk/šolsko/3
Binary files differ
diff --git a/inf/rtk/šolsko/3.c b/inf/rtk/šolsko/3.c
new file mode 100644
index 0000000..041c723
--- /dev/null
+++ b/inf/rtk/šolsko/3.c
@@ -0,0 +1,106 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <sys/mman.h>
+
+/*
+opisno:
+
+Zmanjkalo mi je časa, zato pišem odgovor opisno, kar bi moralo biti v redu, ker bi predvsem implementacija branja podatkov porabila veliko časa pisanja programa.
+
+Torej. Preberemo podatke iz datoteke iz datoteke, kjer so vrstice ločene z novo vrstico in stolpci s presledkom v tabelo z vrednostjo.
+
+Potem v zanki gremo čez vsako vrstico in v tej zanki čez vsak stolpec - vsako polje in si izpišemo za vsak zaporeden niz polij, ki imajo vrednost, večjo od 1, celotno vrstico (glej struct linija), vrednost, začetek in konec linije in usmerjenost (glej enum usmerjenost).
+
+Potem gremo v zanki čez vsak stolpec in gledamo kot pri prejšnjem odstavku od zgoraj navzdol in si v enakem formatu, le da usmerjenost nastavimo na NAVPIČNO, zapisujemo linije z vrednostjo, večjo od 0.
+
+Pri prejšnjih dveh odstavkih tudi iščemo vrstico z linijo z največjo vrednostjo in shranimo X in Y koordinate najmanj vrednega polja (trivialno ga je najti in te koordinate zapisati v dve spremenljivki). Tukaj vrednosti enkrat odštejemo vrednost najmanj vrednega polja, saj tja postavimo žeton in se ne šteje. To odšteto vrednost pa zapišemo v spremenljivko makskalkvred, saj bomo z njo primerjali skupne vrednosi parov.
+
+Sedaj imamo vse vodoravne in navpične linije v dveh preglednih enodimenzionalnih tabelah (struct linija * linijev in struct linija * linije h). Za vsako vodoravno gremo v zanki čez seznam navpičnih in pogledamo, če se ti dve (navpična in vodoravna) liniji sekata. Sekata se, če je pozicija vodoravne linije med začetkom in koncem (vključno z začetkom in koncem). Sedaj pogledamo, ali je seštevek njunih vrednosti, potem ko mu dvakrat odštejemo vrednost polja, kjer se liniji sekata (ker tja postavimo žeton - dvakrat pa zato, kjer je to polje prisotno v obeh linijah), večji od največjega prejšnjega seštevka v spremenljivki makskalkvred, če je, zapišemo to izračunano vrednost v spremenljivko makskalkvred in X in Y koordinate polja, kjer se ti dve liniji sekata. Ena koordinata tega polja je torej pozicija navpične linije, druga pa pozicija vodoravne.
+
+Ko smo šli čez vse pare linij pa na standardni izhod izpišemo spremenljivki obeh koordinat in zaključimo program.
+
+*/
+
+struct linija {
+ int začetek;
+ int konec;
+ int pozicija;
+ int vrednost;
+};
+int main (int argc, char ** argv) {
+ if (argc != 2) {
+ fprintf(stderr, "uporaba: %s polje.txt\n", argv[0] ? argv[0] : "pwnkit");
+ return 1;
+ }
+ int fd;
+ if ((fd = open(argv[1], O_RDONLY)) == -1) {
+ perror("open");
+ return 2;
+ }
+ struct stat statbuf;
+ if (fstat(fd, &statbuf) == -1) {
+ perror("fstat");
+ return 3;
+ }
+ char * vhod;
+ if ((vhod = mmap(NULL, statbuf.st_size, PROT_READ, MAP_SHARED, fd, 0)) == MAP_FAILED) {
+ perror("mmap");
+ return 4;
+ }
+ struct linija * linijev = NULL;
+ struct linija * linijen = NULL;
+ int linijv = 0;
+ int linijn = 0;
+ int * dolžine = NULL;
+ int ** vrstice = NULL;
+ int vrstic = 0;
+ int r = 0;
+ char * c = vhod;
+ int maksdolžina = 0;
+ do {
+ vrstice = realloc(vrstice, sizeof(*vrstice)*++vrstic);
+ dolžine = realloc(dolžine, sizeof(*dolžine)*vrstic);
+ vrstice[vrstic-1] = NULL;
+ dolžine[vrstic-1] = 0;
+ do {
+ vrstice[vrstic-1] = realloc(vrstice[vrstic-1], sizeof(*vrstice[vrstic-1])*++dolžine[vrstic-1]);
+ vrstice[vrstic-1][dolžine[vrstic-1]-1] = strtol(c, &c, 10);
+ } while (*c != '\n');
+ if (dolžine[vrstic-1] > maksdolžina)
+ maksdolžina = dolžine[vrstic-1];
+ } while (c+1 < vhod+statbuf.st_size && *c);
+ for (int i = 0; i < vrstic; i++) {
+ struct linija vrstica = {
+ .začetek = 0,
+ .konec = 0,
+ .pozicija = i,
+ .vrednost = 0
+ };
+ for (int j = 0; j < dolžine[i]; j++) {
+ if (vrstica.vrednost == 0) {
+ vrstica.začetek = j;
+ }
+ if (vrstice[i][j] == 0 && vrstica.vrednost) {
+ vrstica.konec = j;
+ linijev = realloc(linijev, sizeof(*linijev)*linijv++);
+ memcpy(linijev[linijv-1], &linija, sizeof(linija));
+ vrstica.vrednost = 0;
+ }
+ vrstica.vrednost += vrstice[i][j];
+ fprintf(stderr, "%d ", vrstice[i][j]);
+ }
+ fprintf(stderr, "\n");
+ }
+ for (int j = 0; j < maksdolžina; j++) {
+ for (int i = 0; i < vrstic; i++) {
+ //
+ }
+ }
+r:
+ munmap(vhod, statbuf.st_size);
+ return r;
+}
diff --git a/inf/rtk/šolsko/3.txt b/inf/rtk/šolsko/3.txt
new file mode 100644
index 0000000..79f4236
--- /dev/null
+++ b/inf/rtk/šolsko/3.txt
@@ -0,0 +1,4 @@
+0 0 1 2 0
+0 2 3 1 0
+0 0 2 1 2
+0 0 0 3 1
diff --git a/inf/rtk/šolsko/4.c b/inf/rtk/šolsko/4.c
new file mode 100644
index 0000000..1aa574c
--- /dev/null
+++ b/inf/rtk/šolsko/4.c
@@ -0,0 +1,27 @@
+/*
+opisna rešitev:
+
+Naredimo seznam takih elementov:
+
+enum dejanje {
+ PRIHOD,
+ ODHOD
+};
+struct dejanje {
+ int čas;
+ int dolžina;
+ enum dejanje dejanje;
+};
+
+V zanki za vsak tovornjak v ta seznam dodamo ta dejanja. Najprej dodamo dejanje s .dejanje == PRIHOD in čas prihoda, nato pa dejanje s .dejanje == ODHOD, ki vsebuje vrednost prihoda, ki ji je prištet čas postanka. V vsak element seznama dodamo tudi dolžino tovornjaka.
+
+Po velikosti uredimo glede na čas seznam dejanj s standardno funkcijo qsort(). Sortirna funkcija naj v obzir vzame tudi dejanje. Če je prvo dejanje ODHOD in drugo PRIHOD, imata pa isti čas, vrne -1 in s tem postavi ODHOD pred PRIHOD.
+
+Deklariramo številsko spremenljivko maksdolžina in jo inicializiramo na 0, prav tako naredimo spremenljivko trenutnadolžina.
+
+Gremo po urejenem seznamu v zanki in ko naletimo na element s .dejanje == PRIHOD, povečamo spremenljivko trenutnadolžina za .dolžina, ko naletimo na element s .dejanje == ODHOD, zmanjšamo spremenljivko trenutnadolžina za .dolžina. Vsakič na koncu programa v zanki preverimo, če je trenutnadolžina morebiti večja od maksdolžina, v tem primeru maksdolžina nastavimo na trenutnadolžina.
+
+Ob koncu te zanke na standardni izhod izpišemo spremenljivko maksdolžina in končamo program.
+
+*/
+
diff --git a/inf/rtk/šolsko/5.c b/inf/rtk/šolsko/5.c
new file mode 100644
index 0000000..ed777eb
--- /dev/null
+++ b/inf/rtk/šolsko/5.c
@@ -0,0 +1,22 @@
+/*
+opisna naivna rešitev: (levo pomeni z manjšim indeksom, desno pa z večjim indeksom)
+
+Naredimo seznam z elementi:
+
+struct stoplnica {
+ int višina;
+ int indeks;
+ int barva; // barva je na začetku siva - 0
+};
+
+Sedaj moramo spremeniti vsak element seznama tako, da noben element seznama ne bo imel .barva == 0.
+
+Naredimo spremenljivko maksbarva in jo inicializiramo na 0.
+
+Začnemo pri elementu 0. Najti moramo element z nastavljeno barvo (torej .barva != 0), ki ga ne vidimo.
+
+Gledamo element vedno bolj levo, dokler ne dobimo takega, ki ga ne vidimo in ni direktno poleg nas (njegov desni element ne smemo biti mi). Ko ga najdemo, uporabimo to barvo elementa kot našo barvo. Če pridemo do začetka seznama, povečamo spremenljivko maksbarva in trenutnemu elementu nastavimo .barva na maksbarva.
+
+Ko nastavimo barvo zadnjemu elementu, izpišemo spremenljivko maksbarva na standardni izhod in zaključimo program.
+
+*/
diff --git a/inf/rtk/šolsko/Makefile b/inf/rtk/šolsko/Makefile
new file mode 100644
index 0000000..1dd50ea
--- /dev/null
+++ b/inf/rtk/šolsko/Makefile
@@ -0,0 +1,15 @@
+CFLAGS += -Wextra -Wall -pedantic -g -O0 -finput-charset=UTF-8 -fanalyzer -fextended-identifiers
+LDFLAGS += -lm
+CC ?= cc
+SHELL ?= /bin/sh
+cbins := $(subst .c,,$(wildcard *.c))
+asmbins := $(subst .asm,,$(wildcard *.asm))
+default: $(cbins) $(asmbins)
+%: %.c
+ $(CC) $(CFLAGS) $< -o$@ $(LDFLAGS)
+%: %.asm
+ # za zdaj sicer še ni ničesar v zbornem jeziku, mogoče pa bo ...
+ nasm -f elf $< && ld -m elf_i386 -s -o $@ $@.o
+.PHONY: clean
+clean:
+ rm -f $(bins) $(asmbins) *.o