среда, 1 августа 2012 г.

core-labs: procedural


Процедурная Java

     Итерация (циклы)
    - proc.loop.array_inverter_optimized (на GolovachCourses.com)
    - proc.loop.array_merger_fixed (на GolovachCourses.com)
    - proc.loop.bubble_sort_inverted (на GolovachCourses.com)
    - proc.loop.selection_sort_optimized (на GolovachCourses.com)
    - proc.loop.insertion_sort_optimized (на GolovachCourses.com)
    - proc.loop.matrix_mul (на GolovachCourses.com)

     Рекурсия
    - proc.recursion.hanoi_tower (на GolovachCourses.com)
    - proc.recursion.permutation (на GolovachCourses.com)
    - proc.recursion.parser (на GolovachCourses.com)

    Динамические структуры данных
    - proc.dyn.1_single_lib
    - proc.dyn.2_single_lib
    - proc.dyn.3_tree_lib
    - proc.dyn.4_double_lib
    - proc.dyn.5_fibonacci_tree


    Динамические структуры данных
  proc.dyn.1_single_lib (обязательно) (обязательно)
    Разработать класс-библиотеку для работы с односвязными списками. А именно 3 метода:


public class SingleLLUtils_1 {



    public static int length(Node tail) {...}



    public static int max(Node tail) {...}



    public static int sum(Node tail) {...}



}

    Используйте любой или все вместе подходы при решения задачи (итеративный, рекурсивные, в любом направлении).

    proc.dyn.2_single_lib (обязательно) (обязательно)
    Разработать класс-библиотеку для работы с односвязными списками. А именно 4 метода из DynamicArray:

public class SingleLLUtils_2 {



    public static Node add(Node tail, int elem) {...}



    public static Node remove(Node tail) {...}



    public static Node add(Node tail, int index, int elem) {...}



    public static Node remove(Node tail, int index) {...}



}
    Используйте любой или все вместе подходы при решения задачи (итеративный, рекурсивные, в любом направлении).
    proc.dyn.3_tree_lib
    Разработать класс-библиотеку для работы с бинарными деревьями. А именно 4 метода:

public class BinaryTreeUtils {



    public static int size(TreeNode root) {...}



    public static int height(TreeNode root) {...}



    public static int sum(TreeNode root) {...}



    public static int max(TreeNode root) {...}



}
    для класса
public class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

    Используйте любой или все вместе подходы при решения задачи (итеративный, рекурсивные, в любом направлении).

    Примечание: почти так и устроен java.util.TreeMap. Добавляется поддержка "сбалансированности": в отличии от нашего дерева, TreeMap не вырождается в односвязный список (структура данных TreeMap называется Красно-Черное дерево). 



    proc.dyn.4_double_lib
    Разработать класс-библиотеку для работы с двусвязными списками. А именно 4 метода из DynamicArray:


public class SingleLLUtils_2 {



    public static DoubleNode add(DoubleNode tail, int elem) {...}



    public static DoubleNode remove(DoubleNode tail) {...}



    public static DoubleNode add(DoubleNode tail, int index, int elem) {...}



    public static DoubleNode remove(DoubleNode tail, int index) {...}



}
 для класса
public class DoubleNode { 
    public int value;
    public DoubleNode prev;
    public DoubleNode next;
    public DoubleNode(int value, DoubleNode left, DoubleNode right)
        this.value = value;
        this.prev = prev;
        this.next = next;
    }
}      
    Используйте любой или все вместе подходы при решения задачи (итеративный, рекурсивные, в любом направлении).
    Примечание: теперь надо модифицировать две ссылки, а не одну (как у односвязных списков).



    proc.dyn.5_fibonacci_tree
    Разработать класс-библиотеку для генерации бинарного дерева, соответствующего по форме истории рекурсивного вычисления числа Фибоначчи. А именно 2 метода:

 

public class FibonacciTreeUtils{



    public static TreeNode generateArg(int k) {...}



    public static TreeNode generateRes(int k) {...}



}

    generateArg() - в качестве value ставит номер числа Фибоначчи (аргумент, по которому вычисляют число Фибоначчи):
generateArg(3) = 
        1
      /
    2
   /  \
  /    0
3
  \
   1

     generateRes() - в качестве value ставит значение числа Фибоначчи.
generateArg(3) = 
       1
      /
    1
   /  \
  /    0
2
  \
    1

    Вспомогательный метод для визуализации бинарного дерева:

 
public class TreeVisualizer {
    public static void main(String[] args) {
        print(FibonacciTreeGenerator.generateArg(3), 0);
        System.out.println("-------");
        print(FibonacciTreeGenerator.generateRes(3), 0);
    }

    private static void print(TreeNode root, int depth) {
        if (root != null) {
            print(root.right, depth + 1);
            for (int k = 0; k < depth; k++) {
                System.out.print("   ");
            }
            System.out.println(root.value);
            print(root.left, depth + 1);
        }
    }
}

>>>      1
>>>   2
>>>      0
>>>3
>>>   1
>>>-------
>>>      1
>>>   1
>>>      0
>>>2
>>>   1
Автор: