Problema INFORMATICA permutari

Buna! As vrea sa va rog sa ma ajutati pe cei care stiti cu aceasta problema de informatica:

Se dă un şir cu n elemente, numere naturale. Să se verifice dacă reprezintă o permutare a mulţimii {1,2,...,n}.

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale şirului, separate prin spaţii.

Programul afișează pe ecran mesajul DA, dacă şirul reprezintă o permutare a mulţimii {1,2,...,n}, respectiv NU în caz contrar.

• 1 ≤ n ≤ 100

Ca la orice program, primul lucru pe care il faci este sa gandesti algoritmul.

Presupunem ca te-ai gandit sa gasesti un algoritm si nu ti-a reusit.

Uite o varianta:

- faci o bucla pe numerele naturale de la 1 la n

- in interiorul acesteia mai faci o bucla care sa parcurga toate elementele sirului. in aceasta bucla verifici daca cel putin un element al sirului este egal cu contorul primei bucle. Daca cel putin un numar natural din intervalul 1..n nu se regaseste in sir, afisezi NU, altfel afisezi DA

Cam asta e.

Spor la treaba.

1. #include<iostream>
2. using namespace std;

Daca imi explici logica (algoritmul) la programul postat mai sus iti zic si unde e gresit.

Pai m-am gandit ca pentru a fi o permutare trebuie sa aiba in ordine elementele de la 1 la n , iar fiecare numar sa fie pe pozitia i (de aici v=i) si initial am ordonat crescator elementele vectorului prin metoda selectiei (aux=v[i]; v[i]=v[j]; v[j]=aux;) si am luat o variabila p care se facea 1. Apoi am parcurs din nou vectorul de la 1 la n si am verificat conditia ca sirul acela sa fie permutare (v=i) , iar daca nu era indeplinita variabila p se facea 0. Daca p era 0 afisam nu, iar daca p era 1 afisam da.

sunt bune cele 2 solutii propuse mai sus decat ca au complexitate n²

alta de complexitate n:

declari un vector de n elemente(indici de la 1 la n) numit viz
parcurgi vectorul tau v si faci viz[v] = 1. apoi parcurgi din nou viz si daca are un element diferit de 1 atunci nu e permutare, altfel e permutare.

Stefi024 a scris:

Pai m-am gandit ca pentru a fi o permutare trebuie sa aiba in ordine elementele de la 1 la n , iar fiecare numar sa fie pe pozitia i (de aici v=i) ...

Nu. Permutarea este o alta ordonarea a multimii initiale. Pentru asta trebuie sa verifici daca multimea citita de la tastatura are aceleasi elemente cu cea originala. La problema ta e un caz favorizant faptul ca multimea este formata din numere naturale consecutive.

Cel care a facut programul a gandit sa ordoneze crescator elementele multimii si apoi sa verifice daca sunt fiecare pe pozitia lui. Doar ca ... vectorii in majoritatea limbajelor de programare sunt 0 based. Adica primul element are indexul 0. Ar fi trebuit sa iti sara in ochi ca a declarat un vector de 101 elemente, cand multimea ta are maxim 100.

Bun, deci, unde e buba? Buba e ca tu citesti si ordonezi vectorul incepand cu pozitia 0, iar apoi valoarea din vector cu pozitia lui. Ori tu valorea 0 nu o citesti, pentru ca numerele introduse trebuie sa fie intre 1 si 100. (Aici mai are o hiba programul, nu validezi datele introduse). Ca sa mearga ai doua variante:

1. la citire si ordonare pornesti de la i=1

2. la verificarea ordinii pornesti de la i=0 pana la n-1 si compari pe v cu i-1

1. #include<iostream>
2. using namespace std;

Cu placere.