Home Jocul Explicatii Algoritm Analiza algoritmului Despre NIM - istoria jocului


Corectitudine

      In prezentarea algoritmului am afirmat ca mutarile efectuate pot fi impartite in doua submultimi : S = multimea mutarilor sigure si P = multimea mutarilor periculoase, cele 2 multimi avand urmatoarele proprietati:

  1. 0 apartine lui S
  2. Din orice element din P exista o mutare catre un element din S
  3. Toate mutarile dintr-o pozitie din S rezulta intr-un element din P
      Algoritmul implementat de mine numara cate obiecte sunt in fiecare gramada, trece aceste numere in binar si face XOR pe fiecare coloana (verifica daca numarul de unitati de pe fiecare coloana e par sau impar). Daca rezultatul pe fiecare coloana este 0 atunci configuratia e balansata, altfel spunem ca nu este balansata. In continuare voi demonstra ca pozitiile balansate sunt chiar S-pozitiile.
Dem: Voi demonstra ca aceste pozitii verifica cele trei proprietati ale multimilor, S si P.
  1. 0 apartine lui S.  Atunci cand nu mai exista nici un obiect in nici o gramada se va obtine urmatorul rezultat 0 0 0 0 0 = 0 0 este o pozitie balansata.
  2. pentru fiecare pozitie nebalansata exista o mutare catre o pozitie balansata. Din moment ce va aflati pe o pozitie nebalansata inseamna ca exista cel putin o coloana pe care facand XOR ati obtinut 1, adica un numar impar de unitati pe aceste coloane. Intotdeauna exista o mutare astfel incat sa se obtina un numar par de unitati. Exista mai multe modalitati de a efectua aceasta mutare dar eu am ales urmatoarea regula:
    1. Se alege prima coloana cu numar impar de unitati
    2. Se alege prima linie care are 1 pe aceasta coloana
    3. Pe aceasta linie, pe fiecare coloana care are un numar impar de unitati se inverseaza elementele (din 0 in 1 si din 1 in 0). Celelalte elemente raman neschimbate.
              Regulile jocului specifica ca se pot lua obiecte dintr-o singura gramada la un moment de timp, deci trebuie sa alegeti o linie(2). Am ales aceasta linie deoarece e posibil ca pe urmatoarele coloane sa fie nevoie sa inversez 0 in 1 si nu trebuie sa obtin un numar mai mare decat numarul deja existent de obiecte.
              Ca sa ajungeti intr-o pozitie balansata trebuie ca pe toate coloanele sa aveti numar par de unitati, deci trebuie sa modificati niste elemente de pe aceste coloane(3):
                    - daca aveti numar impar de unitati si 1 pe linia aleasa, 1 va deveni 0 si numarul de unitati devine par (scade cu 1)
                    - daca aveti numar impar de unitati si 0 pe linia aleasa, 0 va deveni 1 si numarul de unitati devine par (se aduna 1)
  3. toate mutarile dintr-o pozitie balansata vor duce intr-o pozitie nebalansata. Aceasta afirmatie este usor de demonstrat deoarece orice mutare reduce numarul de bete dintr-o gramada, iar reprezentarea binara a acestei gramezi se va modifica. Cel putin un 1 devine 0 si coloana in care apare 1 initial va avea un numar impar de unitati coloana devine nebalansata.

      Tot in descrierea algoritmului am afirmat ca strategia de castig este sa mutati intotdeauna spre un element din S, adversarul fiind astfel obligat sa mute catre o pozitie din P.
Dem: Daca efectuati o mutare catre un element din S, conform proprietatii (3) adversarul va fi nevoit sa mute catre o pozitie din P. Din proprietate (2) rezulta ca veti putea muta iar spre o pozitie din S. Continuand aceasta strategie, la finalul jocului veti castiga pentru ca veti fi singurul jucator care va putea muta in 0.


Complexitate

      Prin definitie, complexitatea este un indicator al dependentei dintre dimensiunea datelor de intrare si numarul de instructiuni executate de un algoritm. Pentru a calcula numarul de instructiuni care se executa pentru a ajunge la solutia problemei s-a presupus ca o operatie de baza (ex: atribuiri, comparatii) se realizeaza într-o unitate de timp.
      Algoritmul foloseste o matrice cu dimensiunea (m,n), unde n=numarul de gramezi, m=numarul de biti pe care se reprezinta numarul de obiecte dintr-o gramada. Analizand ciclurile algoritmului se obtine urmatoarea complexitate:
  1. pentru alegerea mutarii se obtine complexitatea C(n,m) = n * m + m + n*m + 2*m + n + m = 2*n*m+4*m+n.
  2. pentru luarea efectiva a obiectelor din matrice C(n,m) = m.
      Adunand cele doua complexitati vom obtine complexitatea algoritmului:
            C(n,m) = 2*n*m+5*m+n => in cazul cel mai defavorabil cand m=n complexitatea va fi O(n²), deci complexitate polinomiala.