Problema.

[Geov]

Am si eu o intrebare cu o problema de backtracking.Problema suna cam asa: Se considerã un ºir a cu n numere naturale distincte: a1, a2,..., an.
Sã se genereze în ordine lexicograficã toate subºirurile vârf ale ºirului a, de lungime k≥3. Un subșir vârf este un subșir x al șirului a cu proprietatea cã acesta conține un singur numãr xi (1<i<k) astfel încât: x1 < x2 < … < xi-1 < xi > xi+1 > … > xk.Insa mna suna complicat dar e destul de simplu.Trebuie ca numarul din mijlocul unui sir sa fie mai mare ca vecinii lui de exemplu:
varf.in
4
2 1 4 3

varf.out
2 4 3
1 4 3
Aici e "schita" problemei facute de mine:

#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
int j,n,k,ev,as,s[100],a[100];

//ifstream fin("varf.in"); - Am pus // sa nu mai sterg iar citirea fisierului..
//ofstream fout("varf.out");

void init()
{s[k]=0;}

int succesor()
{ if(s[k]<n)
{ s[k]=s[k]+1; return 1;}
else return 0;}

int valid()
{
for(int i=1;i<k;i++)
if ((s[k]==s[i]) || ((s[i]<s[i-1]) && (s[i]<s[k]))) - problema e aici.Introduc 4 si dupa 2 1 4 3 [ nu conteaza ordinea neaparat ca am Bubble sortul facut in main dar mie imi afiseaza 1 2 3 , 1 2 4 , 1 3 4, 1 4 3 , 2 3 4 , 2 4 3 , 3 4 2 si 4 3 2.Mie imi vede si restul valorilor cu relatia ce am pus-o. In acest sir de exemplu 1 2 3 - 3 e mai
mare si ca 2 si ca 1 din fata din aceasta cauza mi-l ia si pe acesta ca fiind valid.Nu mi le ia doar din mijloc.Aveti vreo idee ce modificari sa aduc?
return 0;
return 1;
}

int solutie()
{return k==n;}

void tipar()
{ for (int i=1;i<n;i++)
cout<<a[s[i]]<<" ";
cout<<endl;}

void bt()
{ k=1; init();
while(k>0)
{ as=1; ev=0;
while(as && !ev)
{ as=succesor();
if(as)
ev=valid();}
if(as)
if(solutie()) tipar ();
else
{k++;
init();}
else k--;}}


int main()
{ int SW,i,aux;
cin>>n;
for(i=1;i<=n;i++)
{cin>>a[i];}

do{
SW=1;
for(i=1;i<=n-1;i++)
if (a[i]>a[i+1])
{SW=0;
aux=a[i];
a[i]=a[i+1];
a[i+1]=aux;}
}
while(SW!=1);

bt();
return 0;
}

[MindBreaker]

Sigur 2 4 3 este solutie. Nu prea îndeplineste cerinta. În sirul a între 2 si 4 este 1 care nu respectã conditia "x1 < x2 < … < xi-1 < xi > xi+1 > … > xk". Plus cã 2 4 3 nu e subsir a lui 2 1 4 3.
Deasemenea nu inteleg de ce sortezi sirul. Un sir sortat(fie el crescator sau descrescator) nu va indeplini niciodata conditia din cerinta.
Tips: 1) Foloseste pastebin.com pentru a trimite surse.
2) Nu mai folosi variabile globale!!!
3) Pentru functia valid si pentru orice functie care returneaza doar 0 sau 1(fals sau adevarator) foloseste tipul de date bool inloc de int. Si la return ai true sau false.


4.0.6 Protection Paladin PvE Guide
4.3.4 Demonology Warlock PvE Guide