{"id":571,"date":"2014-12-31T12:09:39","date_gmt":"2014-12-31T11:09:39","guid":{"rendered":"http:\/\/www.valcon.it\/pascal\/?p=571"},"modified":"2015-07-03T12:57:12","modified_gmt":"2015-07-03T10:57:12","slug":"fusione-di-sequenze","status":"publish","type":"post","link":"https:\/\/www.valcon.it\/pascal\/fusione-di-sequenze\/","title":{"rendered":"Fusione di sequenze"},"content":{"rendered":"

A partire da due sequenze ordinate, v1 e v2, si vuole realizzare una terza sequenza ordinata v3.<\/p>\n

Esempi<\/h3>\n
    \n
  1. v1=(1, 2, 4, 5)
    \nv2=()
    \nv3=(1, 2, 4, 5)<\/tt><\/li>\n
  2. v1=(1, 2, 4, 5)
    \nv2=(20, 30, 40, 60)
    \nv3=(1, 2, 4, 5, 20, 30, 40, 60)<\/tt><\/li>\n
  3. v1=(1, 2, 4, 5, 7, 10)
    \nv2=(2, 3, 4, 6)
    \nv3=(1, 2, 2, 3, 4, 4, 5, 6, 7, 10)<\/tt><\/li>\n<\/ol>\n

    Algoritmo<\/h3>\n

    Una scansione delle due sequenze sceglie, a ogni passo, l’elemento da copiare nella terza sequenza.
    \n\u00c8 sufficiente confrontare i primi elementi perch\u00e9…<\/p>\n

    Esempio<\/h3>\n
    \n\n\n\n\n\n\n\n\n\n\n\n\n\n
    v1<\/em><\/td>\nv2<\/em><\/td>\nv3<\/em><\/td>\n<\/tr>\n
    1<\/strong><\/span>, 2, 4, 5, 7, 10<\/td>\n2, 3, 4, 6<\/td>\n1<\/strong><\/td>\n<\/tr>\n
    2<\/strong><\/span>, 4, 5, 7, 10<\/td>\n2, 3, 4, 6<\/td>\n1, 2<\/strong><\/td>\n<\/tr>\n
    4, 5, 7, 10<\/td>\n2<\/strong><\/span>, 3, 4, 6<\/td>\n1, 2, 2<\/strong><\/td>\n<\/tr>\n
    4, 5, 7, 10<\/td>\n3<\/strong><\/span>, 4, 6<\/td>\n1, 2, 2, 3<\/strong><\/td>\n<\/tr>\n
    4<\/strong><\/span>, 5, 7, 0<\/td>\n4, 6<\/td>\n1, 2, 2, 3, 4<\/strong><\/td>\n<\/tr>\n
    5, 7, 10<\/td>\n4<\/strong><\/span>, 6<\/td>\n1, 2, 2, 3, 4, 4<\/strong><\/td>\n<\/tr>\n
    5<\/strong><\/span>, 7,10<\/td>\n6<\/td>\n1, 2, 2, 3, 4, 4, 5<\/strong><\/td>\n<\/tr>\n
    7, 10<\/td>\n6<\/strong><\/span><\/td>\n1, 2, 2, 3, 4, 4, 5, 6<\/strong><\/td>\n<\/tr>\n
    7<\/strong><\/span>, 10<\/td>\n<\/td>\n1, 2, 2, 3, 4, 4, 5, 6, 7<\/strong><\/td>\n<\/tr>\n
    10<\/strong><\/span><\/td>\n<\/td>\n1, 2, 2, 3, 4, 4, 5, 6, 7, 10<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    Procedure MERGE( \u00a0 \u00a0 V1: Vettore; \u00a0 \u00a0 L1: Integer;\r\n                     V2: Vettore; \u00a0 \u00a0 L2: Integer;\r\n                 Var V3: Vettore; Var L3: Integer);\r\nVar\r\n   I, J, K: Integer;\r\nBegin\r\n   I:=1;\r\n   J:=1;\r\n   K:=1;\r\n   While(I <= L1) And (J <= L2) Do\r\n      Begin\r\n         If(V1[I] <= V2[J]) Then\r\n            Begin\r\n               V3[K]:=V1[I];\r\n               Inc(I);\r\n            End\r\n         Else\r\n            Begin\r\n               V3[K]:=V2[J];\r\n               Inc(J);\r\n            End;\r\n         Inc(K);\r\n      End;\r\n   While(I <= L1) Do\r\n      Begin\r\n         V3[K]:=V1[I];\r\n         Inc(I);\r\n         Inc(K);\r\n      End;\r\n   While(J <= L2) Do\r\n      Begin\r\n         V3[K]:=V2[J];\r\n         Inc(J);\r\n         Inc(K);\r\n      End;\r\n   L3:=K-1;\r\nEnd;<\/pre>\n<\/div>\n
    Sottosequenze<\/h3>\n
    Supponiamo che l\u2019array V<\/strong> contenga due sottoarray adiacenti ordinati<\/p>\n