forum studentów matematyki Politechniki Wrocławskiej

kisieL

Myślę, że warto się wymieniać doświadczeniami z programowaniem w C. Po to ten temat Smile

I od razu zamieszczam program mojego pomysłu na mnożenie dużych liczb, które zostają wczytane przez użytkownika. I proponuję zabawę na długie zimowe wieczory: w 80 linijkach kodu znajdź błąd, przez który program nie działa jak należy Razz

(tak naprawdę to w ok. 30, bo coś jest nie tak wyłącznie z procedurą mnożenia, ale tak lepiej brzmi Wink

)

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100

//funkcje wypelniajace tablice (odpowiednio int i char) zerami
void zero(int tab[]){
int i;
for(i=0;i<SIZE;i++)
tab[i]=0;
}
void chzero(char tab[]){
int i;
for(i=0;i<SIZE;i++)
tab[i]=0;
}

//funkcja przepisujaca liczbe z char do komorek tablicy
void przepisanie(int in[],char ch[]){
int i;
for(i=0;i<strlen(ch);i++)in[i]=ch[strlen(ch)-1-i]-48;
}

//procedura mnozenia
void mnozenie(int A[SIZE],int B[SIZE],int C[SIZE*2],int rozmiarA,int rozmiarB){
int R[SIZE],i,j,ilocz,pilocz,su,psu;

for(i=0;i<SIZE*2;i++) C[i]=0; //wyzerowanie tablicy wynikowej
for(i=0;i<SIZE;i++){
//przemnozenie pierwszej liczby przez ity kawalek drugiej liczby
pilocz=0;
for(j=0;j<rozmiarA;j++){
ilocz=B[i]*A[j]+pilocz;
pilocz=ilocz/10;
R[j]=ilocz%10;
}

if(i!=0){
//przesuniecie komorek tablicy roboczej o odpowiednia ilosc zer
for(j=rozmiarA;j>0;j--)R[j+i]=R[j];
//wypelnienie luk zerami
for(j=0;j<i;j++)R[j]=0;
}
//sumowanie A*B[i] z A*B[i+1]
psu=0;
if(i==0)for(j=0;j<rozmiarA+1;j++)C[j]=R[j];
else for(j=0;j<rozmiarA+rozmiarB+1;j++){
su=C[j]+R[j]+psu;
psu=su/10;
C[j]=su%10;}
}
}

int main() {
int tabA[SIZE],tabB[SIZE],tabC[SIZE*2],i;
char robA[SIZE],robB[SIZE];

zero(tabA); zero(tabB); chzero(robA); chzero(robB); //wyzerowanie tablic wejsciowych

//wczytywanie duzych liczb
printf("podaj pierwsza duza liczbe:\n");
gets(robA);
przepisanie(tabA,robA);
printf("podaj druga duza liczbe:\n");
gets(robB);
przepisanie(tabB,robB);

//mnozenie obu liczb
mnozenie(tabA,tabB,tabC,strlen(robA),strlen(robB));

/*procedura pomocnicza - wyswietlenie wczytanych duzych liczb
for(i=0;i<strlen(robA);i++)printf("%d\n",tabA[strlen(robA)-i-1]);
printf("\n");
for(i=0;i<strlen(robB);i++)printf("%d\n",tabB[strlen(robB)-i-1]);
printf("\n"); */

for(i=0;i<strlen(robA)+strlen(robB);i++)printf("%d",tabC[i]);

system("pause");
return 0;
}

kisieL

Już sam obczaiłem główny błąd, przez który program się wieszał.
jak jest:

//procedura mnozenia
void mnozenie(int A[SIZE],int B[SIZE],int C[SIZE*2],int rozmiarA,int rozmiarB){
int R[SIZE],i,j,ilocz,pilocz,su,psu;

for(i=0;i<SIZE*2;i++) C[i]=0; //wyzerowanie tablicy wynikowej
for(i=0;i<SIZE;i++){

najbezpieczniej dać

//procedura mnozenia
void mnozenie(int A[SIZE],int B[SIZE],int C[SIZE*2],int rozmiarA,int rozmiarB){
int R[SIZE],i,j,ilocz,pilocz,su,psu;

for(i=0;i<SIZE*2;i++) C[i]=0; //wyzerowanie tablicy wynikowej
for(i=0;i<rozmiarA+rozmiarB;i++){

jak było tam SIZE to pewnie jakoś tam się wykraczało poza dopuszczalne granice;) Ale program i tak jest wciąż pełen błędów, więc szukajcie Smile

Zapewne są to sprawy kosmetyczne typu: tu wydłuż przebieg pętli o 1, tam skróć 2 itd Wink

cadaver

cadaver

OK- nie chciało mi się poprawiać, więc sam napisałem działający program. Niestety poszedłem na łatwiznę i program teoretycznie wysypuje się już, gdy druga liczba sklada sie z 250tys. znakow, a w pierwszej występuje cyfra 9. Za dodatkowy smaczek może uchodzić to, że możemy sobie przemnożyć "szatan" przez "dupa".
Edit: Usuwam "zerowanie" pustych tablic - zupełnie niepotrzebne.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ZIOBRO 0
#define MAX_SIZE 100

void convert (char in[], int out[]) {
/*
Funkcja do zamiany tablicy typu char na tablice typu int, z odwrocona
kolejnoscia znakow.
*/
int len = strlen(in), i;
for (i=0;i<len;i++)
out[i]=in[len-i-1]-48;
}
void mn (int A[], int B[], int lenA, int lenB, int C[]) {
//Inicjujemy tablice pomocnicze i zmienne.
int R[2*MAX_SIZE],tempX[lenB],x,i,n;
for (i=ZIOBRO; i<2*MAX_SIZE;i++)
R[i] = ZIOBRO;
/*
Mnozymy.
*/
for(i=ZIOBRO;i<lenA+lenB;i++) {
for(n=ZIOBRO;n<lenB;n++) {
if((i-n >= ZIOBRO) && (i-n<lenA))
tempX[n]=A[i-n]*B[n];
else
tempX[n]=ZIOBRO;
}
/*
Sumujemy tempX.
*/
x=ZIOBRO;
for(n=ZIOBRO; n<lenB;n++) x+=tempX[n];

C[i]=(x + R[i]) % 10;
/* Procedura pomocnicza
printf("n=%d %d %d %d\n",i,x,R[i],C[i]);
*/
R[i+1]=(x + R[i])/10;
}
}

int main () {
//Deklaracja tablic i zmiennych.
char tempA[MAX_SIZE], tempB[MAX_SIZE];
int A[MAX_SIZE], B[MAX_SIZE], C[2*MAX_SIZE],lenA,lenB,i;

//Czytanie liczby A
printf("Podaj pierwsza liczbe niedluzsza niz %d znakow: ",MAX_SIZE);
gets(tempA);
lenA = strlen(tempA); //Przypisujemy zmiennej lenA - dlugosc liczby A
//Sprawdzamy, czy podana liczba nie jest za dluga.
if (lenA > MAX_SIZE) {
printf("Podana liczba jest za duza.\n");
system("pause");
return 1;
}
//Czytanie liczby B
printf("Podaj druga liczbe niedluzsza niz %d znakow: ",MAX_SIZE);
gets(tempB);
lenB = strlen(tempB); //Przypisujemy zmiennej lenB - dlugosc liczby B
//Sprawdzamy, czy podana liczba nie jest za dluga.
if (lenB > MAX_SIZE) {
printf("Podana liczba jest za duza.\n");
system("pause");
return 1;
}

//Zamieniamy ciag znakow na tablice int.
convert(tempA,A);
convert(tempB,B);
//Mnozymy
mn(A,B,lenA,lenB,C);
printf("Wynik:\n");
for (i=ZIOBRO;i<lenA+lenB-1;i++)
printf("%d",C[lenA+lenB-i-2]);
printf("\n");

system("pause");
return ZIOBRO;
}

Buku

To jeszcze ja wrzucę swój program. Nie mnoży on dwóch podanych przez użytkowanika dużych liczb, tylko liczy x! korzystając z mnożenia i dodawania dużych liczb. 100! można policzyć bez trudu, myślę że 1000! również da radę, tylko problem jest taki, że trudno ocenić jaki rozmiar tablicy wtedy ustalić - dam za mały - program w pewnym momencie będzie chciał zapisać cyfrę w komórce tablicy spoza zakresu, dam za duży - program będzie liczył i liczył i liczył... Szczerze mówiąc nie chciało mi się czekać na wynik, ale algorytm z pewnością jest dobry. Może ktoś będzie miał cierpliwości na tyle, by wyliczyć 1000!

Ps: program teoretycznie oblicza maksymalnie 9999!. Gdyby ktoś był na tyle szalony bądź też skrajnie znudzony i chciał więcej może łatwo dopisać jedną czy też dwie linijki kodu które umożliwią programowi liczenie x! dla jeszcze większych liczb.

------------------------------------

#include <stdio.h>
#include <stdlib.h>
#define rozmiar 200
#define silnia 100

int dodaj(int A[], int B[], int C[])
{ int i, p, su;
p=0;
for(i=0; i<rozmiar; i++)
{ su=p+A[i]+B[i];
C[i]=su%10;
p=su/10;}
return 0; }

int mnoz(int A[], int B[], int C[])
{ int Rob[rozmiar];
int W[rozmiar];
int d, i, j, k, m, p;
d=0;
for(i=0; i<rozmiar; i++)
{C[i]=0; W[i]=0;}
for(i=0; i<rozmiar; i++)
{ p=0;
for(j=0; j<rozmiar; j++)
Rob[j]=0;
for(k=0; k<rozmiar; k++)
{ Rob[k+d]+=((B[i]*A[k])%10)+p;
p=(B[i]*A[k])/10;}

dodaj(C, Rob, W);
for(m=0; m<rozmiar; m++)
C[m]=W[m];
d++; }
return 0;}

int main()
{ int K[rozmiar];
int L[rozmiar];
int M[rozmiar];
int i, l, k;

for(i=0; i<rozmiar; i++)
{ K[i]=0; L[i]=0; M[i]=0; }

K[0]=1;

for(i=2; i<silnia+1; i++)
{ L[0]=i%10;
L[1]=(i%100)/10;
L[2]=(i%1000)/100;
L[3]=i/1000;

mnoz(K, L, M);
for(l=0; l<rozmiar; l++)
K[l]=M[l];
}

for(i=0; i<rozmiar; i++)
if (M[rozmiar-i-1] != 0) {k=i; break;}

printf("%d! = ", silnia);
for(i=k; i<rozmiar; i++)
printf("%d", M[rozmiar-i-1]);

printf("\n\n");
system("PAUSE");
return 0;
}

Musashi

Mój programik troszkę inaczej wygląda Wink

Co o tym sądzicie?
Oczywiście dla 100! wystarczą tablice o rozmiarze 200 ale ten program pisany jest dla max 1000! Wink

Jest mało wydajny ale nie chciało mi sie go przyspieszać na razie Razz

Buku

Jeżeli komuś się chce policzyć 1000! to najlepiej dopisać sobie linijkę w kodzie odpowiadającą za wypisanie na ekran czegoś w stylu "licze x=x*i" gdzie i jest liczbą przez którą aktualnie mnożymy. Tym sposobem udało mi się wyczekać aż doliczy do 1000! Fajnie ta liczba wygląda i o ile się nie mylę ma 2568 znaków [dla pewności lepiej ustawić rozmiar tablicy na 2600 - w końcu im większy tym program dłużej się męczy]

Musashi

1000!= 402 387 260 077 093 773 543 702 433 923 003 985 719 374 864 210
543 799 910 429 938 512 398 629 020 592 044 208 486 969 404 800 479 988
196 058 631 666 872 994 808 558 901 323 829 669 944 590 997 424 504 087
918 823 627 727 188 732 519 779 505 950 995 276 120 874 975 462 497 043
278 094 646 496 291 056 393 887 437 886 487 337 119 181 045 825 783 647
012 476 632 889 835 955 735 432 513 185 323 958 463 075 557 409 114 262
349 347 553 428 646 576 611 667 797 396 668 820 291 207 379 143 853 719
808 126 867 838 374 559 731 746 136 085 379 534 524 221 586 593 201 928
297 308 431 392 844 403 281 231 558 611 036 976 801 357 304 216 168 747
871 348 312 025 478 589 320 767 169 132 448 426 236 131 412 508 780 208
683 151 027 341 827 977 704 784 635 868 170 164 365 024 153 691 398 281
213 092 761 244 896 359 928 705 114 964 975 419 909 342 221 566 832 572
333 186 116 811 553 615 836 546 984 046 708 975 602 900 950 537 616 475
421 889 679 646 244 945 160 765 353 408 198 901 385 442 487 984 959 953
723 355 556 602 139 450 399 736 280 750 137 837 615 307 127 761 926 849
625 200 015 888 535 147 331 611 702 103 968 175 921 510 907 788 019 393
194 545 257 223 865 541 461 062 892 187 960 223 838 971 476 088 506 276
146 674 697 562 911 234 082 439 208 160 153 780 889 893 964 518 263 243
762 179 168 909 779 911 903 754 031 274 622 289 988 005 195 444 414 282
361 745 992 642 956 581 746 628 302 955 570 299 024 324 153 181 617 210
036 786 906 117 260 158 783 520 751 516 284 225 540 265 170 483 304 226
286 933 061 690 897 968 482 590 125 458 327 168 226 458 066 526 769 958
272 807 075 781 391 858 178 889 652 208 164 348 344 825 993 266 043 367
999 612 831 860 788 386 150 279 465 955 131 156 552 036 093 988 180 612
600 301 435 694 527 224 206 344 631 797 460 594 682 573 103 790 084 024
465 657 245 014 402 821 885 252 470 935 190 620 929 023 136 493 273 497
958 720 559 654 228 749 774 011 413 346 962 715 422 845 862 377 387 538
865 688 976 461 927 383 814 900 140 767 310 446 640 259 899 490 222 221
339 901 886 018 566 526 485 061 799 702 356 193 897 017 860 040 811 889
311 021 171 229 845 901 641 921 068 884 387 121 855 646 124 960 798 722
296 819 372 388 642 614 839 657 382 291 123 125 024 186 649 353 143 970
531 926 649 875 337 218 940 694 281 434 118 520 158 014 123 344 828 015
694 290 153 483 077 644 569 099 073 152 433 278 288 269 864 602 789 864
083 506 217 095 002 597 389 863 554 277 196 742 822 248 757 586 765 752
207 573 630 569 498 825 087 968 928 162 753 848 863 396 909 959 826 280
450 994 871 701 244 516 461 260 379 029 309 120 889 086 942 028 510 640
399 457 156 805 941 872 748 998 094 254 742 173 582 401 063 677 404 595
160 829 230 135 358 081 840 096 996 372 524 230 560 855 903 700 624 271
909 004 153 690 105 933 983 835 777 939 410 970 027 753 472 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

I wszystko jasne... ;-]

kisieL

tak sobie trzaskam właśnie tą naszą genialną listę i przy zadaniu 2.6 pojawił mi się problem następujący: jaki jest maksymalny rozmiar tablicy? Bo chciałem sobie dać milion elementów, to mi sie program zawiesza :/

Musashi

zawiesza ci się? a może on tylko tak długo liczy?

kisieL

zawiesza -> wyskakuje komunikat windowsa, żeby wysłać informację Microsoftowi Razz

maUa

a nie lepiej kupic programy w A0 razem z tytulem magistra Razz

Gość

LISTA 3 - cwiczenia 3,4,5 w jednym:

#include <stdio.h>
#include <string.h>
#include <math.h>

char ZNAKI [16] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};

void strev (char s[]) {
int j = 0;
char x;

for ( j=0; j<strlen(s)/2; j++) {
x = s[j];
s[j] = s[strlen(s)-1 - j];
s[strlen(s)-1 - j] = x;
}
}

void uint2str (unsigned int n, int r, char s[]) {

int i = 0;

if (n==0) s[i++] = '0';
else
while (n) {
s[i++] = ZNAKI [n % r];
n = n / r;
}

s[i] = '\0';
strev(s);
}

int char2uint (int r, char s[]) {
int k,i = 0;
int wynik = 0;

while (s[i] != '\0') {
k=0;
while (s[i] != ZNAKI[k]) k++;
if (k >= r) return -1;
wynik = wynik*r + k;
i++;
}
return wynik;
}

void d2r (double x, char s[], int r) {
int i = 0;
while (i < 40) {
x=x*r;
s[i]=ZNAKI[(int)floor(x)];
x-=floor(x);
i++;
}
s[i]='\0';
}

int main () {

int n, r;
char s[100],t[100];
double x;

printf ("podaj liczbe n : ");
scanf ("%d", &n);
printf ("podaj podstawe r : ");
scanf ("%d", &r);
printf ("podaj liczbe x : ");
scanf ("%lf", &x);

uint2str (n,r,s);
printf ("%s\n", s);

printf("%d\n", char2uint(r,s));

uint2str((int)floor(x),r,t);
d2r (x-floor(x),s,r);

printf("%s,%s\n", t, s);

printf ("\n\n");
return 0;
}

Gość

Gość