Здравствуйте Гость
Вход | Регистрация

Алгоритмисты есть?

1 [2] 3  
Страниц: 3, Сообщений: 45  ( Перейти к первому непрочитанному сообщению )
« Предыдущая тема | Следующая тема » Подписка на эту тему | Отправить тему на e-mail | Версия для печати
Мелкий
Дата 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
ну и т.д. wub.gif

--------------------
Хотели как лучше!...а получилось как всегда... :))
 
     | наверх
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



QUOTE
короче
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


Похоже, Доктору такая задача уже попадалась. Умеете вы, мужики, темки подкидывать. Чуть сам алгоритм придумывать не начал. Чур меня, чур!
 
  | наверх
Dr.Evil
Дата 4 Апреля 2004, 05:31


Unregistered










я тоже было начал... западло такие вопросы на интервью получать... хотя если их интересовал
ход мыслей а не ответ, то может и не так страшно...
многое в этом мире уже придумано до нас ... а военный инженер - как говаривал Шурик Холопов - должен уметь пользоваться справочниками...
...и - добавляли мы - выговаривать слово ЛАБОЛАТОРИЯ...
 
| наверх
Мелкий
  Дата 4 Апреля 2004, 11:03


Активный участник


Профиль
Группа: Члены клуба
Сообщений: 1209
ID пользователя: 4829
Регистрация: 16 Дек 2003



QUOTE (Dr.Evil @ 4 Апр 2004, 05:31)
выговаривать слово ЛАБОЛАТОРИЯ...

при этом делая шесть подъёмов-переворотом... laugh.gif beer.gif

--------------------
Хотели как лучше!...а получилось как всегда... :))
 
     | наверх
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
user posted image
 
     | наверх
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
user posted image
 
     | наверх
Tim
Дата 5 Апреля 2004, 18:53


Активный участник


Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003



Да еще после того, как вроде бы обнаружил маркер нужно назать очередь отмотать и проверить попал ли ты туда, откуда начинал, а то вдруг это и маркер вообще.

--------------------
Now let your mind do the walking...
© M.L.Gore
user posted image
 
     | наверх
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
user posted image
 
     | наверх
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 кафедре есть дока по таким алгоритмам преподаватель Ваулин Арис Ефимович. Он даже книгу написал по таким алгоритмам. Есть дальше направление - попробуйте придумать алгоритм разбиения множеств. smile.gif)) Если еще будут вопросы, могу попробовать его вспомнить.
 
    | наверх
Scroller
Дата 11 Апреля 2004, 19:53


Активный участник


Профиль
Группа: Члены клуба
Сообщений: 193
ID пользователя: 1684
Регистрация: 1 Апр 2003



QUOTE
Господа, это из комбинаторики.

Интересно, как поможет комбинаторика, если в очереди все элементы будут одинаковыми.
 
  | наверх
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
1 [2] 3  
Страниц: 3, Сообщений: 45
« Назад в Клубная курилка

44 ответов с 2 Апреля 2004, 11:41