Nu exista diferente intre titluri.
Diferente intre continut:
Un dezavantaj fata de Pascal este faptul ca in C nu putem avea expresii de genul {@A[-100]@} unde $A$ este un vector. Dar acest lucru se poate remedia. Spre exemplu, daca vrem sa facem un vector $A$ cu elemente de la $-100$ la $100$ procedam astfel:
p(pre).
{@int A[201];@}
{@#define A (A + 100)@}
Folositi {@freopen()@} in loc de {@fopen()@} deoarece este mai comod, in special la concursurile in care intrare si iesirea sunt standard.
p(pre).
{@freopen("in.txt", "r", stdin);@}
{@freopen("out.txt", "w", stdout);@}
h2. "Smenul lui Mars" (Marius Andrei)
Consideram urmatoarea problema: se da un vector $A$ de $N$ elemente pe care se fac $M$ astfel de operatii: {@ADUNA(st, dr, x)@} - toate elementele cu indicii intre $st$ si $dr$ isi cresc valoarea cu {$x$}. La sfarsit trebuie sa se afiseze vectorul rezultat. In continuarea vom descrie o metoda care ne da un timp de rulare de $O(1)$ pentru operatia $ADUNA$ si $O(N)$ pentru a determina un element din vector. Vom construi un al doilea vector $B$ de $N+1$ elemente, cu proprietatea ca {$A{~i~} = B{~0~} + B{~1~} + ... B{~i~}$}. Astfel, o operatie ADUNA(st, dr, x) devine:
Consideram urmatoarea problema: se da un vector $A$ de $N$ elemente pe care se fac $M$ astfel de operatii: {@ADUNA(st, dr, x)@} - toate elementele cu indicii intre $st$ si $dr$ isi cresc valoarea cu {$x$}. La sfarsit trebuie sa se afiseze vectorul rezultat. In continuarea vom descrie o metoda care ne da un timp de rulare de $O(1)$ pentru operatia $ADUNA$ si $O(N)$ pentru a determina un element din vector. Vom construi un al doilea vector $B$ de $N+1$ elemente, cu proprietatea ca {$A{~i~} = B{~0~} + B{~1~} + ... B{~i~}$}. Astfel, o operatie {@ADUNA(st, dr, x)@} devine:
B[st] += x;
B[dr + 1] -= x;
p(pre).
{@B[st] += x;@}
{@B[dr + 1] -= x;@}
Da, este chiar asa de simplu! Pentru a determina un element A[i] vom aduna pur si simplu B[0] + B[1] + ... B[i]. Incercati pe foaie sa vedeti cum funtioneaza. Aceasta ideea poate fi extinsa si in doua dimensiuni, construind B astfel incat A[i][j] = suma subtabloului din B cu coltul in (0, 0) si (i, j), astfel (pt. ADUNA(x1,y1,x2,y2,v)):
Da, este chiar asa de simplu! Pentru a determina un element A{~i~} vom aduna pur si simplu {$B{~0~} + B{~1~} + ... B{~i~}$}. Incercati pe foaie sa vedeti cum funtioneaza. Aceasta ideea poate fi extinsa si in doua dimensiuni, construind $B$ astfel incat $A{~i,j~}$ = suma subtabloului din $B$ cu coltul in ({$0, 0$}) si ({$i, j$}), astfel (pt. {@ADUNA(x1,y1,x2,y2,v)@}):
B[x1][y1] += v;
B[x1][y2 + 1] -= v;
B[x2 + 1][y1] -= v;
B[x2 + 1][y2 + 1] += v;
p(pre).
{@B[x1][y1] += v;@}
{@B[x1][y2 + 1] -= v;@}
{@B[x2 + 1][y1] -= v;@}
{@B[x2 + 1][y2 + 1] += v;@}
Pe cazul general, daca vrem sa facem operatii in d dimensiuni vom avea o complexitate O(2^d). Reamintesc ca aceasta metoda este eficienta doar cand se vrea afisata vectorul/matricea/etc. doar la sfarsitul operatiilor, deoarece aflarea unui element este o operatie foarte ineficienta.
Pe cazul general, daca vrem sa facem operatii in $d$ dimensiuni vom avea o complexitate {$O(2^d^)$}. Reamintesc ca aceasta metoda este eficienta doar cand se vrea afisata vectorul/matricea/etc. doar la sfarsitul operatiilor, deoarece aflarea unui element este o operatie foarte ineficienta.
h2. Grafuri cu liste de adiacenta (ideea originala de la Radu Berinde)
Se stie (sau ar trebui sa se stie!) ca lucrul cu pointerii este foarte incet... astfel, cand retinem un graf rar (numar mare de noduri, numar mic de muchii) cu pointeri (vezi mai jos) incetinim foarte mult programul.
struct list
{
int n;
struct list *next;
}
typedef struct list list;
In contiuare vom prezenta o metoda care este de 3-4 ori mai rapida (adica parcurgerile DF , BF sau altii algoritmi ruleaza de 3-4 ori mai rapid cand graful este stocat astfel), dar are ca dezavantaj necesitatea de a citi de doua ori fisierul de intrare.
#include <stdlib.h>
#include <stdio.h>
int N, M, *G[N], Deg[N];
int main(void)
{
int i, j;
freopen("in.txt", "r", stdin);
scanf("%d %d", &N, &M);
for (; M > 0; M--)
{
scanf("%d %d", &i, &j);
Deg[i - 1]++, Deg[j - 1]++;
}
for (i = 0; i < N; Deg[i++] = 0)
G[i] = (int *) malloc(Deg[i]*sizeof(int));
fseek(stdin, 0, SEEK_SET);
scanf("%d %d", &N, &M);
for (; M > 0; M--)
{
scanf("%d %d", &i, &j);
i--, j--;
G[i][Deg[i]++] = j,
G[j][Deg[j]++] = i;
p(pre).
{@struct list@}
{@{@}
{@ int n;@}
{@ struct list *next;@}
{@}@}
{@typedef struct list list;@}
}
In contiuare vom prezenta o metoda care este de $3-4$ ori mai rapida (adica parcurgerile DF , BF sau altii algoritmi ruleaza de $3-4$ ori mai rapid cand graful este stocat astfel), dar are ca dezavantaj necesitatea de a citi de doua ori fisierul de intrare.
}
p(pre).
{@#include <stdlib.h>@}
{@#include <stdio.h>@}
{@ @}
{@int N, M, *G[N], Deg[N];@}
{@ @}
{@int main(void)@}
{@{@}
{@ @}
{@ int i, j;@}
{@ @}
{@ freopen("in.txt", "r", stdin);@}
{@ scanf("%d %d", &N, &M);@}
{@ for (; M > 0; M--)@}
{@ {@}
{@ scanf("%d %d", &i, &j);@}
{@ Deg[i - 1]++, Deg[j - 1]++;@}
{@ }@}
{@ for (i = 0; i < N; Deg[i++] = 0)@}
{@ G[i] = (int *) malloc(Deg[i]*sizeof(int));@}
{@ fseek(stdin, 0, SEEK_SET);@}
{@ scanf("%d %d", &N, &M);@}
{@ for (; M > 0; M--)@}
{@ {@}
{@ scanf("%d %d", &i, &j);@}
{@ i--, j--;@}
{@ G[i][Deg[i]++] = j,@}
{@ G[j][Deg[j]++] = i;@}
{@ }@}
{@ @}
{@ return 0;@}
{@}@}
Sporul de viteza se datoreaza faptului ca se folosesc vectori in loc de pointeri si struct-uri. Daca ne permite memoria putem evita citirea de doua ori a fisierul prin pastrarea muchiilor intr-o lista de muchii si apoi, dupa calcularea gradelor, inserarea muchiilor in liste. Pentru a demonstra eficienta acestei metode faceti urmatorul test: implementati o sursa cu pointeri si struct si implementati un BF, apoi scrieti codul de mai sus cu urmatoarele modificari:
...
for (i = 0; i < N; i++)
{
G[i] = (int *) malloc((Deg[i]+1)*sizeof(int));
G[i][Deg[i]] = -1;
Deg[i] = 0;
}
...
p(pre).
{@...@}
{@for (i = 0; i < N; i++)@}
{@{@}
{@ G[i] = (int *) malloc((Deg[i]+1)*sizeof(int));@}
{@ G[i][Deg[i]] = -1;@}
{@ Deg[i] = 0;@}
{@}@}
{@...@}
si implementati BF astfel:
void BF(int n)
{
int Q[N], ql, qr, *p;
char U[N];
memset(U, 0, sizeof(U));
U[Q[ql = qr = 0] = n] = 1;
for (; ql <= qr; ql++)
for (p = G[Q[ql]]; *p != -1; p++)
if (!U[*p]) U[Q[++qr] = *p] = 1;
}
p(pre).
{@void BF@}
{@{@}
{@ int Q[N], ql, qr, *p;@}
{@ char U[N];@}
{@ memset(U, 0, sizeof(U));@}
{@ U[Q[ql = qr = 0] = n] = 1;@}
{@ for (; ql <= qr; ql++)@}
{@ for (p = G[Q[ql]]; *p != -1; p++)@}
{@ if (!U[*p]) U[Q[++qr] = *p] = 1;@}
{@}@}
Apoi, incercati sa vedeti diferenta de timp intre cele doua programe... impresionant, nu?
h2. Numere mari (ideea originala de la Radu Berinde)
In continuare voi prezenta cum se pot realiza operatii pe numere mari cu foarte putine linii de cod. In general, multi programatori se complica la aceste operatii, desi nu este nevoie! Vom considera ca numerele mari sunt vectori in care elementul de indice 0 indica lungimea numarului, iar cifrele sunt retinute in ordinea inversa decat cea a citirii.
In continuare voi prezenta cum se pot realiza operatii pe numere mari cu foarte putine linii de cod. In general, multi programatori se complica la aceste operatii, desi nu este nevoie! Vom considera ca numerele mari sunt vectori in care elementul de indice $0$ indica lungimea numarului, iar cifrele sunt retinute in ordinea inversa decat cea a citirii.
h3. Suma a doua numere mari
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;
}
p(pre).
{@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;@}
{@}@}
h3. Inmultirea unui numar mare cu un numar mic
void mul(int A[], int B)
{
int i, t = 0;
for (i = 1; i <= A[0] || t; i++, t /= 10)
A[i] = (t += A[i] * B) % 10;
A[0] = i - 1;
}
p(pre).
{@void mul(int A[], int B)@}
{@{@}
{@ int i, t = 0;@}
{@ for (i = 1; i <= A[0] || t; i++, t /= 10)@}
{@ A[i] = (t += A[i] * B) % 10;@}
{@ A[0] = i - 1;@}
{@}@}
h3. Inmultirea unui numar mare cu un numar mare
void mul(int A[], int B[])
{
int i, j, t, C[];
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));
}
p(pre).
{@void mul(int A[], int B[])@}
{@{@}
{@ int i, j, t, C[];@}
{@ 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));@}
{@}@}
h3. Scaderea a doua numere mari
void sub(int A[], int B[])
{
int i, t = 0;
for (i = 1; i <= A[0]; i++)
A[i] += (t = (A[i] -= B[i] + t) < 0) * 10;
for (; A[0] > 1 && !A[A[0]]; A[0]--);
}
p(pre).
{@void sub(int A[], int B[])@}
{@{@}
{@ int i, t = 0;@}
{@ for (i = 1; i <= A[0]; i++)@}
{@ A[i] += (t = (A[i] -= B[i] + t) < 0) * 10;@}
{@ for (; A[0] > 1 && !A[A[0]]; A[0]--);@}
{@}@}
h3. Impartirea unui numar mare la un numar mic
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]--);
}
p(pre).
{@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]--);@}
{@}@}
h3. Restul unui numar mare la un numar mic
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;
}
p(pre).
{@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;@}
{@}@}
h2. AVL-uri (ideea originala de la Radu Berinde - again)
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
