Numarare- tehnici de baza

Numarare- tehnici de baza

Regula produsului

Sa consideram A o multime cu n elemente si B o multime cu m elemente.

Numarul de posibilitati de a selecta un element din A si un element din B este n*m

Exemplu

Daca avem bluze si perechi de pantaloni exista variante diferite de a ne imbraca.

Generalizare:

Sa consideram A₁ A₂ A_n multimi cu L₁ L₂ L_n elemente.

Numarul de posibilitati de a selecta un element din A₁, un element din A₂, , un element din A_n este L₁*L₂**L_n

(numarul de elemente ale produsului cartezian A₁xA₂x.xA_n

Regula sumei

Sa consideram A o multime cu n elemente si B o multime cu m elemente (A si B disjuncte).

Numarul de posibilitati de a selecta un element din multimea A sau un element din multimea B este n+m

Exemplu

Daca in tema avem 4 exercitii si 5 probleme, iar profesorul spune ca o rezolvare este gresita, exista 4+5=9 posibilitati pentru greseala.

Principiul includerii si al excluderii

Pentru doua multimi

Sa consideram A si B doua multimi nu neaparat disjuncte.

In continuare vom nota cu |X| numarul de elemente ale multimii X

Numarul de posibilitati de a selecta un element din multimea A sau un element din multimea B este |A|+|B|-|A∩B|

Exemplu

Daca 5 elevi din clasa merg la CEX la mate si 7 elevi merg la CEX la info, iar dintre acestia 2 merg si la mate si la info, pentru a selecta elevul care va merge la Concursul centrelor de excelenta la Suceava avem 5+7-2 posibilitati.

Pentru 3 multimi

Fie A, B si C 3 multimi.

Numarul de posibilitati de a selecta un element din multimea A sau un element din multimea B sau un element din multimea C este

|A|+|B|+|C|-|A∩B|-|A∩C|-|C∩B|+|A∩B∩C|

Puteti generaliza pentru 4 multimi?

Atentie!

Evitarea dublei numarari este un aspect delicat al problemelor de combinatorica.

Tehnica bijectiei

O bijectie este o asociere 1:1 pe care o facem intre doua multimi.

Mai exact, prin aceasta asociere fiecarui element din multimea A ii va corespunde un singur element din multimea B si reciproc.

Este evident ca pentru a putea stabili o bijectie intre doua multimi aceastea trebuie sa aiba acela numar de elemente.

Prin urmare, daca reusim sa stabilim o bijectie intre doua multimi, deducem ca ele au acelasi numar de elemente.

Exemplu

Sa consideram multimea tezelor la matematica elevilor clasei a VII-a. Putem stabili o bijectie intre multimea tezelor si multimea elvilor prezenti.

Prin urmare, numarand tezelor, vom determina si numarul elevilor prezenti la teza.

Pentru a utiliza tehnica bijectiei este util sa cunoastem modalitatile de numarare ale unor elemente combinatoriale:

Relatii de recurenta

Spunem ca un sir este definit prin relatie de recurenta daca pentru a descrie un termen al sau utilizam o formula in care intervin alti termeni ai sirului.

Exemple

Multe probleme de numarare se pot reduce la o relatie de recurenta.

Bacalaureat

Din cei n elevi de clasa a XII-a de la Liceul de Informatica, doar k vor sustine examenul de bacalaureat in liceu, ceilalti fiind repartizati la alte centre. Pentru n si k doua numere naturale date de la tastatura (k n<50

Sa se calculeze numarul de posibilitati de a selecta cei k elevi care urmeaza sa sustina bacalaureatul in liceul lor!

Solutie

C(n,n)=1

C(n,0)=1

Triunghiul lui Pascal

Solutia nerecursiva se poate baza pe formula de recurenta alaturata, care sta la baza algoritmului de calcul al combinarilor cunoscut sub denumirea "triunghiul lui Pascal". De exemplu, triunghiul lui Pascal pentru n=5, este

1

1 1

1 2 1

1 3 3 1

Observati ca pe linia i i variind de la la n) in triunghiul lui Pascal se gasesc combinarile de k elemente ale multimii (k variind de la la i

Pentru a rezolva problema nu este necesar sa retinem intr-o matrice triunghiul lui Pascal in intregime, este suficient sa retinem la fiecare pas i i variind de la la n) numai linia curenta si cea precedenta, pe care o vom utiliza pentru determinarea liniei curente.

O alta solutie ar putea utiliza definitia:

Dar in acest caz, in urma calcularii factorialelor, se vor obtine erori datorate depasirilor valorilor maxime ce pot fi memorate intr-un tip intreg (pentru n>16 va fi depasita valoarea , maximum pentru long int

Paianjen

Sa ne imaginam o retea planara, formata din noduri situate in punctele de coordonate intregi, fiecare nod fiind unit prin bare paralele cu axele de coordonate de cele 4 noduri vecine. Un paianjen este plasat initial in originea sistemului de coordonate. La fiecare secunda, paianjenul se poate deplasa din nodul in care se afla in unul din nodurile vecine.

Scrieti un program care sa determine in cate moduri se poate deplasa paianjenul din pozitia initiala, intr-o pozitie finala data prin coordonatele ei x si y, in timpul cel mai scurt. (ONIG 2001, VII-VIII)

Exemple

Pentru x=1 si y=2, numarul de moduri determinat va fi . Pentru x=2 si y=3, numarul de moduri va fi

Solutie

Cum paianjenul se deplaseaza numai de-a lungul barelor, el poate sa ajunga (in timpul cel mai scurt) in pozitia (x y) numai din pozitia (x-1 y) sau din pozitia (x y-1). Daca notam cu nr(x,y) numarul de modalitati prin care paianjenul poate ajunge in timp minim in pozitia (x y), atunci deducem ca:

nr(0,y)=nr(x,0)=1;

nr(x,y)=nr(x-1,y)+nr(x,y-1), pentru orice x,y>0

Exercitiu

Rezolvati aceasta problema si pentru cazul in care dimensiunea maxima a retelei este . Veti observa ca numarul de modalitati creste foarte rapid si va fi necesar sa implementati adunarea cu numere mari.

Traversare

Pod de lungime n, pasi de lungime 1, 2 3, fara scanduri deteriorate.

Pod

Intre doua maluri ale unei vai adanci s-a construit un pod suspendat format din N bucati de scandura, legate cu liane. Vom considera ca scandurile sunt numerotate de la la N, incepand de pe malul pe care ne aflam. In timp unele bucati de scandura s-au deteriorat, iar altele chiar au disparut. Pentru traversarea podului se stie ca:

se pot face pasi doar de lungime sau

scandurile deteriorate sunt nesigure, deci pe ele si de pe ele se pot face doar pasi de lungime

Evident, nu se poate pasi pe o scandura care lipseste.

Scrieti un program care sa determine numarul de modalitati de traversare a podului (mai exact, de a ajunge pe celalalt mal), precum si o solutie de traversare, daca o astfel de solutie exista.

Date de intrare

Fisierul de intrare POD.IN are structura:

Date de iesire

Fisierul de iesire POD.OUT va contine pe prima linie valoarea daca nu este posibil sa traversam podul, respectiv numarul de posibilitati de a traversa podul, daca aceasta este posibil. In cazul in care exista solutii, pe cea de a doua linie va fi afisata o astfel de solutie, prin indicarea, in ordine, a scandurilor pe care se paseste, sub forma:

Restrictii si precizari

N

k, h N

Nr are cel mult de cifre.

Timp maxim de executie/test: 1 secunda.

Exemplul 1 Exemplul 2 Exemplul 3

(ONI, Braila 2002, IX)

De reluat

Generare combinari

Fie n si m doua numere naturale, 1 m n≤20.

Sa se genereze in ordine lexicografica toate submultimile formate din m elemente ale multimii .

Solutie

Vom reprezenta o submultime ca un vector C cu m elemente (elementele submultimii).

Evident, 1≤C[i]≤n.

Deoarece ordinea elementelor intr-o submultime nu conteaza, pentru a nu genera de mai multe ori aceeasi submultime vom conveni ca plasam elementele in submultime in ordine crescatoare: C[i]<C[i+1], pentru orice 1≤i<m.

Vom genera submutimile printr-un algoritm de tip succesor.

Cea mai mica submultime (din pdv lexicografic) este 1, 2, , m.

Cea mai mare submultime este:  n-m+1,, n-1, n

Intrebare: care este cea mai mare valoare care poate fi plasata pe pozitia i:

Observam ca atunci cand pozitia scade cu 1, valoarea maxima scade cu 1, deci diferenta dintre Valoarea maxima si Pozitie este constanta:

Valoare_maxima-Pozitie=n-m=?-i.

Deducem ca valoarea maxima care poate fi plasata pe pozitia i este n-m+i.

Pas 1. Initializam vectorul C (C[i]=1, pentru orice 1≤i≤m)

Pas 2. Cat timp este posibil (mai exista succesor)

afisam submultimea curenta;

generam submultimea urmatoare; in acest scop cautam prima componenta (incepand din dreapta catre stanga) care poate fi marita (adica C[i]<n-m+i); daca gasim o astfel de componenta o marim, si repunem pe cea mai mica valoare posibila toate componentele urmatoare (C[j]=C[j-1]+1, i<j≤m); daca nu gasim o astfel de componenta deducem ca generarea s-a incheiat, acesta a fost cea mai mare submultime din punct de vedere lexicografic.