Задачка для программистов (на любом языке)
#1
Отправлено 12 Сентябрь 2006 - 22:36
#2
Отправлено 13 Сентябрь 2006 - 07:51
Решений на самом деле много.. Некоторые - зависят от языка..
#3
Отправлено 13 Сентябрь 2006 - 14:10
#4
Отправлено 13 Сентябрь 2006 - 14:20
Например.. для системы реального времени требуется написать функцию, которая получает байт, а возвращает байт с битами в обратном порядке.
Основная задача заключается в том, что функция должна работать, как можно быстрее. Ибо - система реального времени.
Есть и другие задачки такого типа В основном о системах реального времени..
Хотя.. есть и на алгоритмику... Сейчас вот участвую в конкурсе Гуглевом - там оригинальные задачки есть.
#6
Отправлено 13 Сентябрь 2006 - 15:22
Но уже, увы Жди следующего раза.
Потому что раунд квалификации уже прошел. На прошлой неделе. Отобрали 1000 из тысяч 15-16. Следующий раунд завтра. Останутся 500...
#7
Отправлено 13 Сентябрь 2006 - 15:38
И порешать ( порешить? ).
#10
Отправлено 13 Сентябрь 2006 - 15:55
Уже решил?
Просто в алгоритмических задачках тяжело проверять решение.. Ибо не единственное есть
Но, к примеру, вот задачка оттуда. Для начала определения. Строка называется палиндромом, если слева направо и справа налево она читается одинаково.
Часть строки называется палиндромом, если эта часть строки читается одинаково слева направо и справа налево.
Часть строки называется максимальным палиндромом, если эта часть строки является палиндромом и в то же время, как эту часть строки не пытайся расширить (добавляя из строки справа и слева от взятой части), а более длинного палиндрома не получишь.
На примерах.
В строке ABC три максимальных палиндрома: A, B и C. Каждая из этих частей строки АВС не может быть расширена до бОльшего палиндрома.
В строке АААА всего один максимальный палиндром: вся строка.
В строке АВАВ есть два максимальных палиндрома: АВА и ВАВ. Каждый из этих двух палиндромов не может быть расширен.
Задача.. Написать функцию, которая получает строку и возвращает кол-во максимальных палиндромов в оной.
Строк может быть длиной до 1000 символов.. Функция должна работать не более 2 секунд.
#11
Отправлено 14 Сентябрь 2006 - 03:33
Биты в обратном порядке - догадываюсь, что какой-то хитрый прикол, которого я не знаю. Но я придумал совсем не хитрое и быстрое решение. Вопрос - достаточно ли быстрое? Как это определить?
#13
Отправлено 15 Сентябрь 2006 - 08:57
Лови еще одну
В некотором месте в памяти хранится текущее значение времени, состоящее из 4 байт и равное кол-ву секунд, проистекших с 1 января 1970-ого года.
Каждую секунду процессор прерывает работу текущей программы и выполняет некоторую процедуру, которая прибавляет к вышеупомянутому значению единицу, а затем возвращается к выполнению текущей программы.
Теперь о самой задаче. В некоторой программе нужно прочитать значение времени и записать его в локальную переменную. Т.е. по сути нужно скопировать 4 байта из одного места памяти в другое.
Беда в том, что всё нужно написать для 8-разрядного процессора, который не умеет одной командой копировать 4 байта. Т.е. нужно, как минимум 4 команды, чтобы скопировать 4 байта по одному. А, как было написано выше, в любой момент процессор может прервать выполнение текущей программы и изменить значение, записанное в этих 4 байтах.
Запрещать прерывания нельзя. Требуется надёжно прочитать точное текущее значение времени. Как это сделать?
#14
Отправлено 15 Сентябрь 2006 - 19:20
#15
Отправлено 15 Сентябрь 2006 - 19:27
Большой Грызь (13.9.2006, 12:22) писал:
Но уже, увы Жди следующего раза.
Потому что раунд квалификации уже прошел. На прошлой неделе. Отобрали 1000 из тысяч 15-16. Следующий раунд завтра. Останутся 500...
Ну как прошел раунд ?
#16
Отправлено 16 Сентябрь 2006 - 16:47
with_hello (15.9.2006, 19:20) писал:
Ну, вообще-то измениться могут все байты вообще )
А прошлое значение можно восстановить, как для старших, так и для младшего разряда
Если правильно подойти..