Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Fisuri anvelope?

Valabilitate permis auto cat. A s...

Caramida aparenta peste termosistem

Linistea din timpul penelor de cu...
 Achiziție laptop baterie det...

Cenzura in masa comentarii youtube

Inscriere copil la scoala in Roma...

exista adaptoare pentru baterii P...
 Sa folosim antivirus, antimalware?

SMS suspect livrare "posta ro...

Film original sau pirat?

Cum poti inregistra CD-uri in for...
 Ceainaria celor pasionați de...

Probleme la acoperis din cauza in...

Transferuri instant intre bancile...

player video cu preview cadru pe ...
 

Metoda backtracking

- - - - -
  • Please log in to reply
12 replies to this topic

#1
tuddy_09

tuddy_09

    New Member

  • Grup: Candidate Members
  • Posts: 2
  • Înscris: 27.10.2022
Salut,
De cateva zile ma chinui sa inteleg metoda backtracking si nu am inteles cum pot sa o folosesc in rezolvarea problemelor.

Ma puteti ajuta sa inteleg si sa rezolv aceasta problema: Se da o secventa a = a1,a2,...,an cu elemente numere intregi. Determinati toate subsecventele strict crescatoare ale secventei a folosind metoda backtracking. (ordinea elementelor din secventa initiala trebuie pastrata).

#2
tavitu

tavitu

    Minune: HE a început să emită facturile!

  • Grup: Senior Members
  • Posts: 5,598
  • Înscris: 16.02.2009
Uite o secvență de numere

Quote

1 3 6 9 10 8 5 7 2 4

Care sunt toate subsecvențele strict crescătoare ale acestei secvențe?

Întreb asta în primul rând că să se înțeleagă ce se cere, și in al doilea rând că poate lucrând la problemă manual ajungi la un algoritm care apoi se poate transpune în (pseudo)cod.

Edited by tavitu, 27 October 2022 - 15:23.


#3
roPopa

roPopa

    Active Member

  • Grup: Members
  • Posts: 1,218
  • Înscris: 21.01.2011
ce inseamna subsecventa?

2 numere?
3 numere?
x numere?

din ex lui tavitu

1 3 este o secventa?
3 6 este alta secventa?
sau daca 1 3 este o secventa 3 nu mai poate fi folosit in alta secventa si urmatoarea secventa este 6 9?

#4
utopium

utopium

    Guru Member

  • Grup: Senior Members
  • Posts: 45,387
  • Înscris: 14.08.2007
Subsecventa crescatoare inseamna minim 2 numere din punctul meu de vedere. Ideea e sa iei initial primul numar care corespunde regulii de a fi mai mare decat cel anterior, iar prin backtracking cand nu mai poti lua alt numar, te intorci, scoti ultimul numar adaugat la secventa si incerci sa iei altul aflat mai la dreapta lui pana le termini pe toate ... apoi te intorci si il schimbi pe urmatorul si tot asa.

#5
tavitu

tavitu

    Minune: HE a început să emită facturile!

  • Grup: Senior Members
  • Posts: 5,598
  • Înscris: 16.02.2009
Din punctul meu de vedere o subsecvență crescătoare poate însemna și o subsecvența formată dintr-un singur număr, și din această cauză l-am rugat să exemplifice, pentru a elimina dubiile.

#6
utopium

utopium

    Guru Member

  • Grup: Senior Members
  • Posts: 45,387
  • Înscris: 14.08.2007

View Posttavitu, on 27 octombrie 2022 - 15:22, said:

Uite o secvență de numere

1 3 6 9 10 8 5 7 2 4

Care sunt toate subsecvențele strict crescătoare ale acestei secvențe?
Sunt prea multe ... trebuie sa iei un exemplu mai simplu daca vrei sa le gasesti manual pe toate, sa zicem:
1 6 10 8 2 4
Algoritmul ar da intai prima solutie:
1 6 10 (well, discutabil, cred ca si 1 6 ar fi mai intai) ... apoi il sterge pe 10 si cauta urmatorul numar care se potriveste, si vine 1 6 8 ... apoi il sterge pe 8 si cauta alta solutie, nu mai gaseste ... asa ca trebuie sa-l stearga pe 6 si il ia pe 10, deci solutia 1 10 ... nu mai gaseste alta solutie cu 10, asa ca il sterge pe 10 si il ia pe 8, solutie 1 8 ... nu mai gaseste alta, il sterge pe 8 si il ia pe 2 si apoi pe 4, deci solutie 1 2 4 ... le sterge pe amandoua si ajunge sa-l elimine pe 1 din lista si sa faca solutii gen 6 10, 6 8, 2 4.

Cred ca de fiecare data cand are minim 2 numere trebuie afisata o solutie, adica si 1 6 ar fi o solutie, inainte de a il adauga pe 10.

View Posttavitu, on 27 octombrie 2022 - 16:16, said:

Din punctul meu de vedere o subsecvență crescătoare poate însemna și o subsecvența formată dintr-un singur număr, și din această cauză l-am rugat să exemplifice, pentru a elimina dubiile.
Nu are cum sa fie crescatoare daca vorbim de un singur numar ... de aia zic ca minim 2 numere trebuie sa fie.

Edited by utopium, 27 October 2022 - 16:29.


#7
darkangel2

darkangel2

    Senior Member

  • Grup: Senior Members
  • Posts: 3,238
  • Înscris: 26.01.2019

View Posttuddy_09, on 27 octombrie 2022 - 11:51, said:

Se da o secventa a = a1,a2,...,an cu elemente numere intregi. Determinati toate subsecventele strict crescatoare ale secventei a folosind metoda backtracking.

Fie secventa de numere v = [ 10 50 30 40 60 ].

Exemple de subsecvente cautate:
s1 = [ 10 50 60 ]; indecsii corespunzatori din v sunt vx1 = [ 1 2 5 ] (presupun ca primul index este 1)
s2 = [ 10 30 40 60 ]; indecsii corespunzatori din v sunt vx2 = [ 1 3 4 5 ]
s3 = [ 10 40 60 ]; indecsii corespunzatori din v sunt vx3 = [ 1 4 5 ]

Prin urmare: subsecventele cautate sunt vectori vx care indeplinesc niste conditii:
1 pentru orice i: 1 <= vx[i] <= 5 (valorile sunt indecsi in v)
2 pentru orice i < 4: vx[i] < vx[i+1] (valorile sunt indecsi crescatori)
3 pentru orice i < 4: v[ vx[i] ] < v[ vx[i+1] ] (valorile din v de pe pozitile vx[i] si vx[i+1] trebuie sa fie crescatoare)
4 vx trebuie sa aiba minim un element


Problema s-ar putea rezolva simplu daca ai reusi sa generezi cumva toti vectorii vx posibili; tot ce ai mai avea de facut ar fi sa verifici care din acesti vectori respecta conditiile de mai sus.

Backtracking este una din metodele care iti permite sa generezi toti vectorii posibili care respecta conditia 1 de mai sus.
Practic trebuie sa generezi toti vectorii de maxim 5 elemente care contin numere de la 1 la 5:
- [ 1 ]
- [ 1 1 ]
- [ 1 1 1 ]
- [ 1 1 1 1 ]
- [ 1 1 1 1 1 ]
- [ 1 1 1 1 2 ]
- ............
- [ 1 1 1 1 5 ]
- [ 1 1 1 2 ]
- [ 1 1 1 2 1 ]
- [ 1 1 1 2 2 ]
- ..........


Dupa ce ai generat fiecare vector, tot ce trebuie sa faci este sa verifici daca respecta conditiile 2 - 4; daca da, atunci ai gasit o subsecventa.

Abordarea de mai sus poate fi imbunatatita astfel: in loc sa generezi vectorii tinand cont doar de prima conditie, poti sa tii cont si de a doua conditie care zice ca numerele trebuie sa fie crescatoare:
- [ 1 ]
- [ 1 2 ]
- [ 1 2 3 ]
- [ 1 2 3 4 ]
- [ 1 2 3 4 5 ]
- [ 1 2 3 5 ]
- [ 1 2 4 ]
- [ 1 2 4 5 ]
- [ 1 2 5 ]
- [ 1 3 ]
- ......


Deja ai reusit sa generezi mult mai putine valori invalide.

#8
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,296
  • Înscris: 10.08.2005

Quote

Ma puteti ajuta sa inteleg si sa rezolv aceasta problema:
Se da o secventa a = a1,a2,...,an cu elemente numere intregi.
Determinati toate subsecventele strict crescatoare ale secventei a
folosind metoda backtracking
(ordinea elementelor din secventa initiala trebuie pastrata).
ce ar fi sa ignoram natura ordonata a subsecevntei
si sa vedem cate subsecvente are secventa a

View Posttavitu, on 27 octombrie 2022 - 16:16, said:

Din punctul meu de vedere o subsecvență crescătoare poate însemna și o subsecvența formată dintr-un singur număr, și din această cauză l-am rugat să exemplifice, pentru a elimina dubiile.

Un singur numar este o subsecventa nedefinita.
El formeaza o subsecenta crescatoare sau descrescatoare in raport cu alta subseventa (fie ea definta sau nu).

Edited by MarianG, 27 October 2022 - 22:07.


#9
tuddy_09

tuddy_09

    New Member

  • Grup: Candidate Members
  • Posts: 2
  • Înscris: 27.10.2022

View Posttavitu, on 27 octombrie 2022 - 15:22, said:

Uite o secvență de numere



Care sunt toate subsecvențele strict crescătoare ale acestei secvențe?

Întreb asta în primul rând că să se înțeleagă ce se cere, și in al doilea rând că poate lucrând la problemă manual ajungi la un algoritm care apoi se poate transpune în (pseudo)cod.
Nu se precizeaza exact, dar eu consider si secventele de un element strict crescatoare.

#10
darkangel2

darkangel2

    Senior Member

  • Grup: Senior Members
  • Posts: 3,238
  • Înscris: 26.01.2019

View Posttuddy_09, on 28 octombrie 2022 - 08:44, said:

dar eu consider si secventele de un element strict crescatoare

Si eu consider la fel.
Oricum, din moment ce secventele de un element pot fi usor determinate, poti ignora acest aspect (in sensul ca nu este critic pentru rezolvarea problemei)...

Edited by darkangel2, 28 October 2022 - 09:49.


#11
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,296
  • Înscris: 10.08.2005
cum sunt secventele extrase este irelevant

va interesează cum parcurgeți șirul primit, "nod cu nod, și înapoi"

Edited by MarianG, 28 October 2022 - 10:17.


#12
utopium

utopium

    Guru Member

  • Grup: Senior Members
  • Posts: 45,387
  • Înscris: 14.08.2007

View Posttuddy_09, on 28 octombrie 2022 - 08:44, said:

Nu se precizeaza exact, dar eu consider si secventele de un element strict crescatoare.
Termenul strict crescator nu are sens pentru un element, are sens pentru minim doua elemente.

#13
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,296
  • Înscris: 10.08.2005
multimile cu un singur element sunt "singleton"
link

View Posttavitu, on 27 octombrie 2022 - 15:22, said:

Uite o secvență de numere
porniti de aici
1 3 6 9 10 8 5 7 2 4
Attached File  matrice.png   18.53K   1 downloads

se permit miscari doar in jos, si la dreapta

Edited by MarianG, 29 October 2022 - 10:21.


Anunturi

Bun venit pe Forumul Softpedia!

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate