Številske domine

Številske domine

Avtor: Urška Pikl

Učni cilji: opis problema in ideja rešitve, razlaga algoritma, testni primeri in filmček.

Navodila

Številske domine


V tekstovni datoteki je zapisanih ducat pozitivnih celih števil. Poišči najdaljša zaporedje, ki ga lahko sestavimo iz teh števil. Dve števili v zaporedju sta lahko sosednji, če si nista tuji. Tako sta lahko zaporedni števili 12 in 18, ne pa tudi 15 in 22.


  • Vnesi ime datoteke: podatki.txt
  • Najdaljšo kačo sestavljajo števila: 12, 15, 110, 33

Opis problema in ideja rešitve

Opis

Števili sta tuji, če je njun največji skupni delitelj enak 1. Največji skupni delitelj dveh števil je največji od deliteljev, ki so skupna obema številoma.

Lahko tudi rečemo, da sta števili tuji, če imata skupnih deliteljev.


Ideja

Za poivedbo, če sta števili tuji, uporabimo najprej funkcijo, ki poišče največji skupni delitelj (GCD) in nato vrnemo true če sta števili tuji, torej je njun največji skupni delitelj enak 1, sicer vrnemo false.

Ideja za iskanje najdaljšega zaporedja netujih sosednjih števil je naslednja:

  • Najprej gremo po vseh elementih npr. neke tabele. Preverjamo vsak element z njegovim naslednjim. Če nista tuji, ju damo v nek pomožen niz števil.
  • Kakor hitro naletimo na neko tuje število, se prejšnje zaporedje prekine. Preverimo, če je dolžina sedanjega najdaljšega zaporedja daljša od prejšnjega in ju ustrezno zamenjamo, pomožni niz pa "izpraznemo".
  • na koncu vrnemo niz z najdaljšo verigo.

Algoritem

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

namespace StevilskeDomine
{
    class Program
    {

        /// <summary>
        /// Iz tabele ducatih števil najde najdaljšo verigo in vrne niz z rešitvijo
        /// </summary>
        /// <param name="tab">Tabela števil</param>
        /// <returns>Vrne najdaljše zaporedje netujih števil</returns>
        static string StevilskeDomine(int[] tab)
        /*V tekstovni datoteki je zapisanih ducat pozitivnih celih števil. Poišči najdaljša zaporedje, ki ga lahko
sestavimo iz teh števil. Dve števili v zaporedju sta lahko sosednji, če si nista tuji. Tako sta lahko
zaporedni števili 12 in 18, ne pa tudi 15 in 22.*/
        {
            if (tab.Length == 0)
                throw new Exception("Tabela je prazna");

            // seznama, ki hranita trenutno najboljšo kačo in trenutno kačo
            List<int> trenutni = new List<int>() { };
            List<int> najboljsi = new List<int>() { };


            for (int i = 0; i < tab.Length; i++)
            {   
                // element tabele damo v seznam trenutne kače
                trenutni.Add(tab[i]);

                // od zadnjega elementa, ki smo ga dali v trenutni seznam pogledamo nadaljne elemente
                for (int j = i + 1; j < tab.Length; j++)
                {
                    // če sta zadnji v trenutnem in tekoči element tabele tuji, damo tekoči element na zadnje mesto trenutnega rezultata
                    if (!Knj.TujiStevili(tab[j], trenutni[trenutni.Count - 1]))
                        trenutni.Add(tab[j]);
                }
                                
                // če je trenutna kača daljša od do sedaj najboljše, potem jo damo v seznam najboljšij
                if (trenutni.Count > najboljsi.Count)
                {
                    najboljsi.Clear();
                    najboljsi.AddRange(trenutni);
                }
                // trenutni seznam izpraznemo
                trenutni.Clear();
            }

            // iz seznama naredimo niz, ki ga potem vrnemo
            string niz = "";
            foreach (int el in najboljsi)
            {
                if (niz.Length > 0)
                    niz += ", ";
                niz += el;
            }
            return niz;
        }

        /// <summary>
        /// Iz datoteke prebere ducat števil in vrne niz najdaljše verige ne tujih si števil
        /// </summary>
        /// <param name="imeDatoteke">Ime datoteke, v kateri je shranjenih 12 celih pozitivnih števil</param>
        /// <returns>Vrne niz, najdaljšo verigo ne tujih si števil</returns>
        static string StevilskeDomine(string imeDatoteke)
        {
            // preberi iz datoteke
            // tabela, kamor bomo iz datoteke shranili stevila
            int[] tab = new int[12];

            // preverimo, ce datoteka obstaja
            if (!File.Exists(imeDatoteke)) throw new Exception("Ta datoteka ne obstaja");

            StreamReader branje = File.OpenText(imeDatoteke);
            string vrstica; // prebrana vrstica datoteke
            string[] vrs; // tabela ločenih podatkov v vrstici

            int stevilo = 0; // ko poskušamo število pretvoriti iz niza
            int indeks = 0; // indeks elementa v tabeli (po vrsti)

            while ((vrstica = branje.ReadLine()) != null)
            {
                vrs = vrstica.Split(); // ločimo podatke

                foreach (string element in vrs)
                {
                    // če je prazen
                    if (element.Length == 0)
                        continue;
                    // če je element število, ga dodamo v tabelo in povečamo indeks
                    else if (int.TryParse(element, out stevilo))
                    {
                        if (indeks >= 12)
                            throw new Exception("Preveč podatkov na datoteki");
                        tab[indeks] = stevilo;
                        indeks++;
                    }
                    else
                        throw new Exception("Napačni podatki v datoteki");
                }
            }
            if (indeks != 12)
                throw new Exception("Premalo podatkov na datoteki");

            // zapri datoteko
            branje.Close();

            return StevilskeDomine(tab);
        }

        public static Random generator = new Random();

        static void Main(string[] args)
        {
            #region Nakljucni podatki
            Console.WriteLine("************ Naključna tabela ************");
            Console.WriteLine();

            int[] nak = new int[12];
            int st;

            for (int i = 0; i < 12; i++)
            {
                st = generator.Next(1, 50);
                nak[i] = st;
            }

            Console.Write("Naključna tabela : ");
            Console.WriteLine(Knj.TabelaVNiz(nak));
            Console.WriteLine();
            try
            {
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(nak));
            }
            catch (Exception e)
            {
                Console.WriteLine("Napaka: " + e.Message);
            }
            Console.WriteLine();

            #endregion

            Console.WriteLine();
            Console.WriteLine("************ Še nekaj tabel ************");
            Console.WriteLine();

            #region Primeri nekaj tabel

            // ce so vsi elementi enaki
            int[] tab1 = new int[] { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 };
            Console.WriteLine("Tabela : " + Knj.TabelaVNiz(tab1));
            try
            {
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(tab1));
            }
            catch (Exception e)
            {
                Console.WriteLine("Napaka: " + e.Message);
            }
            Console.WriteLine();

            // ce je v seznamu 1
            int[] tab2 = new int[] { 1, 15, 21, 7, 1, 2, 13, 18, 9, 3, 7, 5 };
            Console.WriteLine("Tabela : " + Knj.TabelaVNiz(tab2));
            try
            {
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(tab2));
            }
            catch (Exception e)
            {
                Console.WriteLine("Napaka: " + e.Message);
            }
            Console.WriteLine();

            // ce so sama tuja stevila
            int[] tab3 = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
            Console.WriteLine("Tabela : " + Knj.TabelaVNiz(tab3));
            try
            {
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(tab3));
            }
            catch (Exception e)
            {
                Console.WriteLine("Napaka: " + e.Message);
            }
            Console.WriteLine();

            // izmišljen primer
            int[] tab4 = new int[] { 12, 32, 23, 12, 4, 7, 56, 9, 3, 10, 3, 5 };
            Console.WriteLine("Tabela : " + Knj.TabelaVNiz(tab4));
            try
            {
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(tab4));
            }
            catch (Exception e)
            {
                Console.WriteLine("Napaka: " + e.Message);
            }
            Console.WriteLine();

            // Prazna tabela
            int[] tab5 = new int[] { };
            Console.WriteLine("Tabela : " + Knj.TabelaVNiz(tab5));
            try
            {
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(tab5));
            }
            catch (Exception e)
            {
                Console.WriteLine("Napaka: " + e.Message);
            }
            #endregion

            Console.WriteLine();
            Console.WriteLine("************ Datoteke ************");
            Console.WriteLine();

            #region Napake na datotekah
            Console.WriteLine("Prva datoteka");
            try
            {
                string dat1 = Environment.CurrentDirectory + "\\d1.txt";
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(dat1));
            }
            catch (Exception e)
            {
                Console.WriteLine("Napaka: " + e.Message);
            }
            Console.WriteLine();

            // premalo podatkov
            Console.WriteLine("Druga datoteka");
            try
            {
                string dat2 = Environment.CurrentDirectory + "\\d2.txt";
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(dat2));
            }
            catch (Exception e)
            {
                Console.WriteLine("Napaka: " + e.Message);
            }
            Console.WriteLine();

            // preveč podatkov
            Console.WriteLine("Tretja datoteka");
            try
            {
                string dat3 = Environment.CurrentDirectory + "\\d3.txt";
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(dat3));
            }
            catch (Exception e)
            {
                Console.WriteLine("Napaka: " + e.Message);
            }
            Console.WriteLine();

            //napačni podatki
            Console.WriteLine("Četrta datoteka");
            try
            {
                string dat4 = Environment.CurrentDirectory + "\\d4.txt";
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(dat4));
            }
            catch (Exception e)
            {
                Console.WriteLine("Napaka: " + e.Message);

            }
            Console.WriteLine();
            #endregion

            Console.WriteLine();
            Console.WriteLine("************ Vnos datoteke ************");
            Console.WriteLine();

            #region Primer v navodilih - vnašanje datoteke
            Console.Write("Vnesi ime datoteke : ");
            string dat = Console.ReadLine();

            try
            {
                Console.WriteLine("Najdaljšo kačo sestavljajo števila : " + StevilskeDomine(dat));
            }
            catch (Exception ee)
            {
                Console.WriteLine(ee.Message);
            }
            #endregion

            Console.ReadKey();


        }
    }
}

Pomožne funkcije

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

namespace Knjiznica
{
    public class Knj
    {
        /// <summary>
        /// Vrne najvecji skupni delitelj stevil a in b
        /// </summary>
        /// <param name="a">prvo stevilo</param>
        /// <param name="b">drugo stevilo</param>
        /// <returns></returns>
        public static int GCD(int a, int b)
            /* Evklidov algoritem*/
        {
            // a mora biti vecji ali enak b
            if (a < b)
            {
                int pom = a;
                a = b;
                b = pom;
            }
            if (b == 0) return a;
            return GCD(b, a % b);

        }

        /// <summary>
        /// Vrne true, ce sta stevili a in b tuji, sicer vrne false
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static bool TujiStevili(int a, int b)
        /*najvecji skupni delitelj je 1*/
        {
            return GCD(a, b)==1;
        }

        /// <summary>
        /// Iz tabele celih števil naredi in vrne niz
        /// </summary>
        /// <param name="tab">Tabela celih števil</param>
        /// <returns>Vrne tabelo izpisano v nizu</returns>
        public static string TabelaVNiz(int[] tab)
        {
            string niz = "";
            for (int i = 0; i < tab.Length; i++)
            {
                if (i != 0)
                    niz += ", ";
                niz += tab[i].ToString();
            }
            return niz;
        }
    }
}

Razlaga algoritma

Imamo dve podobni funkciji:

  • static string StevilskeDomine(int[] tab)
  • static string StevilskeDomine(string imeDatoteke)

Prva funkcija dobi za parameter tabelo celih števil, vrne pa niz najdaljšega zaporedja netujih števil.

Druga funkcija dobi za parameter datoteko, ki jo prebere. Podatke z datoteke napiše v tabelo (če so ustrezni seveda) in na koncu pokliče prvo funkcijo in vrne niz, ki ga prva funkcija vrne.



Prva funkcija


Druga funkcija

Prva funkcija

V prvi funkciji imamo torej dano tabelo. Definiramo še dva seznama:

  • Seznam trenutne kače
  • Seznam do sedaj najdaljše najdene kače Oba seznama sta na začetku prazna.

Nato gremo po indeksih dane tabele:

  • v seznam trenutnih damo najprej element iz tabele, ki ima trnutni indeks.

  • Še ena zanka po indeksih tabele, od prejšnjega trenutnega dalje:

    • Če sta zadnji element trenutnega seznama in trenutni element tabele tuji števili, damo v seznam trenutne kače trenutni element tabele
  • Ko pretečemo vse notranje indekse preverimo še, če je trenutna kača daljša od do sedaj najdaljše shranjene. V tem primeru shranimo v seznam do sedaj najboljše trenutno kačo
  • Seznam s trenutno rešitvijo moramo še izprazniti pred naslednjim korakom zunanje zanke

Na koncu moramo še iz seznama najdaljše kače tujih števil števila prepisati v niz in ga vrniti.

Druga funkcija

V drugi funkciji je bistveno branje z datoteke. V tej funkciji preverjamo podatke z datoteke in vržemo ustrezne izjeme, ko naletimo na nepravilnosti. Če je vse v redu, potem shranimo števila v tabelo in s klicem prve funcije dobimo niz z najdaljšim zaporedjem ne tujih si števil.

  • Najprej preverimo, če datoteka sploh obstaja, in vržemo izjemo, če ne.
  • Nato odpremo datoteko za branje. Nastavimo indeks elementa v tabeli na 0 in definiramo pomožno tabelo nizov, kamor bomo shranili različna števila shrnajena v posamezni vrstici.
  • Beremo datoteko po vrsticah. V pomožno tabelo shranimo različne podatke v vrstici. Podatke ločimo z ukazom split.

  • Nato gremo po vseh elementih tega seznama.

    • Če je element prazen niz, ga ignoriramo.
    • Če lahko element, ki je niz, pretvorimo v celo število, potem ga dodamo v tabelo in povečamo indeks Še prej preverimo, če je indeks že 12. V tem primeru je podatkov na datoteki preveč in vržemo ustrezno izjemo.
    • Sicer vržemo izjemo, saj so v tem primeru podatki napačni (niz,...)
  • Zunaj vseh zank preverimo, če je mogoče indeks različen od 12. V tem primeru imamo na datoteki premalo podatkov in vržemo izjemo.
  • Še zapremo datoteko za branje in vrnemo rezultat s klicem prve funkcije.

Testni primeri

V testni funkciji najprej preverjamo na nekaj tabelah, če nam funkcija vrača pravilne rezultate.

Preverjamo naslednje tabele:

  • Najprej preverimo, če deluje pravilno na neki naključni tabeli 12 celih pozitivnih števil, manjših od 50.

  • Nadaljujemo s preverjanjem na nekaj že vnešenih tabelah:

    • Tabela samih enakih števil ( v našem primeru tabela dvanajstih 2 ). Rezultat mora biti kar cela tabela.
    • Če je v tabeli število 1. Število 1 je po definiciji tuje vsem celim številom. Torej 1 ne sme biti del najdaljšega zaporedja ne tujih števil.
    • Rezultat tabele samih tujih števil mora biti rezultat prazen.
    • Preverimo tudi na nekem izmišljenem primeru.
    • Če je tabela prazna, nam mora program sporočiti napako.

Nato sledijo testi na datotekah.

  • Prva datoteka preverja 12 števil zapisanih na datoteki. Nekatera števila so ločena s presledkom, nekatera pa so v novih vrsticah. Nekaj vrstic je vmes tudi praznih. Rezultat naj bi bil enak izmišljenem primeru ( ki smo ga preverjali na tabelah )
  • Druga datoteka ima shranjenih premalo števil in bi se morala sprožiti izjema.
  • Klic funkcije na tretji datoteki mora javiti napako o preveč številih shranjenih na datoteki.
  • Četrta datoteka ima shranjene neke čudne podatke (črke). Klic funkcije na tej datoteki javi napako o tem.

Na koncu lahko še poiščemo najdaljšo kačo ne tujih si števil na poljubni datoteki, tako da vnesemo pot datoteke in ime v konzolo in nam vrne rezultat.

Viri

0%
0%