Preštej podnize

Napiši funkcijo PrestejPodnize, ki mora vrniti število pojavitev niza PodNiz v nizu Niz. Štejejo tudi nestrnjene pojavitve, torej je lahko med črkami PodNiz-a v Niz-u tudi poljubna število drugih črk.

Najprej razmislimo kako bi se lotili.

• Pogledamo majhen problem: Iščemo podniz abc v nizu aabc. Kolikokrat se pod niz v nizu ponovi?

aabc in aabc

V tem primeru se ponovi dvakrat, ker črka a nastopa dvakrat zaporedno.

• Če vzamemo večji problem: Če iščemo podniz abc v nizu vafbjkbkjchj. Koliko krat se pod niz v tem primeru ponovi?

vafbjkbkjchj in vafbjkbkjchj

V tem primeru se tudi dvakrat ponovi, le da črka b nastopa dvakrat.

Preverit moremo dve stvari. Ali sploh obstaja podniz v nizu in kolikokrat se ponovi. Rešitev bo iz dveh delov.

• Prvi del:
  Preverili bomo, ali v nizu nastopajo črke iz podniza. To bomo naredili s for zankami pri pogoju, da sta črki enaki, jo bomo shranili v pomožni niz. Nato bomo preverili, ali je pomožni niz enak podnizu. V primeru, da sta enaka nadaljujemo v naslednji del naloge, sicer ne naredimo ničesar.
  
  
• Drugi del:
  Ponovno bomo preverjali črke, le da bomo tedaj preverili črke iz podniza, če so enake črkam niza. Če sta črki enaki, jo shranimo v pomožni niz. Pred začetkom zanke definiramo pomožni števec na ena(vemo iz prvega dela da enkrat nastopi), ki nam bo štel pojavitve podniza v nizu. Preveriti moramo le še kolikokrat se ponovi podniz. Z novo zanko for bomo preverili, ali se katera črka zaporedno ponovi. Če se, števec povečamo za 2 krat sedanji števec.
  

Funkcija

class Program
    {
        static int PrestejPodnize1(string niz, string podniz)
        {/*naloga podamo niz in podniz, ali vsebuje niz ta podniz in koliko krat*/
            string pom = "";
            int st=0;
            for (int j = 0; j < podniz.Length; j++)
                for (int i = 0; i < niz.Length; i++)
                    if (pom.Length < podniz.Length)
                        if (podniz[j] == niz[i])
                        {
                            pom += niz[i];
                            j += 1;
                        }
            if (podniz == pom)
            {
                st = 1;
                pom = "";//zbrišemo vsebino pom. niza
                for (int i = 0; i < niz.Length; i++)
                {
                    for (int j = 0; j < podniz.Length; j++)
                        if (podniz[j] == niz[i]) pom += niz[i];
                }
                for (int i = 0; i < pom.Length - 1; i++)
                    if ((pom[i]) == pom[i + 1]) st = st * 2;
            }
            return st;
        }

Izvedba testnih primerov:

Na prvi sliki vidimo tri primere. Iz prvih dveh primerov je razvidna rešitev. V tretjem primeru, pa je rešitev , ker se vseh šest črk podniza ponovijo.

Na drugi sliki pa imamo primer, kadar ne nastopa podniz v nizu. V testnem programu smo zapisali, da v takem primeru vrne ob rešitvi tudi komentar.

Fiksna vsota

Med n različnimi števili, zapisanimi v urejeni tabeli bi radi poiskali tak par števil, da bo njuna vsota enaka m.

Enostavno reševanje problema

Imamo tabelo števil, na primer:

tabela= 2 10 14 18 vsota = 20
Hitro vidimo, da par 2+18 = 20 ustreza vsoti 20.

S pomočjo zanke bomo šli po tabeli števil in primerjali števila. Če vsota para ustreza, ga bomo izpisali in nadaljevali. Pri tem bomo v pomožni števec shranjevali število takih parov.

Funkcija

class Program
    {
        static void IzpisiPare(int[] sez, int vsota)
        {
            /*izpise pare ki imajo vsoto enako izbrani vsoti*/
            int n = sez.Length;
            int stevec = 0;
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j < n; j++)
                {
                    int v = sez[i] + sez[j];
                    if (v == vsota)
                    {
                        Console.WriteLine((stevec+1)+".par: "+sez[i] + " + " + sez[j] + " = "+ vsota);
                        stevec++;
                        j += 1;
                    }
                }
            Console.WriteLine("Število vseh parov, ki vsteza podani vsoti: " + stevec);
        }

Naredimo nekaj primerov tabel in vsot.

static void Main(string[] args)
        {

            int[] seznam = { 2, 7, 10, 14, 18 };
            string sez="";
            for (int i = 0; i < seznam.Length; i++)
                sez = sez + seznam[i] + " ";
            int vsota = 20;
            Console.WriteLine("Primer 1:\n- - - - - - - - - - ");
            Console.WriteLine("Podan urejen seznam števil: "+sez);
            Console.WriteLine("Iščemo pare z vsoto: " + vsota );
            IzpisiPare(seznam, vsota);
            sez = "";
            int[] seznam1 = { 4, 8, 15, 22, 35 };
            for (int i = 0; i < seznam1.Length; i++)
                sez = sez + seznam1[i] + " ";
            int vsota1 = 30;
            Console.WriteLine("\n \n");
            Console.WriteLine("Primer 2:\n- - - - - - - - - - ");
            Console.WriteLine("Podan urejen seznam števil: " + sez);
            Console.WriteLine("Iščemo pare z vsoto: " + vsota1);
            IzpisiPare(seznam1, vsota1);
            sez = "";
            int[] seznam2 = { 2, 7, 10, 14, 24, 31, 35, 44, 45, 55, 56, 30, 67, 69, 75, 90, 93, 95, 98 };
            for (int i = 0; i < seznam2.Length; i++)
                sez = sez + seznam2[i] + " ";
            int vsota2 = 100;
            Console.WriteLine("\n \n");
            Console.WriteLine("Primer 3:\n- - - - - - - - - - ");
            Console.WriteLine("Podan urejen seznam števil: " + sez);
            Console.WriteLine("Iščemo pare z vsoto: " + vsota2);
            IzpisiPare(seznam2, vsota2);



            sez = "";
            int[] seznam3 = { 1, 2, 3, 4, 5 };
            for (int i = 0; i < seznam3.Length; i++)
                sez = sez + seznam3[i] + " ";
            int vsota3 = 10;
            Console.WriteLine("\n \n");
            Console.WriteLine("Primer 4:\n- - - - - - - - - - ");
            Console.WriteLine("Podan urejen seznam števil: " + sez);
            Console.WriteLine("Iščemo pare z vsoto: " + vsota3);
            IzpisiPare(seznam3, vsota3);
            Console.ReadLine();
        }
    }

Imamo tri primere, ki ustrezajo pogojem.
Pri vsakem se izpiše par oz. pari, ki ustrezajo pogoju in koliko jih je.
Zadnji primer je izjema pri katerem se izpiše komentar. Noben par ne ustreza pogoju.

Navodila naloge:

Napišite razred Student, s katerim predstavite vse smiselne lastnosti in metode za študente. Rešite naslednje probleme:

• Vrnite novo tabelo, ki naj vsebuje le tiste študente, ki niso v zadnjem letniku.
• Vrnite tabelo tistih študentov, ki so v zadnjem letniku.
• Vsi študenti v tabeli naj "napredujejo" v višji letnik. Prej tiste, ki so v zadnjem, 4. letniku, pa izločite (glejte prejšnjo metodo).
• Vrnite tabelo, ki vsebuje število študentov posameznega letnika.
• Koliko je deklet v tabeli študentov?
• Vsaj en ( zaželeno pa več) problem po vaši izbiri ... (opišite jih!)

Sestaviti morete dva testna programa. Eden služi, da ustvarite vsaj 20 objektov in jih zapišete na datoteko. V drugem pa naredite naslednje:

• Napišite ustrezne metode za reševanje zastavljenih problemov.
• Ustvarite vsaj en objekt in ga dodajte (z DodajNaDatotekov) v datoteko (na tej je sedaj vsaj 21 objektov).
• Preberite vse podatke z datoteke v tabelo.
• Tabelo potem pregledno izpišite.
• Nato kličite metode, ki so potrebne, da rešite zastavljene probleme in pregledno izpišite rezultate.
• Na koncu V datoteko z imenom imeDat (parameter) zapišite ponovno vse podatke vseh objektov (ne glede na to, ali so jih zgornje metode spremenile ali ne) v tabeli, med sabo ločene z znakom ':' (podatki o posameznem objektu gredo v svojo vrstico).

Kako se lotimo reševanja te naloge?
Najprej se vprašamo, kako bo rešitev sestavljena. Vemo, da bosta dva testna programa ter razred Student.

Najprej se lotimo konstrukcije razreda Student.

• Kakšne podatke o študentu moramo definirati in katere je smiselno dodati?
  Da rešimo probleme potrebujemo letnik študija(od 1. do 4.), spol študenta. Smiselno je dodati vpisno številko, ime ter priimek. Ker moramo rešiti še probleme po želji, dodamo še smer vpisa ter leto vpisa.
  
  
• Kaj pa bosta vsebovala testna programa?
  V prvem testnem programu bomo le ustvarili objekte, v našem primeru študente. Drugi testni program bo pa vseboval klice funkcij iz razreda Student ter izpisal rešitve funkcij.

Dodamo nove probleme, ki jih lahko rešimo s podatki o študentu.

1. Vrnite tabelo tistih študentov, ki so vpisani na smer Praktična matematika("PRM").
2. Vrnite tabelo tistih študentov, ki so se vpisali leta 2010.
3. Vrnite študenta, ki ima vpisno številko enako 27002.

Razredu Student bomo najprej definirali spremenljivke, ki bodo javne.
Spremenljivke ime, priimek, spol ter smer bodo oblike niz (string). Ostale pa cela števila (int), to so vpisna številka, letnik in leto vpisa.

Sestavimo konstruktor s katerim bomo shranili v spremenljivke vrednosti.

Lotimo se konstruiranja funkcij za reševanje problemov.

• Sestavimo tri funkcije:
  Če vrednost spr. letnika je enaka 4
           public bool zadnjiLetnik()
              {
                  if (this.letnik == 4)
                      return true;
                  else { return false; }
              }
  Če vrednost spr. letnika je manjša od 4, vrednost letnika povečaj
  public bool napredNaslednjiLetnik()
     {
        if (this.letnik < 4)
            this.letnik++;
        else { return false; }
            return true;
     }
  Če vrednost spr. spola je ženski
           public bool zenskiSpol()
              {
                  if (this.spol == "Ž")
                      return true;
                  else { return false; }
              }

• Sestavimo funkcije za naše dodane probleme:
  Če je vrednost spr. smer enaka podani smeri
           public bool smerStudija(string imeSmeri)
              {
                  if (this.smer.Equals(imeSmeri))
                      return true;
                  else { return false; }
              }
  Če je vrednost spr. letoVpisa enaka podanemu letu
           public bool letoVpisaJe(int leto)
              {
                  if (this.letoVpisa.Equals(leto))
                      return true;
                  else { return false; }
              }
  Če je vrednost spr. vpisnaSt enaka podani stevilki
           public bool vpisnaStevilkaJe(int stevilka)
              {
                  if (this.vpisnaSt.Equals(stevilka))
                      return true;
                  else { return false; }
              }

V razredu Student bomo dodali funkcijo ToString. Funkcija vsebuje le ukaz za izpisovanje podatkov o študentu. Vsak podatek bo ločen z vejico.
         public override string ToString()
            {
                return " Študent: " + this.vpisnaSt + ",  " + this.ime +" "+ this.priimek + ",  " +
         this.spol +",  " + this.letnik + ",  " + this.letoVpisa + ",  " + this.smer;
            }
Dodamo še funkcijo DodajNaDatoteko. Parameter bo ime datoteke, v katero bomo shranili podatke. Funkcija vsebuje ukaz za odpiranje datoteke, ter za pisanje na njo. Definiramo le, kako naj zapisuje na datoteko podatke o študentu. V navodilih piše, da moramo podatke ločiti s podpičji (";").
         public void DodajNaDatoteko(string imeDatoteke)
            {
                FileStream f = new FileStream(imeDatoteke, FileMode.Append);
                TextWriter p = new StreamWriter(f);
                p.WriteLine(this.vpisnaSt + ";" + this.ime + ";" + this.priimek + ";" + this.spol +

              ";" + this.letnik + ";" + this.letoVpisa + ";" + this.smer);
                p.Close();
            }
Da lahko rešujemo probleme potrebujemo še funkcijo, ki nam bo omogočala branje podatkov zapisanih na datoteki. Funkcija bo vsebovala ukaz za branje z datoteke, ter ukaz kako bo podatke ločil in opredelil.
     static List<Student> PreberiZDatoteke (string imeDatoteke)
        {  //preberemo z datoteke
            StreamReader f = new StreamReader(imeDatoteke);//odpremo datoteko za branje
            string[] vrsticeStudenti = f.ReadToEnd().Split('\n');//vrstice shranimo glede na odstavek

            for (int i = 0; i < vrsticeStudenti.Length; i++)
                if (vrsticeStudenti[i].Length > 0)
                    vrsticeStudenti[i] = vrsticeStudenti[i].Substring(0, vrsticeStudenti[i].Length -

1);

            //definiramo nov seznam
            List<Student> tabelaStudentov = new List<Student>();
            //gremo po vrsticah študentov, ter določimo kako podatke loči in kakšne vrednosti so
            //sestavimo novo tabelo, ki vrnemo določeno vrednosti
            for (int i = 0; i < vrsticeStudenti.Length; i++)
            {
                if (vrsticeStudenti[i].Length < 1)
                    continue;
                string[] podatki = vrsticeStudenti[i].Split(';');
                tabelaStudentov.Add(new Student(
                    int.Parse(podatki[0]),
                    podatki[1],
                    podatki[2],
                    podatki[3],
                    int.Parse(podatki[4]),
                    int.Parse(podatki[5]),
                    podatki[6]));
            }
            return tabelaStudentov;
        }

Prvi testni program smo rekli, da vsebuje le podatke o študentih, ki jih zapišemo na datoteko s klicom funkcije DodajNaDatoteko.

Primer:
     static void testniProgram1(string imeDat)
        {
            //na datoteko dodamo študente
            Student student = new Student(27001, "Lara", "Pal", "Ž", 2, 2009, "PRM");
            student.DodajNaDatoteko(imeDat);
            .
            .
            .
  }
Drugi testni program:

1. Naloga zahteva da dodamo novega študenta. Mi bomo dodali dva nova študenta, ki sta se prepisala.
2. Preberemo podatke z datoteke s pomočjo funkcije PreberiZDatoteke in nato na vsako vrstico uporabimo funkcijo ToString, da te podatke tudi izpišemo.
   

3. Izpisujemo rešitve problemov:

   • Vrnemo tabelo študentov, ki niso v zadnjem letniku. Tabela vsebuje študente, ki ne ustrezajo pogoju funkcije zadnjiLetnik. Rešitev je izpis tabele študentov, ki niso v 4. letniku.
   • Vrnemo tabelo študentov, ki so v zadnjem letniku. Tabela vsebuje študente, ki ustrezajo pogoju funkcije zadnjiLetnik. Rešitev je izpis tabele študentov, ki obiskujejo 4. letnik.
   • Zdaj pa želimo, da študenti napredujejo v naslednji letnik. Tabela bo zdaj vsebovala študente, ki napredujejo v naslednji letnik. To so študenti, ki ustrezajo pogojem funkcije napredNaslednjiLetnik. Nato pa vse študente, ki so v tabeli nisoVZadnjemLetniku izbrišemo iz tabele študentov. Rešitev je izpis študentov, ki so napredovali.
   • Izpisati želimo število študentov po letnikih. Definiramo tabelo steviloStudentovPoLetniku velikosti 4. V tabeli študentov, seštevamo število študentov, ki obiskujejo isti letnik in število shranimo v novo tabelo. Za vsak letnik izpišemo število posebej.
   • Vrnemo število deklet med študenti. Potrebujemo pomožni števec za štetje. Če je študent v tabeli študentov,študent ustreza pogoju funkcije zenskiSpol, števec povečamo. Nato izpišemo števec.
   • Vrnemo tabelo študentov, ki so vpisani na smer Praktična matematika. Če študent v tabeli študentov ustreza pogoju funkcije smerStudija z parametrom "PRM", ga izpiše.
   • Vrnimo tabelo študentov, ki so bili vpisani leta 2010. To so študenti, ki ustrezajo pogoju funkcije letoVpisaJe z parametrom 2010.
   • Izpisati želimo študenta z vpisno številko 27002. Če študent v tabeli študenti ustreza pogoju funkcije vpisnaStevilkaJe z parametrom 27002, ga izpiše.
4. Za konec predelane podatke shranimo na končno datoteko, ki smo jo imenovali predelaniPodatki.txt. To naredimo s pomočjo funkcije dodajNaDatoteko.

        static void testniProgram2(string imeDat)
        {
            //dadamo še dva nova študenta, ki sta se prepisala
            Student student20 = new Student(26099, "Miha", "Kovač", "M", 3, 2010, "PRM");
            Student student21 = new Student(26098, "Nika", "Kolenc", "Ž", 2, 2010, "FIZ");
            student20.DodajNaDatoteko(imeDat);
            student21.DodajNaDatoteko(imeDat);
            Console.WriteLine("Dodali smo dva nova študenta, ki sta se prepisala:");
            Console.WriteLine(student20.ToString());
            Console.WriteLine(student21.ToString());

            // preberemo tabelo študentov z datoteke
            List<Student> tabelaStudentov = PreberiZDatoteke(imeDat);

            // izpišemo tabelo študentov
            Console.WriteLine("\n -- -- -- -- -- -- -- -- -- -- -- -- ");
            Console.WriteLine("Tabela študentov: \n ");
            foreach (Student stud in tabelaStudentov)
                Console.WriteLine(stud.ToString());

            // izpišemo  vse studente, ki niso v zadnjem letniku
            List<Student> nisoVzadnjemLetniku = new List<Student>();
            for (int i = 0; i < tabelaStudentov.Count; i++)
                if (!tabelaStudentov[i].zadnjiLetnik())
                    nisoVzadnjemLetniku.Add(tabelaStudentov[i]);
            Console.WriteLine("\n -- -- -- -- -- -- -- -- -- -- -- --  ");
            Console.WriteLine(" V zadnjem letniku niso studenti: \n");
            foreach (Student stud in nisoVzadnjemLetniku)
                Console.WriteLine(stud.ToString());

            //izpišemo tiste študente, ki so v zadnjem letniku
            List<Student> soVZadnjemLetniku = new List<Student>();
            for (int i = 0; i < tabelaStudentov.Count; i++)
                if (tabelaStudentov[i].zadnjiLetnik())
                    soVZadnjemLetniku.Add(tabelaStudentov[i]);
            Console.WriteLine("\n -- -- -- -- -- -- -- -- -- -- -- --  ");
            Console.WriteLine("V zadnjem letniku so studenti: \n");
            foreach (Student stud in soVZadnjemLetniku)
                Console.WriteLine(stud.ToString());

            //vsi studenti napredujejo v naslednji letnik. Tisti, ki so bli v zadnjem letniku izbrišemo
            for (int i = 0; i < tabelaStudentov.Count; i++)
                tabelaStudentov[i].napredNaslednjiLetnik();
            for (int i = 0; i < soVZadnjemLetniku.Count; i++)
                tabelaStudentov.Remove(soVZadnjemLetniku[i]);
            Console.WriteLine("\n -- -- -- -- -- -- -- -- -- -- -- --  ");
            Console.WriteLine("Tabela študentov po napredovanju v naslednji letnik: \n");
            foreach (Student stud in tabelaStudentov)
                Console.WriteLine(stud.ToString());

            //izpišemo število študentov v posameznem letniku
            int[] steviloStudentovPoLetniku = new int[4];
            for (int i = 0; i < tabelaStudentov.Count; i++)
                steviloStudentovPoLetniku[tabelaStudentov[i].letnik - 1] += 1;
            Console.WriteLine("\n -- -- -- -- -- -- -- -- -- -- -- --  ");
            Console.WriteLine("Število študentov posameznega letnika: ");
            for (int i = 0; i < steviloStudentovPoLetniku.Length; i++)
                Console.WriteLine((i+1) + ".letnik: " + steviloStudentovPoLetniku[i]);

           //izpišemo število deklet v tabeli študentov
            int stevec = 0;
            for (int i = 0; i < tabelaStudentov.Count; i++)
                if (tabelaStudentov[i].zenskiSpol())
                    stevec++;
            Console.WriteLine("\n -- -- -- -- -- -- -- -- -- -- -- --  ");
            Console.WriteLine(" V tabeli študentov je deklet " + stevec + "!");


            //*izpišemo studente, ki so vpisani na smer PRM
            Console.WriteLine("\n -- -- -- -- -- -- -- -- -- -- -- --  ");
            Console.WriteLine("Študenti, ki so vpisani na smer Praktična matematika: \n");
            for (int i = 0; i < tabelaStudentov.Count; i++)
                if (tabelaStudentov[i].smerStudija("PRM"))
                    Console.WriteLine(tabelaStudentov[i].ToString());

            //*izpišemo študente, ki so vpisani leta 2010
            Console.WriteLine("\n -- -- -- -- -- -- -- -- -- -- -- --  ");
            Console.WriteLine("Študenti vpisani, ali prepisani leta 2010: \n");
            for (int i = 0; i < tabelaStudentov.Count; i++)
                if (tabelaStudentov[i].letoVpisaJe(2010))
                    Console.WriteLine(tabelaStudentov[i].ToString());

            //*izpišemo študenta, ki ima vpisno številko 27002
            int vpisna=27002;
            Console.WriteLine("\n -- -- -- -- -- -- -- -- -- -- -- --  ");
            Console.WriteLine("Študent z vpisno številko " + vpisna + ":\n");
            for(int i=0;i<tabelaStudentov.Count;i++)
                if (tabelaStudentov[i].vpisnaStevilkaJe(vpisna))
                    Console.WriteLine(tabelaStudentov[i].ToString());

            //v izhodno datoteko izpišemo študente z končnimi spremembami
            string imeDatoteke = "predelaniPodatki.txt";
            foreach (Student stud in tabelaStudentov)
                stud.DodajNaDatoteko(imeDatoteke);
            Console.ReadLine();
        }

Definiramo ime datoteke, v katero bomo shranili podatke o študentih. Nato pokličemo oba testna programa. Prvi nam doda podatke na datoteko, drugi pa obdeluje te podatke.

static void Main(string[] args)
      {
            string imeDat = "tabelaPodatkov.txt";
            testniProgram1(imeDat);
            testniProgram2(imeDat);
        }