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