Odczyt z pliku, wielkie liczby

Question

Otóż zmagam się z ćwiczeniem 4   http://www.algorytm.edu.pl/pliki-cwiczenia.html

Tu liczby http://www.algorytm.edu.pl/images/zadania/suma_cyfr.txt

Niektóre z tych liczb są tak duże, że funkcje takie jak atoi czy atol ich nie ogarniają. Więc postanowiłem wymyślić inny sposób.

To jest pierwsze moje rozwiązanie, które owszem działa, ale tylko jak wpiszę własne, niezbyt duże liczby do pliku dane.txt

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

int main()
{
    int liczby[100001]; 
	/* o 1 wiecej bo zaczynam zapisywac liczby od szufladki o indeksie 1, a nie 0,
	wiec 100 tysieczna liczba bedzie w szufladce o indeksie 100000, a gdybym napisal liczby[100000] to indeks ostatniego elementu bylny rowny 999999
	odwolywalbym sie zatem do niezarezerwowanego obszaru w pamieci RAM i spowodowal blad krytyczny*/
    
    cout << "Dla ilu liczb chcesz policzyc sume ich cyfr? (maksimum 100000)\n";
    int ile;
    cin >> ile;

    while(ile>100000)
	{
        cout << "Nie ma tylu liczb w pliku. Podaj jeszcze raz\n";
        cin >> ile;
	}

    fstream plik;

    plik.open("dane.txt", ios::in);

    string linia;
    short nr_linii=1, ktora=0;

    while(getline(plik,linia))
	{
        switch(nr_linii)
        {
            case 1: cout << "";                          break;
            case 2: liczby[ktora] = atol(linia.c_str()); break;
			case 3: liczby[ktora] = atol(linia.c_str()); break;
        }
        ktora++;
        nr_linii++;
        if(nr_linii==4)
            nr_linii=2;
	}

    plik.close();

    fstream plik2;
    int x,reszta,suma_cyfr=0;

    plik2.open("wynik.txt", ios::out);
    for(int i=1; i<=ile; i++)
	{

        while(liczby[i]>=10)
        {
			reszta = liczby[i] % 10;
			x = liczby[i] - reszta;
			liczby[i] = x/10;
			suma_cyfr = suma_cyfr + reszta;
        }
        plik2 << suma_cyfr+liczby[i] << endl;
        suma_cyfr=0; //Wazne! Trzeba wyzerowac sume cyfr na koniec petli!
	}
    plik2.close();

    cout << "Dane zostaly zapisane do pliku wynik.txt\n";
    system("pause");
    return 0;
}

Potem wpadłem na inny pomysł, który pozwolił mi na odczyt z pliku tekstowego każdej cyfry danej liczby, a potem za pomocą pętli for sklejenie z tych cyferek liczby.

Biorąc pod uwagę wielkość liczb stąd http://www.algorytm.edu.pl/images/zadania/suma_cyfr.txt to typ unsigned long long int powinien je spokojnie pomieścić.

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

int main()
{
    unsigned long long int liczby[100001]; 
	/* o 1 wiecej bo zaczynam zapisywac liczby od szufladki o indeksie 1, a nie 0,
	wiec 100 tysieczna liczba bedzie w szufladce o indeksie 100000, a gdybym napisal liczby[100000] to indeks ostatniego elementu bylny rowny 999999
	odwolywalbym sie zatem do niezarezerwowanego obszaru w pamieci RAM i spowodowal blad krytyczny*/
    cout << "Dla ilu liczb chcesz policzyc sume ich cyfr? (maksimum 100000)\n";
    int ile;
    cin >> ile;

    while(ile>100000)
    {
        cout << "Nie ma tylu liczb w pliku. Podaj jeszcze raz\n";
        cin >> ile;
    }

    fstream plik;

    plik.open("dane.txt", ios::in);

    string linia;
    short nr_linii=1, ktora=0;

    while(getline(plik,linia))
    {
        switch(nr_linii)
        {
        case 1:
            cout << "";
            break;
        case 2:
        {
            int *cyfry;
            int rozmiar = linia.length();
            cyfry = new int [rozmiar];

            for(int k=0; k<rozmiar; k++)
            {
                switch(linia[k])
                {
					case '0': cyfry[k]=0; break;
                    case '1': cyfry[k]=1; break;
                    case '2': cyfry[k]=2; break;
                    case '3': cyfry[k]=3; break;
                    case '4': cyfry[k]=4; break;
                    case '5': cyfry[k]=5; break;
                    case '6': cyfry[k]=6; break;
                    case '7': cyfry[k]=7; break;
                    case '8': cyfry[k]=8; break;
                    case '9': cyfry[k]=9; break;
                }
            }
            liczby[ktora] = 0;
            for(int k=0; k<rozmiar; k++)
                liczby[ktora] = liczby[ktora]*10 + cyfry[k];

            delete [] cyfry;
        }
            break;
        case 3:
        {
            int *cyfry;
            int rozmiar = linia.length();
            cyfry = new int [rozmiar];

            for(int k=0; k<rozmiar; k++)
            {
                switch(linia[k])
                {
					case '0': cyfry[k]=0; break;
                    case '1': cyfry[k]=1; break;
                    case '2': cyfry[k]=2; break;
                    case '3': cyfry[k]=3; break;
                    case '4': cyfry[k]=4; break;
                    case '5': cyfry[k]=5; break;
                    case '6': cyfry[k]=6; break;
                    case '7': cyfry[k]=7; break;
                    case '8': cyfry[k]=8; break;
                    case '9': cyfry[k]=9; break;
                }
            }
            liczby[ktora] = 0;
            for(int k=0; k<rozmiar; k++)
                liczby[ktora] = liczby[ktora]*10 + cyfry[k];

            delete [] cyfry;
        }
            break;
        }
        ktora++;
        nr_linii++;
        if(nr_linii==4)
            nr_linii=2;
    }

    plik.close();

    fstream plik2;
    int x,reszta,suma_cyfr=0;

    plik2.open("wynik.txt", ios::out);
    for(int i=1; i<=ile; i++)
    {

        while(liczby[i]>=10)
        {
            reszta = liczby[i] % 10;
            x = liczby[i] - reszta;
            liczby[i] = x/10;
            suma_cyfr = suma_cyfr + reszta;
        }
        plik2 << suma_cyfr+liczby[i] << endl;

        suma_cyfr=0; //Wazne! Trzeba wyzerowac sume cyfr na koniec petli!
    }
    plik2.close();

    cout << "Dane zostaly zapisane do pliku wynik.txt\n";
    system("pause");
    return 0;
}

Jednak pomyślałem sobie: "Skoro można z tych liczb wyłuskiwać cyfry, a program ma wyświetlać sumę cyfr danej liczby, to może można go ulepszyć żeby był szybszy i działał nawet dla ogromnych liczb nie mieszczących się w żadnych zmiennych, takich które skladaja sie nawet z setek cyfr.

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

int main()
{
	int liczby[100001];
	/* o 1 wiecej bo zaczynam zapisywac liczby od szufladki o indeksie 1, a nie 0,
	wiec 100 tysieczna liczba bedzie w szufladce o indeksie 100000, a gdybym napisal liczby[100000] to indeks ostatniego elementu bylny rowny 999999
	odwolywalbym sie zatem do niezarezerwowanego obszaru w pamieci RAM i spowodowal blad krytyczny*/
    cout << "Dla ilu liczb chcesz policzyc sume ich cyfr? (maksimum 100000)\n";
    int ile;
    cin >> ile;

    while(ile>100000)
    {
        cout << "Nie ma tylu liczb w pliku. Podaj jeszcze raz\n";
        cin >> ile;
    }

    fstream plik;

    plik.open("dane.txt", ios::in);

    string linia;
    short nr_linii=1, ktora=0;

    while(getline(plik,linia))
    {
        switch(nr_linii)
        {
        case 1:
            cout << "";
            break;
        case 2:
        {
            int *cyfry;
            int rozmiar = linia.length();
            cyfry = new int [rozmiar];

            for(int k=0; k<rozmiar; k++)
            {
                switch(linia[k])
                {
                    case '0': cyfry[k]=0; break;
                    case '1': cyfry[k]=1; break;
                    case '2': cyfry[k]=2; break;
                    case '3': cyfry[k]=3; break;
                    case '4': cyfry[k]=4; break;
                    case '5': cyfry[k]=5; break;
                    case '6': cyfry[k]=6; break;
                    case '7': cyfry[k]=7; break;
                    case '8': cyfry[k]=8; break;
                    case '9': cyfry[k]=9; break;
                }
            }
            liczby[ktora] = 0;
            for(int k=0; k<rozmiar; k++)
                liczby[ktora] = liczby[ktora] + cyfry[k];

            delete [] cyfry;
        }
            break;
        case 3:
        {
            int *cyfry;
            int rozmiar = linia.length();
            cyfry = new int [rozmiar];

            for(int k=0; k<rozmiar; k++)
            {
                switch(linia[k])
                {
                    case '0': cyfry[k]=0; break;
                    case '1': cyfry[k]=1; break;
                    case '2': cyfry[k]=2; break;
                    case '3': cyfry[k]=3; break;
                    case '4': cyfry[k]=4; break;
                    case '5': cyfry[k]=5; break;
                    case '6': cyfry[k]=6; break;
                    case '7': cyfry[k]=7; break;
                    case '8': cyfry[k]=8; break;
                    case '9': cyfry[k]=9; break;
                }
            }
            liczby[ktora] = 0;
            for(int k=0; k<rozmiar; k++)
                liczby[ktora] = liczby[ktora] + cyfry[k];

            delete [] cyfry;
        }
            break;
        }
        ktora++;
        nr_linii++;
        if(nr_linii==4)
            nr_linii=2;
    }

    plik.close();

    fstream plik2;

    plik2.open("wynik.txt", ios::out);

    for(int i=1; i<=ile; i++)
        plik2 << liczby[i] << endl;

    plik2.close();

    cout << "Dane zostaly zapisane do pliku wynik.txt\n";
    system("pause");
    return 0;
}

 

Każda wersja tych programów działa dla małych liczb, które sam wpiszę do pliku dane.txt. Natomiast dla tych liczb  http://www.algorytm.edu.pl/images/zadania/suma_cyfr.txt  , które wklejam do pliku dane.txt, każda z tych trzech wersji się wysypuje. Wie ktoś może dlaczego?

Answer 1

Wydaje mi sie że po prostu próbujesz dojechać z gdańska do warszawy przez rzym, można zrobić to bardzo prostymi sposobami, wczytanie tej wartości z pliku do programu nie ma sensu lepiej konwertować znak i od razu dodawać go do sumy:

 

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main()
{
    int j;
    cin>>j;

    fstream plik, wynik;
    plik.open("dane.txt", ios::in);
    wynik.open("wyniki.txt", ios::out);

    for(int i=0; i<j; ++i)
    {
        int suma=0;
        string linia;
        getline(plik, linia);

        for(int z=0; z<linia.length(); ++z)
            suma += static_cast<int>(linia[z])-48;  //zamiana wartoœci znaku ASCII na liczbe

         wynik<<suma<<endl;
    }

    wynik.close();
    plik.close();


    return 0;
}

 

Answer 2

Odniosę się do pomysłu z pętlą. Jest to może innowacja, ale proszę sobie porównać długość kodu i czas wykonania programu,

Comments

Masz rację, jednak nie udało mi się wymyślić lepszego sposobu. Ale ten i tak nie jest taki zły. Dla każdej liczby ilość iteracji jest równa ilości cyfr, wiec ilość wszystkich iteracji to ilość wszystkich cyfr. Więc gdyby było np. 100 tys liczb i każda 10 cyfrowa to iteracji będzie milion czyli 10 do potęgi 6. Są programy z wykorzystaniem pętli, gdzie złożoność czasowa wynosi n*n czyli ilość operacji dla 100 tys liczb byłaby równa 10 do potęgi 10.

---

Oczywiście, w przypadku takich "domowych" programów czas wykonania programu jest niezauważalny, jednak podczas korzystania z "dużego" programu czas będzie dłuższy.