infoarena

infoarena - concursuri, probleme, evaluator, articole => Articole => Subiect creat de: Paul Diac din Noiembrie 25, 2005, 11:07:58



Titlul: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Paul Diac din Noiembrie 25, 2005, 11:07:58
Se poate folosi primul "smen" si pe tablouri bidimensionale? De exemplu daca vreau sa folosesc a[0..100][-100..100] se poate cumva?

int A[201];
#define A (A + 100)
Asta era pentru tablouri unidimensionale.

stiu ca se poate remedia cu o noua dimensiune, ceva de genul a[0..100][0..1][0..100] cu a
  • [j] consider j-ul pozitiv si a[1][j] consdier j-ul negativ. Asta in schimb complica algoritmul, adica apar foruri in plus, etc...


Titlul: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Adrian Vladu din Noiembrie 25, 2005, 13:07:18
Da. Gandeste-te cum este alocata matricea. Valorile din celulele ei sunt pastrate pe pozitii consecutive de memorie. Astfel dupa pozitia in care este pastrata valoarea lui A[ x ][0] urmeaza valoarea lui A[ x ][1], ..., dupa pozitia lui A[ x ][NMAX - 1] urmeaza valoarea lui A[x + 1][0] etc.

Asadar, A[ i ][j] poate fi adresat altfel prin A + i * NMAX + j (am notat cu NMAX numarul de coloane cu care este declarata matricea).

Dar macro-ul ce face? Inlocuieste direct in cod orice aparitie a lui A cu A + 100. Adica daca vei avea declarat A[ i ][j], care este acelasi cu A + i * NMAX + j, acel define il va transforma in A + 100 + i * NMAX + j, adica A[ i ][j +100]  :D

Ai totusi grija cu astfel de define-uri, deoarece in programarea serioasa nu sunt recomandate, deoarece (de multe ori datorita neintelegerii modului  in care functioneaza) pot duce la erori greu de gasit si de reparat. ;)


Titlul: Raspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Andrei Homorodean din Ianuarie 12, 2007, 17:09:12
Imi cer scuze daca gresesc, dar mie functia de inmultire a2-a nr mari nu-mi da bine intotdeauna. Nu se poate cineva uita peste ea, sa dea niste teste si sa-mi zica daca gresesc? Multumesc, si scuzati orice deranj :?

Aceasta este functia:
Cod:
   1. void mul(int A[], int B[])  
   2. { 
   3.       int i, j, t, C[]; 
   4.       memset(C, 0, sizeof(C)); 
   5.       for (i = 1; i <= A[0]; i++) 
   6.       { 
   7.               for (t=0, j=1; j <= B[0] || t; j++, t/=10) 
   8.                       C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10; 
   9.               if (i + j - 2 > C[0]) C[0] = i + j - 2; 
  10.       } 
  11.       memcpy(A, C, sizeof(C)); 
  12. }
 

Nu stiu, poate ma insel(din nou), chiar daca mie nu imi merge pe borland e corect sa zici " int C[]; "? Mie nu mi se prea pare...


Titlul: Raspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Marius Stroe din Ianuarie 12, 2007, 18:00:28
Functia e corecta. Trebuie doar sa ai 0 daca depasesti numarul de cifre al numarului pastrat in vector.

Prin int C[] lasa dimensiunea vectorului la alegerea ta.


Titlul: Raspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Sima Cotizo din Ianuarie 13, 2007, 14:56:06
Da ?!? ... :) nu ma gandisem, intelegeam altceva   =D&gt;
Totusi, e la fel de corect sa pui :
Cod:
void mult(int *A, int *B, int *C) {
    ...
}
si tot aia e... si e corecta functia, dar trebuie sa ai mare grija cum o folosesti ca pot ramane niste valori in C dinainte... prin memorie... si sa afecteze felul cum functioneaza... eu asta am patit de multe ori in ultmul timp  :x


Titlul: Raspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Marius Stroe din Ianuarie 13, 2007, 19:46:27
Daca vectorul C e transmis ca pointer, atunci ai grija la memset(C, 0, sizeof(C)), ca sizeof(C) == sizeof(int).


Titlul: Raspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Mircea Pasoi din Ianuarie 13, 2007, 22:08:55
Fixed. Nu uitati ca site-ul este acum un wiki ceea ce inseamna ca orice utilizator poate edita continutul, asadar cand mai gasiti erori nu ezitati sa le corectati chiar voi.. user power  :thumbup:


Titlul: Raspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Andrei Homorodean din Februarie 02, 2007, 13:14:58
Cod:
#include <stdio.h>
#include <memory.h>

#define NMAX 100


int a[NMAX], b[NMAX];


void mul(int A[], int B[])
{
int i, j, t, C[NMAX];


memset(C, 0, sizeof(C));


for (i = 1; i <= A[0]; i++)
{
for (t=0, j=1; j <= B[0] || t; j++, t/=10)
C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
if (i + j - 2 > C[0]) C[0] = i + j - 2;
}

memcpy(A, C, sizeof(C));
}


void read(int v[NMAX])
{
int i;

scanf("%d\n", &v[0]);

for(i = 1; i <= v[0]; ++i)
scanf("%d ", &v[i]);

scanf("\n");
}

void write(int v[NMAX])
{
int i;

for(i = 1; i <= v[0]; ++i)
printf("%d", v[i]);
}

int main()
{
freopen("mare.in", "r", stdin);
freopen("mare.out", "w", stdout);

read(a);

read(b);

mul(a, b);

write(a);

fclose(stdin);
fclose(stdout);


return 0;
}

Bun, si totusi, tot nu inteleg ce nu fac bine, m-a terminat functia asta...

3
4 1 5
4
1 4 5 6

Pentru testul asta ar trebui sa dea 604240..


Titlul: Raspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Airinei Adrian din Februarie 02, 2007, 13:44:34
Nu ai facut putin debug? Ideea e ca numarul trebuie sa-l tii invers in vector.


Titlul: Raspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Andrei Homorodean din Februarie 02, 2007, 14:38:28
Ce bomba sunt....Mi-e si rusine, dar faza e ca e atat de incurcata functia aia de...... multumesc mult, oricum :|


Titlul: Răspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: HighScore din Martie 03, 2007, 21:36:37
la smenul lui "Mars" nu ar trebui sa se prezinte in enunt si faptul ca B0=0?


Titlul: Răspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Silviu-Ionut Ganceanu din Martie 10, 2007, 11:15:00
la smenul lui "Mars" nu ar trebui sa se prezinte in enunt si faptul ca B0=0?

Mai degraba ar trebui precizat ca indicii (st, dr) din operatia ADUNA respecta inegalitatea 0 <= st <= dr < N. B-ul este plin cu 0 la inceputul operatiilor presupunand ca A este si el umplut tot cu 0. Apropo, gandeste-te cum adaptezi algoritmul daca elementele lui A  au niste valori initiale.


Titlul: Răspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: HighScore din Martie 13, 2007, 16:38:41
adicã ce valori initiale ar trebui sa avem in B dacã A-ul este deja initializat? :?


Titlul: Răspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Silviu-Ionut Ganceanu din Martie 13, 2007, 22:53:15
adicã ce valori initiale ar trebui sa avem in B dacã A-ul este deja initializat? :?

Da.


Titlul: Răspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Stefan Istrate din Ianuarie 08, 2008, 01:10:18
La implemetarea AVL-urilor din articol, se pare ca functiile rotleft si rotright fac exact pe dos ceea ce ar trebui sa faca: rotleft face rotatie la dreapta, iar rotright la stanga. Conform http://en.wikipedia.org/wiki/Tree_rotation (http://en.wikipedia.org/wiki/Tree_rotation), ar trebui exact invers. Am dreptate sau mi se pare mie? :)


Titlul: Răspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Mircea Pasoi din Ianuarie 08, 2008, 02:18:24
La implemetarea AVL-urilor din articol, se pare ca functiile rotleft si rotright fac exact pe dos ceea ce ar trebui sa faca: rotleft face rotatie la dreapta, iar rotright la stanga. Conform http://en.wikipedia.org/wiki/Tree_rotation (http://en.wikipedia.org/wiki/Tree_rotation), ar trebui exact invers. Am dreptate sau mi se pare mie? :)

Depinde cum privesti :)


Titlul: Răspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Stefan Istrate din Ianuarie 08, 2008, 08:52:39
Pai consider rotatie stanga cand radacina subarborelui se duce in stanga. La fel am vazut in multe alte surse, dar, intr-adevar, nu se schimba corectitudinea algoritmului.


Titlul: Răspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Adrian Diaconu din Ianuarie 08, 2008, 09:48:49
Poti sa te gandesti ca rotleft e o rotatie in urma careia nodul stang ajunge radacina.


Titlul: Răspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Andrei Grigorean din Ianuarie 08, 2008, 18:18:37
Si mie mi se pare ca ar trebui sa fie invers. :)


Titlul: Răspuns: Multe "smenuri" de programare in C/C++... si nu nu
Scris de: Stefan Istrate din Februarie 20, 2009, 01:44:55
Discutiile pot continua in topicul destinat acestui articol: http://infoarena.ro/forum/index.php?topic=3673.0