Sčítání libovolně velkých čísel v C# .NET

C# .NET Kolekce a LINQ Sčítání libovolně velkých čísel v C# .NET

Napadlo vás někdy, jak by se sčítalo číslo větší než datové typy? Třeba takových 80 miliard nebo ještě víc? V tomto případě můžeme použít datovou strukturu BigInt, jenž reprezentuje nekonečně veliké číslo.

My si za účelem procvičování zkusíme použít metodu LSS k ukládání čísel jako jednotlivé cifry. Tuto metodu v praxi nepoužívejte, slouží pouze k procvičení programování a myšlení.

Velké přirozené číslo budeme v programu reprezentovat jako seznam. Např.: 879653 by v seznamu vypadalo takto: 8;7;9;6;5;3

V tutoriálu si nejen procvičíme používání Listu<>, cyklů a parsování, ale také StreamReader a to proto, že program bude načítat čísla z textového souboru. Tak se pořádně připoutejte a jdeme na to!

Nejdříve musíme přidat jmenný prostor pro práci se soubory System.IO. IO znamená Input-Output. Náš kód by měl vypadat nějak takto:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

Díky tomuto řádku budeme moci používat například StreamReader pro načítání textových souborů nebo třeba StreamWriter pro jejich zápis.

Aby kód vypadal přehledněji, vytvoříme metodu pro načtení čísel ze souboru a druhou metodu pro sečtení čísel a následný výpis. V metodě Main pouze zavoláme tyto metody.

1) Příprava

Než začneme, deklarujeme si nějaké proměnné mimo metodu Main, aby se nacházely v třídním oboru platnosti

static List<int> cislo1 = new List<int>();
static List<int> cislo2 = new List<int>();
static List<int> vysledek = new List<int>();

List je vlastně dynamické pole (počet jeho prvků není pevný) a jelikož nevíme o jak velké číslo půjde, je to asi nejjednodušší volba.

Dále si vytvoříme v počítači obyčejný textový soubor a napíšeme do něj dvě čísla, každé na jiný řádek.

2) Načítání ze souboru

Vytvoříme si statickou metodu Nacti(), která nemá žádný parametr.

static void Nacti()
{

}

Uvnitř metody vytvoříme blok pro práci se soubory:

using(StreamReader sr = new Streamreader(***));
{
}

Using označuje vnořený blok v němž používáme StreamReader. Mezi jeho složenými závorkami je kód, ve kterém načítáme soubory. Po ukončení kódu mezi závorkami se StreamReader ukončí.

*** - cesta k souboru s textem, např.: @"C:\temp\text.txt"

Zavináč nám ve stringu „vypíná“ escape sekvence. Pokud bychom ho nechtěli použít, museli bychom místo každého \ napsat \\.

Do bloku using vložíme následující kód, který si hned vysvětlíme:

//Pomocná proměnná
int c;
//Cyklus načítá do cislo1 dokud nenarazí na konec řádku nebo souboru
while ((c = sr.Read()) != 13 && c != -1)
{
    //Převod na hodnotu (ne ASCII)
    c = (int)Char.GetNumericValue((char)c);
    //Přidání do seznamu
    cislo1.Add(c);

}
//Přeskočení hodnoty 10
sr.Read();

//Cyklus totožný s prvním, ale načítá do cislo2
while ((c = sr.Read()) != 13 && c != -1)
{

    c = (int)Char.GetNumericValue((char)c);

    cislo2.Add(c);

}

c je pomocná proměnná, do které zapisujeme hodnotu přečteného znaku (hodnoty jsou z ASCII tabulky).

Následuje cyklus while, který probíhá tak dlouho, jak platí podmínka.

Do c přiřadíme znak, poté se zeptáme, zdali se c nerovná 13 (na konci řádku jsou vždy 2 netisknutelné znaky a to: 13 10) nebo -1 (sr.Read() vrací -1 pokud se dostane na konec souboru).

Teď nám ovšem nastává problém. Proměnná c je celé číslo a my celé číslo potřebujeme, ale toto celé číslo neukazuje hodnotu, ale číslo znaku v tabulce ASCII.

Proto musíme na proměnnou c přetypovanou na char použít metodu Char.GetNumeric­Value(), jenž nám vrátí hodnotu čísla a tu teprve poté přetypovat na int. Vím, že to pro někoho může znít složitě, ale pokud se nad tím zamyslíte, vezmete si papír a tužku a načrtnete si to, uvidíte, že je to velmi jednoduché.

A teď nám už jen zbývá zapsat číslo do seznamu.

Po proběhnutí prvního cyklu je celé číslo zapsáno v seznamu znak po znaku a cyklus narazí na číslo 13 (což je znak konce řádku), které nezapíše a ukončí se.

sr.Read(); nám přečte další znak a to 10, kterou chceme pouze přeskočit a tak ji nikam nezapisujeme.

Nakonec ještě opakujeme stejný cyklus, jenom zapisujeme cislo2.

3) Sčítání

Vytvoříme si statickou metodu Secti():

static void Secti()
{
    //Rozdíl v počtu prvků jednotlivých polí
    int rozdil = Math.Abs(cislo1.Count - cislo2.Count);

    //Přidávání 0 na začátek
    if (cislo1.Count > cislo2.Count)
    {
        for (int j = 0; j < rozdil; j++)
        {
            cislo2.Insert(0, 0);
        }
    }
    //Přidávání 0 na začátek
    else if (cislo2.Count > cislo1.Count)
    {
        for (int j = 0; j < rozdil; j++)
        {
            cislo1.Insert(0, 0);

        }
    }

    //Zápis do stringů (jenom kvůli výpisu)
    string c1 = string.Join("", cislo1);
    string c2 = string.Join("", cislo2);

    //Výpis
    Console.WriteLine("{0,60}",c1.TrimStart('0'));

    Console.WriteLine("{0,60}",c2.TrimStart('0'));


    for (int i = 0; i < 65; i++)
        Console.Write("=");




    //Výpočet výsledku
    int zbytek = 0;
    List<int> vysledek = new List<int>();

    //cyklus sčítající jednotlivé prvky a přičítající zbytek
    for (int i = 1; i <= cislo1.Count; i++)
    {
        //Sečte čísla nad sebou a přidá zbytek
        int cislo = cislo1[cislo1.Count - i] + cislo2[cislo2.Count - i] + zbytek;
        //Zbytek je vynulován
        zbytek = 0;

        //Při sčítání dvou jednociferných čísel nemůžeme dostat číslo větší než 18,
        //proto nemusíme řešit zbytek větší než 1
        if (cislo >= 10)
        {
            zbytek = 1;
            cislo -= 10;
        }
        //Vložení čísla na začátek seznamu
        vysledek.Insert(0, cislo);

    }
    //Pokud při posledním číslu by byl zbytek, napíše ho jako první
    if (zbytek != 0)
    {
        vysledek.Insert(0, zbytek);
    }

    //Výpis výsledku
    string vys = string.Join("", vysledek);
    Console.WriteLine("\n{0,60}",vys);

}

Vytvoříme si proměnnou rozdil, do které zapíšeme absolutní hodnotu rozdílu počtu prvků v obou číslech.

Např. 125 - 3 cifry, 22568 - 5 cifer, rozdil = |3-5| = 2

Udělali jsme to proto, abychom věděli kolik 0 před které číslo přidělat. Chceme oba seznamy stejně dlouhé, abychom je procházeli jedním jednoduchým cyklem.

Následují 2 podmínky pro zjištění kratšího seznamu a doplnění 0 na jeho začátek.

Následně vytvoříme dvě proměnné typu string a zapíšeme do nich seznam pomocí metody string.Join(), oddělovač nastavíme na prázdný znak, protože chceme číslo v jednom kuse.

Řetězce vypíšeme zarovnané na 60 míst (kvůli velkým číslům)

Poté napíšeme velké množství "=" pro vytvoření dělící čáry na obrazovce.

Následuje asi nejzáživnější část a tou je výpočet. Vytvoříme si proměnnou pro zapisování zbytku a nový seznam pro výsledek.

Postup počítání je dostatečně popsán v kódu a tak zrovna přeskočíme do metody Main(), čímž se chýlíme ke konci.

V metodě Main jenom jednoduše zavoláme metody a poté použijeme Console.ReadLine(), ať se nám program sám neukončí.

static void Main(string[] args)
{

    Nacti();
    Secti();
    Console.ReadLine();
}

Nyní stačí jen spustit a uvidíte, jak jste tuhle lekci zvládli :)

Pokud by byly nějaké otázky, napište do komentářů nebo zprávu.

PS. Pro procvičení si můžete program zkusit přepsat pro načítání čísel ze vstupu nebo třeba vytvořit násobení.


 

Stáhnout

Staženo 52x (33.88 kB)
Aplikace je včetně zdrojových kódů v jazyce C#

 

  Aktivity (1)

Článek pro vás napsal konecnyj96
Avatar
Autor se věnuje programování v C# a C++. Občas si také pohraje s Unity nebo Blenderem

Jak se ti líbí článek?
Celkem (1 hlasů) :
55555


 


Miniatura
Všechny články v sekci
Kolekce v C# .NET a LINQ

 

 

Komentáře

Avatar
lastp
Redaktor
Avatar
lastp:

Zkusil jsem sečíst čísla dlouhá milion číslic a trvalo to 5 minut. Když jsem řádek vysledek.Insert(0, cislo) změnil na vysledek.Add(cislo) a zároveň jsem za for cyklus přidal příkaz vysledek.Reverse(), potom sčítání trvalo jen půl sekundy (když nepočítám dobu výpisu do konzole).

 
Odpovědět  +3 14.12.2014 12:19
Avatar
prokop.mejstrik:

Luxusní článek, přesně takovéhle, kde je nějaký příklad (ne jen teorie) a vše je podrobně vysvětleno mi dají nejvíce. Jen je zde malá chyba:

using(StreamReader sr = new Streamreader(***));
{
}

by neměl být ten středník :)

 
Odpovědět 11. srpna 15:51
Avatar
roman_8253
Člen
Avatar
roman_8253:

Pekny clanek.
Pouziti genericke kolekce List<T> pro takovy trivialni ukol je trosku moc. Stacilo by pole a vypocet by se jeste zrychlil.

 
Odpovědět 13. srpna 15:05
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 3 zpráv z 3.