|
Мелкий |
Дата 2 Апреля 2004, 18:18 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 1209
ID пользователя: 4829
Регистрация: 16 Дек 2003
|
попробуй есчо такой алгоритм: 7=6+1 теперь от шести отнимаем единицу и прибавляем к следующему слагаемому: 7=5+2 тоже делаем теперь с двойкой: 7=5+1+1 опять скидываем единицу: (из 7=5+2): 7=4+3 7=4+2+1 7=4+1+2 - не катит...отсекаем, если след. слагаемое больше предыдущего. 7=4+1+1+1 (из 7=5+1+1): не трогаем, т.к. он из варианта (7=5+2), который мы уже разложили) далее: (из 7=4+3): 7=3+4 - не катит 7=3+3+1 7=3+2+2 7=3+1+3 - нет 7=3+1+2+1 - нет 7=3+1+1+2 - нет 7=3+1+1+1+1 (из 7=3+3+1): 7=2+4+1 - не катит 7=2+3+2 - нет 7=2+2+3 - нет 7=2+2+2+1 ну и т.д.
-------------------- Хотели как лучше!...а получилось как всегда... :))
|
Dr.Evil |
Дата 3 Апреля 2004, 17:12 |
|
|
Unregistered
|
короче http://aspn.activestate.com/ASPN/Cookbook/...n/Recipe/218332 а вообще см.google - partitions of an integer e.g. http://www.pcworldmalta.com/archive/iss37/num22.htm http://www.encyclopedia4u.com/i/integer-partition.html
|
Scroller |
Дата 3 Апреля 2004, 19:36 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 193
ID пользователя: 1684
Регистрация: 1 Апр 2003
|
Похоже, Доктору такая задача уже попадалась. Умеете вы, мужики, темки подкидывать. Чуть сам алгоритм придумывать не начал. Чур меня, чур!
|
Dr.Evil |
Дата 4 Апреля 2004, 05:31 |
|
|
Unregistered
|
я тоже было начал... западло такие вопросы на интервью получать... хотя если их интересовал ход мыслей а не ответ, то может и не так страшно... многое в этом мире уже придумано до нас ... а военный инженер - как говаривал Шурик Холопов - должен уметь пользоваться справочниками... ...и - добавляли мы - выговаривать слово ЛАБОЛАТОРИЯ...
|
Мелкий |
Дата 4 Апреля 2004, 11:03 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 1209
ID пользователя: 4829
Регистрация: 16 Дек 2003
|
QUOTE (Dr.Evil @ 4 Апр 2004, 05:31) | выговаривать слово ЛАБОЛАТОРИЯ... | при этом делая шесть подъёмов-переворотом...
-------------------- Хотели как лучше!...а получилось как всегда... :))
|
Tim |
Дата 5 Апреля 2004, 11:26 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
QUOTE (Dr.Evil @ 4 Апр 2004, 05:31) | я тоже было начал... западло такие вопросы на интервью получать... хотя если их интересовал ход мыслей а не ответ, то может и не так страшно... |
Да нет интересовал не ход мыслей, а именно реализация. Во еще пара интересных вопросиков оттуда же: 1. Без использования третьей ячейки памяти обменять содержимое двух переменных. Здесь я догадался: Х=3; У=5; Х=Х+У; У=Х-У; Х=Х-У; Но это для целых, а в общем случае так: X=X XOR Y; Y=Y XOR X; X=X XOR Y;
2. Есть двунаправленная очередь, содержащая целые. Для очереди реализованы методы: взять элемент справа, взять элемент слева, положить элемент справа, положить элемент слева. Необходимо со 100% уверенностью подсчитать количество элементов в очереди, при условии, что нельзя выделить память для всех элементов, т.е. нельзя вытаскивать все элементы, пока очередь не опустеет и считать их в процессе вытаскивания, зато можно выделить память под конечное количество своих элементов. Мне сказали, что до сих пор решения не было.
-------------------- Now let your mind do the walking... © M.L.Gore
|
Dr.Evil |
Дата 5 Апреля 2004, 18:44 |
|
|
Unregistered
|
а, понятно причем тут вероятность если известно что-то о природе данных в очереди - то, возможно, задача и решаема типа
1. засунуть в очередь маркер, вроде 00000
pushright(0); pushright(0); pushright(0); pushright(0); pushright(0);
если знать какие там целые могут быть, то маркером должно быть что-нибудь ненатуральное ...
2. прогнать в цикле всю очередь пока not_a_marker() не обнаружит маркер, ну для того чтобы маркер можно было обнаружить надо помнить последние N элементов - и это тоже надо сделать внутри цикла
while (not_a_marker()) { int x = popleft(); counter++; pushright(x); save_to_marker_buffer(x); }
|
Tim |
Дата 5 Апреля 2004, 18:48 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
Да, чем уникальнее будет маркер, тем больше будет вероятность правильного обнаружения маркера, но это на 100% не потянет, а про характер данных в очереди ничего не говориться. Мож там и пять нулей подряд есть и шесть где-нибудь.
-------------------- Now let your mind do the walking... © M.L.Gore
|
Tim |
Дата 5 Апреля 2004, 18:53 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
Да еще после того, как вроде бы обнаружил маркер нужно назать очередь отмотать и проверить попал ли ты туда, откуда начинал, а то вдруг это и маркер вообще.
-------------------- Now let your mind do the walking... © M.L.Gore
|
Dr.Evil |
Дата 5 Апреля 2004, 18:59 |
|
|
Unregistered
|
да, согласен, это не 100% и отмотать надо
может, ее вообще - отсортировать? или хотя бы найти min. max элемент? должна ли очередь остаться в первозданном виде? если известен максимум или минимум - маркером может быть число большее / меньшее.
но если интервьюер сказал что задача пока никем не решена ( я правильно понял?) то, возможно, что цель вопроса была посмотреть - как испытуемый определяет/выясняет недостающие условия / requirements?
|
Scroller |
Дата 6 Апреля 2004, 17:45 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 193
ID пользователя: 1684
Регистрация: 1 Апр 2003
|
QUOTE | Мне сказали, что до сих пор решения не было. |
Сдается мне, что цель этих распальцованных дателей - просто послать Тима подальше. Но, похоже, люди интеллигентные... А от задачки про очередь как-то повеяло детской головоломкой про кораблики: стоят они, бедные, двумя караванами навстречу друг-другу, надо им разойтись, а место, где можно разминуться, только для одного.
|
Tim |
Дата 6 Апреля 2004, 18:05 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
Ну тут, на самом деле, есть две составляющие: 1. конечно хорошо, если у меня будут работать люди, которые если не участвовали в олимпиадах, то хотябы решениями таких задач интересовались. 2. приходит человек, говорит хочу зряплату 1,5к. Ему дают решать такие задачки, после чего дают 700 и будь счастлив сынок, что ты у нас работаешь, видал какие у нас спецы.
-------------------- Now let your mind do the walking... © M.L.Gore
|
Dr.Evil |
Дата 6 Апреля 2004, 20:34 |
|
|
Unregistered
|
с вашего позволения - вот к чему пришел коллективный разум http://discuss.fogcreek.com/techinterview/...895&ixReplies=4
|
Глеб |
Дата 9 Апреля 2004, 17:01 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 1123
ID пользователя: 1357
Регистрация: 11 Июн 2001
|
Господа, это из комбинаторики. Алгоритм разбиения чисел. В Можайке на 53 кафедре есть дока по таким алгоритмам преподаватель Ваулин Арис Ефимович. Он даже книгу написал по таким алгоритмам. Есть дальше направление - попробуйте придумать алгоритм разбиения множеств. )) Если еще будут вопросы, могу попробовать его вспомнить.
|
Scroller |
Дата 11 Апреля 2004, 19:53 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 193
ID пользователя: 1684
Регистрация: 1 Апр 2003
|
QUOTE | Господа, это из комбинаторики. |
Интересно, как поможет комбинаторика, если в очереди все элементы будут одинаковыми.
|