Navodila za nalogo

V vasi nobena informacija ne ostane skrita. Branjevka Mici si vestno zapisuje, kako so se gospe na trgu srečevale. Tako je nastal seznam
Petra:Alenka
Jožica:Karmen
Alenka:Francka
Karmen:Urška
Alenka:Majda
Petra:Urška
Karmen:Majda
Zaradi enostavnosti v seznamu niso zapisani časi srečanj, vendar je seznam urejen po časovnem zaporedju, pogovori sami pa so bilo tako kratki, da prekrivanj pogovorov ni bilo.
Zanima nas, ali je neka zaupna informacija, ki jo je imela oseba A, lahko preko pogovorov prišla do B? Mogoče se je oseba A z B pogovarjala neposredno, ali pa je, kot se za klepetulje spodobi, se je ta infomacija širila od ust do ust.

Ideja

Ideja rešitve je, da po seznamu pogovorov poiščemo najprej osebo A. Nato pogledamo, s kom se je pogovarjala. Če se je direktno pogovarjala z osebo B, vrnemo true. Če pa to ne drži, potem pa pogledamo kako se je novica širila naprej. To pa naredimo tako, da rekurzivno pokličemo funkcijo na skrajšanem seznamu in s spremenjeno osebo A. Seznam skrajšamo tako, da iz prejšnjega izbrišemo prvi pogovor. Glede na to kar dobimo iz rekurzije, nato vrnemo true, ali pa nadaljujemo z zanko. Če se zanka izteče do konca, pomeni, da novica ni potovala od osebe A do osebe B, zato vrnemo false.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace klepetulje
{
    class Program
    {
        /// <summary>
        /// Preverimo, če je novica prišla od ene klepetulje do druge
        /// </summary>
        /// <param name="k">seznam pogovorov, nizov oblike "klepetulja1:klepetuja2"</param>
        /// <param name="a">prva klepetulja</param>
        /// <param name="b">druga klepetulja</param>
        /// <returns></returns>
        static bool Klepetulje(List<string> k, string a, string b)
        {
            //spremenljivka, ki nam pove, če je novica prišla do prave klepetulje
            bool je = false;
            //če je seznam prazen vrnemo false
            if (k.Count == 0) return false;
            //z zanko se sprehodimo čez seznam klepetulj
            for (int i = 0; i < k.Count; i++)
            {
                //niz razbijemo tako, da dobimo tabelo v kateri sta zapisani obe klepetulji
                string[] kl = k[i].Split(':');
                //če je kljepetulja v pogovoru
                if (kl[0] == a || kl[1] == a)
                {
                    //in se ujema tudi njena sogovornica, vrnemo true
                    if (kl[0] == b || kl[1] == b) return true;
                    else
                    {
                        //drugače pa prepišemo preostali seznam v novega
                        List<string> s = new List<string>();
                        for (int j = i+1; j < k.Count; j++) s.Add(k[j]);
                        //ter pokličemo rekurzijo na skrajšanem seznamu, drugi klepetulji iz para in podani drugi klepetulji
                        if (kl[0] == a) je = Klepetulje(s, kl[1], b);
                        else if (kl[1] == a) je = Klepetulje(s, kl[0], b);
                    }
                }
                //na koncu preverimo še, če je rekurzija vrnila true, tudi mi vrnemo true
                if (je) return true;
            }
            //če pa se zanka izteče, to pomeni, da par ni bil ustrezen in vrnemo false
            return false;
        }

        static void Main(string[] args)
        {
            List<string> k = new List<string>() ;
            k.Add("Petra:Alenka");
            k.Add("Jožica:Karmen");
            k.Add("Alenka:Francka");
            k.Add("Karmen:Urška");
            k.Add("Alenka:Majda");
            k.Add("Petra:Urška");
            k.Add("Karmen:Majda");
            k.Add("Jožica:Urška");

            string a1 = "Jožica";
            string b1 = "Karmen";
            Console.WriteLine("Ali je novica prišla od " + a1 + " do " + b1 + " ?");
            Console.WriteLine(Klepetulje(k,a1,b1));

            string a2 = "Jožica";
            string b2 = "Majda";
            Console.WriteLine("Ali je novica prišla od " + a2 + " do " + b2 + " ?");
            Console.WriteLine(Klepetulje(k, a2, b2));

            string a3 = "Jožica";
            string b3 = "Alenka";
            Console.WriteLine("Ali je novica prišla od " + a3 + " do " + b3 + " ?");
            Console.WriteLine(Klepetulje(k, a3, b3));

            string a4 = "Alenka";
            string b4 = "Petra";
            Console.WriteLine("Ali je novica prišla od " + a4 + " do " + b4 + " ?");
            Console.WriteLine(Klepetulje(k, a4, b4));

            string a5 = "Alenka";
            string b5 = "Urška";
            Console.WriteLine("Ali je novica prišla od " + a5 + " do " + b5 + " ?");
            Console.WriteLine(Klepetulje(k, a5, b5));

            string a6 = "Alenka";
            string b6 = "Jožica";
            Console.WriteLine("Ali je novica prišla od " + a6 + " do " + b6 + " ?");
            Console.WriteLine(Klepetulje(k, a6, b6));

            k.Clear();
            Console.WriteLine("Če podamo prazen seznam, metoda vrne:");
            Console.WriteLine(Klepetulje(k, a1, b1));
            Console.ReadKey();
        }
    }
}

Napisali smo metodo Klepetulje, ki vrne logično vrednost, kot vhodne spremenljivke pa dobimo seznam pogovorov, osebo A in osebo B.
static bool Klepetulje(List<string> k, string a, string b)
Definiramo spremenljivko za logično vrednost, v katero bomo shranili rezultat rekurzije. Nato preverimo še, če je seznam slučajno prazen. V tem primeru vrnemo false.
bool je = false;
if (k.Count == 0) return false;
Nato se z zanko sperhodimo po seznamu pogovorov.
for (int i = 0; i < k.Count; i++)
Vsak pogovor razdelimo glede na ':'. Tako dobimo seznam dolžine 2 v katerem sta imeni oseb, ki sta se pogovarjali.
string[] kl = k[i].Split(':'); Potem preverimo, če je katera od oseb enaka osebi A. Če je pa preverimo še, če se ujema tudi druga oseba in oseba B. Če oboje drži vrnemo true.
if (kl[0] == a || kl[1] == a)
       if (kl[0] == b || kl[1] == b) return true; Če pa je prava le oseba A, potem naredimo nov seznam. Vanj nato prepišemo seznam pogovorov, brez prvega. Ko imamo skrajšan seznam, pa lahko izvedemo rekurzijo. Tako funkcijo pokličemo s skrajšanim seznamom, novo osebo A in osebo B. Nova oseba A je sogovornica prvotne osebe A v trenutnem pogovoru.
    else
           List<string> s = new List<string>();
           for (int j = i+1; j < k.Count; j++) s.Add(k[j]);
           if (kl[0] == a) je = Klepetulje(s, kl[1], b);
           else if (kl[1] == a) je = Klepetulje(s, kl[0], b);
Na koncu koraka zanke pa preverimo še, če je rekurzija slučajno vrnila true, tudi tukaj vrnemo true in zaključimo zanko.
if (je) return true;
Če pa se zanka izteče do konca in je ne prekinemo, torej nismo našli pravih parov, preko katerih bi novica prišla od osebe A do osebe B. Zato vrnemo false.
return false;

Najprej sestavimo seznam pogovorov.
   List<string> k = new List<string>() ;
   k.Add("Petra:Alenka");
   k.Add("Jožica:Karmen");
   k.Add("Alenka:Francka");
   k.Add("Karmen:Urška");
   k.Add("Alenka:Majda");
   k.Add("Petra:Urška");
   k.Add("Karmen:Majda");
   k.Add("Jožica:Urška");
Preverimo, če je novica pripotovala od Jožice do Karmen.
   string a1 = "Jožica";
   string b1 = "Karmen";
   Console.WriteLine("Ali je novica prišla od " + a1 + " do " + b1 + " ?");
   Console.WriteLine(Klepetulje(k,a1,b1));
Preverimo, še če je novica pripotovala od Jožice do Majde.
   string a2 = "Jožica";
   string b2 = "Majda";
   Console.WriteLine("Ali je novica prišla od " + a2 + " do " + b2 + " ?");
   Console.WriteLine(Klepetulje(k, a2, b2)); Preverimo tudi, če je novica pripotovala od Jožice do Alenke.
   string a3 = "Jožica";
   string b3 = "Alenka";
   Console.WriteLine("Ali je novica prišla od " + a3 + " do " + b3 + " ?");
   Console.WriteLine(Klepetulje(k, a3, b3));
Preverimo, če je novica pripotovala od Alenke do Petre.
   string a4 = "Alenka";
   string b4 = "Petra";
   Console.WriteLine("Ali je novica prišla od " + a4 + " do " + b4 + " ?");
   Console.WriteLine(Klepetulje(k, a4, b4)); Preverimo, če je novica pripotovala od Alenke do Urške.
   string a5 = "Alenka";
   string b5 = "Urška";
   Console.WriteLine("Ali je novica prišla od " + a5 + " do " + b5 + " ?");
   Console.WriteLine(Klepetulje(k, a5, b5)); Preverimo, če je novica pripotovala od Alenke do Jožice.
   string a6 = "Alenka";
   string b6 = "Jožica";
   Console.WriteLine("Ali je novica prišla od " + a6 + " do " + b6 + " ?");
   Console.WriteLine(Klepetulje(k, a6, b6)); Spraznimo seznam, nato pa pogledamo, kaj vrne metoda.
   k.Clear();
   Console.WriteLine("Če podamo prezen seznam, metoda vrne:");
   Console.WriteLine(Klepetulje(s, a1, b1));

Razlaga izbire testnih primerov

Za prvi testni primer smo vzeli osebi, ki sta se pogovarjali direktno. V tem primeru metoda seveda vrne true.
Kot drugi primer smo vzeli osebi tako, da je novica od osebe A potovala do osebe B preko ostalih sogovornic. Tudi tukaj metoda vrne true.
V naslednjem primeru smo vzeli osebi, med katerima novica ni potovala. Metoda v tem primeru vrne false.
Še en testni primer je, kaj vrne metoda, če bi novica lahko potovala v obratni smeri. Metoda vrne True.
V zadnjem primeru pa smo vzeli primer s praznim seznamom pogovorov.

• List C#
• List C# primeri