Dzialania na duzych liczbach jako string

0

Witam,

mam pytanie: czy jest jakas funkcja biblioteczna umozliwiajaca mnozenie stringow? Czyt. liczb zapisanych za pomoca stringow...

sa trzy wartosci podane: a, b, c; wszystkie 1<=x<=10^80 a wzor:

wynik=2ab+2b;
for(int i=1; i<=a; i++)
wynik+=2ic;

oczywiscie wiem, nie moge ich mnozyc w taki sposob...

co prawda funcje na dodawanie stringow napisalem:

string licz(string a, string b)
{
       int lena, lenb;
       lena=a.length();
       lenb=b.length();
       while(lena>lenb)
       {b="0"+b;
       lenb=b.length();}
       while(lenb>lena)
       {a="0"+a;
       lena=a.length();}
       bool pom=0;
       
       for(int i=(lena-1); i>=0; i--)
       {
               if((a[i]+b[i]+pom)>105)
               {
               a[i]=((a[i]+b[i]+pom-96)%10)+48;
               pom=1;
               }
               else
               {
               a[i]=a[i]+b[i]+pom-48;
               pom=0;
               }
       }
       
       if(pom==1)
       a="1"+a;
       
       
       
       return a;
}

ale poszukuje funkcji na mnozenie(tak, wiem, a*n to (a+a) razy n-1, ala przy tym pamiec wysiada...

chetnie uzyje rowniez klasy w ktorej mozna operowac tak duzymi liczbami ;>

z gory dzieki!

0

Biblioteka vlong.
Duże liczby
Standardowo nie ma czegoś takiego. Zresztą do czego ci to potrzebne? Moze problem da się rozwiązać inaczej niż implementując takie coś ;)

0

dzieki, dobra rzecz, ale ja niestety nie moge dolaczac niestandardowych bibliotek...

Zadanie  LIC

 Liczba schodów.

   Firma kurierska ma po jednym odbiorcy na parterze i każdym piętrze wieżowca.

Schody pomiędzy poszczególnymi piętrami mają po P stopni, a przed drzwiami wejściowymi na parter znajduje się R schodów.

   Pewnego dnia zepsuła się winda i dostawca musiał dostarczyć każdemu z klientów jednakowej wielkości paczki, przy czym za każdym razem mógł unieść tylko jedną paczkę. Po ilu stopniach będzie musiał wejść i zejść, by dostarczyć wszystkie paczki do miejsca przeznaczenia i wrócić do autokaru ?    

Wejście

   W pierwszym  wierszu standardowego wejścia  zapisano całkowitą liczbę większe od jeden i mniejsze od  1080 liczba pięter w wieżowcu. W drugim wierszu zapisano całkowitą liczbę większe od jeden i mniejsze od  1080 liczba schodów przy wejściu na parter .

W trzecim wierszu zapisano całkowitą liczbę większe od jeden i mniejsze od  1080 liczba schodów między każdymi piętrami. 

Wyjście

   W pierwszym wierszu standardowego wyjścia zapisano liczbę schodów , które ma pokonać dostawca .

Przykład

Dla danej

6

6

18

poprawny wynik

 840

0

W zadaniu nie ma słowa o stringu ;)

Wyjście

   W pierwszym wierszu standardowego wyjścia zapisano liczbę schodów , które ma pokonać dostawca .

Przykład

Dla danej

6

6

18

poprawny wynik

 840

6, 18, 840 to same inty

int i, b;
cin >> i >> b;

Poza tym są funkcje do zamieniania stringów na inty.

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main (void)
{
	stringstream ss;
	int foo;
	string inp;

	while (getline (cin, inp)) {
		ss.clear ();
		ss.str ("");
		ss << inp;

		while (ss >> foo) {
			cout << foo << endl;
		}
	}

	return 0;
}

Oraz itoa() .

0

nie ma, ale jest napisane ze kazda z liczb moze miec 10^80, tylko zle mi sie wkleila tresc zadania.

Robiac unsigned long long dostalem 44/100pkt.

0

Nie ma innej metody niż po prostu zaimplementować sobie to mnożenie i dodawanie pisemne.
Wbrew pozorom to nie jest aż takie ciężkie i długie, zresztą masz źródła vlong, więc mozesz sobie "ściągnąć" trochę.

0
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXLEN 201

using namespace std;

string odej(string a)
{
       int lena=a.length();
       for(int i=(lena-1);i>=0; i--)
       {
               if(a[i]>48)
               {
                          a[i]--;
                          break;
               }
               else
               a[i]='9';
       }
       string c="";
       if(a[0]=='0')
       {
                    for(int i=0; i<(lena-1); i++)
                    {
                            c="0"+c;
                    }
                    
                    for(int i=0; i<(lena-1); i++)
                    c[i]=a[i+1];
                    
                    a=c;
                    
       }

       return a;
}

string licz(string a, string b)
{
       int lena, lenb;
       lena=a.length();
       lenb=b.length();
       while(lena>lenb)
       {b="0"+b;
       lenb=b.length();}
       while(lenb>lena)
       {a="0"+a;
       lena=a.length();}
       bool pom=0;
       
       for(int i=(lena-1); i>=0; i--)
       {
               if((a[i]+b[i]+pom)>105)
               {
               a[i]=((a[i]+b[i]+pom-96)%10)+48;
               pom=1;
               }
               else
               {
               a[i]=a[i]+b[i]+pom-48;
               pom=0;
               }
       }
       
       if(pom==1)
       a="1"+a;
       
       
       
       return a;
}

string mnoz(string a, string b)
{
       int lena=a.length(), lenb=b.length(), i=9;
                           string c;
                           
       if(lenb>lena)
       {
                    

                    c=a;
                    a=b;
                    b=c;
       }
       c=b;
       string aa=a;
       if(c.length()>1){
       while(c.length()>1)
       {
                        a=licz(aa,a);
                        c=odej(c);
       }
       i=9;
       }
       else
       i=(c[0]-48);
       
       for(;i>1; i--)
       a=licz(aa,a);
       
       return a;
                    
       
}


int main()
{
    string a,b,c;
    cin >> a >> b >> c;
    string wynik;
    wynik = licz(b,b);
    string bb=licz(b,b);
    string aa=a;
    int i;
    if(aa.length()>1){
    while(aa.length()>1)
    {
                        wynik=licz(wynik, bb);
                        string g=mnoz(aa,c);
                        g=licz(g,g);
                        wynik=licz(wynik,g);
                        aa=odej(aa);
    }
    i=9;
}
else
i=aa[0]-48;

for(;i>0;i--)
{
                                     wynik=licz(wynik, bb);
                        string g=mnoz(aa,c);
                        g=licz(g,g);
                        wynik=licz(wynik,g);
                        aa=odej(aa);
}

cout << wynik;


    system("PAUSE");
    return 0;
}

program dziala, podaje dobre wartosci. Ale wykonuje sie za dlugo i teraz mam 33pkt ;p Nie da sie tak szybko operowac na tak ogromnych stringach... o.0

0

To może zrób tak:
wczytaj do stringa liczby. Sprawdź ich długość. Jeśli są krótkie to za pomocą stringstream zrób z nich inty i licz normalnie. Jeśli sa za długie to licz stringami.
poza tym funkcje inline, a jeśli i to zawiedzie to moze zamiast stringów użyć char[].

0

Moglby mi ktos wytlumaczyc zasade dodawania na stringach i jak to sie robi? Probowalam jakos zrozumiec program z pierwszego postu ale zabardzo mi to nie wychodzi.

0

A umiesz dodawać pisemnie (uczyli tego w podstawówce)? Tak to właśnie działa. Dodajesz od końca i jeśli wynik dodawania ostatnich cyfr > 9 to przenosisz w góre jedynkę a jako wynik wpisujesz sume cyfr modulo 10 (czyli cyfrę jedności wyniku). Następne cyfry dodajesz biorąc pod uwagę przeniesienie z poprzedniego dodawania.

0

Co wy kombinujecie? Największy możliwy wynik w tym zadaniu to dokładnie: 1257382438
Co bezproblemowo mieści się w 32 bitowym int! To organicznie na 1079 pięter schodów zostało wprowadzone właśnie po to by nie bawić się w wielkie liczby.
A zadanie jest tak proste, że rozwiązanie można zmieścić w 3 instrukcjach umieszczonych w main.
1 linia: wczytanie danych, 2 linia: wydrukowanie wyniku, 3 linia: return 0; .
Autor tego wątku nadinterpretował treść zadania (a razej go nie przemyślał zanim usiadł do klawiatury).

0

@up

  1. Ktoś właśnie odkopał ten temat, poprzedni autor już dostał odpowiedź.
  2. Nie 1080 a 10^80, kłania się czytanie 1 posta...
0

Mi raczej chodzi o to czemu musi byc warunek z liczba 105? Czemu ta liczba? No i co daja cyfry +/-48?

0

Bo autor kodu lubi widać magiczne cyferki ;]
znak numer 48 w ascii to '0'
Wiec jeśli masz cyfrę w postaci znaku char to odjecie od niej 48 da ci wartość tej cyfry w zmiennej. Tzn
'5'-48 = '5'-'0' = 5
105 to jest 57 (czyli '9') + 57 (czyli '9') + 1 czyli sytuacja kiedy następnuje przeniesienie.

Osobiście uważam ze wygodniej byłoby od razu zmienić te znaki na cyfry odejmując od nich '0' po prostu ;]

0

Dzieki wielkie za wytlumaczenie tego. [browar]

0

Bylabym jeszcze bardziej wdzieczna gdyby mi ktos jeszcze wytlumaczyl jak zrobic odejmowanie. A dokladnie kiedy mamy np. 12-5. Wiadomo, ze to 7 ale przeciez odejmujac słóbkowo nie mozemy przeciez odjac 2 od 5. Wiec pobieramy 1 tworzac 12. W jaki sposob to zapisac na stringach?

0

Tak samo jak przy dodawaniu. Odejmujesz w ten sposób i zapisujesz sobie "przeniesienie" tylko tym razem wsteczne. Tzn jeśli różnica tych liczb jest < 0 (np. 2-5) to do wyniku dodajesz 10 a z kolejnej liczby odejmujesz 1.

0

Robie cos takiego ale nadal nie dziala poprawnie.

           if (a[i]-p < b[i])
           {
              a[i]=(a[i]-b[i]+48);
              a[i]= (a[i]+10)-p;
              p=1;
           }
           else 
           {
              a[i]=(a[i] - b[i] + 48);
              a[i]= a[i] - p;
              p=0; 
           }

Nie ma sie co dziwic skoro w kodzie ascii nie ma cos takiego jak -3 (powstaje w wyniku odejmowania 2-5 czyli w ascii 50-53)

A zrobienie b[i]-a[i] konczy sie bledem. Operuje na stringach. Jak to poprawic?

0

Zapisz to sobie na chwile do signed char albo do inta po prostu? o_O

0

No wlasnie nie moge. Musze operowac na stringach i nie moge zamieniac na char lub int.

0

No to sobie porównuj na zasadzie:
if(pierwszacyfra < drugacyfra) // to samo co pierwszacyfra-drugacyfra < 0
{
//pozyczamy ;]
}

0

A moglbys to bardziej skonkretyzowac? Bo nie mam pomyslu jak to poprawic kiedy liczby sa mniejsze. W koncu przeciez zwiekszam o 10 ale problem tkwi w a[i]-b[i] kiedy a jest mniejsze. Bo niby co zrobic skoro liczba wychodzi ujemna?

0

A nie możesz zrobić:

if(a[i] < b[i])
{
  wynik[i] = 10+a[i] - b[i];
}
else
  wynik[i] = a[i]-b[i]

?

0

Dziala juz prawie. Bo wszystko juz ladnie odejmuje ale jeszcze jest jedno ale. Bo przy odejmowaniu np. 12-4 wynik jest 08 a nie 8. Jak to mozna poprawic?

string odejmowanie(string a, string b)
{
      
       int dlA, dlB, p=0;
       dlA=a.length();
       dlB=b.length();
       
       while (dlA>dlB)
       {
             b="0"+b;
             dlB=b.length();      
       }
       
       while (dlA<dlB)
       {
             a="0"+a;
             dlA=a.length();    
       }
       
       for (int i = dlA-1; i >= 0; i--)
       {
           
           if (a[i] < b[i])
           {
              a[i]=10+a[i]-b[i]+48-p;
              p=1;
           }
           else 
           {
              a[i]=(a[i] - b[i]+48);
              a[i]= a[i] - p;
              p=0; 
           }
       }

       return a;
}

0

Przeleć tablicę od przodu i usuwaj nieznaczące zera? ;) Najłatwiej zrobić to tak:

//twój wynik jest w zmiennej char wynik[]
//zmienna int rozmiar to długość tablicy wynikowej
int i=rozmiar-1;
int j=0;
while(wynik[i--] == 0)
  j++;
char* wypisywanie = wynik+j;
//i wypisujesz wypisywanie, tzn np.
printf("%s",wypisywanie);
//albo
cout<<wypisywanie;

Pisane z palca, może być błąd jakiś

0

Fajne, na jakiej stronce mozna sie w takie zadanka pobawic ?

0

<spam>http://asd3.tcs.uj.edu.pl/problems.html tutaj masz fajne zadanka. Zadanie z mnożeniem jest podobne co tutejsze tyle że trzeba użyć FFT a nie zwykłego mnożenia pisemnego.</spam>

:)

0

Niestety twoj sposob nie byl dobry. Ale i tak dzieki za pomoc bo dzieki temu wpadlam na inny. Moze komus sie przyda jak usuwac ze stringa 0 na poczatku:

           for (i=0; i<dlA; i++)
           {
               if (a[i]!='0')
               {
                  break;
               }    
           }
           a = a.substr(i, dlA - i);
 

A ma ktos pomysl odnosnie dzielenia?

Robilam tak:

10:3, i=0
10-3=7, i++
7-3=4, i++
4-3=1, i++
i=3, reszta=1

Ale ten sposob okazal sie byc calkowicie zly bo dzielenie duzych liczb zajmowalo mu kilka minut.

0

Mój sposób byl dobry, gdybyś uzywała char* a nie string ;)
Trzeba było mówić to zaproponowałbym rozwiązanie z substr ;]

1 użytkowników online, w tym zalogowanych: 0, gości: 1