Pripremni zadaci - veliki brojevi

Napisati program za rad sa dva velika pozitivna cela broja a, b sa standardnog ulaza (sa ne više od 100 cifara) i na standardni izlaz ispisuje a,b (u klasi od po 3 cifre kako smo i navikli da pišemo), a+b, a-b(računa samo ako a>b), a*b, a/b, a%b. Učitavanje para brojeva se prekida unosom karaktera koji nije dekadna cifra. Program napisati tako da maksimalan broj cifara možemo jednostavno povećati ili smanjiti.

OBJAŠNJENJE:
Brojevi koji se ne mogu smestiti u neki od standardnih tipova podataka nazivaju se "veliki". Ukoliko ima potrebu da radi sa takvim brojevima programer mora izgraditi skup funkcija koje nad njima mogu realizovati osnovne aritmetičke operacije.

Primeri:
$40!= 815915283247897734345611269596115894272000000000$ - broj ima 47 cifara.
$2^{128}=340282366920938463463374607431768211456$ - broj ima 38 cifara.

SAVET: Uradite jednu funkciju (npr. za sabiranje velikih brojeva) pa je proverite (testirajte). Nakon toga predjite na drugu funkciju. Prilikom rada na novoj funkciji ne zaboravite da možete koristiti one koje ste već uradili.

Rešenje

#include <stdio.h>
#include <ctype.h>

#define DA 1
#define NE 0
#define MAX 50

typedef int LRez; /* Tip za logicke rezultate LRez*/

// provera da li j dati broj 0
LRez nula (const char a[], int na) 
{ 
   return na==1 && a[0]==0; 
}

// uporedjuje dva broja
// vraca: 0, ako si jednaki
// negativan broj, ako je prvi broj manji
// pozitivan broj, ako je prvi broj veci
int uporedi (const char a[], int na, const char b[], int nb) 
{
   int i;
   if (na != nb) 
      return na - nb;
   for (i= na-1;i>0 && a[i]==b[i]; i--);
   return a[i] - b[i];
}

// kopira niz a u niz b
void kopiraj (const char a[], int na, char b[], int *nb) 
{
   int i;
   for (i=0; i<na; i++) b[i] = a[i];
   *nb = na;
}

// sabira a i b i rezultat stavlja u c
// vraca DA uvek
LRez zbir (const char a[], int na, const char b[], int nb, char c[], int *nc) 
{
   int i, p;
   for (p=i=0; i<na || i<nb; i++)  
   {
      int d = p;
      if (i < na) 
      d += a[i];
      if (i < nb) 
      d += b[i];
      if (d >= 10) 
   { 
      p = 1; 
   d -= 10; 
      } 
   else 
      p = 0;
      c[i] = d;
   }
   if (p) c[i++] = p;
   * nc = i;
   return DA;
}

// oduzima a i b i rezultat stavlja u c
// vraca DA ako je operacija uspela, NE ako nije
LRez razlika (const char a[], int na, const char b[], int nb, char c[], 
              int *nc) 
{
   int i, p;
   if (uporedi (a, na, b, nb) < 0) 
      return NE;
   for (p=i=0; i<na; i++) 
   {
      int d = a[i] + p;
      if (i <nb) 
      d -= b[i];
      if (d < 0) 
   { 
      p = -1; 
   d += 10; 
      } 
   else 
      p = 0;
      c[i] = d;
   }
   for (i=na-1; i>0 && c[i]==0; i--);
   *nc = i + 1;
   return DA;
}

// mnozi a i b i rezultat stavlja u c
// vraca DA uvek
LRez proizvod (const char a[], int na, const char b[], int nb, char c[],
               int *nc) 
{
   if (!nula(a,na) && !nula(b,nb)) 
   {
      int i, j, p;
      *nc = na + nb;
      for (i=0; i<*nc; c[i++]=0);
      for (i=0; i<na; i++)
      for (p=j=0; j<nb || p; j++) 
      {
         int d = c[i+j] + p;
         if (j < nb) 
      d += a[i] * b[j];
         c[i+j] = d % 10; 
   p = d / 10;
      }
      if (c[*nc-1] == 0) (*nc)--;
   } 
   else 
   { 
      *nc = 1; 
   c[0] = 0; 
   }
   return DA;
}

// deli a i b i kolicnik stavlja u c a ostatak u d
// vraca DA ako je operacija uspela, NE ako nije
LRez kolicnik (const char a[], int na, const char b[], int nb, char c[], 
               int *nc, char d[], int *nd) 
{
   int i, j, nn;
   if (nula (b, nb)) 
      return NE; /*ne mozemo deliti nulom*/
   kopiraj (a, na, d, nd);
   nn = na - nb + 1;
   if (nn > 0)  
   {
      *nc = nn; *nd = nb;
      for (i=*nc-1, j=na-nb; i>=0; i--, j--, (*nd)++)
      {
         c[i] = 0;
         while (uporedi (d+j, *nd, b, nb) >= 0) 
   {
            razlika (d+j, *nd, b, nb, d+j, nd);
            c[i]++;
         }
      }
      if (*nc > 1 && c[*nc-1] == 0) 
      (*nc)--;
      while (*nd>1 && d[*nd-1]==0) 
      (*nd)--;
   } 
   else 
   {
      *nc = 1; 
   c[0] = 0;
   }
   return DA;
}

// cita i popunjava broj a i broj cifara n
// vraca DA ako je operacija uspela, NE ako nije
LRez citaj (char a[], int *n) 
{
   char broj[MAX+1]; 
   int i, j;
   scanf ("%s", broj);
   for (i=0; broj[i]; i++)
   if (! isdigit (broj[i])) 
      return NE;
   *n = i;
   for (i=*n-1, j=0; i>=0; a[i--]=broj[j++]-'0');
   while (*n>1 && a[*n-1] == 0) 
      (*n)--;
   return DA;
}

// ispisuje broj a
// sir je sirina - maksimalan broj cifara
// grupe je DA ako zelimo odvajanje u grupe po 3 cifre, NE ako ne zelimo
// ne vraca nista
void pisi (const char a[], int n, int sir, LRez grupe) 
{
   int i;
   printf ("%*s", (sir - n - (n-1)/3*grupe), "");
   for (i=n-1; i>=0; i--) 
   {
      putchar (a[i] + '0');
      if (grupe && i % 3 == 0) 
      putchar (' ');
   }
}

// glavni program - ucitava dva velika broja, racuna njihov zbir, razliku,
// proizvod,kolicnik i ostatak pri deljenju i ispisuje ih. Ako neka od 
// operacija nije definisana ispisuje "ne moze" umesto rezultata
void main () 
{
   char a[MAX], b[MAX], c[2*MAX], d[MAX]; /* brojevi a,b,c,d zadati nizom */
   int na, nb, nc, nd; /*dimenzije nizova a,b,c,d*/
   while (citaj (a, &na) && citaj (b, &nb)) 
   {
      printf ("a= "); 
   pisi (a, na, MAX, DA); 
   putchar ('\n');
      printf ("b= "); 
   pisi (b, nb, MAX, DA); 
   putchar ('\n');
      printf ("a+b= "); 
   zbir (a, na, b, nb, c, &nc);
      pisi (c, nc, MAX, DA); 
   putchar ('\n');
      printf ("a-b= ");
      if (razlika (a, na, b, nb, c, &nc))
      { 
      pisi (c, nc, MAX, DA); putchar ('\n'); 
      }
      else 
      printf ("ne moze\n");
      printf ("a*b= "); 
   proizvod (a, na, b, nb, c, &nc);
      pisi (c, nc, MAX, DA); 
   putchar ('\n');
      printf ("a/b= ");
      if (kolicnik (a, na, b, nb, c, &nc, d, &nd)) 
   {
         pisi (c, nc, MAX, DA); 
   putchar ('\n');
         printf ("a%%b= "); 
   pisi (d, nd, MAX, DA); 
   putchar ('\n');
      } 
   else 
      printf ("ne moze\n");
      putchar ('\n'); 
   }
}