Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune. tutorial, tools, info, programe, lectii de informatica, referate, exemple, soft

Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
» Permutari, aranjamente


Permutari, aranjamente



Permutari, aranjamente

1.      Scopul lucrarii. Insusirea notiunile teoretice si practice legate de modul in care se abordeaza problemele care pot fi solutionate folosind:

-         permutarile de n elemente,

-         aranjamentele de n elemente luate cite m.

2.  Notiuni teoretice

2.1. Generarea permutarilor

Fie o multime finita A cu n elemente. Aceasta multime se poate  ordona in mai multe moduri. Se obtin astfel multimi ordonate care se deosebesc intre ele numai prin ordinea elementelor. Fiecare din multimile ordonate care se formeaza cu cele n elemente ale multimii A se numeste permutare a acestei multimi. In literatura de specialitate exista foarte multi algoritmi  pentru generarea permutarilor.

2.1.a. Algoritmul iterativ.

Se prezinta o modalitate de generare a permutarilor in ordine lexicografica. Se pleaca de la permutarea identica p=(1, 2, , n), care  este cea mai mica permutare in ordine lexicografica. Sa presupunem ca la un moment dat avem construita o permutare p=(p1, p2, , pn). Se pune problema generarii unei noi permutari p'=(p1', p2', , pn')  care  sa fie succesoarea in ordine lexicografica a acestei permutari. Se procedeaza dupa cum urmeaza:

            a) Se determina cel mai mare indice i pentru care avem pi < pi+1 si pi+1 > pi+2 > pi+3 >.> pn. In aceste  conditii este evident ca pentru a se obtine permutarea p' trebuie sa se modifice elementele de pe pozitiile pi, pi+1, , pn. Modificarea acestei secvente este prezentata mai jos.

            b) Deoarece p' urmeaza imediat dupa p in ordine lexicografica rezulta ca pi trebuie inlocuit cu un element mai mare decit el. Acest element trebuie sa fie in secventa (pi+1,.., pn) si il notam cu pk. El este de fapt cel mai mic element din multimea , care este mai mare decit pi. Se schimba elementele pi si pk intre ele. Dupa aceasta prelucrare vectorul initial are forma:

            (p1, p2, , pi-1, pk, pi+1, .., pk-1, pi, pk+1, , pn)

In  acest ultim caz ultimile n-1 elemente sunt in ordine descrescatoare. Pentru a obtine permutarea p' aceste ultime elemente se aseaza in asa fel incit sa fie ordonate crescator.

Ultima permutare generata de algoritm este p=(n, n-1, , 1).

Procedurile de initializare si generare sunt prezentate mai jos:

procedura INIT(v, n, ig) este

 pentru i=1, n, 1 repeta

    vi <- i

 

 ig <- 1

sfarsit.

procedura GEN(v, n, ig) este

   i <- n

   cat_timp (i>0) si (vi > vi+1) repeta

     i <- i-1

  

   daca i>0 atunci

     k <- n

   │ ┌ cat_timp vi > vk repeta

   │ │   k <- k+1

   │ └  

   │ x <- vi

   │ vi <- vk]

   │ vk <- x

   │ m <- [(n-i)/2]

   │ ┌ pentru j=1, m, 1 repeta

   │ │  x <- vi+j

   │ │  vi+j <- vn+1-j

   │ │  vn+1-j <- x

   │ └

   altfel

       ig <- 0

  

sfarsit.

 

Daca se doreste folosirea pentru cautare a unei metode cu santinela, aceasta trebuie asezata pe pozitia 0 si sa aiba valoarea 0. Varianta cu santinela conduce la urmatoarele proceduri:

procedura INIT (n, v, ig) este

 pentru i=0, n, 1 repeta

    vi <- i

 

 ig <- 1

sfarsit

procedura GEN (n, v, ig) este

   i <- n-1

   cat_timp vi > vi+1 repeta

     i <- i-1

  

   daca i = 0 atunci

     ig <- 0 

   altfel

      k <- n

      cat_timp vi > vk repeta

        k <- k-1

     

      x <- vi

      vi <- vk

      vk <- x

      m <- [(n-i)/2]

      pentru j=1, m, 1 repeta

        x <- vi+j

        vi+j <- vn+1-j

        vn+1-j <- x

     

  

sfarsit

Exemplu rezolvat. Sa se genereze toate posibilitatile de aranjare pe o tabla de sah de N x N a N turnuri astfel incit doua turnuri sa nu se poata lua si sa nu apara in colturile tablei de sah.

Este evident ca pe o coloana sau pe o linie  nu poate sa apara decit un singur turn. Consideram ca o astfel de pozitie  se poate reprezenta printr-o configuratie de forma (l1, l2, , ln) unde li este linia pe care se afla turnul de pe coloana i. In acest caz vectorul (l1, l2, , ln) reprezinta o permutare de n elemente deoarece li ¹ lj oricare ar fi i, j din multimea . Ca atare se vor genera toate cele n! permutari si se vor retine acele permutari care respecta restrictiile impuse, adica cele care nu satisfac conditia l1=n sau l1=1 sau ln=n sau ln=1.

In aceste conditii procedura de prelucrare arata astfel:

procedura PREL(v, n) este

pentru i=1, n, 1 repeta

  scrie v(i)

daca (v1 ¹ 1) si (vn ¹ 1) si (v1 ¹ n) si (vn ¹ n)atunci

    scrie 'Este solutie'         

altfel

    scrie 'Nu este solutie'

sfarsit

 

Programul principal in pseudocod va arata astfel:

scrie 'Introduceti dimensiunea tablei'

citeste n

executa INIT(n, v, ig)

cat_timp ig¹0 repeta

  executa PREL(v, n)

  executa GEN(n, v, ig)

sfarsit.

Pentru cazul particular cind dimensiunea tablei este 4 rezultatele vor fi afisate astfel:

Introduceti dimensiunea tablei: 4

1 2 3 4    Nu este solutie

1 2 4 3    Nu este solutie

1 3 2 4    Nu este solutie

1 3 4 2    Nu este solutie

1 4 2 3    Nu este solutie

1 4 3 2    Nu este solutie

2 1 3 4    Nu este solutie

2 1 4 3    Este solutie

2 3 1 4    Nu este solutie

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

4 3 2 1    Nu este solutie

In programele ce urmeaza s-a implementat varianta cu santine­la.

2.1.a. Algoritmul recursiv.

Generarea recursiva a permutarilor are la baza metoda generala de programare backtracking.

Vom folosi acelasi vector v care contine cate un element al permutarilor. Procedura PREL( ) va prelucra conform aplicatiei vectorul v.

Algoritmul de generare arata astfel:

procedura permut( k) este

  daca k=n+1 atunci

        executa  PREL();

    altfel

         v[k]=k;

        pentru i=1,k,1  repeta

                   c=v[i];

                  v[i]=v[k];

                  v[k]=c;

                   executa permut(k+1);

                   c=v[i];

                   v[i]=v[k];

                   v[k]=c;

                                            

 

sfarsit             

2.2. Generarea aranjamentelor

Fie o multime finita A cu n elemente. Daca exista m £ n atunci se pot forma multimi ordonate cu cite m elemente fiecare, in care intra numai elemente ale multiimi A.

Multimile ordonate care se formeaza cu elementele unei submultimi oarecare a unei multimi finite A, se numesc submultimi ordonate ale lui A sau aranjamente. Daca A este o multime cu n elemente atunci submultimile ordonate ale lui A avind fiecare cite m elemente, 0 £ m £ n se numesc aranjamente de n elemente luate cite m.

Numarul  acestor grupe este Anm. Doua aranjamente de n elemente luate cite m se deosebesc prin natura elementelor sau prin ordinea lor.

2.2.a. Algoritmul iterativ.

O modalitate de generare a tuturor gruparilor de m elemente din n elemente, elementele diferind intre ele fie prin natura lor, fie prin pozitia pe care o au in grupa, are la baza algoritmul de generare a permutarilor si a combinarilor.

executa INITCOMB(c, n, m, ig1)

cat_timp ig1¹0 repeta

executa  INITPERM(p, m, ig2)

│ ┌ cat_timp ig2¹0 repeta

│ │ ┌ pentru i=1, m, 1 repeta

│ │ │  a[i] <- c[p[i]]

│ │ └

│ │ executa PRELARANJ(a, m, n)

│ │ executa GENPERM(p, m, ig2)

│ └

executa GENCOMB(c, n, m, ig1)

sfarsit

Descrierea prezentata anterior este ineficienta deoarece execu­tia programului corespunzator acestui algoritm dureaza mult si este  necesara cunoasterea algoritmilor pentru generarea combinarilor si permutarilor.

Deci, este necesar gasirea  unei metoda de generare  mai performanta. O asemenea metoda se prezinta in continuare si se bazeaza pe generarea aranjamentelor in ordine lexico­grafica printr-un procedeu iterativ. Se pleaca de la multimea (vectorul) a=(1, 2, , m). Fie un aranjament oare­care a=(a1, a2, , am). Pentru a se genera succesorul acestuia in ordine lexicografica se procedeaza astfel:

Se determina indicele i pentru care ai poate fi marit (cel mai mare indice). Un element ai nu poate fi marit daca valorile  care sunt mai mari decit el respectiv ai+1, ai+2, , n nu sunt disponibile, adica apar pe alte pozitii in aranjament. Pentru a se determina usor elementele disponibile se introduce un vector  DISP cu n elemente, astfel incit DISP(i) este 1 daca elemntul i apare in aranjamentul curent si 0 in caz contrar.

Se observa ca in momentul determinarii indicelui este necesar ca elementul curent care se doreste a fi marit trebuie sa se faca disponibil. Dupa ce acest element a fost gasit, acesta si elementele  urmatoare se inlocuiesc cu cele mai mici numere disponibile. In cazul in care s-a ajuns la vectorul (n-m+1, , n-1, n) procesul de generare al aranjamentelor se opreste.

De exemplu, pentru n=5 si m=3  si a=(2 4 1) avem DISP=(0,0,1,0,1), iar succesorii sai sunt in ordine (2 4 1), (2 4 3), (2 4 5), (3 1 2), (3 1 4), s.a.m.d.   

Procedurile de initializare si generare sunt prezentate mai jos:

procedura INIT(v, n, m, ig) este

 pentru i=1, m, 1 repeta

    vi <- 1

 │ disp(i) <- 0

 

 pentru i=m+1, n, 1 repeta

 │ disp(i) <- 1

 

 ig <- 0

sfarsit.

procedura GEN(v, n, m, ig, disp) este

 i <- m

 gasit <- 0

 cat_timp (i>0) si (gasit=0) repeta

   disp(vi) <- 1

   j <- vi+1

   cat_timp (j£n) si (gasit=0) repeta

   │ ┌ daca disp(j)=1 atunci

   │ │  vi <- j

   │ │  disp[j] <- 0

   │ │  k <- 0

   │ │  pentru l=i+1, m, 1 repeta

   │ │  │ ┌  repeta

   │ │  │ │   k <- k+1

   │ │  │ └  pana disp(k)=1

   │ │  │ vl <- k

   │ │  │ disp(k) <- 0

   │ │   

   │ │  gasit <- 1

   │ │altfel

   │ │    j <- j+1

   │ └

  

   i <- i-1

 

 daca gasit=0 atunci

    ig <- 0

 

sfarsit.

Exemplu rezolvat. Intr-o urna se afla n bile care sunt numerotate cu valori intre 1 si n. Care sunt posibilitatile de extragere a m bile astfel incit suma lor sa fie 'suma', daca conteaza si ordinea lor de extragere?

Deoarece conteaza si ordinea de aparitie trebuie generate toate aranjamentele de n luate cite m. Dupa ce au fost generate aceste elemente se retin ca solutie doar acelea pentru care suma este 'suma'. Procedurile de initializare si generare sunt identice cu cele descrise anterior iar procedura de prelu­crare este:

procedura PREL(v, n, m, suma) este

   s <- 0

   pentru i=1, m, 1 repeta

   │ s <- s+vi

    

   pentru i=1, m, 1 repeta

     scrie vi

    

   daca s=suma atunci

     scrie 'Este solutie'

   altfel

      scrie 'Nu este solutie'

  

sfarsit

Programul principal in pseudocod va arata astfel:

scrie 'Introduceti numarul total de bile'

citeste n

scrie 'Introduceti numarul de bile de extras'

citeste m

scrie 'Introduceti suma'

citeste suma

executa INIT(v, n, m, ig)

cat_timp ig¹0 repeta

  executa PREL(v, n, m, suma)

  executa GEN(v, n, m, ig, disp)

sfarsit.

Pentru cazul particular, cind numarul total de bile           este 5, iar numarul de bile de extras este 3 rezultatele vor fi afisate astfel:

Introduceti numarul total de bile: 5

Introduceti numarul de bile de extras: 3

Introduceti suma: 6

1 2 3    Este solutie

1 2 4    Nu este solutie

1 2 5    Nu este solutie

1 3 2    Este solutie

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

5 4 3    Nu este solutie   

2.2.a. Algoritmul recursiv.

Generarea recursiva a aramjamentelor are la baza metoda generala de programare backtracking.

Vom folosi acelasi vector v care contine cate un element al aranjamentelor. Procedura PREL(suma ) va prelucra conform aplicatiei vectorul v.

Algoritmul de generare arata astfel:

procedura  aranj ( k,  p) este

  daca p=k+1) atunci

         executa PREL(suma);

  altfel 

         daca p=1 atunci

                  pentru i=1,n,1 repeta

                               v[p]=i;

                            executa aranj(k,p+1)

                  

       altfel

                  max=v[1];

                   pentru i=2,p-1,1 repeta

                            daca v[i]>max atunci

                                     max=v[i]

                         

                

                  pentru i=max+1,n,1 repeta

                           v[p]=i;

                            pentru j=1,p,1 repeta

                                                 m=v[p];

                                                v[p]=v[j];

                                                 v[j]=m;

                                    executa aranj(k,p+1);

                                    m=v[p];

                                               v[p]=v[j];

                                                v[j]=m;

                          

              

      

sfarsit

void aranj(int k, int p)

   else

                        }

   }

}

3. Probleme propuse

1 Se considera un grup de n dominouri, fiecare diferit de celelalte (pe fiecare este inscrisa o pereche unica de numere de la 1 la 6). Dominourile se considera orientate, adica nu pot fi pozitionate decit in orientarea stinga-dreapta si nu rotit cu 180 grade. Sa se determine toate lanturile corecte de m dominouri. Un lant corect este acela in care numarul inscris pe partea dreapta a dominoului i este egal cu cel inscris pe partea stinga a domi­noului i+1, pentru orice i de la 1 la n-1 (n, m, precum si pere­chile de numere de pe fiecare domino se introduc de utilizator).

2. Fie G un grup de n atenuatoare electronice, fiecare diferit de celelalte (fiecare atenuator este caracterizat de o pereche unica de impedanta intrare-impedanta iesire; gama impedantelor este: 10, 20, 50, 100, 200, 500 ohmi). Atenuatoarele  se considera orientate, adica nu pot fi pozitionate decit in orientarea in­trare-iesire si nu rotit cu 180 grade. Sa se determine toate lanturile corecte de m atenuatoare. Un lant corect este acela in care impedanta de iesire a atenuatorului i este egala cu impedanta de intrare a atenuatorului i+1, pentru orice i de la 1 la m-1 (n, m, precum si perechile de impedante ale fiecarui atenua­tor se introduc de utilizator).

3. Se considera un grup de n amplificatoare electronice, fiecare diferit de celelalte (fiecare este caracterizat de o pereche unica impedanta intrare-impedanta iesire; gama impedantelor este: 10, 20, 50, 100, 200, 500 ohmi). Amplificatoarele se considera orientate, adica nu pot fi pozitionate decit in orientarea in­trare iesire si nu rotit cu 180 grade. Sa se determine toate lanturile corecte de m amplificatoare. Un lant corect este acela in care impedanta de iesire a amplificatorului i este egala cu impedanta de intrare a amplificatorului i+1, pentru orice i de la 1 la m-1 (n, m, precum si perechile de impedante ale fiecarui amplificator se introduc de utilizator).

4. Se considera o bara de metal de lungime L, din care se taie bucati de lungimi l1, l2, , ln. Sa se afiseze toate posibili­tatile de a taia m bucati identice sau diferite din bara. (L, l1, l2, , ln si m se introduc de utilizator)

5. Se da un balot de stofa de lungime L, din care se taie bucati de lungimi l1, l2, , ln. Sa se afiseze toate posibili­tatile de a taia m bucati identice sau diferite din balot. (L, l1, l2, , ln si m se introduc de utilizator)

6. Se considera o secventa de n numere naturale distincte. Se cere sa se scrie un program de generare a tuturor permutarilor celor n numere.

7. Se considera o secventa de n numere naturale, distincte.

     a.Sa se scrie un program care genereaza toate aranjamentele cu repetitie luate cite m ale celor n numere.

     b.Realizati un program care tipareste toate aranjamentele luate cite m ale celor n numere.

  8. Care sint posibilitatile de aranjare a 2*n persoane de inaltimi diferite in 2 linii de cite n persoane, astfel incit aranjarea in cadrul fiecarei linii sa se faca in ordinea crescatoare a inaltimii, de la stinga la dreapta, si in plus fiecare persoana din prima linie sa fie mai inalta decit persoana vecina din cea de‑a doua linie?

9. O fabrica de jucarii confectioneaza inele pe care sint dispuse cite m bile rosii si n bile albastre. Cite jucarii diferite se pot obtine (doua jucarii se considera identice daca se pot obtine una din alta prin deplasarea bilelor pe inel sau prin rasturnare) ?

 10.Fie n perechi de litere (2 cite 2 identice). Sa se genereze toate modurile in care pot fi aranjate aceste litere in cuvinte de lungime 2n, astfel incit 2 litere identice sa nu fie alaturate.

 11. Un joc popular, jucat de n persoane, alterneaza jocul in hora (cerc) cu ruperea periodica a horei si apoi refacerea ei aleatoare. Sa se determine toate horele distincte pe care le pot forma cei n dansatori.

 12. La o intrunire trebuie sa vorbeasca 5 persoane, simbolizate A, B, C, D, E. Determinati si afisati toate listele de inscriere la cuvint in care A urmeaza sa vorbeasca inaintea lui B.

 13. Se considera un grup de m baieti de inaltimi diferite si un grup de n fete de inaltimi diferite. Sa se genereze toate posibilitatile in care fiecare baiat din grupul de baieti isi poate alege cite o fata din grupul de fete astfel incit pentru orice doi baieti A si B dintre care A este mai inalt decit B, fata aleasa de baiatul A sa fie strict mai inalta decit fata aleasa de baiatul B.

14. Intr‑o discoteca se afla m baieti si n fete. Sa se genereze toate posibilitatile in care baietii pot invita fetele la dans astfel incit sa nu existe conflicte( sa nu invite doi baieti aceeasi fata) si fiecare baiat sa danseze( n>=m ).

15. O caravana formata din n camile calatoreste prin desert, in sir indian. Pentru a sparge monotonia zilelor lungi de drum, beduinul se hotaraste sa schimbe asezarea camilelor, astfel incit fiecare camila sa nu mai vada in fata ei aceeasi camila de pina atunci. Care sint posibilitatile sale?

16. Un grup de m sportivi de greutati diferite servesc masa la o cantina ce are la dispozitie n meniuri, fiecare meniu avind un numar de calorii diferit de celelalte. Sa se genereze toate posibilitatile de alegere a meniurilor de catre sportivi astfel incit un sportiv mai gras decit un altul sa manince un meniu cu cel putin la fel de multe calorii ca al acestuia.

17.  Intr‑o clinica pentru slabire sint internate m persoane obeze. La cantina clinicii sint disponibile n meniuri. Se stie ca persoanele au greutati diferite si oricare doua meniuri nu au acelasi numar de calorii. Sa se genereze toate posibilitatile in care persoanele isi pot alege meniurile, stiind ca daca o persoana este mai grasa decit alta trebuie sa manince strict mai putin decit aceasta( n>=m ).

ANEXE

B.L11. 3. Perm

Sa se genereze toate posibilitatile de aranjare pe o tabla de sah de N x N a N turnuri astfel incit doua turnuri sa nu se poata lua si sa nu apara in colturile tablei de sah. (Varianta iterativa)

#include <stdio.h>

#include <conio.h>

#define MAX  25

int n,v[MAX],ig;

void INIT(int n)

void PREL()

void GEN()

             }

}

 void main()

 }

B. L11.4 PERM REC

Sa se genereze toate posibilitatile de aranjare pe o tabla de sah de N x N a N turnuri astfel incit doua turnuri sa nu se poata lua si sa nu apara in colturile tablei de sah. (varianta recursiva)

#include <stdio.h>

#include <conio.h>

#define MAX  25

int n,v[MAX];

void PREL()

void permut(int k)

              }

 }

 void main()

B.L11. 5  ARAN

Intr-o urna se afla n bile care sunt numerotate cu valori intre 1 si n. Care sunt posibilitatile de extragere a m bile astfel incit suma lor sa fie 'suma', daca conteaza si ordinea lor de extragere? (varianta iterativa)

void INIT(int m, int n)

for(i=m+1;i<=n;i++)

            disp[i]=1;

ig=1;

}

void PREL(int suma)

void GEN()

                          gasit=1;

                        }

                        else

                            j++;

            i--;

}

if(!gasit)

            ig=0;

}

void main()

}

B.L11.6   ARAN REC

Intr-o urna se afla n bile care sunt numerotate cu valori intre 1 si n. Care sunt posibilitatile de extragere a m bile astfel incit suma lor sa fie 'suma', daca conteaza si ordinea lor de extragere? (varianta recursiva)

#include <stdio.h>

#include <conio.h>

int v[20],n,k,suma;

void PREL(int suma)

void aranj(int k, int p)

   else

                        }

   }

}

   }

void main()



Informatica


Access
Adobe photoshop
Autocad
Baze de date
C
Calculatoare
Corel draw
Excel
Foxpro
Html
Internet
Java
Linux
Mathcad
Matlab
Outlook
Pascal
Php
Powerpoint
Retele calculatoare
Sql
Windows
Word

Sisteme de numeratie
Probleme fundamentale privind propagarea VHF si UHF
Inteligenta Artificiala
ADAPTORUL VGA
PROIECT PENTRU OBTINEREA ATESTATULUI PROFESIONAL INFORMATICA EVIDENTA ANGAJTILOR UNEI INTREPRINDERI
IMPACTUL NOILOR TEHNOLOGII ASUPRA SOCIETATII ROMANESTI SI NECESITATEA REMODELARII SISTEMULUI INFORMATIONAL IN INSTITUTIILE PUBLICE DIN ROMANIA
Stive si Cozi - Creare. Inserare. Stergere.
PACHETUL DE PROGRAME Microsoft OFFICE
RETELE DE CALCULATOARE
MONITORIZARE SI CONTROL

















 
Copyright © 2014 - Toate drepturile rezervate