API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2017
91
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
StandardML 6.87 KB | None | 0 0
raw download clone embed print report
  1. Control.Print.printDepth := 100;
  2.  
  3. (*natural (Naravna števila definiramo tako: Obstaja ničla (ZERO).
  4. Vsako naravno število ima svojega naslednika (NEXT).
  5. -----------------------------------------------------------------
  6. Nič ni naslednik nobenega naravnega števila.
  7. Če sta dve števili enaki, sta enaka tudi njuna naslednika.) *)
  8.  
  9. datatype natural =
  10.     NEXT of natural
  11.     | ZERO
  12.  
  13. (*fun toInt(a: natural): int (vrne celoštevilsko (int) predstavitev naravnega števila)*)
  14.  
  15.  
  16.  
  17. fun toInt(a: natural): int =
  18.  
  19.     case a of
  20.         NEXT b => toInt(b) +1
  21.         | ZERO => 0
  22.  
  23. val test_toInt1 = 0 = toInt(ZERO);
  24. val test_toInt2 = 1 = toInt(NEXT(ZERO));
  25. val test_toInt3 = 12 = toInt(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))))))))));
  26.  
  27.  
  28. (*fun add(a: natural, b: natural): natural (vrne naravno število, ki ustreza vsoti števil a in b · deluje naj direktno na naravnih številih, brez pretvorbe v int)*)
  29. fun add(a: natural, b: natural): natural =
  30.     case a of
  31.         NEXT a => NEXT (add(b,a))
  32.         | ZERO =>  b
  33.  
  34. val test_add1 = ZERO = add(ZERO, ZERO);
  35. val test_add2 = NEXT(ZERO) = add(NEXT(ZERO), ZERO);
  36. val test_add3 = NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))) = add(NEXT(NEXT(NEXT(ZERO))), NEXT(NEXT(NEXT(ZERO))));
  37. val test_add4 = NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))))) = add(NEXT(NEXT(ZERO)), NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))));
  38. val test_add5 = NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))))) = add(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))), NEXT(NEXT(ZERO)));
  39. val test_add6 = NEXT(ZERO) = add(ZERO, NEXT(ZERO));
  40.  
  41.  
  42. (*----------------------------------------------------------------------------------------------------*)
  43. (* bstree (Binarno iskalno drevo definiramo tako: Obstaja prazno iskalno drevo (lf).
  44. Obstaja tudi veja (br), za katero poznamo vrednost elementa v njej ter obe poddrevesi (bstree * int * bstree).
  45. Za poddrevesi velja, da so vsi elementi znotraj levega poddrevesa (strogo) manjši od elementa v veji, vsi elementi desnega poddrevesa pa so (strogo) večji.
  46.  
  47. val tree = br (br (br (lf, 2, lf), 7, lf), 9, br (br (lf, 13, lf), 21, br (lf, 25, lf)))
  48. *)
  49.  
  50. datatype bstree =
  51.     br of bstree * int * bstree
  52.     | lf
  53.  
  54.      
  55. val tree = br (br (br (lf, 2, lf), 7, lf), 9, br (br (lf, 13, lf), 21, br (lf, 25, lf)));
  56.  
  57. (*fun min(tree: bstree): int option (vrne najmanjši element drevesa, če ta obstaja)*)
  58. fun min(tree: bstree): int option =
  59.         case tree of
  60.         br(left, i, _) => if(left = lf) then SOME i else min(left)
  61.         | lf => NONE
  62.        
  63.  
  64. val test_min1 = NONE = min(lf);
  65. val test_min2 = SOME 5 = min(br(lf, 5, lf));
  66. val test_min3 = SOME 2 = min(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))));
  67. val test_min4 = SOME(~3) = min(br(br(br(br(lf, ~3, lf), ~1, lf), 3, lf), 100, lf));
  68. val test_min5 = SOME 2 = min(br(br(lf, 2, lf), 5, lf));
  69.  
  70. (*fun max(tree: bstree): int option (vrne največji element drevesa, če ta obstaja)*)
  71. fun max(tree: bstree): int option =
  72.     case tree of
  73.             br(_, i, right) => if(right = lf) then SOME i else max(right)
  74.             | lf => NONE
  75.  
  76.  
  77. val test_max1 = NONE = max(lf);
  78. val test_max2 = SOME 5 = max(br(lf, 5, lf));
  79. val test_min3 = SOME 25 = max(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))));
  80. val test_max4 = SOME 100 = max(br(br(br(br(lf, ~3, lf), ~1, lf), 3, lf), 100, lf));
  81. val test_max5 = SOME 5 = max(br(br(lf, 2, lf), 5, lf));
  82.  
  83. (*fun contains(tree: bstree, x: int): bool (vrne true, če drevo vsebuje vejo s podano vrednostjo)*)
  84. fun contains(tree: bstree, x: int): bool =
  85.     case tree of
  86.         br(left, i, right) => if(x < i) then contains(left, x)
  87.                               else if(x > i) then contains(right, x)
  88.                               else true
  89.         | lf => false
  90.  
  91. val test_contains1 = false = contains(lf, 500)
  92. val test_contains2 = true = contains(br(lf, 5, lf), 5)
  93. val test_contains3 = true = contains(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))), 21)
  94. val test_contains4 = true = contains(br(br(br(br(lf, ~3, lf), ~1, lf), 3, lf), 100, lf), ~3)
  95. val test_contains5 = false = contains(br(lf, 5, br(lf, 6, lf)), 4)
  96. val test_contains6 = false = contains(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))), 3)
  97.  
  98. (*fun countLeaves(tree: bstree): int (vrne število listov (lf) v drevesu)*)
  99. fun countLeaves(tree: bstree): int =
  100.     case tree of
  101.         br(left, i, right) => countLeaves(left) + countLeaves(right)
  102.         | lf => 1
  103.  
  104.  
  105. val test_countLeaves1 = 1 = countLeaves(lf)
  106. val test_countLeaves2 = 2 = countLeaves(br(lf, 5, lf))
  107. val test_countLeaves3 = 7 = countLeaves(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))))
  108. val test_countLeaves4 = 5 = countLeaves(br(br(br(br(lf, ~2, lf), ~1, lf), 3, lf), 100, lf))
  109. val test_countLeaves5 = 3 = countLeaves(br(lf, 5, br(lf, 6, lf)))
  110.  
  111. (*fun countBranches(tree: bstree): int (vrne število vej (br) v drevesu)*)
  112.  
  113. fun countBranches(tree: bstree): int =
  114.     case tree of
  115.         br(left, i, right) => countBranches(left) + countBranches(right) +1
  116.         | lf => 0
  117.  
  118. val test_countBranches1 = 0 = countBranches(lf)
  119. val test_countBranches2 = 1 = countBranches(br(lf, 5, lf))
  120. val test_countBranches3 = 6 = countBranches(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))))
  121. val test_countBranches4 = 4 = countBranches(br(br(br(br(lf, ~2, lf), ~1, lf), 3, lf), 100, lf))
  122. val test_countBranches5 = 2 = countBranches(br(lf, 5, br(lf, 6, lf)))
  123.  
  124. (*fun toList(tree: bstree): int list (vrne seznam urejenih elementov podanega drevesa,
  125. v seznamu naj bo prvi element min(tree), zadnji pa max(tree)
  126. · za združevanje seznamov lahko uporabite operator @) *)
  127.  
  128. fun toList(tree: bstree): int list =
  129.     case tree of
  130.         br(left, i, right) => toList(left) @ [i] @ [] @ toList(right)
  131.         | lf => []
  132.  
  133. val test_toList1 = [] = toList(lf)
  134. val test_toList2 = [5] = toList(br(lf, 5, lf))
  135. val test_toList3 = [2,7,9,13,21,25] = toList(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))))
  136. val test_toList4 = [~2,~1,3,100] = toList(br(br(br(br(lf, ~2, lf), ~1, lf), 3, lf), 100, lf))
  137. val test_toList5 = [5,6] = toList(br(lf, 5, br(lf, 6, lf)))
  138.  
  139. (* fun valid(tree: bstree): bool (vrne true, če je podano drevo veljavno binarno iskalno drevo (glej definicijo zgoraj))*)
  140. fun pridobi(tree: bstree): int =
  141.     case tree of
  142.         br(_,i,_) => i
  143.         | lf => 0
  144.  
  145.  
  146. fun valid(tree: bstree): bool =
  147.     case tree of              
  148.         br(left, i, right) =>
  149.             if(pridobi(left) >= i andalso i >= pridobi(right)) then false
  150.             else valid(left) andalso valid(right)
  151.         | lf => true
  152.  
  153. val test_valid1 = true = valid(lf)
  154. val test_valid2 = true = valid(br(lf, 5, lf))
  155. val test_valid3 = true = valid(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))))
  156. val test_valid5 = true = valid(br(lf, 5, br(lf, 6, lf)))
  157. val test_valid4 = false = valid(br(br(br(br(lf, ~3, lf), ~1, lf), 3, lf), 0, lf))
  158. val test_valid6 = false = valid(br(br(br(lf, 6, lf), 3, lf), 5, lf))
  159. val test_valid7 = false = valid(br(br(br(lf, 3, lf), 3, lf), 3, lf))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!