Pagini: 1 [2] 3   În jos
  Imprimă  
Ajutor Subiect: Multe "smenuri" de programare in C/C++... si nu numai!  (Citit de 38085 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
MoroJr
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #25 : Ianuarie 09, 2012, 20:04:21 »

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.
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #26 : Ianuarie 09, 2012, 21:09:44 »

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.
Memorat

Am zis Mr. Green
Robytzza
De-al casei
***

Karma: -49
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #27 : Ianuarie 14, 2012, 12:15:49 »

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;
}
Memorat
lovematter26
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #28 : Ianuarie 16, 2012, 20:26:54 »

pentru cei mai incepatori erau perfecte si niste comentarii la anumite instructiuni  Rolling Eyes
Memorat
VisuianMihai
De-al casei
***

Karma: -9
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #29 : Ianuarie 17, 2012, 16:03:57 »

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?
Memorat
Robytzza
De-al casei
***

Karma: -49
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #30 : Februarie 02, 2012, 11:03:02 »

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
Memorat
andrici_cezar
De-al casei
***

Karma: -47
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #31 : Martie 12, 2012, 09:52:24 »

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

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #32 : Martie 13, 2012, 15:27:22 »

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.
« Ultima modificare: Martie 13, 2012, 15:59:10 de către Alexandru-Iancu Caragicu » Memorat
laurion
De-al casei
***

Karma: -41
Deconectat Deconectat

Mesaje: 102



Vezi Profilul
« Răspunde #33 : Martie 13, 2012, 15:38:19 »

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...)
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #34 : Martie 13, 2012, 15:42:03 »

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 Wink.

[PS] Am postat in acelasi timp Smile.

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.
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #35 : Martie 13, 2012, 16:07:17 »

@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?
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #36 : Martie 13, 2012, 21:28:46 »

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 Smile.
Memorat
VisuianMihai
De-al casei
***

Karma: -9
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #37 : Iunie 22, 2012, 21:30:17 »

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...
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 341
Deconectat Deconectat

Mesaje: 804



Vezi Profilul
« Răspunde #38 : Iunie 22, 2012, 21:39:11 »

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 Cool 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.
Memorat
VisuianMihai
De-al casei
***

Karma: -9
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #39 : Iunie 22, 2012, 21:41:43 »

A chiar... la asta nu m-am gandit Aha
Memorat
CezarMocan
Nu mai tace
*****

Karma: 252
Deconectat Deconectat

Mesaje: 567



Vezi Profilul
« Răspunde #40 : Iunie 23, 2012, 05:05:08 »

Budau Adrian e un boss Smile
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #41 : Decembrie 12, 2012, 14:02:24 »

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.
Memorat
dutzul
De-al casei
***

Karma: 42
Deconectat Deconectat

Mesaje: 119



Vezi Profilul
« Răspunde #42 : Ianuarie 30, 2013, 21:14:07 »

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.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #43 : Ianuarie 30, 2013, 21:18:48 »

Prin A se intelege defapt adresa de inceput a vectorului. Deci, A[3] e defapt A + 3.
Memorat
dutzul
De-al casei
***

Karma: 42
Deconectat Deconectat

Mesaje: 119



Vezi Profilul
« Răspunde #44 : Februarie 07, 2013, 01:28:57 »

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
« Ultima modificare: Februarie 07, 2013, 01:43:10 de către Bodnariuc Dan-Alexandru » Memorat
soriyn
Vorbaret
****

Karma: 24
Deconectat Deconectat

Mesaje: 150



Vezi Profilul
« Răspunde #45 : Februarie 07, 2013, 01:53:11 »

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.
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #46 : Februarie 07, 2013, 14:19:05 »

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));
}
Memorat
hiticas_abel
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #47 : Iunie 26, 2013, 11:49:36 »

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.
Memorat
pitbull007
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #48 : Mai 08, 2014, 14:07:35 »

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


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #49 : August 06, 2018, 11:29:27 »

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.
Memorat
Pagini: 1 [2] 3   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines