Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
iakovlev.org

Алгоритмы - Рекурсия, сортировка

В этой статье я использовал материалы с персонального блога Владимира Васильева. Он живет в Красноярске и работает в Сибирском федеральном университете.
Его блог можно найти по адресу: https://pro-prof.com/
С его любезного разрешения здесь будут представлены материалы из раздела Алгоритмы:
1. Алгоритм. Свойства алгоритма
2. Рекурсия в программировании. Анализ алгоритмов

В первой статье Владимир рассматривает такие общие вопросы, как определение понятия Алгоритм, свойства алгоритмов. Алгоритмы обладают следующими свойствами:
дискретность
детерминированность
результативность
массовость
правильность.

В качестве примера рассмотрен пример синтаксического анализа корректности расстановки скобок.
Это классическая задача, которую часто задают на собеседовании для программистов самого различного уровня. Она может иметь различные вариации, в условии задачи может быть сказано, что скобки только круглые, но может быть задача с тремя типами скобок - круглыми, квадратными и фигурными.
В этой задаче нет одного универсального решения. Существует рекурсивный вариант решения задачи, существует вариант решения с использованием стека и т.д.
Примеры правильных скобочных последовательностей:
((()()()()))
()[()]{()()[]}


Один из вариантов решения:
Пусть нам дана скобочная последовательность, записанная в строку S. Возьмем переменную 𝚌𝚘𝚞𝚗𝚝𝚎𝚛. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем 𝚌𝚘𝚞𝚗𝚝𝚎𝚛 на 1, закрывающую — уменьшаем на 1. Если на протяжении всего перебора 𝚌𝚘𝚞𝚗𝚝𝚎𝚛 было неотрицательным (не встречалось закрывающих скобок, для которых не было соответствующих открывающих) и после завершения осталось нулем (все открывающие скобки закрыты, при этом нет лишних закрытых скобок), то скобочная последовательность правильна. Псевдокод
 
 boolean check(s: string):
    counter = 0
    for i = 1 to length(s)
      if s[i] == '('
        counter++
      else
        counter-- 
      if counter < 0
        return false 
    return counter == 0
 
 
Похожий алгоритм можно реализовать с помощью стека: Идем по строке и помещаем в стек левые скобки. Когда скобка правая, извлекаем из стека последнюю левую и смотрим, соответствует ли она текущей правой. Код для трех типов скобок на питоне:
 
 def isBalanced(expr):
     if len(expr)%2!=0:
         return False
     opening=set('([{')
     match=set([ ('(',')'), ('[',']'), ('{','}') ])
     stack=[]
     for char in expr:
         if char in opening:
             stack.append(char)
         else:
             if len(stack)==0:
                 return False
             lastOpen=stack.pop()
             if (lastOpen, char) not in match:
                 return False
     return len(stack)==0
 
 print isBalanced('({[}}((}')
 print isBalanced('({[]()(())})')
 
 
Тот же алгоритм на go :
 
 package main
 
 import (
 	"bufio"
 	"fmt"
 	"os"
 	"strings"
 )
 
 func isBalanced(input string) string {
 
 	if len(input) > 0 {
 		var stack []byte
 		for i := 0; i < len(input); i++ {
 			if input[i] == '(' || input[i] == '{' || input[i] == '[' {
 				stack = append(stack, input[i])
 			} else {
 				if len(stack) > 0 {
 					pair := string(stack[len(stack)-1]) + string(input[i])
 					stack = stack[:len(stack)-1]
 
 					if pair != "[]" && pair != "{}" && pair != "()" {
 						return input + " is not balanced."
 					}
 				} else {
 					return input + " is not balanced."
 				}
 			}
 		}
 		if len(stack) == 0 {
 			return input + " is balanced."
 		}
 	}
 	return "Please enter a sequence of brackets."
 }
 
 func main() {
 	reader := bufio.NewReader(os.Stdin)
 	fmt.Print("Enter sequence of brackets: ")
 	text, _ := reader.ReadString('\n')
 
 	text = strings.TrimSpace(text)
 	fmt.Println(isBalanced(text))
 }
 
 
Тот же алгоритм на си:
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <assert.h>
 
 #define SIZE 100
 
 struct node
 {
     char data;
     struct node *link;
 };
 
 int c = 0;         // c used as counter to check if stack is empty or not
 struct node *head; //declaring head pointer globally assigned to NULL
 
 void push(char x) //function for pushing
 {
     struct node *p = head, *temp;
     temp = (struct node *)malloc(sizeof(struct node));
     temp->data = x;
     if (head == NULL) //will be execute only one time i.e, 1st time push is called
     {
         head = temp;
         p = head;
         p->link = NULL;
         c++;
     }
     else
     {
         temp->link = p;
         p = temp;
         head = p;
         c++;
     }
 }
 
 char pop(void) //function for pop
 {
     char x;
     struct node *p = head;
     x = p->data;
     head = p->link;
     free(p);
     c--;
     return x;
 }
 
 int isBalanced(char *s)
 {
     int i = 0;
     char x;
     while (s[i] != '\0') //loop for covering entire string of brackets
     {
         // printf("\t s[i]=%c\n", s[i]); //DEBUG
         if (s[i] == '{' || s[i] == '(' || s[i] == '[') //if opening bracket then push
             push(s[i]);
         else
         {
             if (c <= 0) //i.e, stack is empty as only opening brackets are added to stack
                 return 0;
 
             x = pop();
             if (x == '{' && s[i] != '}')
                 return 0;
             if (x == '[' && s[i] != ']')
                 return 0;
             if (x == '(' && s[i] != ')')
                 return 0;
         }
         i++;
     }
 
     //at end if stack is empy which means whole process has been performed correctly so return 1
     return (c == 0) ? 1 : 0;
 }
 
 void destroyStack(void)
 {
     struct node *p = head;
     if (c > 0)
     {
         while (p->link)
         {
             struct node *tmp = p;
             p = p->link;
             free(tmp);
         }
 
         c = 0;
     }
 }
 
 int main(void)
 {
     int t;
     printf("\t\tBalanced parenthesis\n\n");
     printf("\nPlease enter the number of processing rounds? ");
     scanf("%d", &t);
     for (int a0 = 0; a0 < t; a0++)
     {
         char s[SIZE];
         printf("\nPlease enter the expression? ");
         scanf("%s", s);
 
         if (isBalanced(s))
             printf("\nYES\n");
         else
             printf("\nNO\n");
 
         /* tidy up stack for new round */
         destroyStack();
     }
     return 0;
 }
 
 
 
Во второй статье рассматривается рекурсия. Она применяется в таких структурах данных, как связные списки, деревья, графы.
Рекурсию можно применить для вычисления чисел Фибоначчи. Числа Фибоначчи вычисляются по следующему правилу:
F0=0
F1=1
Fn=Fn-1 + Fn-2

Код на питоне:
 
 def fib_recursive(n):
     if n <= 1:
         return n
     else:
         return fib_recursive(n-1) + fib_recursive(n-2)
 
 fib_recursive(10)
 
 
Код на go:
 
 package main
 import "fmt"
 
 //using recursion
 func fibo(num int) int {
   if num <= 1 {
     return num
   }
   return fibo(num -1) + fibo(num - 2)
 }
 
 func main(){
   num := 10
   result := fibo(num)
   fmt.Println(result)
 }
 
 
 
Ко на си:
 
 #include <stdio.h> 
 int fibonacci(int n) 
 { 
 if (n==1||n==0)
 	return n; 
 return fibonacci(n-1) + fibonacci(n-2); 
 } 
 
 int main () 
 { 
   int n;
   printf("Enter the number");
   scanf("%d",&n); 
   printf("Fibonacci number of %d : %d", n, fibonacci(n)); 
   return 0; 
 }
 
 
Рекурсивные алгоритмы могут применяться при сортировке массивов. Массив разбивается на более мелкие части до тех пор, пока обработка частей не становится элементарной.
В статье рассматриваются два варианта сортировки - быстрая (quick sort) и слиянием (merge sort).
Быстрая сортировка — один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы O(n * logn), что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из n элементов в худшем случае может составить O(n2), на практике этот алгоритм является одним из самых быстрых.

Быстрая сортировка не требует дополнительной памяти.
Алгоритм следующий:
Берется случайное число посередине массива и делается опорным. Берем два указателя - слева и справа, движемся навстречу. Слева ищем число большее опорного, слева меньшее. Как нашли - меняем их местами. Опять ставим указатели на начало и конец и повторяем процесс. В конце слева от опорного окажутся числа меньшие, справа большие (но пока еще неотсортированные). Далее рекурсивно повторяем процедуру сначала для левой половины, потом для правой, и рекурсия будет продолжаться до тех пор, пока размер подмассива не станет равным двум элементам.

Код на питоне:
 
 def quick_sort(data):
     left = []
     List = []
     right = []
     if len(data) <= 1:
         return data
     else:
         d = data[0]
         for i in data:
             if i < d:
                 left.append(i)
             elif i > d:
                 right.append(i)
             else:
                 List.append(i)
         left = quick_sort(left)
         right = quick_sort(right)
         return left + List + right
 
 print quick_sort([1,9,4,7,2,55,8,33,456,2,11])
 >> [1, 2, 2, 4, 7, 8, 9, 11, 33, 55, 456]
 
 
Код на go:
 
 package main
 
 import (
     "math/rand"
     "fmt"
 )
 
 func quick_sort(arr []int) []int {
     
     if len(arr) <= 1 {
         return arr
     }
  
     median := arr[rand.Intn(len(arr))]
     
     low_part := make([]int, 0, len(arr))
     high_part := make([]int, 0, len(arr))
     middle_part := make([]int, 0, len(arr))
  
     for _, item := range arr {
         switch {
         case item < median:
             low_part = append(low_part, item)
         case item == median:
             middle_part = append(middle_part, item)
         case item > median:
             high_part = append(high_part, item)
         }
     }
  
     low_part = quick_sort(low_part)
     high_part = quick_sort(high_part)
 
     low_part = append(low_part, middle_part...)
     low_part = append(low_part, high_part...)
  
     return low_part
 }
 
 func main() {
     arr := []int{1,9,4,7,2,55,8,33,456,2,11}
     fmt.Println("Sorted array is: ", quick_sort(arr))
 }
 
 
Код на си:
 
 #include <stdio.h> 
   
 // A utility function to swap two elements 
 void swap(int* a, int* b) 
 { 
     int t = *a; 
     *a = *b; 
     *b = t; 
 } 
   
 /* This function takes last element as pivot, places 
    the pivot element at its correct position in sorted 
     array, and places all smaller (smaller than pivot) 
    to left of pivot and all greater elements to right 
    of pivot */
 int partition (int arr[], int low, int high) 
 { 
     int pivot = arr[high];    // pivot 
     int i = (low - 1);  // Index of smaller element 
   
     for (int j = low; j <= high- 1; j++) 
     { 
         // If current element is smaller than or 
         // equal to pivot 
         if (arr[j] <= pivot) 
         { 
             i++;    // increment index of smaller element 
             swap(&arr[i], &arr[j]); 
         } 
     } 
     swap(&arr[i + 1], &arr[high]); 
     return (i + 1); 
 } 
   
 /* The main function that implements QuickSort 
  arr[] --> Array to be sorted, 
   low  --> Starting index, 
   high  --> Ending index */
 void quickSort(int arr[], int low, int high) 
 { 
     if (low < high) 
     { 
         /* pi is partitioning index, arr[p] is now 
            at right place */
         int pi = partition(arr, low, high); 
   
         // Separately sort elements before 
         // partition and after partition 
         quickSort(arr, low, pi - 1); 
         quickSort(arr, pi + 1, high); 
     } 
 } 
   
 /* Function to print an array */
 void printArray(int arr[], int size) 
 { 
     int i; 
     for (i=0; i < size; i++) 
         printf("%d ", arr[i]); 
     printf("n"); 
 } 
   
 int main() 
 { 
     int arr[] = {1,9,4,7,2,55,8,33,456,2,11};
     int n = sizeof(arr)/sizeof(arr[0]); 
     quickSort(arr, 0, n-1); 
     printf("Sorted array: n"); 
     printArray(arr, n); 
     return 0; 
 } 
 
 
Cортировка слиянием требует дополнительной памяти, равной размеру сортируемого массива, время работы - n * log(n) По сравнению с быстрой сортировкой недостаток в том, что требуется дополнительная память, в который мы пишем результирующий массив
Рекурсивный алгоритм состоит из двух частей:
1 Рекурсивное разбиение : Исходный массив разбивается на пары, каждая пара сортируется
2 Слияние : Пары сливаются в четверки
Затем четверки сливаются в восьмерки и т.д.
Код на питоне:
 
 def merge(left, right):  
     sorted_list = []
     i_left = i_right = 0
 
     # Длина списков часто используется, поэтому создадим переменные для удобства
     left_list_length, right_list_length = len(left), len(right)
 
     for _ in range(left_list_length + right_list_length):
         if i_left < left_list_length and i_right < right_list_length:
             # Сравниваем первые элементы в начале каждого списка
             # Если первый элемент левого подсписка меньше, добавляем его
             # в отсортированный массив
             if left[i_left] <= right[i_right]:
                 sorted_list.append(left[i_left])
                 i_left += 1
             # Если первый элемент правого подсписка меньше, добавляем его
             # в отсортированный массив
             else:
                 sorted_list.append(right[i_right])
                 i_right += 1
 
         # Дальше идет необязательная часть, ее можно на собеседовании пропустить 
         # Если достигнут конец левого списка, элементы правого списка
         # добавляем в конец результирующего списка
         elif i_left == left_list_length:
             sorted_list.append(right[i_right])
             i_right += 1
         # Если достигнут конец правого списка, элементы левого списка
         # добавляем в отсортированный массив
         elif i_right == right_list_length:
             sorted_list.append(left[i_left])
             i_left += 1
 
     return sorted_list
 
 def merge_sort(nums):  
     # Возвращаем список, если он состоит из одного элемента
     if len(nums) <= 1:
         return nums
 
     # Для того чтобы найти середину списка, используем деление без остатка
     # Индексы должны быть integer
     mid = len(nums) // 2
 
     # Сортируем и объединяем подсписки
     left  = merge_sort(nums[:mid])
     right = merge_sort(nums[mid:])
 
     # Объединяем отсортированные списки в результирующий
     return merge(left, right)
 
 list = [120, 45, 68, 250, 176]  
 res = merge_sort(list)  
 print(res)
 >> [45, 68, 120, 176, 250]
 
 
Код на go:
 
 package main
 
 func Merge(left, right []int) []int {
     result := make([]int, 0, len(left) + len(right))
     
     for len(left) > 0 || len(right) > 0 {
         if len(left) == 0 {
             return append(result, right...)
         }
         if len(right) == 0 {
             return append(result, left...)
         }
         if left[0] <= right[0] {
             result = append(result, left[0])
             left = left[1:]
         } else {
             result = append(result, right[0])
             right = right[1:]
         }
     }
     
     return result
 }
 
 func MergeSort(arr []int) []int {
     if len(arr) <= 1 {
         return arr
     }
     
     middle := len(arr) / 2
     
     left := MergeSort(arr[:middle])
     right := MergeSort(arr[middle:])
     
     return Merge(left, right)
 }
 
 
Код на си:
 
 #include <stdlib.h>
 #include <stdio.h>
 
 // Merge the two half into a sorted data.
 void merge(int arr[], int l, int m, int r)
 {
     int i, j, k;
     int n1 = m - l + 1;
     int n2 =  r - m;
 
     /* create temp arrays */
     int L[n1], R[n2];
 
     /* Copy data to temp arrays L[] and R[] */
     for (i = 0; i < n1; i++)
         L[i] = arr[l + i];
     for (j = 0; j < n2; j++)
         R[j] = arr[m + 1+ j];
 
     /* Merge the temp arrays back into arr[l..r]*/
     i = 0; // Initial index of first subarray
     j = 0; // Initial index of second subarray
     k = l; // Initial index of merged subarray
     while (i < n1 && j < n2)
     {
         if (L[i] <= R[j])
         {
             arr[k] = L[i];
             i++;
         }
         else
         {
             arr[k] = R[j];
             j++;
         }
         k++;
     }
 
     /* Copy the remaining elements of L[], if there
        are any */
     while (i < n1)
     {
         arr[k] = L[i];
         i++;
         k++;
     }
 
     /* Copy the remaining elements of R[], if there
        are any */
     while (j < n2)
     {
         arr[k] = R[j];
         j++;
         k++;
     }
 }
 
 /* l is for left index and r is right index of the
    sub-array of arr to be sorted */
 void mergeSort(int arr[], int l, int r)
 {
     if (l < r)
     {
         // Same as (l+r)/2, but avoids overflow for
         // large l and h
         int m = l+(r-l)/2;
 
         // Sort first and second halves
         mergeSort(arr, l, m);
         mergeSort(arr, m+1, r);
 
         merge(arr, l, m, r);
     }
 }
 
 void printArray(int A[], int size)
 {
     int i;
     for (i=0; i < size; i++)
         printf("%d ", A[i]);
     printf("\n");
 }
 
 int main()
 {
     int arr[] = {12, 11, 13, 5, 6, 7};
     int arr_size = sizeof(arr)/sizeof(arr[0]);
 
     printf("Given array is \n");
     printArray(arr, arr_size);
 
     mergeSort(arr, 0, arr_size - 1);
 
     printf("\nSorted array is \n");
     printArray(arr, arr_size);
     return 0;
 }
 
 
В статье дается строгое математическое обоснование сложности основных алгоритмов:
Сложность поиска элемента в неотсортированном массиве - O(n)
Сложность бинарного поиска - O(log(n))
Сложность сортировки слиянием - O(n * log(n))
Сложность быстрой сортировки - O(n * log(n))

Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье