Naloga - Skrivnost

Naloga - Skrivnost

Avtor: Poboljšaj Nina

Opis problema in ideja rešitve

Telefonski operaterji imajo tako imenovane prometne podatke o telefonskih razgovorih: kdo je koga klical in kdaj. Čeprav pri tem zbiranju še ne gre za prisluškovanje pogovorom, so tudi prometni podatki strogo zasebni podatki, saj se da na njihovi podlagi marsikaj sklepati o klicočih in jih lahko operaterji posredujejo preiskovalnim organom samo na izrecno zahtevo sodišča ob utemeljenem sumu kaznivih dejanj (ko lahko sodišče odredi tudi prisluškovanje imetnikom izbranih telefonskih številk). Pa recimo, da teh moralnih dilem nimamo. Dobili smo zaporedni seznam prometnih podatkov nekega operaterja o vseh telefonskih klicih v nekem časovnem obdobju. Elementi seznama so pari številk, ki sta uspešno vzpostavili telefonsko zvezo, torej takole (zaradi enostavnosti bomo pri tej nalogi predpostavili, da so vse telefonske številke štirimestne, npr. interne številke nekega podjetja):

  • 1705 2312
  • 1326 1705
  • 3789 1230
  • 2312 2372
  • 0137 1705

In tako dalje. Zaradi enostavnosti v tabeli niso zapisani časi klicev, vendar je seznam urejen po časovnem zaporedju, torej prvi element seznama je prvi klic v opazovanem časovnem obdobju in tako naprej. Zanima nas, ali je neka zaupna informacija, ki jo je imel lastnik telefonske številke a, lahko prek telefonskih pogovorov prišla do osebe, ki je lastnik telefonske številke b? Mogoče se je a najprej pogovarjal z nekim c, potem pa je d poklical c-ja in nazadnje je d poklical b-ja. Informacija od a do b bi lahko prišla tudi po kakšni drugačni poti, npr. tako, da e najprej pokliče a-ja in potem b pokliče e-ja.

V programu najprej zgeneriramo seznam klicev. V njem je torej 100-krat po 2 elementa, ki so se vsi zgenerirali naključno. Torej najverjetneje nobeni 2 številki ne bosta enaki. Zato brez popravljanja seznama skrivnost verjetno nikoli ne bi bila razkrita, pa ni važno s katero številko bi začeli iskati. Zato popravimo seznam tako, da vemo da je bila skrivnost razkrita. Potem pa to ugotovimo še z algoritmom.

Razlaga algoritma

Zgradimo seznam klicev z generatorjem naključnih števil. V seznamu je 100 klicev. Telefonski številki naključno generiramo med 1000 in 9999.

  //Zgradimo seznam klicev
            int[,] klici = new int[100,2]; //V seznamu naj bo npr. 100 klicev
            Random rand = new Random();//Generator nakljucnih stevil
            for (int i = 0; i <= 99; i++)//Seznam napolnimo z nakljucnimi stevili
            {
                int num1 = rand.Next(1000, 9999);//Izbere nakljucno stevilo med 1000 in 9999
                int num2 = rand.Next(1000, 9999);
                klici[i, 0] = num1;//Tisti ki klice
                klici[i, 1] = num2;//Klicani
            }

Razlaga algoritma

Nato popravimo seznam klicev a,b,c,d in e. Izpišemo vse klic in jih ločimo z ','.

//Popravimo seznam klicev
            int a = 1234;
            int b = 5678;
            int c = 2222;
            int d = 3333;
            int e = 9191;
            klici[10, 0] = a;
            klici[10, 1] = c;
            klici[35, 0] = d;
            klici[35, 1] = c;
            klici[62, 0] = d;
            klici[62, 1] = e;
            klici[73, 0] = b;
            klici[73, 1] = e;


            //Izpise vse klice
            for (int i = 0; i <= 99; i++)
            {
                Console.WriteLine(klici[i, 0] + ", " + klici[i, 1]);
            }


            bool razkrita = razkritaSkrivnost(a, b, klici);//Ali je skrivnost razkrita?
            if (razkrita) Console.WriteLine("Skrivnost je razkrita");
            else Console.WriteLine("Skrivnost ni razkrita");

            //To je tukaj zato, da se okno ne zapre avtomatsko po koncu izvajanja programa
            //in tako lahko preberemo rezultate.
            Console.ReadLine();

Razlaga algoritma

Sedaj pa napišemo program, ki razkrije ali je informacija prišla od a do b. zgradimo nov seznam, v katerem hranimo vse tiste številke, za katere vemo, da poznajo skrivnost. Na začetku vemo, da jo pozna a. Pregledamo vse klice. Če je eden izmed obeh v pogovoru z b in drugi pozna skrivnost, potem je skrivnost razkrita. Kaj pa če b ni sodeloval v trenutno obravnavanem klicu? Z if stavkom preverimo, če tisti, ki kliče pozna skrivnost in če klicani prej še ni poznal skrivnosti, jo sedaj pozna in ga dodamo v seznam tistih , ki jo poznajo. Če pa klicani pozna skrivnost in pa če tisti, ki kliče prej ni poznal skrivnosti, jo sedaj pozna in ga zato dodamo v seznam tistih , ki jo poznajo. Tako smo pregledali vse klice in skrivnost ni bila razkrita.

public static bool razkritaSkrivnost(int a, int b, int[,] klici)
        {
            //Ali je informacija prisla od a do b?

            //Zgradimo nov seznam, v katerem hranimo vse tiste stevilke,
            //za katere ze vemo, da poznajo skrivnost. Na zacetku vemo, da jo pozna a.
            Seznam poznajoSkrivnost = new Seznam(new Element(a));

            for (int i = 0; i <= klici.Length/2-1; i++)//pregledamo vse klice
            {
                int st0 = klici[i, 0];//Tisti ki klice
                int st1 = klici[i, 1];//Klicani

                //Ce je eden izmed obeh v pogovoru b in drugi pozna skrivnost,
                //potem je skrivnost razkrita. Koncam pregledovati.
                if (st0 == b && poznajoSkrivnost.jeVseznamu(st1)) return true;
                if (st1 == b && poznajoSkrivnost.jeVseznamu(st0)) return true;

                //b ni sodeloval v trenutno obravnavanem klicu
                if (poznajoSkrivnost.jeVseznamu(st0))//tisti ki klice pozna skrivnost
                {
                    //ce klicani prej se ni poznal skrivnosti, jo sedaj pozna in ga
                    //zato dodamo v seznam tistih, ki jo poznajo
                    if (!poznajoSkrivnost.jeVseznamu(st1)) poznajoSkrivnost.dodaj(new Element(st1));
                }
                else if (poznajoSkrivnost.jeVseznamu(st1))//klicani pozna skrivnost
                {
                    //ce tisti ki klice prej se ni poznal skrivnosti, jo sedaj pozna in ga
                    //zato dodamo v seznam tistih, ki jo poznajo
                    if (!poznajoSkrivnost.jeVseznamu(st0)) poznajoSkrivnost.dodaj(new Element(st0));
                }
            }
            //pregledali smo vse klice in skrivnost ni bila razkrita
            return false;
        }večvrstični zapis kode

Razlaga algoritma

Naredimo nov razred seznam, v katerem hranimo vse tiste številke, za katere vemo, da poznajo skrivnost. Naredimo konstruktor, ki zgradi seznam z enim elementom in doda nov element na konec seznama. Nato pregledamo, če je število x v seznamu. Začnemo z prvim elementom v seznamu. Z while zanko seznam pregledujemo, dokler ne pridemo do konca. Če je število x v seznamu vrnemo true in prestavimo kazalec na naslednji element seznama. Drugače števila x ni v seznamu in vrnemo false.

//Seznam, v katerem hranimo vse tiste stevilke,
    //za katere ze vemo, da poznajo skrivnost.
    class Seznam
    {
        Element prvi;//prvi element seznama
        Element zadnji;//zadnji element seznama

        public Seznam(Element pr)//konstruktor, ki zgradi seznam z enim elementom
        {
            prvi = pr;
            zadnji = pr;
        }

        public void dodaj(Element el)//doda nov element na konec seznama
        {
            zadnji.naslednji = el;
            zadnji = el;
        }

        public bool jeVseznamu(int x)//pregleda, ce je stevilo x v seznamu
        {
            Element el = prvi;//zacnemo s prvim elementom seznama
            while (el != null)//seznam pregledujemo dokler ne pridemo do konca
            {
                if (el.stevilka == x) return true;//stevilo x je v seznamu
                else el = el.naslednji;//prestavimo kazalec na naslednji element seznama
            }
            return false;//stevila x ni v seznamu
        }

    }

Razlaga algoritma

Naredimo razred element seznama, ki vsebuje številke in kazalec na naslednji element.

//Element seznama, ki vsebuje stevilko in kazalec na naslednji element.
    class Element
    {
        public int stevilka;
        public Element naslednji;

        public Element(int st)//konstruktor, zgradi nov element
        {
            stevilka = st;
            naslednji = null;
        }
    }

Testni primeri

Seznam klicev zgradimo z generatorjem naključnih števil. V seznamu je 100 klicev. Telefonske številke pa so med 1000 in 9999.

Rezultat

(1primer.png)

Posnetek

0%
0%