Question

Codul ar trebui sa realizeze un fazan cu cuvintele primite de la stanga la dreapta fara sa se intoarca doar ca intampin un bug pentru:
"ana nare revista reclama mare"
In loc sa afiseze:
ana
nare
reclama
mare
El afiseaza:
ana
nare
revista
Codul trebuie sa afiseze lungimea cea mai mare ca numar de cuvinte. Nu am realizat corect backtracking ul pentru ca vreau chiar daca a gasit un cuvant care se potrivste sa verifice si pe restu care se potrivesc.

d43416e5f6ca7c8984054b5b6d9e6fb0.txt

Answer 1

Sunt mai multe probleme, unele mai grave decat altele:

• De multe ori e posibil sa se apeleze fazan.pop_back(), dar vectorul fazan sa fie gol, ceea ce rezulta intr-o eroare la executie
• Este insuficient sa initializezi i cu valoarea "pozitie + 1" pentru a garanta ca cuvintele nu se repeta si ca se pastreaza ordinea initiala. Daca avem sirul "ana dorina remia popescu nare mari iare remuscari" atunci la pozitie=0 se va adauga in vector "ana", la pozitie=1 se va adauga in vector "nare", iar apoi la pozitie=3 apare buba, se va adauga in vector remia, ceea ce nu e ok pentru ca trebuie ca cuvintele sa isi pastreze ordinea. Trebuie sa incercam practic urmatoarele cuvinte de dupa "nare", nu cuvantul de pe a treia pozitie... Acest lucru e dificil de realizat in complexitate ok in modul in care e construit programul acum, e unul din motivele pentru care am ales sa fac o restructurare completa
• Functia de backtracking nu prea respecta structura, ceea ce duce la batai de cap serioase cand incerci sa repari programul. O functie de backtracking ar trebui sa aiba in mare urmatoarea structura :

┌void backtracking(int nivel){

│    daca (nivel<0) return;

│   ┌pentru toate elementele i disponibile

│   │   ┌daca solutia este valida adaugand elementul i

│   │   │    adauga i la solutie

│   │   │    verifica daca e solutie finala si afiseaza/stocheaza/etc.

│   │   │    backtracking(nivel+1)

│   │   │    sterge elementul i din solutie

│   │   └■

│   └■

└■

Se pot face mici modificari acestei structuri daca e cazul, putem adauga i la solutie si verificam dupa daca e valid (in acest caz stergem elementul i la final din solutie indiferent daca e solutie finala sau nu)

Alte probleme/lucruri nerecomandate:

• #include <bits/stdc++.h> adauga chestii inutile proiectului (care e posibil sa ne incurce), face executabilul neportabil, nu functioneaza in multe IDE-uri, etc. Se evita folosirea lui
• using namespace std → nerecomandat, pot aparea conflicte de nume greu de diagnosticat in cazul in care lucram cu biblioteci externe multiple
• variabilele globale nu sunt recomandate. Daca o sa lucrezi cu fisiere multiple o sa aflii usor de ce. In cazul in care folosim variabile care sunt folosite de mai multe functii ar fi cazul sa ne intrebam daca nu cumva e mai bine sa adaugam elementele respective intr-o clasa
• Cand transmitem stringuri sau vectori la alte functii e indicat sa le transmitem prin referinta pentru a evita realizarea unei copii inutile care incarca degeaba memoria si dureaza destul de mult de realizat. Transmitem variabilele acestea ca constante in cazul in care nu dorim sa le modificam. In plus, in loc sa lucram direct cu vectori de stringuri putem lucra cu vector de intregi in care fiecare intreg ii corespunde un string din vectorul de stringuri. Aceasta abordare salveaza destul de mult timp ca eficienta si e in special recomandata pentru problema noastra

► Nota:

• Si programul meu are loc de imbunatatiri pe partea de performanta dar am vrut in special sa fie cat se poate de usor de citit, fara a folosi mici "smecherii" pentru a evita unele operatiii. Functia recursiva de backtracking putea fi implementata ca una interativa, lucru care e aproape mereu recomandat.

• Backtracking nu e modalitatea recomandata de rezolvare a acestei probleme (existand probabil o solutie mai eficienta folosind programarea dinamica) - deci probabilitatea de a primi scor mare pe platformele de evaluare automate e destul de mica. Am implementat solutia cu backtracking pentru ca nu am vrut sa schimb complet algoritmul gandit de tine, doar sa in repar si sa fac o refactorizare.

► COD FUNCTIONAL RECOMANDAT :

Vezi in atasament

c6bb45f685ef4cf219c0767ac0952689.txt