?

Log in

No account? Create an account
entries friends calendar profile My Website Previous Previous Next Next
Разминаемся красненьким - Уголок Школьника
scolar
scolar
Разминаемся красненьким
Хорошую, хотя и несложную задачку для интервью подкинули мне несколько минут назад - удивительно, как при такой простоте формулировки она мне раньше не встречалась: есть длинная посделовательность целых чисел, в которой все числа, кроме одного, встречаются два раза. Найти то число, которое встречается один раз, за минимальное количество проходов с минимальной дополнительной памятью.
9 comments or Leave a comment
Comments
From: a_shen Date: August 7th, 2009 09:36 am (UTC) (Link)

xoрошая

задача, действительно!
scolar From: scolar Date: August 21st, 2009 01:01 am (UTC) (Link)

Re: xoрошая

Посмотри, тут вот её довольно забавное развитие получилось: http://scolar.livejournal.com/310974.html
From: vinopivets Date: August 7th, 2009 09:41 am (UTC) (Link)
Я правильно помню, что решения с минимизацией или числа проходов, или памяти - учебниковые?
scolar From: scolar Date: August 7th, 2009 06:41 pm (UTC) (Link)
Нет, конечно. Например, когда Вам кажется, что ваша электронная книжка слишком медленно отрисовывает очередную страницу, это, вполне вероятно, следствие того, что рисовальщики где-то делают лишние проходы. А если Вам кажется, что у Вашей электронной книжки слишком быстро садится батарейка, то это значит, что недостаток, описанный выше, решили компенсировать мощностью процессора.
upstartn From: upstartn Date: August 7th, 2009 09:45 am (UTC) (Link)
XOR ? :)
From: a_shen Date: August 7th, 2009 11:10 am (UTC) (Link)

ещё можно

спросить, что будет, если все числа встречаются по три раза, кроме одного, которое встречается только один раз...
m_ustinov From: m_ustinov Date: August 7th, 2009 02:46 pm (UTC) (Link)

не удержался :)

Поле вычетов по модулю 3
spamsink From: spamsink Date: August 7th, 2009 04:40 pm (UTC) (Link)

Re: ещё можно

Для этой задачи троичная машина нужна. :)
vanja_y From: vanja_y Date: August 7th, 2009 01:14 pm (UTC) (Link)
Ну вот, не дали подумать:(
9 comments or Leave a comment