Witam, napisałem program liczący silnie, który ma jednak ograniczenia jako że zmienne są w stanie przechować bardzo ograniczoną liczbę cyfr; w jaki sposób przy użyciu tablic można napisać program zdolny policzyć silnie z dużych liczb np 1000, 10000, 1000000, 1000000000? Chodzi mi o to, jak można dużą liczbę pofragmentować na krótkie ciągi liczb zapisywalne do tablicy, i jak je mnożyć?
0
1
gmplib.org albo podejrzyj źródła klasy BigInteger z Javy.
0
Chodziłoby mi raczej o niekorzystanie z żadnych bibliotek itp; tylko najbardziej podstawowe narzędzia tzn, normalne zmienne int, tablice, nic poza tym.
0
"prawie" elementarnie policzyłem 30'000! w mniej niż sekundę. Piwa do dziś nie przysłali.
0
Najprostszym sposobem (poza użyciem GMP czy innego bignuma) byłoby liczenie na tekstowej reprezentacji liczby. Działania robisz niemal jak na papierze. ;)
Innym, nieco lepszym jeśli chodzi o wykorzystaniem pamięci ale wymagającym podstawowej znajomości systemu binarnego sposobem byłoby działanie na tablicy bitów (choćby vector<bool>, dla wygody), traktując całość jako jedną wielką liczbę binarną. Wykorzystanie pamięci miałbyś takie samo jak zwykłe liczby w pamięci - bajt: 256 wartości, itd. Dodawanie byłoby dość proste, a mnożenie możesz zrobić jako dodawanie w pętli, jeśli innego pomysłu nie masz. ;)
Działać będzie, ale liczenie silni z miliona to raczej porządną "chwilę" potrwa. ;P
0
Prosta implementacja podstawowych działań na bardzo dużych liczbach w C:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _liczba
{
int dlugosc;
char *cyfry;
} Liczba;
#define ALOKUJ(CZEGO, ILE) (CZEGO*) malloc(sizeof(CZEGO) * ILE)
#define A_DLUZSZE_OD_B \
if(a->dlugosc < b->dlugosc)\
{\
Liczba *temp = a;\
a = b;\
b = temp;\
}
#define MAKSYMALNY_ROZMIAR_LICZBY 100
#define ABS(LICZBA) (LICZBA<0)?-LICZBA:LICZBA
Liczba *Utworz(int liczbaCyfr);
Liczba *stdinNaLiczbe();
void Usun(Liczba *liczba);
void Wyswietl(Liczba *liczba);
Liczba *Dodaj(Liczba *a, Liczba *b);
Liczba *Odejmij(Liczba *a, Liczba *b);
Liczba *Pomnoz(Liczba *a, Liczba *b);
//Liczba *Podziel(Liczba *a, Liczba *b);
//-----------------------------------------------------------------------------
int main()
{
char dzialanie;
Liczba *skladnik1, *skladnik2, *wynik;
while(1)
{
if((dzialanie = getchar()) == EOF)
break;
skladnik1 = stdinNaLiczbe();
skladnik2 = stdinNaLiczbe();
switch(dzialanie)
{
case '+':
wynik = Dodaj(skladnik1, skladnik2);
break;
case '-':
wynik = Odejmij(skladnik1, skladnik2);
break;
case '*':
wynik = Pomnoz(skladnik1, skladnik2);
break;
// case '/':
// wynik = Podziel(skladnik1, skladnik2);
// break;
}
Wyswietl(wynik);
Usun(wynik);
Usun(skladnik1);
Usun(skladnik2);
}
return 0;
}
//-----------------------------------------------------------------------------
Liczba *Utworz(int liczbaCyfr)
{
Liczba *wynik = ALOKUJ(Liczba, 1);
wynik->dlugosc = liczbaCyfr;
wynik->cyfry = ALOKUJ(char, liczbaCyfr);
return wynik;
}
//-----------------------------------------------------------------------------
Liczba *stdinNaLiczbe()
{
char *bufor = ALOKUJ(char, MAKSYMALNY_ROZMIAR_LICZBY+1);
char *kursor = bufor;
unsigned int iloscCyfr = 1;
while(1)
{
*kursor = getchar();
if(*kursor != ' ' && *kursor != '0')
break;
}
while(1)
{
*(++kursor) = getchar();
if(*kursor == ' ' || *kursor == '\n')
break;
else iloscCyfr++;
}
Liczba *wynik = Utworz(iloscCyfr);
memcpy(wynik->cyfry, bufor, iloscCyfr);
free(bufor);
return wynik;
}
//-----------------------------------------------------------------------------
void Usun(Liczba *liczba)
{
free(liczba->cyfry);
free(liczba);
}
//-----------------------------------------------------------------------------
void Wyswietl(Liczba *liczba)
{
char *kursor = liczba->cyfry;
for(unsigned int i = liczba->dlugosc; i>0; i--)
{
putchar(*(kursor++));
}
putchar('\n');
}
//-----------------------------------------------------------------------------
Liczba *Dodaj(Liczba *a, Liczba *b)
{
A_DLUZSZE_OD_B
char *bufor = ALOKUJ(char, a->dlugosc + 1);
char *kursorW = bufor + a->dlugosc;
char *kursorA = a->cyfry + a->dlugosc - 1;
char *kursorB = b->cyfry + b->dlugosc - 1;
unsigned int pamiec = 0;
while(kursorB >= b->cyfry)
{
pamiec += (*(kursorA--)-'0') + (*(kursorB--)-'0');
*(kursorW--) = pamiec % 10 + '0';
pamiec /= 10;
}
while(kursorA >= a->cyfry)
{
pamiec += *(kursorA--)-'0';
*(kursorW--) = pamiec % 10 + '0';
pamiec /= 10;
}
Liczba *wynik;
if(pamiec>0)
{
*kursorW = pamiec + '0';
wynik = Utworz(a->dlugosc+1);
memcpy(wynik->cyfry, bufor, wynik->dlugosc);
}
else
{
wynik = Utworz(a->dlugosc);
memcpy(wynik->cyfry, bufor+1, a->dlugosc);
}
free(bufor);
return wynik;
}
//-----------------------------------------------------------------------------
Liczba *Odejmij(Liczba *a, Liczba *b)
{
A_DLUZSZE_OD_B
char *bufor = ALOKUJ(char, a->dlugosc);
char *kursorW = bufor + a->dlugosc - 1;
char *kursorA = a->cyfry + a->dlugosc - 1;
char *kursorB = b->cyfry + b->dlugosc - 1;
int pamiec = 0;
while(kursorB >= b->cyfry)
{
pamiec += (*(kursorA--)-'0') - (*(kursorB--)-'0');
if(pamiec>=0)
{
*(kursorW--) = pamiec + '0';
pamiec = 0;
}
else
{
*(kursorW--) = 10 + pamiec + '0';
pamiec = -1;
}
}
while(kursorA >= a->cyfry)
{
pamiec += *(kursorA--)-'0';
if(pamiec>=0)
{
*(kursorW--) = pamiec + '0';
pamiec = 0;
}
else
{
*(kursorW--) = 10 + pamiec + '0';
pamiec = -1;
}
}
while(*(++kursorW)=='0');
unsigned int dlugoscWyniku = bufor + a->dlugosc - kursorW;
if(dlugoscWyniku == 0)
{
kursorW--;
dlugoscWyniku++;
}
Liczba *wynik = Utworz(dlugoscWyniku);
memcpy(wynik->cyfry, kursorW, dlugoscWyniku);
free(bufor);
return wynik;
}
//-----------------------------------------------------------------------------
Liczba *Pomnoz(Liczba *a, Liczba *b)
{
A_DLUZSZE_OD_B
char *bufor = ALOKUJ(char, a->dlugosc + b->dlugosc);
char *kursorW = bufor;
for(unsigned int i = a->dlugosc+b->dlugosc; i>0; i--)
*(kursorW++) = '0';
char *kursorA;
char *kursorB = b->cyfry + b->dlugosc - 1;
unsigned int pamiec = 0;
for(unsigned int i = b->dlugosc; i>0;)
{
i--;
unsigned int liczbaB = *(kursorB--)-'0';
kursorA = a->cyfry + a->dlugosc - 1;
kursorW = bufor + a->dlugosc + i;
for(unsigned int j = a->dlugosc; j>0;j--)
{
pamiec += (*(kursorA--)-'0') * liczbaB + (*kursorW - '0');
*(kursorW--) = (pamiec % 10) + '0';
pamiec /= 10;
}
while(pamiec>0)
{
*(kursorW--) = pamiec % 10 + '0';
pamiec /= 10;
}
}
kursorW++;
unsigned int dlugoscWyniku = bufor + a->dlugosc + b->dlugosc - kursorW;
Liczba *wynik = Utworz(dlugoscWyniku);
memcpy(wynik->cyfry, kursorW, dlugoscWyniku);
free(bufor);
return wynik;
}
Aczkolwiek należy zaznaczyć, że jest to bardzo nieefektywne, na pewno nie dorasta gmp czy implementacjom z pythona czy innych języków. No, ale chyba lepszy rydz niż nic.
0
A może konkurs, kto lepiej to zrobi?
0
Proszę, silnia z dowolnie dużych liczb w scheme
(define (fact n) (if (> n 1) (* n (fact (- n 1))) 1))
Fajnie mieć w standardzie dowolnie duże liczby :P.
0
Już wspomniałem, że niektóre mają taki fajny ficzer, że liczą na każdych liczbach (ja akurat podałem pythona -- i tu prędzej człowiekowi spodoba składnia [aczkolwiek nic nie mam do schema]).
0
Hmmm, to może ja tak dam na szybko i chyba najprościej jak się da w paru językach:
- Maxima:
1000000000! - Yacas:
10000000000!
Jeśli ktoś przebije to bardzo chętnie zobaczę jak to zrobił.
0
Silnia dla ubogich
#include <stdio.h>
int main(){
unsigned int t[1000], c, j, k, i, N;
int z;
scanf("%d",&N);
k=0; t[k]=1;
for(i=2;i<=N;i++){
c=0;
for(j=0;j<=k;j++){
c += t[j]*i;
t[j]=c % 100000;
c = c / 100000;
}
while(c>0){
t[++k]=c % 100000;
c = c / 100000;
}
}
printf("%d! = %d", N, t[k]);
for(z=k-1;z>=0;z--)
printf("%05d",t[z]);
}
1
winerfresh napisał(a)
Hmmm, to może ja tak dam na szybko i chyba najprościej jak się da w paru językach:
- Maxima:
1000000000!- Yacas:
10000000000!
Jeśli ktoś przebije to bardzo chętnie zobaczę jak to zrobił.
- PARI/GP
1e9!:-)
Powiedzmy, że skorzystamy z jakiejś biblioteki, potrafiącej liczyć na wielkich liczbach i przede wszystkim potrafiącej szybko mnożyć czyli nie bignum z javy, a raczej GMP.
Nawet wtedy liczenie silni nie jest takie oczywiste.
PARI/GP (korzysta z GMP)
gp > n=200000;
time = 0 ms.
gp > n!;
time = 1,172 ms.
gp > prod(i=2,n,i); //iloczyn 2*3*....*n
time = 1mn, 18,860 ms.
gp > f(2,n); // moja funkcja
time = 1,891 ms.
Wbudowana silnia liczy kilkadziesiąt razy szybciej!!
A liczy szybciej bo algorytm dowcipniejszy
W mniej niż dziesięciu wierszach zapisałem pewien algorytm. Prawda, że gorszy od wbudowanego ale jednak sporo lepszy od naiwnego.
Rzecz jest ciekawa i warta zastanowienia.