Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- (*Zadania z kolokwiów*)
- (*1 III13/14*)
- (*Postiadamu globalnie zadeklarowany graph g*)
- let path () =
- let n = size g in
- let length = Array.make n 0 in
- let look akt l =
- List.fold_left (fun wyn node ->
- if akt < node then max (length.(node)+1) wyn
- else wyn) 0 l in
- let wynik = ref 0 in
- for i = (n-1) downto 0 do
- let l = neighbours g i in
- wynik:= look i l;
- length.(i) <- !wynik
- done;
- !wynik;;
- (* Kolokwium 2017/18 *)
- open Array;;
- let segment t =
- let n = Array.length t in
- let dp = make_matrix n n 0 in
- let fib = make (n + 1) 0 in
- fib.(1) <- 1; fib.(2) <- 1;
- let i = ref 3 in
- while !i <= n
- do
- fib.(!i) <- fib.(!i - 1) + fib.(!i - 2); i := !i + 1;
- done;
- i := 0; let j = ref 0 in
- while !i < n
- do
- j := 2;
- while !j <= n
- do
- if t.(!i) = fib.(!j) then dp.(!i).(!i) <- !j;
- j := !j + 1;
- done;
- i := !i + 1;
- done;
- let odp = ref 0 in
- i := 1;
- while !i < n
- do
- j := 0;
- while !i + !j < n
- do
- let l = ref !j in
- while !l < !i + !j
- do
- let a = dp.(!j).(!l) and b = dp.(!l + 1).(!j + !i) in
- if a = 2 && b = 2
- then dp.(!j).(!j + !i) <- 3
- else if a - b = 1 || a - b = -1
- then dp.(!j).(!j + !i) <- max a b + 1;
- l := !l + 1;
- done;
- odp := max !odp dp.(!j).(!j + !i);
- j := !j + 1;
- done;
- i := !i + 1;
- done;
- !odp;;
- (*segment [|4; 2; 1; 2; 3; 5; 2; 8; 7|];;*)
- (* sadzawka [| [|2; 3; 2|]; [|2; 1; 2|]; [|2; 2; 2|] |] (1, 1) *)
- let sadzawka sadz (x, y) =
- let xsize = Array.length sadz in
- let ysize = Array.length sadz.(0) in
- let rozmiar = xsize * ysize in
- let kolejka = make (rozmiar + 1) [] in
- let i = ref 0 and j = ref 0 in
- while !i < xsize
- do
- while !j < ysize
- do
- let pole = sadz.(!i).(!j) in
- kolejka.(pole) <- ((!i, !j)::kolejka.(pole));
- j := !j + 1;
- done;
- i := !i + 1;
- done;
- let lider = init (rozmiar + 1) (fun x -> x) in
- let rec f a =
- if lider.(a) = a then a
- else begin lider.(a) <- f lider.(a); lider.(a) end
- in
- let union a b =
- if f b = rozmiar then lider.(f a) <- f b
- else lider.(f b) <- f a
- in
- i := rozmiar;
- let jest = ref false in
- while !jest = false && !i > 0
- do
- let rec dod lis =
- match lis with
- | [] -> ()
- | (ax, ay)::t ->
- if ax = 0 || ax = xsize - 1 || ay = 0 || ay = ysize - 1 then
- union rozmiar (ax * ysize + ay);
- if ax > 0 then union ((ax - 1) * ysize + ay) (ax * ysize + ay);
- if ax < xsize - 1 then union ((ax + 1) * ysize + ay) (ax * ysize + ay);
- if ay > 0 then union (ax * ysize + ay - 1) (ax * ysize + ay);
- if ay < ysize - 1 then union (ax * ysize + ay + 1) (ax * ysize +ay);
- dod t
- in
- dod kolejka.(!i);
- if f (x * ysize + y) = rozmiar && sadz.(x).(y) >= !i then jest := true;
- i := !i - 1;
- done;
- !i + 2;;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement