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

[•stef2n]

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

[•INSiDe123]

la functia : inmultirea unui numar mare cu un numar mare

ce inseama memset si memcpy ..

[•gabor_oliviu1991]

memset(vect, x, sizeof(vector)); pune in vect[] pe toate pozitiile elementul x, iar memcpy(A,B,sizeof(B)) copiaza vectorul B in vectorul A.

[•INSiDe123]

ok.. ms.. si pt a folosi astea trebuie o inclusa o anumita biblioteca?

[•gabor_oliviu1991]

string.h

[•sima_cotizo]

memset(vect, x, sizeof(vector)); pune in vect[] pe toate pozitiile elementul x, iar memcpy(A,B,sizeof(B)) copiaza vectorul B in vectorul A.

De fapt nu pune chiar elementul x. Daca x este un byte, e ok, dar daca este int nu functioneaza cum te astepti tu (si in cazul asta cel mai sigur e sa initializezi vectorii cu un for).

[•vladtarniceru]

foarte tare

adica sunt niste algoritmi foarte simpli
eu aveam altii(facuti de mine)  mult mai inceti si mai lungi
multumesc mult 

[•APOCALYPTO]

Salut!
Am o intrebare.
Daca am un numar mare de 100.000 de cifre in baza 16 si trebuie sa-l tranform in unul in baza 8 ce pot face sa imbunatatesc algoritmul urmator(care ruleaza in 16 secunde pe cand mie imi trebuie maxim 1 secunda):

Cod:

#include<iostream>
#include<cstring>
#include<fstream>
#include<cstdlib>
using namespace std;

void div(int A[], int B)
{
      int i, t = 0;
      for (i = A[0]; i > 0; i--, t %= B)
              A[i] = (t = t * 10 + A[i]) / B;
      for (; A[0] >= 1 && !A[A[0]]; A[0]--);
}
void inm(int A[],int B)
{int i,t=0;
    for(i=1;i<=A[0]||t;i++,t/=10)
        A[i]=(t+=B*A[i])%10;
    A[0]=i-1;
}
int mod(int A[], int B)
{
      int i, t = 0;
      for (i = A[0]; i > 0; i--)
              t = (t * 10 + A[i]) % B;
      return t;
}
void inm2(int A[],int nova[],int B)
{int i,t=0;
    for(i=1;i<=A[0]||t;i++,t/=10)
        nova[i]=(t+=B*A[i])%10;
    nova[0]=i-1;
}
void add(int A[],int B[])
{int i,t=0;
 for(i=1;i<=A[0]||i<=B[0]||t;i++,t/=10)
    B[i]=(t+=A[i]+B[i])%10;
 B[0]=i-1;

}
int main()
{
    int i=0;
int a[100005]={0};
int *suma=new int[200000],*produs=new int[200000],*pow16=new int[200000],*rez=new int[200000];
char x;
int k=0;

ifstream fin("hex.in");
    while(fin>>x)
    {k++;
        if(x>='A'&&x<='F')
          a[k]=10+x-'A';
        else
           a[k]=x-'0';
    }

    fin.close();

pow16[1]=1;
pow16[0]=1;
for(i=k;i>=1;i--)                                        //transform in baza 10, numarul in baza 10 va fi vectorul suma care este de forma
    {                                                        // a[1]*16^k+a[2]*16^k-1+... din acest motiv l-am numit suma
    for(int contor=0;contor<=produs[0];contor++)
       produs[contor]=0;
     produs[0]=produs[1]=1;     // iar vectorul produs reprezita rezultatul inmultire dintre a[x] si uterea lui 16 corespunzatoare
    inm2(pow16,produs,a[i]);
    add(produs,suma);                           
    inm(pow16,16);                              // eu nu calculez de k ori puterile lui 16 ci pur si simplu stiind 16^x il aflu pe 16^x+1
    }



 i=0;                                                                    //tranform in baza 8
 while(suma[0]!=0)                          // cat timp numarul in baza 10 este diferit de 0 adica are macar o cifra diferita de 0
  { i++;
  rez[i]=mod(suma,8);                     //restul impartirii la 8

  div(suma,8);                               //impartima numarul in baza 10 la 8

  }

freopen ("hex.out","w",stdout);
  for(k=i;k>=1;k--)
   printf("%d",rez[k]);
printf("\n");

 return 0;

 }

Multumesc anticipat!

[•wefgef]

Trebuie sa treci numarul prin baza 2.

[•APOCALYPTO]

Trebuie sa treci numarul prin baza 2.

De ce?
Asa merge mai repede?

[•stef2n]

O cifră în baza 16 reprezintă 4 cifre în baza 2. După ce ai transformat în baza 2, poți grupa câte 3 cifre și obții numărul în baza 8.

[•APOCALYPTO]

Daca am 10101 cum impart in cate 3?
asa:
101 01
sau asa :
10 101 ?

[•gabitzish1]

De la dreapta la stanga : 10 101. Pornesti de la cifra unitatilor, continui cu a zecilor.. si asa mai departe, si unde nu mai ai biti destui poti completa cu 0'uri in fata.

[•MciprianM]

LA "Smenul lui Batog" unde se imparte intervalul in bucati de sqrt ( n ) cum se face query-ul?

[•klamathix]

Pentru intervale de forma k * sqrt(n) , (k + 1) * sqrt(n) ai raspunsul in o(1). Profiti de chestia asta ca sa calculezi cat mai mult din suma intervalului [st,dr] in timp constant si apoi ce ramane poti aduna manual.

[•devilkind]

De fapt calculezi manual cu for de la st pana la primu numar de forma k * sqrt(n). Apoi incepi sa mergi din sqrt(n) in sqrt(n) pana ajungi la cel mai mare numar care e multiplu de sqrt(n) dar mai mic decat dr. De acolo calculezi din nou manual pana la dr. Worst case o sa ai complexitatea 3 * sqrt(n) = O(sqrt(n))

[•MciprianM]

Dar nu inteleg un lucru. Sa luam ca exemplu datele din enunt. Un sir A_0...15 si un sir B_0...3. Sa presupunem ca la inceput toate elementele acestor siruri sunt egale cu 0. Apoi facem update pe intervalul [ 4, 7 ]- sa zicem ca crestem elementele din intervalul asta cu 2- apoi cautam sa gasim suma elementelor din intervalul [ 6, 8 ]. Acest interval are prima parte ( [ 6, 7 ] ) in intervalul [ 4, 7 ] si a doua parte ( [ 8,8 ] ) in intervalul [ 8, 11 ]. Acuma daca vom cauta elementele 6 si 7 in sirul A, acestea vor fi 0, nu? Cand am facut Update pe intervalul [ 4, 7 ] am crescut cu 2 doar B₁, elementele din A au ramas nemodificate. Un astfel de exemlu poate fi gasit si cand intervalul a carui suma o cautam contine un interval de forma [ k sqrt(n), (k+1) sqrt(n) ]. Unde gresesc? Din enuntul articolului si din ce ati spus voi nu imi dau seama.

[•devilkind]

Ah, la primul post pe care l-am dat am crezut ca update-urile sunt pe fiecare element nu pe interval. Pai in cazul asta in vectorul B tii minte ce update-uri ai facut (ma rog cred ca iti mai trebuie un vector aici pe care sa tii minte suma initiala pe fiecare bucata). In momentul asta cand faci query-ul pe 6-8, o sa parcurgi manual toate elementele, iar pentru 6 si 7 o sa vezi ca sunt 0 in A insa o sa vezi in B ca ai facut un update pe bucata respectiva si deci o sa aduni la valoarea din A valoarea respectiva din B la fiecare element.

[•Bit_Master]

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

[•hunter_ionutzzz]

imi zice cnv  ce inseamna step <<= 1  de la cautare binara ?

[•blasterz]

step *= 2;

e operatie pe biti.. a << b inseamna a * (2^b)
iar a >> b inseamna a / (2^b)

[•lucian666]

am o intrebare;la primul exemplu cel cu indexarea de la -100;
daca vreau sa indexez un vector de frecventa care memoreaza valori de la -1000 pana la 1000;
int a[2001];
#define a( a + 1000)
este corect?

[•Magnus]

da, e corect

[•Doru_AC]

My first comment

Ce face linia

Cod:

for (; A[0] > 1 && !A[A[0]]; A[0]--); ?

?

Ce inseamna A[A[0]] ?
Ms !

Later Edit : Mi-am dat seama.

[•vladtarniceru]

elimina zerourile care raman in plus la inceputul numarului (care practic e sfarsitul pentru ca la operatii pe numere mari trebuie rotite mai intai numerele)