Matematické Fórum

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

//Tato třída umožňuje uchovávat libovolně dlouhá čísla a implementuje některé operace s nimi. Číslo je interně uloženo jako spojový seznam uzlů, obsahujících fragmenty čísla o velikostech 0 - 999999.
//Jednotlivé fragmenty jsou spojeny ve směru od nejméně významného k nejvýznamnějšímu.
namespace VelkaCisla
{
    class VelkeCislo
    {
        public static int MAXVALUE = 999999; //maximální povolená velikost čísla v jednom kusu
        public static int MAXFAKTOR = 1000000; //Vlastně maximální počet načtených cifer; musí mít stejný počet nul jako MAXVALUE ve třídě KusČísla.
        public static int LENGTH = 6; //délka fragmentu čísla
        
        KusCisla cislo;

        public VelkeCislo() //konstruktor - vytvoří dlouhé číslo o velikosti 0
        {
            cislo = new KusCisla(0);
        }

        private VelkeCislo(KusCisla retezecKusuCisel) //privátní konstruktor pro vracení výsledků sčítání a násobení
        {
            cislo = retezecKusuCisel;
        }

        private bool JeCislice(int znak) //Signalizuje, zda je předávaný znak číslice či nikoliv.
        {
            return ((znak >= (int)'0')&&(znak <= (int)'9'));
        }
        
        public VelkeCislo(string retezec) //konstruktor – načte velké číslo ze vstupního řetězce
        {
            cislo = null;
            KusCisla poziceVCisle = null;
            int znak = 0;
            int nacteneCislo = 0;
            int faktor = 1; //hodnota, kterou se bude aktuálně zpracovávaná cifra násobit, aby byla umístěna na správnou pozici
            for (int i = retezec.Length - 1; i >= 0; i--) 
            {
                znak = retezec[i];
                if (JeCislice(znak)) //Pokud je načtený znak číslice, vlož jej do budovaného čísla. Jakmile je načteno dost číslic, vytvoř nový kus čísla a přidej ho na konec stávajícího.
                {
                    nacteneCislo += ((znak - (int)'0') * faktor); //Číslo je budováno ve směru odzadu dopředu.
                    faktor *= 10; //Aktuální faktor je vynásoben 10, aby byla příští číslice v načteném číslu umístěna před dosavadní.
                    if ((i == 0) || (faktor == MAXFAKTOR)) //Pokud byl dosažen konec řetězce nebo bylo načteno číslo o maximální povolené velikosti.
                    {
                        if (cislo == null) //Pokud nebyl doposud načten žádný kus čísla:
                        {
                            cislo = new KusCisla(nacteneCislo);
                            poziceVCisle = cislo; //Inicializuj ukazatel na aktuálně poslední kus čísla.
                        }
                        else //Pokud už nějaký kus čísla načten byl:
                        {
                            poziceVCisle.dalsiKus = new KusCisla(nacteneCislo); //Vytvoř další kus čísla a připoj jej ke stávajícímu řetězci.
                            poziceVCisle = poziceVCisle.dalsiKus; //Přejdi na nový poslední kus čísla.
                        }
                        //Nyní znovuinicializuj všechny pomocné hodnoty.
                        nacteneCislo = 0;
                        faktor = 1;
                    }
                }
                else throw new InvalidOperationException("Neplatný vstup."); //Jinak vyhoď výjimku.
            }
        }

        public string VratCislo() //Vrátí číslo uložené v instanci. Jde na to tak, že nejprve projde celý řetězec kusů čísla od začátku do konce, přičemž reference na jednotlivé kusy odkládá do zásobníku.
        {                        //Poté celý zásobník vysype a pro každý kus vloží jeho číslici do stringu, který nakonec vrátí.
            KusCisla aktualniPozice = cislo;
            Stack<KusCisla> zasobnikReferenci = new Stack<KusCisla>();
            do
            {
                zasobnikReferenci.Push(aktualniPozice); //Vlož aktuální pozici do zásobníku...
                aktualniPozice = aktualniPozice.dalsiKus; //...a přejdi na další.
            } while (aktualniPozice != null);
            string cisloKVraceni = "";
            string pripojovaneCislo;
            bool prvniKusHotov = false; //U prvního fragmentu čísla se nebudou přidávat nuly.
            while (zasobnikReferenci.Count != 0) //Dokud zásobník není prázdný:
            {
                aktualniPozice = zasobnikReferenci.Pop(); //Vyjmi číslo ze zásobníku...
                pripojovaneCislo = aktualniPozice.cifry.ToString(); //...a ulož jeho cifru do výstupního řetězce.
                if (prvniKusHotov)
                {
                    while (pripojovaneCislo.Length != LENGTH) //Dokud není připojované číslo dostatečně dlouhé:
                    {
                        pripojovaneCislo = "0" + pripojovaneCislo;
                    }
                }
                cisloKVraceni += pripojovaneCislo;
                prvniKusHotov = true;
            }
            return cisloKVraceni;
        }

        public void VypisCislo() //Vypíše pomocí metody VratCislo číslo v instanci na výstup.
        {
            string cisloKVytisknuti = this.VratCislo();
            Console.Write(cisloKVytisknuti);
        }

        public static VelkeCislo operator + (VelkeCislo a, VelkeCislo b) //Sečte dvě čísla a vrátí výsledek.
        {
            int vkladanaHodnota = 0; //Hodnota vkládaná do aktuálního kusu výsledku.
            int prenos = 0; //Přenos do "vyššího řádu", tj. hodnota, která se přičte do vyššího kusu čísla výsledku.
            KusCisla vysledek = new KusCisla(0); //hlava výsledku; na konci bude odříznuta
            KusCisla aktPozVeVysledku = vysledek; //aktuální pozice ve výsledku
            KusCisla aktPozVA = a.cislo; KusCisla aktPozVB = b.cislo; //akutální pozice ve sčítancích
            while ((aktPozVA != null) && (aktPozVB != null))
            {
                vkladanaHodnota = aktPozVA.cifry + aktPozVB.cifry + prenos;
                if (vkladanaHodnota > MAXVALUE) //Pokud bude vkládaná hodnota do prvku větší než maximální povolená:
                {
                    prenos = vkladanaHodnota / MAXFAKTOR; //Je uložen přenos do vyššího řádu...
                    vkladanaHodnota %= MAXFAKTOR; //... a prvních šest cifer vypočtené hodnoty k vložení uloženo pro vytvoření nového prvku.
                }
                else prenos = 0;
                aktPozVeVysledku.dalsiKus = new KusCisla(vkladanaHodnota);
                //Posun na další pozici:
                aktPozVeVysledku = aktPozVeVysledku.dalsiKus;
                aktPozVA = aktPozVA.dalsiKus;
                aktPozVB = aktPozVB.dalsiKus;
            }
            while (aktPozVA != null) //Pokud jsem ještě nedošel na konec prvního čísla:
            {
                vkladanaHodnota = aktPozVA.cifry + prenos;
                if (vkladanaHodnota > MAXVALUE) //Pokud bude vkládaná hodnota do prvku větší než maximální povolená:
                {
                    prenos = vkladanaHodnota / MAXFAKTOR; //Je uložen přenos do vyššího řádu...
                    vkladanaHodnota %= MAXFAKTOR; //... a prvních šest cifer vypočtené hodnoty k vložení uloženo pro vytvoření nového prvku.
                }
                else prenos = 0;
                aktPozVeVysledku.dalsiKus = new KusCisla(vkladanaHodnota);
                //Posun na další pozici:
                aktPozVeVysledku = aktPozVeVysledku.dalsiKus;
                aktPozVA = aktPozVA.dalsiKus;
            }
            while (aktPozVB != null) //Pokud jsem ještě nedošel na konec druhého čísla:
            {
                vkladanaHodnota = aktPozVB.cifry + prenos;
                if (vkladanaHodnota > MAXVALUE) //Pokud bude vkládaná hodnota do prvku větší než maximální povolená:
                {
                    prenos = vkladanaHodnota / MAXFAKTOR; //Je uložen přenos do vyššího řádu...
                    vkladanaHodnota %= MAXFAKTOR; //... a prvních šest cifer vypočtené hodnoty k vložení uloženo pro vytvoření nového prvku.
                }
                else prenos = 0;
                aktPozVeVysledku.dalsiKus = new KusCisla(vkladanaHodnota);
                //Posun na další pozici:
                aktPozVeVysledku = aktPozVeVysledku.dalsiKus;
                aktPozVB = aktPozVB.dalsiKus;
            }
            while (prenos != 0)
            {
                aktPozVeVysledku.dalsiKus = new KusCisla(prenos);
                aktPozVeVysledku = aktPozVeVysledku.dalsiKus;
                prenos = vkladanaHodnota / MAXFAKTOR; //Je uložen přenos do vyššího řádu...
            }
            vysledek = vysledek.dalsiKus; //zahození hlavy výsledku
            return new VelkeCislo(vysledek);
        }

        private static VelkeCislo NasobCislici(VelkeCislo a, int nasobitel, int oKolik) //Vynásobí daný řetězec kusů čísel zadanou číslicí. Zadaná číslice musí být nutně jednociferná!
        {                                                                               //Dále posune dané číslo doleva o zadaný počet pozic. Tato operace odpovídá násobení čísla pomocí 10^počet pozic.
            StringBuilder vysledek = new StringBuilder();
            StringBuilder pridavaneNuly = new StringBuilder(""); //Posun doleva je realizován přidáním odpovídajícího počtu nul na konec výsledného čísla.
            for (int i = 0; i < oKolik; i++) //vytvoření řetězce nul požadované délky
            {
                pridavaneNuly.Append('0');
            }
            vysledek.Append(pridavaneNuly);
            string nasobenec = a.VratCislo();
            int vkladaneCislo = 0;
            int prenos = 0; //Přenos do "vyššího řádu", tj. hodnota, která se přičte do vyššího kusu čísla výsledku.
            for (int i = nasobenec.Length - 1; i >= 0; i--) //Výpočet výsledku; obsah však bude v opačném pořadí.
            {
                vkladaneCislo = (((int)nasobenec[i] - (int)'0') * nasobitel) + prenos;
                if (vkladaneCislo > 9)
                {
                    prenos = vkladaneCislo / 10;
                    vkladaneCislo %= 10;
                }
                else prenos = 0;
                vysledek.Append(vkladaneCislo);
            }
            while (prenos != 0) //Přidání zbylého obsahu přenosu.
            {
                vkladaneCislo = prenos % 10;
                vysledek.Append(vkladaneCislo);
                prenos /= 10;
            }
            StringBuilder otocenyVysledek = new StringBuilder("");
            for (int i = vysledek.Length - 1; i >= 0; i--) //otočení výsledku
            {
                otocenyVysledek.Append(vysledek[i]);
            }
            
            return new VelkeCislo(otocenyVysledek.ToString());
        }

        public static VelkeCislo operator * (VelkeCislo a, VelkeCislo b) //Vynásobí dvě čísla a vrátí výsledek. Jde na to tak, že 
        {
            VelkeCislo vysledek = new VelkeCislo();
            string nasobitel = b.VratCislo(); //načtení násobitele z instance VelkéhoČísla b
            VelkeCislo vysledekNasobeniJednouCifrouNasobitele; //Zde budou uloženy výsledky jednotlivých elementárních násobení násobence jednotlivými ciframi násobitele.
            int posun = 0; //počet pozic, o které se má aktuální mezivýsledek posunout
            for (int i = nasobitel.Length - 1; i >= 0; i--) //Procházej násobitele odzadu:
            {
                vysledekNasobeniJednouCifrouNasobitele = NasobCislici(a, (int)nasobitel[i] - (int)'0', posun++);
                vysledek += vysledekNasobeniJednouCifrouNasobitele;
            }
            return vysledek;
        }
    }
    
    class KusCisla
    {
        public static int MAXVALUE = 999999; //maximální povolená velikost čísla v jednom kusu
        public static int MAXFAKTOR = 1000000; //Vlastně maximální počet načtených cifer; musí mít stejný počet nul jako MAXVALUE ve třídě KusČísla.
        
        public int cifry;
        public KusCisla dalsiKus;

        public KusCisla(int aJehoObsah) //konstruktor; pokud je předávaná hodnota větší než MAXVALUE, je automaticky vytvořen další uzel s oříznutým zbytkem čísla
        {
            if (aJehoObsah <= MAXVALUE)
            {
                cifry = aJehoObsah;
                dalsiKus = null;
            }
            else //Prvních čest cifer je uloženo do právě vytvářené instance; na zbytek je zavolán tento konstruktor; výsledek je uložen jako následník uzlu.
            {
                cifry = aJehoObsah % MAXFAKTOR; //Toto mi uřízne prvních 6 cifer.
                dalsiKus = new KusCisla(aJehoObsah / MAXFAKTOR);
            }
        }
    }
    
    class Program
    {
        static void Main(string[] args)
        {
            VelkeCislo A = new VelkeCislo("147258369147258369147258369147258369147258369147258369147258369147258369123456789123456789123456789123456789");
            A.VypisCislo();
            Console.WriteLine();
            VelkeCislo B = new VelkeCislo("147258369147258369147258369147258369147258369147258369147258369147258369123456789123456789123456789123456789");
            B.VypisCislo();
            Console.WriteLine();
            VelkeCislo vysledekScitani = A + B;
            vysledekScitani.VypisCislo();
            Console.WriteLine();
            VelkeCislo vysledekNasobeni = A * B;
            vysledekNasobeni.VypisCislo();
            Console.WriteLine();
            Console.Read();
        }
    }
}