SHARE
TWEET

Untitled

a guest May 25th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package exercises
  2.  
  3. object Exercise {
  4.  
  5.   // 0. Вам нужно реализовать ADT дерева. Трейт для декомпозиции: Derevo. Наследники: Listok и Vetka.
  6.  
  7.   // 1 Вам нужно реализовать вспомогательный конструктор для тестов.
  8.   // 2. Напишите функцию вычисления размера, которая подсчитывает количество узлов (листьев и ветвей) в дереве.
  9.   // 3. Напишите функцию вычисления максимума, которая возвращает максимальный элемент в дереве(тип [Int]).
  10.   // 4. Напишите функцию вычисления глубины, которая возвращает максимальную длину пути от корня дерева до любого листа.
  11.   // 5. Напишите функцию map, которая изменяет сопоставляет каждый элемент дерева с заданной функцией.
  12.  
  13.   // 6. Напишите функцию вычисления размера(sizeF), которая подсчитывает количество узлов (листьев и ветвей)
  14.   // в дереве через fold.
  15.   // 7. Напишите функцию вычисления максимума(maximumF), которая возвращает максимальный элемент в дереве [Int]. (Заметка:
  16.   //В Scala вы можете использовать x.max (y) или x max y, чтобы вычислить максимум двух целых чисел x
  17.   //и у.) через fold
  18.   // 8. Напишите функцию вычисления глубины (depthF), которая возвращает максимальную длину пути от корня
  19.   // дерева до любого листа через fold
  20.   // 9. Напишите функцию mapF, которая изменяет сопоставляет каждый элемент дерева с заданной функцией через fold.
  21.  
  22.   //Подсказка
  23.   //Вы можете использовать x.max (y) или x max y, чтобы вычислить максимум двух целых чисел x и у.
  24.  
  25.   trait Derevo[A]
  26.  
  27.   case class Vetka[A](lft: Derevo[A], rgt: Derevo[A]) extends Derevo[A]
  28.  
  29.   case class Listok[A](a: A) extends Derevo[A]
  30.  
  31.   object Derevo {
  32.     def vetka[A](lft: Derevo[A], rgt: Derevo[A]): Derevo[A] = Vetka[A](lft, rgt)
  33.  
  34.     def listok[A](a: A): Derevo[A] = Listok[A](a)
  35.   }
  36.  
  37.   def size[A](t: Derevo[A]): Int = t match {
  38.     case t: Listok[A] => 1
  39.     case t: Vetka[A] => size(t.lft) + size(t.rgt)
  40.   }
  41.  
  42.   def maximum(t: Derevo[Int]): Int = t match {
  43.     case t: Listok[Int] => t.a
  44.     case t: Vetka[Int] => math.max(maximum(t.lft), maximum(t.rgt))
  45.   }
  46.  
  47.   def depth[A](t: Derevo[A]): Int = t match {
  48.     case t: Vetka[A] => math.max(depth(t.lft) + 1, depth(t.rgt) + 1)
  49.     case t: Listok[A] => 1
  50.   }
  51.  
  52.   def map[A, B](t: Derevo[A])(f: A => B): Derevo[B] = t match {
  53.     case t: Listok[A] => Listok(f(t.a))
  54.     case t: Vetka[A] => Vetka(map(t.lft)(f), map(t.rgt)(f))
  55.   }
  56.  
  57.   def fold[A, B](t: Derevo[A])(f: A => B)(g: (B, B) => B): B = t match {
  58.     case t: Listok[A] => f(t.a)
  59.     case t: Vetka[A] => g(fold(t.lft)(f)(g), fold(t.rgt)(f)(g))
  60.   }
  61.  
  62.   def depthF[A](t: Derevo[A]): Int = t match {
  63.     case t: Vetka[A] => fold(t)((m: A) => 1)((m: Int, n: Int) => (m max n) + 1)
  64.     case t: Listok[A] => 1
  65.   }
  66.  
  67.   def sizeF[A](t: Derevo[A]): Int = t match {
  68.     case t: Listok[A] => 1
  69.     case t: Vetka[A] => fold(t)((m: A) => 1)((m: Int, n: Int) => m + n)
  70.   }
  71.  
  72.   def maximumF(t: Derevo[Int]): Int = t match {
  73.     case t: Listok[Int] => t.a
  74.     case t: Vetka[Int] => fold(t)((m: Int) => m)((m: Int, n: Int) => m max n)
  75.   }
  76.  
  77.   def mapF[A, B](t: Derevo[A])(f: A => B): Derevo[B] = {
  78.     fold(t)(a => Listok(f(a)): Derevo[B])((left, right) => Vetka(left, right))
  79.   }
  80. }
RAW Paste Data
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
 
Top