Multe "smenuri" de programare in C/C++... si nu numai!

[MoroJr]

La adunarea numerelor mari

Cod:

void add(int A[], int B[])
{
      int i, t = 0;
      for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)
              A[i] = (t += A[i] + B[i]) % 10;
      A[0] = i - 1;
}

este corecta functia daca cele 2 numere au acelasi numar de cifre ( A[0] == B[0] ), iar in acest caz suma cifrelor dominante este mai mica decat 9.  

Si de ce A[0] = i - 1 ? Daca am avea:

Cod:

A[] = {3, 9, 9, 9};
B[] = {3, 8, 8, 8};
add(A, B);

Vectorul A ar trebui sa fie 47881.

[•pauldb]

1. De ce nu?

2. A[0] = i-1 pentru ca la finalul for-ului i va avea o valoare pentru ca nici una dintre cele 3 conditii nu este adevarata. Desi nu cred ca rezultatul pe care il astepti tu pentru cazul respectiv e corect.

[•Robytzza]

La solutia lui Mihai Patrascu ar mai merge optimizat un pic:

Cod:

int x[n], n;

int best_binary(int elem)
{
    int poz = 0, nr_bit = 0, m = n;

    for ( ; m ; m = m & ((nr_bit = m) - 1) );

    for ( ; nr_bit ; nr_bit >>= 1)
        if (poz + nr_bit < n && x[poz + nr_bit] <= elem)
            poz += nr_bit;

    return poz;
}

[•lovematter26]

pentru cei mai incepatori erau perfecte si niste comentarii la anumite instructiuni 

[•VisuianMihai]

Nu inteleg la smenul lui mars. De ce complexitatea de adunare pe un interval este O(1)?
EX:
n = 6
sirul: 1 2 3 4 5 6 si vreau sa incrementez pe intervalul [1,4] valorile cu 10 .
Cum se face update-ul in B daca A = B[0]+...+B?

[•Robytzza]

A = [1,  2, 3, 4, 5, 6]
B = [0, 10, 0, 0, 0, -10]
Este O(1) pentru update si O(N) pentru afisarea sirului. Este eficient doar atunci cand ai multe operatii de update si doar una de afisare.
Ai = Ai + B0 + B1 + ... + Bi
A0 = 1 + 0 = 1
A1 = 2 + 10 = 12
A2 = 3 + 10 = 13
A3 = 4 + 10 = 14
A4 = 5 + 10 = 15
A5 = 6 + 10 - 10 = 6

[•andrici_cezar]

Deci cautarea binara pe puteri a lui 2 e mai inceata decat cautarea binara normala. Puteti sa-mi explicat de ce se intampla asta?

[•Bit_Master]

La scaderea a doua numere mari, ce rol are conditia (i <= B[0])? Oricum vectorii in care se retin numerele mari trebuie sa aiba aceeasi lungime declarata si sa aiba numai cifre de 0 in fata. Se observa foarte clar asta la adunare, unde i avanseaza pana cand se termina ambele numere (si restul), si folosirea directa a termenilor A[ i ] si B[ i ] implica automat existenta de 0 la inceputul (dreapta) numarului pana la sfarsit.
Astfel, la scadere, daca i > B[0], B[ i ] va fi oricum 0, deci conditia ((i <= B[0]) ? B[ i ] : 0) mi se pare inutila.

[•laurion]

Deci cautarea binara pe puteri a lui 2 e mai inceata decat cautarea binara normala. Puteti sa-mi explicat de ce se intampla asta?

De ce zici asta? Diferenta mare nu este oricum, din moment ce amandoua fac in principiu cam acelasi lucru, doar ca cea pe puteri ale lui 2 are operatii mai usoare (doar adunare si shift-are), deci este probabil putin mai rapida.

La scaderea a doua numere mari, ce rol are conditia (i <= B[0])? Oricum vectorii in care se retin numerele mari trebuie sa aiba aceeasi lungime declarata si sa aiba numai cifre de 0 in fata. Se observa foarte clar asta la adunare, unde i avanseaza pana cand se termina ambele numere (si restul), si folosirea directa a termenilor A si B implica automat existenta de 0 la inceputul (dreapta) numarului pana la sfarsit.
Astfel, la scadere, daca i > B[0], B va fi oricum 0, deci conditia ((i <= B[0]) ? B : 0) mi se pare inutila.

Intr-o lume ideala, da, in B ar trebui ca peste lungimea B[0] sa fie doar cifre de 0. Dar sunt cazuri in care ai micsorat doar lungimea, dar nu ai mai pus si 0 (asta nu se aplica numai aici, de exemplu si la o stiva implementata manual, cand scoti un element doar micsorezi dimensiunea stivei, nu pui si 0 la sfarsit -- il stergi doar virtual, nu fizic, si la multe chestii din STL la fel...)

[•SpiderMan]

Prima data modifica pt. ca [i ] (adunat) inseamna italic, fa cum am pus eu. Apoi, tu cand ai un vector B sa zicem care retine numarul 1515125125, si tu ca sa il readuci la 0 faci B[0] = 0 (observi ca restul raman la fel). Astfel, cand faci scaderea, daca nu faci acea conditie, cand scazi din A (sa zicem 1234) pe B (care dupa B[0] = 0 o sa fie 15), B[3] o sa fie 1, nu o sa fie 0, pentru ca asa a ramas modificat. De aceea, daca i > B[0] (adica in cazul nostru decat 2, atunci valoarea aceea trebuie sa fie 0). Mai ai o varianta, cand faci B[0] = 0, sa faci memset (B, 0, sizeof (B)), dar dureaza prea mult, si nu merita .

[PS] Am postat in acelasi timp .

Iti propun sa tratezi codul asta :

Cod:

 atr (B, 1555);
atr0 (B);
atr (A, 194);
atr (B, 15);
sub (A, B); 

Unde sub (A, B) <-> A -= B, atr (A, X) <-> A = X (X int) si atr0 (A) <-> A = 0, adica ca si numar mare A[0] = 0.

[•Bit_Master]

@laurion, SpiderMan
Stiu ideea cu resetarea super rapida cu setarea lungimii numarului la 0 (am si spus mai devreme asta).

La functiile acelea de operatie pe numere mari, presupui ca in numar, dincolo de digitii care indica numarul gasesti doar 0. Adica nu putea fi adaptata ca sa functioneze si cand restul digitilor nu-s buni? Ca pierzi mult timp cand egalezi un nr cu 0 sa stai sa faci toate cifrele 0 (in loc sa reglezi direct dimensiunea 0).

Dar am inteles ca abordarea asta complica implementarea operatiilor si de multe ori nu este necesara.
La adunare nu merge daca sunt cifre reziduale in fata, se presupune ca sunt 0. Asa ca nu inteleg de ce scaderea ar fi diferita? De ce o functie este implementata intr-un stil si cealalta in alt stil?

[•SpiderMan]

Si adunarea trebuie facuta dupa modelul scaderii, doar ca nu e, eu am patit-o de multe ori si cu adunarea. Daca o sa am timp, o sa le modific cum trebuie .

[•VisuianMihai]

La operatiile pe numere mari nu prea cred ca merg codurile daca facem operatii cu numere negative... Am incercat si nu prea mergea.
Eu cred ca numerele ar trebui citite ca niste stringuri, in care a[0] sa fie numarul de cifre, iar a[a[0]+1] sa fie semnu sau ceva de genu...

[•freak93]

Sau daca vrei poti sa codifici numerele negative cum le face C++ in baza 2. Fie N numarul maxim de cifre ale unui numar mare din operatiile tale + 1. Atunci -1 e 9999....9(9 de N ori) -2 e 9999.9998(9 de N - 1 ori s un si asa mai departe descrascator. Acum poti face toate operatiile (mai putin impartirea) la fel. Si ca sa afli ce numar ai e doar inlocuiesti fiecare cifra cu 9 - acea cifra si aduni 1.

[•VisuianMihai]

A chiar... la asta nu m-am gandit

[•CezarMocan]

Budau Adrian e un boss

[•geniucos]

Am incercat sa fac problema blockout de pe campion folosind smenul lui Bogdan Batog.Ma poate ajuta cineva cu implementarea smen-lui pe matrice?La vector e logic dar la varianta 2D mi se pare foarte nasol.Implementarea mea are 400 de randuri si tot mai are WA.Daca imi poate arata cineva o implementare mai omeneasca si mai corecta as fi recunoscator.
Multumesc anticipat.

[•dutzul]

Am vazut smenul cu array neidaxat de la 0
 int A [ 201 ] ; 
 #define A (A + 100)
  imi poate si mie explica cum functioneaza asta?? adica A e vector.

[•PlayLikeNeverB4]

Prin A se intelege defapt adresa de inceput a vectorului. Deci, A[3] e defapt A + 3.

[•dutzul]

mersi.
totusi mai am o intrebare daca am o matrice de ex A [ i ][ j ] (fac problema rucsac sa zicem)
 j-ul poate da negativ in acest caz cum fac defineul?
cred ca
#define A (A+100) nu functioneaza.mersi anticipat

[•soriyn]

Nu stiu sa iti raspund la intrebare dar problema asta o poti rezolva si altfel. Sa zicem ca ai un vector A si -100<=i<=100. O sa declari A[205] sa zicem. Acum imi fixez originea pe pozitia 100. Pentru asta iei o variabila mid=100. Iar acum elementul de pe pozitia i din vector se gaseste la A[mid+i]. Asta o poti extinde mai departe si in 2 dimensiuni. Poate ca nu e asa elegant dar e o metoda.

[•blasterz]

mersi.
totusi mai am o intrebare daca am o matrice de ex A [ i ][ j ] (fac problema rucsac sa zicem)
 j-ul poate da negativ in acest caz cum fac defineul?
cred ca
#define A (A+100) nu functioneaza.mersi anticipat

Ai putea face asa:

Cod:

#include <cstdio>

int a[100][200];

#define a(i, j) a[i][j + 100]

int main() {
    a(10, -12) = 15;
    printf ("%d\n", a(10, -12));
}

[•hiticas_abel]

mersi.
totusi mai am o intrebare daca am o matrice de ex A [ i ][ j ] (fac problema rucsac sa zicem)
 j-ul poate da negativ in acest caz cum fac defineul?
cred ca
#define A (A+100) nu functioneaza.mersi anticipat

Ai putea face asa:

Cod:

#include <cstdio>

int a[100][200];

#define a(i, j) a[i][j + 100]

int main() {
    a(10, -12) = 15;
    printf ("%d\n", a(10, -12));
}

Merci mult! Asta m-a ajutat.

[•pitbull007]

procedura rotateright si rotateleft nu este buna sau daca este atunci se poate ilustra cu un exemplu pt ca imi este neclara.

[•oDexter]

Nu pot sa inteleg cum functioneaza smenul lui Mars 2d. Nu pot sa-mi dau seama cum ar vrea sa adun dupa in submatricea aia... si cel mai important nu inteleg de ce e B[x2+1][y2+1] += p care e un element in afara matricei noastre.