Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<fstream>
- using namespace std;
- struct nodo{int info; nodo* next; nodo(int a=0, nodo* b=0){info=a; next=b;}};
- nodo* crea(int dim)
- {
- if(dim)
- {
- int x;
- cin>>x;
- return new nodo(x,crea(dim-1));
- }
- return 0;
- }
- void stampa(nodo*L)
- {
- if(L)
- {
- cout<<L->info<<' ';
- stampa(L->next);
- }
- else
- cout<<endl;
- }
- void leggi(int dim, int*P)
- {
- if(dim)
- {
- cin>>*P;
- leggi(dim-1,P+1);
- }
- }
- /*
- PRE=(L(y) è lista corretta, dimP>=0, P[0..dimP-1]
- è def., vL(y)=L(y))
- TENTA E STACCA IN REALTA'
- Y=lista nodi match
- M=lista completa senza match
- */
- bool tenta(nodo*& y,int*P, int dimP, nodo*&m){
- if(!y)
- return false;
- if(!dimP){
- m=y; y=0;
- return true;}
- if(y->info==*P)
- return tenta(y->next,P+1,dimP-1,m);//(1)
- else
- return false;
- }
- /*Prova di correttezza:
- Caso base:
- y lista vuota, ritorno false, in lista vuota non può essere presente un match.
- dimP==0, P completamente percorso e Y() contiene nei primi dimP-1 nodi il match
- cercato, m sarà uguale al dimP esimo nodo, così da poter saltare il match,
- Y=0;
- ritorno true.
- vale PRE e POST.
- passo induttivo:
- ipotesi:
- supponiamo vera la PRE e POST rispetto alla chiamata ricorsiva (1),
- tenta invocata sul resto della lista, caso base mi garantisce POST.
- Dimostrazione:
- tenta scorre la lista se trova un presunto inizio match dimiuisce dimP, e avanza puntatore di P
- così caso base !dimP sse esiste un match contigui di P[dimP-1] in L1(y).
- POST=(se i primi dimP nodi di vL(y) hanno campi
- info=P[0..dimP-1], allora tenta restituisce true, e L(y) è l
- a lista corretta composta dai primi dimP nodi
- di vL(y) e m ha come valore la lista che resta da vL(y) una volta
- tolti i primi dimP nodi)&&(se i primi dimP nodi di vL(y) non
- esistono o non matchano P, allora tenta restituisce false eL(y)=vL(y))
- */
- nodo* match(nodo*&L1,int*P, int dimP)
- {
- if(!L1)
- return 0;
- nodo*r=L1,*m;
- if(tenta(r,P,dimP,m))
- {L1=m; return r;}
- //basti pensare che se la lista si trova all'inizio, naturalmente L1 partirà dal dimP-1 esimo nodo.
- else
- return match(L1->next,P,dimP); //L1->next a cosa è uguale? pensaci!
- }
- /*PROVA DI CORRETTEZZA:
- Scorro la lista L1 per riferimento,
- ad ogni invocazione ricorsiva valuto se dall elemento L1
- esiste un match con la funzione tenta.
- se il match non esisto continuo a scorrere la lista finchè non
- raggiungo caso base, altrimenti se tenta mi restituisce tre,
- L1 sarà uguale a m che è il nodo successivo alla lista staccata,
- e poi m verrà attaccato con il V(l1) al ritorno,
- */
- main()
- {
- int dim, dimP, P[20];
- cin>>dim;
- nodo* L1=crea(dim);
- cin>>dimP;
- leggi(dimP, P);
- nodo* L2= match(L1,P, dimP);
- stampa(L2);
- stampa(L1);
- cout<<"end"<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement