← All posts tagged CS

GunnerKade
? CS Как перевести Computer scientist?
Есть же геолог, математик, физик, орнитолог и прочие. Не информатик, а то звучит как электроник. Вобщем, нужно придумать красивое слово и продвигать в массы, чтобы закрепилось в умах.
GunnerKade
CS Намедни проходил тест Алгоритмы — Основы quizful.net . Попался такой вопрос: какой алгоритм сортировки является фактически худшим?
1) Блинная сортировка
2) Пузырьковая сортировка
3) Bogosort
4) Глупая сортировка
Из перечисленных знал только пузырьковую. Помогла Википедия. Каждая сортировка по-своему примечательна.
Глупая сортировка самая простая, заключается в том, чтобы удалять первую встретившуюся в массиве инверсию, до тех пор пока есть хотя бы одна инверсия (похоже на пузырьковую кроме того, что поиск инверсии начинается каждый раз с начала массива).
Блинная сортировка знакома каждому, кто имел дело с горкой разновеликих блинов (толстых, как в американских фильмах), которую надо отсортировать в пирамиду — от самого большого блина к наименьшему, используя при этом только перевороты некоторого числа верхних блинов. ru.wikipedia.org — с ней связано много чего интересного — задача нахождения минимального числа переворотов и ее решение биологическим компьютером.
Bogosort — это ответ на вопрос и одна из самых тупых сортировок — рандомно мешаем массив чисел до тех пор, пока он не отсортируется. Как посадить обезьян за печатные машинки и ждать, когда они напишут Гамлета.
Вобщем, так я и не понял, что этот вопрос делает в тесте.
GunnerKade
CS math algo У алгоритма Евклида нахождения НОД натуральных чисел X и Y, есть замечательная геометрическая интерпретация. Пусть дан прямоугольник размерами X на Y, тогда если последовательно отрезать от него квадраты максимально возможного размера, то в итоге останется квадрат размером НОД(X,Y).
Если бы мне в школе дали такую интерпретацию алгоритма, я бы надолго его запомнил.
Такой алгоритм с отсечением квадратов будет конечным для любого исходного прямоугольника с рациональными длинами сторон. Если же длины сторон заданы рациональным и иррациональным числом, то алгоритм никогда не завершится.
Если взять стороны в отношении 1 : 1.618 ( золотое сечение, 1 : \frac{1+\sqrt{5}}{2} ), разрезать этот прямоугольник согласно описанному алгоритму, при этом проводя в каждом квадрате по четверти окружности, то в итоге все эти дуги соединятся в кривую — спираль Архимеда. dl.dropbox.com
Кстати, впервые такой способ начертания спирали Архимеда я увидел в фильме Pi, что произвело на меня впечатление. Разумеется, можно начертить спираль для прямоугольника с любым другим соотношением сторон, однако, она не будет такой же однородной как спираль Архимеда.
GunnerKade
Erlang CS olymp В продолжение вопроса о косвенной рекурсии (#790719). Нашел задачу, которую без такой рекурсии было бы весьма проблематично решить. Собственно задача:
"Строка состоит из клеток, пронумерованных от 1 до n. Состояние клетки можно изменить — если она пуста, поставить в нее шашку (занять ее), иначе убрать из нее шашку (освободить ее). Вначале строка пуста. Нужно занять все клетки, соблюдая следующее правило. Изменение клетки допустимо, если она имеет номер 1 или расположена непосредственно после занятой клетки, имеющей минимальный номер среди занятых клеток."
На входе целое n, на выходе — последовательность состояний строки клеток от начального — [0,0,...,0], когда все клетки свободны, до конечного [1,1,...,1] — все заняты.
Выражаем друг через друга такие подзадачи, как
1) добавление единицы в конец последовательности единиц ([1,1,1,0] -> [1,1,1,1]) ;
2) обратная операция — удаление единицы ([1,1,1,1] -> [1,1,1,0]) ;
3) получение последовательности единиц из последовательности нулей ([0,0,0,0] -> [1,1,1,1]) ;
4) подзадача 3) наоборот ([1,1,1,1] -> [0,0,0,0]).
В итоге получаем то, что нужно.
Задача взята из книги ozon.ru (стр. 83). Решение там предложено слегка другое, но мне нравится мое из-за его симметричности. Код на эрланге pastebin.com
Осталось найти реальное применение двойной рекурсии.
GunnerKade
? CS Жуйк, возникала ли у тебя когда-нибудь необходимость в рекурсии вида:
foo()
{
....
bar();
....
}
bar()
{
....
foo();
....
}
И если возникала, то в связи с какими задачами?