Nu exista diferente intre titluri.
Diferente intre continut:
h1. Probleme cu numere lipsa si nu numai ...
h1. Probleme cu numere lipsa si nu numai...
== include(page="template/implica-te/scrie-articole" user_id="alecman") ==
* 'Problema 9 ':missing-numbers#prob9
* 'Problema 10 ( _el judge_) ':missing-numbers#prob10
* 'Problema 11 ( _Info-Oltenia 2005, clasa a IX-a_) ':missing-numbers#prob11
* 'Problema 12 ( _JBOI 2011 Bistrita_) ':missing-numbers#prob12
* 'Bibliografie':missing-numbers#biblio
h2(#prob1). Problema 1 ( _interviu Microsoft_ )
Prima rezolvare ce ne poate veni in minte este aceea de a verifica daca fiecare numar $1 -> n$ este prezent in sirul nostru, printr-o parcurgere (acest algoritm are complexitatea $O(n^2^)$ ). O alta rezolvare triviala ar fi sa sortam numerele si sa determinam prin parcurgere numarul $i$ pentru care $a[i] != i$ (pentru sortari rapide algoritmul are complexitatea $O(n log n)$ ).
O rezolvare mai eficienta poate fi data folosind _Divide et Impera_. Putem imparti numerele in doua multimi, una in care vom pune mumerele mai mici sau egale cu $n/2$, iar in cealalta restul. Acum vom sti din care din cele doua multimi lipseste numarul, dupa numarul de elemente al acestora. Considerand $T(n)$ timpul de executie al algoritmului, atunci complexitatea devine $T(n) = T(n/2) + O(n) = O(n)$. Deci algoritmul este liniar, si foloseste memorie $O(n)$, ignorand memoria consumata de stiva din algoritmul Divide et Impera ( $O(log n)$ ). O alta idee este de a folosi un tabel de dispersie sau un sir de valori booleene care va folosi memorie suplimentara $O(n)$ (poate fi redusa la $O(n/log n)$ daca se lucreaza pe biti).
O rezolvare mai eficienta poate fi data folosind _Divide et Impera_. Putem imparti numerele in doua multimi, una in care vom pune numerele mai mici sau egale cu $n/2$, iar in cealalta restul. Acum vom sti din care din cele doua multimi lipseste numarul, dupa numarul de elemente al acestora. Considerand $T(n)$ timpul de executie al algoritmului, atunci complexitatea devine $T(n) = T(n/2) + O(n) = O(n)$. Deci algoritmul este liniar, si foloseste memorie $O(n)$, ignorand memoria consumata de stiva din algoritmul Divide et Impera ( $O(log n)$ ). O alta idee este de a folosi un tabel de dispersie sau un sir de valori booleene care va folosi memorie suplimentara $O(n)$ (poate fi redusa la $O(n/log n)$ daca se lucreaza pe biti).
O rezolvare eleganta se foloseste de proprietatea ca suma numerelor naturale de la $1$ la $n$ este $n(n + 1)/2$. Numarul lipsa este egal cu diferenta dintre $n(n + 1 )/2$ si suma numerelor noastre. Aceasta solutie are complexitatea $O(n)$ (parcurgem sirul pentru a determina suma) ca timp si $O(1)$ ca memorie. Daca $n$ este destul de mare, s-ar putea ca $n(n+1)/2$ sa depaseasca domeniul de reprezentare al intregilor, rezultand in necesitatea implementarii operatiilor cu numere mari. Pentru a evita acest lucru folosim operatia **xor** (notata prin ^∧^ ) si proprietatile ei $a ^∧^ a = 0$ si $a ^∧^ b = b ^∧^ a$. Vom face suma xor a numerelor $a[i] ^∧^ i$ (1 <= i <= n):
$S = a[ 1 ] ^∧^ 1 ^∧^ a[ 2 ] ^∧^ 2 ^∧^ ... ^∧^ a[ n - 1 ] ^∧^ n - 1 ^∧^ n$
h3. Rezolvare
Acum vom folosi din nou un algoritm bazat pe Divide et Impera. La primul pas impartim multimea in doua submultimi - cea a numerelor pare si cea a numerelor impare, si vedem in care din ele se gaseste numarul nostru lipsa (am aflat astfel ultimul bit al rezultatului). Acum putem aplica recursiv procedura aceasta pe numerele din o lista cu jumatate din lungimea listei initiale impartite la doi (ignoram ultimul bit al numerelor). Aceasta solutie are complexitate $O(n)$ pentru ca dupa fiecare pas executat in timp liniar, dim
Acum vom folosi din nou un algoritm bazat pe Divide et Impera. La primul pas impartim multimea in doua submultimi - cea a numerelor pare si cea a numerelor impare, si vedem in care din ele se gaseste numarul nostru lipsa (am aflat astfel ultimul bit al rezultatului). Acum putem aplica recursiv procedura aceasta pe numerele din o lista cu jumatate din lungimea listei initiale impartite la doi (ignoram ultimul bit al numerelor). Aceasta solutie are complexitate $O(n)$ pentru ca dupa fiecare pas executat in timp liniar, dimensiunea problemei se injumatateste. Memoria suplimentara e $O(n)$ (doi vectori care sa pastreze indicii elementelor pare, respectiv impare).
h2(#prob9). Problema 9
Generalizam problema anterioara si se cere un algoritm eficient pentru un sir din care lipsesc $n - k$ numere.
h3. Rezolvare
Din nou vedem cate numere din sir au ultima cifra $0$ si cate au $1$. Astfel putem determina $k{~0~}$ - numarul de valori lipsa cu ultima cifra $0$, si $k{~1~}$ - numarul de valori lipsa care au ultima cifra $1$. Daca notam timpul de rezolvare al problemei noastre $T(n, k)$, acum avem de rezolvat doua subprobleme cu timpii $T(n/2, k{~0~})$ si $T(n/2, k{~1~})$. Acum impartim cele $k{~0~}$ numere in $k{~00~}$ si $k{~10~}$ valori care se termina in $00$, respectiv $10$ in reprezentarea in baza $2$. Aceasta solutie are complexitate $O(n log n)$ si nu imbunatateste cu nimic solutia in care sortam elementele sirului.
h2(#prob10). Problema 10 ( _el judge_ )
Se dau $n$ numere intregi astfel incat fiecare numar apare de un numar par de ori, in afara de unul singur, care apare de un numar impar de ori. Se cere determinarea acelui numar. De exemplu in sirul $1 2 2 3 1 2 2 2 3 3 3$, numai elementul $2$ apare de un numar impar de ori.
h3. Rezolvare
Este evident ca daca facem suma xor a tuturor numerelor, rezultatul va fi numarul ce apare de numar impar de ori. Astfel solutia are complexitatea $O(n)$ ca timp si $O(1)$ ca memorie folosita.
h2(#prob11). Problema 11 ( _Info-Oltenia 2005, clasa a IX-a_ )
Se dau $n$ siruri formate din cifre de la $1$ la $8$ (inclusiv), de lungime maxima $500$. Toate sirurile sunt repetate de $k$ ori sau de multiplu de $k$ ori, cu exceptia unui singur sir, care nu este repetat de $k$ ori, sau de multiplu de $k$ ori. Sa se afiseze sirul care nu se repeta. ( $1 <= n <= 32000, k < 2005$ )
h3. Rezolvare
Putem face o solutie similara cu cea de mai sus. Consideram un tablou $A$ cu $500 * 8$ elemente, fiecare linie $i$ corespunzand cifrelor de pe pozitia $i$ din sirurile de cifre date la intrare. Cand procesam un sir dintre cele date la intrare, daca el are pe pozitia $i$ cifra $j$ atunci incrementam elementul $A[ i ][ j ]$. In acest tablou, pe fiecare linie $i$, toate elementele in afara de unul vor fi $0$ sau multiplu de $k$, iar elementul $A[ i ][ j ]$ care nu e multiplu de $k$ este a $j$-a cifra a numarului care se repeta de un numar de ori ce nu este divizibil cu $k$. Aceasta solutie are complexitate ca timp $O(n*L)$, iar ca spatiu $O(L)$, unde $L$ este lungimea maxima a unui sir de cifre.
h2(#prob12). Problema 12 ( _JBOI 2011, Bistrita_ )
Se da un sir de $n$ numere naturale in care orice element apare de exact $k$ ori, mai putin $n%k$ dintre acestea care, de asemenea, sunt egale. Sa se determine valoarea elementelor care apar de exact $n%k$ ori. Se garanteaza ca $n%k>0$.
h3. Rezolvare
Se observa ca pentru $k=2$ este de ajuns sa facem xor intre toate elementele sirului. Cum xor este suma bitilor, de pe fiecare pozitie in parte, modulo $2$, pentru $k>2$ scriem fiecare numar in baza $2$ si formam vectorul $x$ cu semnificatia ca $x[i]$ este suma bitilor de pe pozitia $i$ modulo $k$.
La final pozitile nenule din $x$ vor coincide cu pozitile bitilor de $1$ din scrierea in baza $2$ a numarului cautat. Transformam inapoi in baza $10$ si obtinem rezultatul. Complexitatea algoritmului este $O(n*log(P))$, unde $P$ este numarul maxim din sirul dat, iar memoria este $O(log(P))$.
h2(#biblio). Bibliografie
*(#fn1) 1. 'Relatiile lui Viete, _mathworld_ ':http://mathworld.wolfram.com/VietasFormulas.html
*(#fn2) 2. 'Formulele Newton-Girard, _mathworld_ ':http://mathworld.wolfram.com/Newton-GirardFormulas.html
*(#fn3) 3. {'Cycle detection, _wikipedia_ ':http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm}
Nu exista diferente intre securitate.
Diferente intre topic forum:
