From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 5 Oct 2021 21:49:54 +0200 Subject: Duzy commit ze smieciami --- semestr-3/pf/lista2/__pycache__/pot.cpython-38.pyc | Bin 0 -> 370 bytes semestr-3/pf/lista2/cze.cpp | 29 +++ semestr-3/pf/lista2/dwa.cpp | 22 ++ semestr-3/pf/lista2/pot.py | 7 + semestr-3/pf/lista2/rozw.ml | 230 +++++++++++++++++++++ semestr-3/pf/lista2/test.cpp | 27 +++ 6 files changed, 315 insertions(+) create mode 100644 semestr-3/pf/lista2/__pycache__/pot.cpython-38.pyc create mode 100644 semestr-3/pf/lista2/cze.cpp create mode 100644 semestr-3/pf/lista2/dwa.cpp create mode 100644 semestr-3/pf/lista2/pot.py create mode 100644 semestr-3/pf/lista2/rozw.ml create mode 100644 semestr-3/pf/lista2/test.cpp (limited to 'semestr-3/pf/lista2') diff --git a/semestr-3/pf/lista2/__pycache__/pot.cpython-38.pyc b/semestr-3/pf/lista2/__pycache__/pot.cpython-38.pyc new file mode 100644 index 0000000..9f7b0b3 Binary files /dev/null and b/semestr-3/pf/lista2/__pycache__/pot.cpython-38.pyc differ diff --git a/semestr-3/pf/lista2/cze.cpp b/semestr-3/pf/lista2/cze.cpp new file mode 100644 index 0000000..da58fa5 --- /dev/null +++ b/semestr-3/pf/lista2/cze.cpp @@ -0,0 +1,29 @@ +#include +using namespace std; + +int tab[1000010]; + +int main() +{ + int wsk = 0; + + while (true) + { + cin >> tab[wsk]; + if (tab[wsk] == -1) + break; + wsk++; + } + + for (int i = 0; i < wsk; i += 2) // i += 2 <=> i = i + 2 + { + cout << tab[i] << " "; + } + cout << "-1\n"; + + for (int i = 1; i < wsk; i += 2) + { + cout << tab[i] << " "; + } + cout << "-1\n"; +} \ No newline at end of file diff --git a/semestr-3/pf/lista2/dwa.cpp b/semestr-3/pf/lista2/dwa.cpp new file mode 100644 index 0000000..ba023d6 --- /dev/null +++ b/semestr-3/pf/lista2/dwa.cpp @@ -0,0 +1,22 @@ +#include +using namespace std; + +int t[1000004]; + +int main() +{ + int i = 0; + while (true) + { + cin >> t[i]; + if (t[i] == -1) + break; + i++; + } + for (int j = 0; j < i; j += 2) + cout << t[j] << " "; + cout << "-1\n"; + for (int j = 1; j < i; j += 2) + cout << t[j] << " "; + cout << "-1\n"; +} \ No newline at end of file diff --git a/semestr-3/pf/lista2/pot.py b/semestr-3/pf/lista2/pot.py new file mode 100644 index 0000000..7e86c8f --- /dev/null +++ b/semestr-3/pf/lista2/pot.py @@ -0,0 +1,7 @@ +def fun(r): + for i in range(r): + n = 2**i + while n > 10: + n //= 10 + print(f"{i}: {2**i} {n} {'<-- ' if n == 1 else ''}") + diff --git a/semestr-3/pf/lista2/rozw.ml b/semestr-3/pf/lista2/rozw.ml new file mode 100644 index 0000000..909db7a --- /dev/null +++ b/semestr-3/pf/lista2/rozw.ml @@ -0,0 +1,230 @@ +(* Zadanie 1 *) + +let sublists l = + let rec backtrack sl = function + | [] -> [sl] + | hd :: tl -> (backtrack (sl @ [hd]) tl) @ backtrack sl tl + in backtrack [] l + + +(* Zadanie 2 *) + +(* Znalezione tutaj: https://stackoverflow.com/questions/2710233/how-to-get-a-sub-list-from-a-list-in-ocaml *) + +let rec super_sublist b e = function + | [] -> failwith "empty list" + | hd :: tl -> + let tail = if e <= 1 then [] else super_sublist (b - 1) (e - 1) tl in + if b > 0 then tail else hd :: tail + +(* Moje rozwiązanie: *) + +let rec sublist b e l = + let rec suffix idx l = + if idx = 0 then l else suffix (idx - 1) (List.tl l) in + let rec prefix idx l = + if idx = 0 then [] else (List.hd l) :: (prefix (idx - 1) (List.tl l)) in + prefix (e - 1) (suffix b l) + +let cycle_with_sub sublist_fun xs n = + sublist_fun n (n + (List.length xs)) (xs @ xs) + +let super_cycle = cycle_with_sub super_sublist +let cycle = cycle_with_sub sublist + + +(* Zadanie 3 *) + +let reverse xs = + let rec iter res = function + | [] -> res + | hd :: tl -> (iter (hd :: res) tl) in + iter [] xs + +let merge_iter cmp xs ys = + let rec iter xs ys res = + match xs with + [] -> (reverse ys) @ res + | hdx :: tlx -> + match ys with + [] -> (reverse xs) @ res + | (hdy :: tly) when cmp hdx (List.hd ys) -> + iter tlx ys (hdx :: res) + | (hdy :: tly) -> iter xs tly (hdy :: res) in + (reverse (iter xs ys [])) + +let rec merge cmp xs ys = + match xs with + [] -> ys + | hdx :: tlx -> + match ys with + [] -> xs + | (hdy :: tly) when (cmp hdx (List.hd ys)) -> hdx :: (merge cmp tlx ys) + | (hdy :: tly) -> hdy :: (merge cmp xs tly) + +let gen_pesimistic ?(f = fun x -> x) range = + let rec iter xs = function + | 0 -> xs + | (n : int) -> iter ((f n) :: xs) (n - 1) in + iter [] range + +let time f x = + let t = Sys.time() in + let fx = f x in + Printf.printf "Execution time: %fs\n" (Sys.time() -. t); + fx + +let test_merge range = + let xs = gen_pesimistic range in + let ys = gen_pesimistic range in + time (merge (<) xs) ys + +let test_merge_iter range = + let xs = gen_pesimistic range in + let ys = gen_pesimistic range in + time (merge_iter (<) xs) ys + +let halve xs = + let rec iter xs crawl sth = + match crawl with + [] -> (sth, xs) + | [x] -> (sth, xs) + | st :: nd :: tl -> iter (List.tl xs) tl ((List.hd xs) :: sth) in + let sth, ndh = iter xs xs [] in + ((reverse sth), ndh) + +let rec mergesort_generic merge cmp = function + | [] -> [] + | [x] -> [x] + | xs -> let sth, ndh = halve xs in + merge cmp (mergesort_generic merge cmp sth) (mergesort_generic merge cmp ndh) + +let mergesort = mergesort_generic merge (<) +let mergesort_with_iter_merge = mergesort_generic merge_iter (<) + +let test_mergesort = mergesort [6;4;2;624;4;446;46;3;2346234;623;3246;23;6;3462;346] +let test_mergesort_with_iter_merge = mergesort_with_iter_merge [6;4;2;624;4;446;46;3;2346234;623;3246;23;6;3462;346] + +let range = 10000 +let mergesort_test = gen_pesimistic ~f:(fun x -> range - x) range +let pesimistic_mergesort_test = gen_pesimistic range + +let merge_no_reverse cmp xs ys = + let rec iter xs ys res = + match xs with + [] -> if ys == [] then res else iter xs (List.tl ys) ((List.hd ys) :: res) + | hdx :: tlx -> + match ys with + [] -> iter tlx ys (hdx :: res) + | hdy :: tly -> + if cmp hdx hdy + then iter tlx ys (hdx :: res) + else iter xs tly (hdy :: res) in + iter xs ys [] + + +(* Zadanie 4 *) + +let rec map f = function + | [] -> [] + | hd :: tl -> (f hd) :: (map f tl) + +let rec perm = + let rec iter res pref = function + | [] -> res + | hd :: tl -> + let perms = map (fun ys -> hd :: ys) (perm (pref@tl)) in + iter (res @ perms) (pref @ [hd]) tl in function + | [] -> [[]] + | xs -> iter [] [] xs + +let rec flatmap f = function + | [] -> [] + | hd :: tl -> (f hd) @ (flatmap f tl) + +let rec perm_flat = + let rec iter res x pref = function + | [] -> (pref@[x]) :: res + | hd :: tl -> + iter ((pref@(x :: hd :: tl)) :: res) x (pref@[hd]) tl in function + | [] -> [[]] + | hd :: tl -> + flatmap (iter [] hd []) (perm_flat tl) + + +(* Zadanie 5 *) + +let suffixes xs = + let rec iter res = function + | [] -> [] :: res + | hd :: tl -> iter ((hd :: tl) :: res) tl in + reverse (iter [] xs) + +let prefixes xs = reverse (map reverse (suffixes (reverse xs))) + +(* Zadanie 6 *) + +type 'a clist = { clist : 'z. ('a -> 'z -> 'z) -> 'z -> 'z } + +let cnil = { clist = fun f z -> z } +let ccons x xs = { clist = fun f z -> f x (xs.clist f z) } +let map g xs = { clist = fun f z -> xs.clist (fun a z -> f (g a) z) z } +let append xs ys = { clist = fun f z -> xs.clist f (ys.clist f z) } +let clist_to_list xs = xs.clist (fun x xs -> x :: xs) [] +(* let prod xs ys = fun f z -> { clist = fun f z -> xs.clist ( ) z } *) + +let prod xs ys = { clist = fun f z -> xs.clist (fun a z -> ys.clist (fun b zz -> f (a, b) zz) z) z } + +(* 'a clist -> 'b clist -> ('b -> 'a) clist *) +(* let list_pow xs ys = { clist= fun f x -> } *) + +(* let pow f1 f2 = { cnum = fun f x -> (f2.cnum (mul f1) one).cnum f x } *) + +let ccar xs = List.hd (clist_to_list xs) + +(* Zadanie 7 *) + +type cbool = { cbool : 'a. 'a -> 'a -> 'a } +type cnum = { cnum : 'a. ('a -> 'a) -> 'a -> 'a } + +let even n = + { cbool = fun tt ff -> fst (n.cnum (fun (a, b) -> (b, a)) (tt, ff))} + +let ctrue = + { cbool = fun a b -> a} +let cfalse = + { cbool = fun a b -> b} +let cand f1 f2 a b = f1.cbool (f2.cbool a b) b +let cor f1 f2 a b = f1.cbool a (f2.cbool a b) +let cbool_of_bool b = if b then ctrue else cfalse +let bool_of_cbool f = f.cbool true false + +let zero = { cnum = fun f x -> x } + +let succ fn = { cnum = fun f x -> fn.cnum f (f x) } +let add f1 f2 = { cnum = fun f x -> f1.cnum f (f2.cnum f x) } +let mul f1 f2 = { cnum = fun f x -> f1.cnum (f2.cnum f) x } + +let one = succ zero +let pow f1 f2 = { cnum = fun f x -> (f2.cnum (mul f1) one).cnum f x } + +let rec cnum_of_int = function + | 0 -> zero + | n -> succ (cnum_of_int (n - 1)) +let is_zero f = + let g x = x + 1 + in if (f.cnum g 0) = 0 then true else false +let int_of_cnum f = f.cnum (fun x -> x + 1) 0 + +let two = succ one +let three = succ two +let four = succ three +let five = succ four + +let func x = x * 2 + +let pred n = { cnum = fun f x -> fst (n.cnum (fun (a, b) -> (b, f(b))) (x, x)) } + +let ctail xs = { clist = fun f z -> fst (xs.clist (fun a (z1, z2) -> (z2, f a z2)) (z, z)) } + +let length xs = xs.clist (fun a z -> z + 1) 0 \ No newline at end of file diff --git a/semestr-3/pf/lista2/test.cpp b/semestr-3/pf/lista2/test.cpp new file mode 100644 index 0000000..59d0a45 --- /dev/null +++ b/semestr-3/pf/lista2/test.cpp @@ -0,0 +1,27 @@ +#include + +using namespace std; +int tab[100]; +int main() +{ + int x,n,j; + for(int i=0;i<=1000;i++) + { + cin>>x; + if(x==-1) + { + break; + } + tab[x]++; + } + for(int i=0;i<=100;i++) + { + j=0; + while(j