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

Задача 1. Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.

Сразу поясню. В условии не говорится, что каждое число от 1 до n встречается в массиве, поэтому повторяющихся элементов там может быть сколько угодно (если бы все числа входили по разу, а одно — дважды, то задача была бы гораздо проще). Ограничение на использование дополнительной памяти означает, что нельзя заводить дополнительный массив линейной длины, но можно заводить переменные.

Задача 2. Дана матрица nxn, содержащая попарно различные натуральные числа. Требуется найти в ней локальный минимум за время O(n).

Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.

Под катом — решение первой задачи. Ещё раз призываю вас заглядывать под кат только после того, как порешаете задачу. По второй задаче могу какую-нибудь подсказку сказать.

Иллюстрированная проекция модели сетевого взаимодействия OSI на универсальную последовательную шину.

Три «замечательных» уровня стека USB

Меня не устроил вид стека USB, который можно встретить чаще всего на просторах сети:


Уровень шины, логический, функциональный… Это, конечно, замечательные абстракции, но они скорее для тех, кто собирается делать драйвер или прикладной софт для хоста. На стороне же микроконтроллера я ожидаю шаблонный конечный автомат, в узлы которого мы обычно встраиваем свой полезный код, и он сперва будет по всем законам жанра глючить. Или же глючить будет софт на хосте. Или драйвер. В любом случае кто-то будет глючить. В библиотеках МК тоже с наскока не разобраться. И вот я смотрю на трафик по шине USB анализатором, где происходящие события на незнакомом языке с тремя замечательными уровнями вообще не вяжутся. Интересно, это у меня от гриппозной лихорадки в голове такой диссонанс?

Если у читателя бывали сходные ощущения, предлагаю альтернативное, явившееся мне неожиданно ясно в перегретом мозгу видение стека USB, по мотивам любимой 7-уровневой модели OSI. Я ограничился пятью уровнями:



Я не хочу сказать, что весь софт и библиотеки уже сделаны или должны проектироваться, исходя из этой модели. Из инженерных соображений код c уровнями будет сильно перемешан. Но я хочу помочь тем, кто начинает своё знакомство с шиной USB, кто хочет понять протоколы обмена устройств и терминологию предметной области, подобраться поближе к готовым примерам, библиотекам и лучше ориентироваться в них. Эта модель не для загрузки в МК, но в ваши блестящие умы, дорогие друзья. А ваши золотые руки потом всё сами сделают, я не сомневаюсь:)