aboutsummaryrefslogtreecommitdiff
path: root/Semestr 3/pf/lista2
diff options
context:
space:
mode:
authorFranciszek Malinka <franciszek.malinka@gmail.com>2021-02-25 14:42:55 +0100
committerFranciszek Malinka <franciszek.malinka@gmail.com>2021-02-25 14:42:55 +0100
commit9477dbe667f250ecd23f8fc0d56b942191526421 (patch)
treea4b50c9a726f415f835f5311c11c5d66e95f688c /Semestr 3/pf/lista2
parent1968c1e590077bd51844eacfac722d7963848cb8 (diff)
Stare semestry, niepoukladane
Diffstat (limited to 'Semestr 3/pf/lista2')
-rw-r--r--Semestr 3/pf/lista2/__pycache__/pot.cpython-38.pycbin0 -> 370 bytes
-rw-r--r--Semestr 3/pf/lista2/czebin0 -> 17328 bytes
-rw-r--r--Semestr 3/pf/lista2/cze.cpp29
-rw-r--r--Semestr 3/pf/lista2/dwabin0 -> 17328 bytes
-rw-r--r--Semestr 3/pf/lista2/dwa.cpp22
-rw-r--r--Semestr 3/pf/lista2/n0
-rw-r--r--Semestr 3/pf/lista2/pot.py7
-rw-r--r--Semestr 3/pf/lista2/rozw.ml230
-rw-r--r--Semestr 3/pf/lista2/testbin0 -> 17352 bytes
-rw-r--r--Semestr 3/pf/lista2/test.cpp27
10 files changed, 315 insertions, 0 deletions
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
--- /dev/null
+++ b/Semestr 3/pf/lista2/__pycache__/pot.cpython-38.pyc
Binary files differ
diff --git a/Semestr 3/pf/lista2/cze b/Semestr 3/pf/lista2/cze
new file mode 100644
index 0000000..bce5101
--- /dev/null
+++ b/Semestr 3/pf/lista2/cze
Binary files 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 <iostream>
+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 b/Semestr 3/pf/lista2/dwa
new file mode 100644
index 0000000..f9db34d
--- /dev/null
+++ b/Semestr 3/pf/lista2/dwa
Binary files differ
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 <iostream>
+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/n b/Semestr 3/pf/lista2/n
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/Semestr 3/pf/lista2/n
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 b/Semestr 3/pf/lista2/test
new file mode 100644
index 0000000..1092aca
--- /dev/null
+++ b/Semestr 3/pf/lista2/test
Binary files differ
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 <iostream>
+
+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<tab[i]){
+ cout<<i<<" ";
+ j++;
+ }
+
+ }
+ return 0;
+} \ No newline at end of file