Advertisement
Guest User

Untitled

a guest
Dec 11th, 2016
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.71 KB | None | 0 0
  1. #include<iostream>
  2.  
  3. #include<fstream>
  4. using namespace std;
  5.  
  6.  
  7. struct nodo{int info; nodo* next; nodo(int a=0, nodo* b=0){info=a; next=b;}};
  8.  
  9.  
  10.  
  11. nodo* crea(int dim)
  12. {
  13. if(dim)
  14. {
  15. int x;
  16. cin>>x;
  17. return new nodo(x,crea(dim-1));
  18. }
  19. return 0;
  20. }
  21.  
  22. void stampa(nodo*L)
  23. {
  24. if(L)
  25. {
  26. cout<<L->info<<' ';
  27. stampa(L->next);
  28. }
  29. else
  30. cout<<endl;
  31. }
  32.  
  33. void leggi(int dim, int*P)
  34. {
  35. if(dim)
  36. {
  37. cin>>*P;
  38. leggi(dim-1,P+1);
  39. }
  40.  
  41. }
  42.  
  43. /*
  44. PRE=(L(y) è lista corretta, dimP>=0, P[0..dimP-1]
  45. è def., vL(y)=L(y))
  46. TENTA E STACCA IN REALTA'
  47. Y=lista nodi match
  48. M=lista completa senza match
  49. */
  50. bool tenta(nodo*& y,int*P, int dimP, nodo*&m){
  51.  
  52. if(!y)
  53. return false;
  54.  
  55. if(!dimP){
  56. m=y; y=0;
  57. return true;}
  58.  
  59. if(y->info==*P)
  60. return tenta(y->next,P+1,dimP-1,m);//(1)
  61.  
  62. else
  63. return false;
  64.  
  65. }
  66. /*Prova di correttezza:
  67. Caso base:
  68. y lista vuota, ritorno false, in lista vuota non può essere presente un match.
  69. dimP==0, P completamente percorso e Y() contiene nei primi dimP-1 nodi il match
  70. cercato, m sarà uguale al dimP esimo nodo, così da poter saltare il match,
  71. Y=0;
  72. ritorno true.
  73. vale PRE e POST.
  74.  
  75. passo induttivo:
  76. ipotesi:
  77. supponiamo vera la PRE e POST rispetto alla chiamata ricorsiva (1),
  78. tenta invocata sul resto della lista, caso base mi garantisce POST.
  79. Dimostrazione:
  80. tenta scorre la lista se trova un presunto inizio match dimiuisce dimP, e avanza puntatore di P
  81. così caso base !dimP sse esiste un match contigui di P[dimP-1] in L1(y).
  82.  
  83. POST=(se i primi dimP nodi di vL(y) hanno campi
  84. info=P[0..dimP-1], allora tenta restituisce true, e L(y) è l
  85. a lista corretta composta dai primi dimP nodi
  86. di vL(y) e m ha come valore la lista che resta da vL(y) una volta
  87. tolti i primi dimP nodi)&&(se i primi dimP nodi di vL(y) non
  88. esistono o non matchano P, allora tenta restituisce false eL(y)=vL(y))
  89. */
  90. nodo* match(nodo*&L1,int*P, int dimP)
  91. {
  92. if(!L1)
  93. return 0;
  94.  
  95. nodo*r=L1,*m;
  96.  
  97. if(tenta(r,P,dimP,m))
  98. {L1=m; return r;}
  99. //basti pensare che se la lista si trova all'inizio, naturalmente L1 partirà dal dimP-1 esimo nodo.
  100. else
  101. return match(L1->next,P,dimP); //L1->next a cosa è uguale? pensaci!
  102. }
  103. /*PROVA DI CORRETTEZZA:
  104. Scorro la lista L1 per riferimento,
  105. ad ogni invocazione ricorsiva valuto se dall elemento L1
  106. esiste un match con la funzione tenta.
  107. se il match non esisto continuo a scorrere la lista finchè non
  108. raggiungo caso base, altrimenti se tenta mi restituisce tre,
  109. L1 sarà uguale a m che è il nodo successivo alla lista staccata,
  110. e poi m verrà attaccato con il V(l1) al ritorno,
  111. */
  112. main()
  113. {
  114. int dim, dimP, P[20];
  115. cin>>dim;
  116. nodo* L1=crea(dim);
  117. cin>>dimP;
  118. leggi(dimP, P);
  119. nodo* L2= match(L1,P, dimP);
  120. stampa(L2);
  121. stampa(L1);
  122. cout<<"end"<<endl;
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement