Статьи с тэгом «головоломки»

Немного теории

На собеседованиях по алгоритмам любят давать такую задачку, как нахождение чисел из последовательности Фибоначчи. Эта числовая последовательность названа в честь Леонардо Пизанского – известного математика Средневековья.

Сама последовательность довольно проста. Она состоит из целых положительных чисел, где каждый следующий элемент равен сумме двух предыдущих. Например, 2 = 1 + 1, 3 = 2 + 1, 5 = 3 + 2.

Последовательность начинается с 0 и 1:

Иногда в этой последовательности принято пропускать 0 и начинать её с двух единиц, однако официально она начинается именно с 0.

Двусвязный список – это структура данных, которая состоит из узлов, каждый из которых имеет ссылки на следующий и предыдущий элементы. Одна из часто используемых операций на двусвязных списках – это инверсия списка, то есть изменение порядка элементов на обратный.

Структура элемента

Класс Node, представляющий собой один элемент списка, выглядит следующим образом:

Римская система счисления – это система обозначений чисел, которая использовалась в Древнем Риме и до сих пор применяется в некоторых областях, таких как теория чисел, история и геральдика. В этой системе числа записываются с помощью комбинации символов, известных как римские цифры. В этой статье мы рассмотрим алгоритм записи римских цифр и основные правила, которые следует знать при работе с ними.

Давайте разберёмся, как можно вычислять арифметические выражения. Предположим, на вход нам поступает строка текста, которая содержит корректное арифметическое выражение.

Это выражение состоит из пробелов, чисел, скобок и знаков, обозначающих основные математические действия (плюс, минус, умножить, разделить). Нам нужно разобрать это выражение на отдельные элементы, а затем вычислить результат с учётом приоритетов математических операций. Например, умножение и деление должно выполняться раньше, чем сложение и вычитание. А часть выражения, заключённая в скобки, имеет приоритет над другими частями.

Обработку такого выражения можно разделить на три основных этапа:

1. Разбиение строки на отдельные части
2. Обработка этих частей с учётом математических операций
3. Само вычисление

Разберём каждую из этих частей подробнее.

Что такое системы счисления

В математике и программировании понятие системы счисления занимает очень важную роль. За столь умным названием кроется довольно простая идея. Система счисления – это способ записи (представления) чисел.

Иными словами, как записать любое сколь угодно большое число, имея в арсенале всего 10 цифр-символов? Правильно, комбинируя эти цифры друг с другом. Причём расположение цифры в записи числа имеет значение, ибо 123 не равно 321. Хотя цифры используются одинаковые.

Десятичная система счисления

В повседневной жизни мы используем десятичную систему счисления, хоть и не задумываемся над этим. Просто так исторически сложилось. Десятичной она называется потому что для записи любого числа используется ровно 10 цифр.

Обратите внимание, что любое число в десятичной записи можно разбить на слагаемые и степени числа 10. Например:

Однако помимо десятичной существуют другие системы счисления. И у каждой из них своя область применения.

Давайте рассмотрим алгоритм инвертирования массива. На вход нам подаётся массив произвольной длины и нужно поменять порядок следования его элементов на обратный. То есть сделать первый элемент последним, второй – предпоследним и т.д.

Для массива целых чисел реализация алгоритма на Java будет выглядеть так:

Метод invertArray() получает исходный массив в качестве параметра. Затем в цикле проходим по первой половине элементов и на каждой итерации меняем местами элемент с индексом i и элемент с таким же смещением, но с конца массива (array.length – i – 1). Чтобы обменять значения местами мы используем временную переменную.

Рассмотрим такую алгоритмическую задачу, как определение анаграмм. Реализацию такого алгоритма у вас могут спросить на собеседовании. Даны две строки и нужно определить, являются ли они анаграммами.

Одно слово является анаграммой другого, если второе слово получается из первого путём перестановки букв. Например, слово «фара» является анаграммой слова «арфа». Также «комар» является анаграммой слова «корма».

При этом если в слове встречается несколько одинаковых букв, то должно совпадать также их количество. Например, «каркас» и «краска» имеют по две буквы «а» и «к».

Давайте реализуем алгоритм поиска слов-палиндромов на Java.

Что такое палиндром

Для начала надо определиться, что же такое палиндром? Палиндром – это слово или строка текста, которая читается слева направо и справа налево одинаково. Например, палиндромами являются такие слова как «ага», «дед», «довод», «кабак», «мадам», «шалаш». В более широком смысле число «101» также является палиндромом.

Проверка слова

Давайте сначала рассмотрим более простой алгоритм, который на вход получает одно слово без пробелов. В случае, если данное слово палиндром – возвращаем true.

Ранее я уже приводил Алгоритм поиска простых чисел методом перебора делителей. Эта реализация хороша, если вам нужно ровно N первых простых чисел. Но если вы ищете простые числа в некотором диапазоне (скажем, не превосходящие 1 000 000), то лучше воспользоваться более быстрым алгоритмом, который называется «решето Эратосфена».

Среди алгоритмических задач довольно часто встречается задача на проверку скобочной последовательности. То есть на вход передаётся строка, в которой содержатся символы скобок и, возможно, другие символы. И нужно ответить, правильно ли скобки вложены друг в друга или нет? Иными словами, на каждую открывающую скобку должна приходиться закрывающая скобка.

Зачем нужно проверять вложенность скобок

Практическим применением этой задачи может быть калькулятор, в котором пользователь вводит выражение для вычисления целиком. Также без такой проверки не обойтись при реализации простейшего интерпретатора.

Первое, что приходит в голову, это подсчитать количество открывающих и количество закрывающих скобок в строке и если эти числа равны, то считать, что последовательность скобок правильная. Возможно, это и будет работать в самых простых случаях, однако последовательность «(())» будет правильной, а последовательность «())(» – неправильной. При этом количество открывающих и закрывающих скобок у них одинаковы. Кроме того, скобки могут быть разных типов (круглая, фигурная, квадратная и т.п.) и скобки должны соответствовать ещё и по типу. Поэтому в основе такой проверки должна лежать работа со стеком.