Advertisement
Guest User

Kody 2

a guest
Jan 15th, 2019
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
OCaml 2.80 KB | None | 0 0
  1. (*Zadania z kolokwiów*)
  2.  
  3. (*1 III13/14*)
  4.  
  5. (*Postiadamu globalnie zadeklarowany graph g*)
  6. let path () =
  7.   let n = size g in
  8.   let length = Array.make n 0 in
  9.   let look akt l =
  10.     List.fold_left (fun wyn node ->
  11.       if akt < node then max (length.(node)+1) wyn
  12.       else wyn) 0 l in
  13.  
  14.   let wynik = ref 0 in
  15.  
  16.   for i = (n-1) downto 0 do
  17.     let l = neighbours g i in
  18.     wynik:= look i l;
  19.     length.(i) <- !wynik
  20. done;
  21. !wynik;;
  22.  
  23. (* Kolokwium 2017/18 *)
  24.  
  25. open Array;;
  26.  
  27. let segment t =
  28.     let n = Array.length t in
  29.     let dp = make_matrix n n 0 in
  30.     let fib = make (n + 1) 0 in
  31.     fib.(1) <- 1; fib.(2) <- 1;
  32.     let i = ref 3 in
  33.     while !i <= n
  34.     do
  35.         fib.(!i) <- fib.(!i - 1) + fib.(!i - 2); i := !i + 1;
  36.     done;
  37.    
  38.     i := 0; let j = ref 0 in
  39.     while !i < n
  40.     do
  41.         j := 2;
  42.         while !j <= n
  43.         do
  44.             if t.(!i) = fib.(!j) then dp.(!i).(!i) <- !j;
  45.             j := !j + 1;
  46.         done;
  47.         i := !i + 1;
  48.     done;
  49.     let odp = ref 0 in
  50.  
  51.     i := 1;
  52.     while !i < n
  53.     do
  54.         j := 0;
  55.         while !i + !j < n
  56.         do
  57.             let l = ref !j in
  58.             while !l < !i + !j
  59.             do
  60.                 let a = dp.(!j).(!l) and b = dp.(!l + 1).(!j + !i) in
  61.                 if a = 2 && b = 2
  62.                 then dp.(!j).(!j + !i) <- 3
  63.                 else if a - b = 1 || a - b = -1
  64.                 then dp.(!j).(!j + !i) <- max a b + 1;
  65.                 l := !l + 1;
  66.             done;
  67.             odp := max !odp dp.(!j).(!j + !i);
  68.             j := !j + 1;
  69.         done;
  70.         i := !i + 1;
  71.     done;
  72.    
  73.     !odp;;
  74.        
  75. (*segment [|4; 2; 1; 2; 3; 5; 2; 8; 7|];;*)
  76.  
  77. (* sadzawka [| [|2; 3; 2|]; [|2; 1; 2|]; [|2; 2; 2|] |] (1, 1) *)
  78.  
  79. let sadzawka sadz (x, y) =
  80.     let xsize = Array.length sadz in
  81.     let ysize = Array.length sadz.(0) in
  82.     let rozmiar = xsize * ysize in
  83.     let kolejka = make (rozmiar + 1) [] in
  84.    
  85.     let i = ref 0 and j = ref 0 in
  86.     while !i < xsize
  87.     do
  88.         while !j < ysize
  89.         do
  90.             let pole = sadz.(!i).(!j) in
  91.             kolejka.(pole) <- ((!i, !j)::kolejka.(pole));
  92.             j := !j + 1;
  93.         done;
  94.         i := !i + 1;
  95.     done;
  96.  
  97.     let lider = init (rozmiar + 1) (fun x -> x) in
  98.  
  99.     let rec f a =
  100.         if lider.(a) = a then a
  101.             else begin lider.(a) <- f lider.(a); lider.(a) end
  102.     in
  103.    
  104.     let union a b =
  105.         if f b = rozmiar then lider.(f a) <- f b
  106.             else lider.(f b) <- f a
  107.     in
  108.    
  109.     i := rozmiar;
  110.     let jest = ref false in
  111.     while !jest = false && !i > 0
  112.     do
  113.         let rec dod lis =
  114.             match lis with
  115.             | [] -> ()
  116.             | (ax, ay)::t ->
  117.                 if ax = 0 || ax = xsize - 1 || ay = 0 || ay = ysize - 1 then
  118.                     union rozmiar (ax * ysize + ay);
  119.                 if ax > 0 then union ((ax - 1) * ysize + ay) (ax * ysize + ay);
  120.                 if ax < xsize - 1 then union ((ax + 1) * ysize + ay) (ax * ysize + ay);
  121.                 if ay > 0 then union (ax * ysize + ay - 1) (ax * ysize + ay);
  122.                 if ay < ysize - 1 then union (ax * ysize + ay + 1) (ax * ysize +ay);
  123.                 dod t
  124.             in
  125.             dod kolejka.(!i);
  126.             if f (x * ysize + y) = rozmiar && sadz.(x).(y) >= !i then jest := true;
  127.             i := !i - 1;
  128.     done;
  129.        
  130.     !i + 2;;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement