Ассоциативные алгебры

kukina_eg


Задачи и незадачи


Previous Entry Share Next Entry
Задачи про алгоритмы
Ассоциативные алгебры
kukina_eg
Готовила для спецкурса подборку задачек про придумывание алгоритмов и про сложности алгоритмов. Решила сохранить тут, пусть валяются.

0. Определить сложность метода Гаусса для решения системы линейных уравнений из n уравнений и k неизвестных.

1. Посчитать, сколько различных чисел в массиве. Усложнение: памяти О(1). Следующее усложнение: нельзя портить массив.

2. Определить, является ли массив длины n перестановкой чисел от 1 до n. Усложнение: памяти О(1), времени О(n).

3. В множестве из n человек каждый может знать или не знать другого (из того, что А знает Б не следует, что Б знает А). Все знакомства заданы булевой матрицей nxn. В этом множестве может найтись Знаменитость: человек, которого все знают, но который сам не знает никого. Предложите алгоритм, который искал бы Знаменитость, или говорил бы, что ее нет. Усложениние: памяти О(1), времени О(n).

4. Дан массив длины n из нулей и единиц. Предложите алгоритм нахождения подмассива максимальной длины, в котором количество единиц равно количеству нулей.

5. На вход подают поток чисел. Поскольку памяти всего О(1), каждое число можно обрабатывать только один раз. Про поток заранее известно, что он из n чисел, причем одно из чисел встречается больше, чем n/2 раз. Предложите алгоритм нахождения этого популярного числа.

6. В массиве из 2n+1 числа n пар одинаковых элементов и еще один элемент без пары. Найти непарный элемент. Усложнение: О(n) времени, О(1) памяти.

Задачи без решения специально. Некоторые решения встречаются в других постах этого же жж.

?

Log in