http://mozhayka.org/forum/?act=ST&f=1&t=1967
| Автор: Tim 2 Апреля 2004, 11:41 |
В понедельник ездил, как сейчас модно говорить, на интервью  . Предложили там несколько задачек. Одна из них мне до сих пор покоя не дает:Для целого числа необходимо вывести все варианты разложения его на слагаемые без повторов. Т.е., например для Х=4 должно получится 3+1, 2+2, 2+1+1, 1+1+1+1. Представители 25-й кафедры на сцену  . |
| Автор: Vic 2 Апреля 2004, 12:09 |
Самый простой способ для Х - это цклическое деление на 1, потом на 2, потом на 3 и т.д. до (Х-1), каждое предыдущее деление необходимо запоминать, т.к. полученное с его поощью разложение участвует в последующем, а уж строковое представление можно оформить и с "+", и с "-" или с ";"...  (Примечание: то, на что делишь и есть кличество раз, которое встречается данная цифра в разложении, а остаток - другое слагаемое.) |
| Автор: Tim 2 Апреля 2004, 12:28 | ||
Не подумайте, что дурак полный, но прошу прокомментировать: Х=4: 1. Делим на 1: 4/1 = 4 получили 4(+0) 2. Делим на 2: 4/2 = 2 получили 2+2 3. Делим на 3 4/3 = 1 получили 1+1+1 ? |
| Автор: Мелкий 2 Апреля 2004, 12:42 |
| а интервью - это приём на работу штоли?... попробуй так: 5=1+4 5=1+1+3 5=1+1+1+2 5=1+1+1+1+1 5=2+3 5=1+2+2 (из 5=1+4) т.е. разбиваешь сначала каждое число, которое больше 1 на 1 и (х-1), потом на 2 и (х-2)...ну и т.д.  думаю дальше поймёшь...вникать проста неохота...  |
| Автор: Vic 2 Апреля 2004, 12:56 |
| Молодец!!! Это ты сделал для 4. А в памяти у тебя уже должно быть тоже самое для 3 и 2. Осталось их тоже подставить. И все готово !!!! |
| Автор: Tim 2 Апреля 2004, 13:26 | ||
Интервью - это собеседование при приеме на работу у распальцованных работодателей. Это уже ближе, но хотелось бы формализовать, как отфильтровать повторы: Х=5 1. Рекурсивно раскладываем на сумму 1+(Х-1) 5=1+4 5=1+1+3 5=1+1+1+2 5=1+1+1+1+1 2. Рекурсивно раскладываем на сумму 2+(Х-2) 5=2+3 5=2+2+1 3. Рекурсивно раскладываем на сумму 3+(Х-3) 5=3+2 - повтор получился. 4. Рекурсивно раскладываем на сумму 4+(Х-4) 5=4+1 - опять повтор |
| Автор: Tim 2 Апреля 2004, 13:28 | ||
Я не очень понял какие слагаемые получатся путем деления 4/3 |
| Автор: Мелкий 2 Апреля 2004, 13:47 |
значит делай, пока y<x/2...т.е. 3 уже больше 5/2...  |
| Автор: Tim 2 Апреля 2004, 15:05 | ||
А причем здесь магическая цифра 2? Как формально описать условие окончания? |
| Автор: Мелкий 2 Апреля 2004, 16:04 | ||||
иппонский бог...сам то немного додумывай!... ...грю ведь, что думать неохота!... если ты переберёшь все варианты, то их будет в 2 раза больше...(например 2-3 и 3-2)... значит отсекай их, например, если остаток будет меньше числа, то не бери такой вариант. ...ну или придумай другой алгоритм отсекания... (не крайней плоти...  )Х=5 1. Рекурсивно раскладываем на сумму 1+(Х-1) 5=1+4 5=1+1+3 5=1+1+1+2 5=1+1+1+1+1 2. Рекурсивно раскладываем на сумму 2+(Х-2) Сначала пробуем уже получившиеся варианты: (5=1+4): 5=1+2+2 (5=1+1+3): 5=1+1+1+2 - не пойдёт, т.к. остаток (1) меньше 2 5=2+3 5=2+2+1 - не пойдёт, т.к. остаток (1) меньше 2 3. Рекурсивно раскладываем на сумму 3+(Х-3) и на 4+(Х-4) не канает, т.к. в любом случае остаток меньше... осталось доказать, что таким образом ты отсекаешь повторяющиеся варианты!... зы. жопой чувствую, что отсекает!...  |
| Автор: Tim 2 Апреля 2004, 16:21 | ||||
Это конечно сильный аргумент , но врядли подходящий.
Ладно,недумай(одним словом) дальше.  Не буду отвлекать. |
| Автор: Мелкий 2 Апреля 2004, 17:16 |
| я те есчо одын алгоритм придумал! значит допустим нада разложить число 7. максимальное кол-во слагаемых 7: 1+1+1+1+1+1+1 - это единственный вариант... берём количество цифр на 1 меньше: 7-1=6. оставшуюся единицу прибавляем к первому числу: 2+1+1+1+1+1 - это тоже единственный вариант, т.к. оставшуюся единицу прибавлять кроме как к единицам не имеет смысла... дальше:6-1=5: у тебя имеется: 1+1+1+1+1 и 1+1 значит к 1+1+1+1+1 ты прибавляешь 2+0 и 1+1...получаешь два варианта: 3+1+1+1+1 2+2+1+1+1 5-1=4. имеешь: 1+1+1+1 и 1+1+1. Прибавляешь 3+0+0 2+1+0 1+1+1 варианты 2+1+0 и 2+0+1 - однох***нны... (В переборе вариантов тоже такой же алгоритм: по единичке скидываешь с первого числа и гонишь её на последнее место, но чтобы следующее число не было больше предыдущего, т.к. будет повтор) Получаешь: 4+1+1+1 3+2+1+1 2+2+2+1 ...ну а дальше (4-1=3.) в 1+1+1 суёшь 1+1+1+1...: 4+0+0+0 3+1+0+0 2+2+0+0 2+1+1+0 1+2+1+0 - не канает уже... Получаешь: 5+1+1 4+2+1 3+3+1 3+2+2 3-1=2. в 1+1 суём 1+1+1+1+1. Варианты: 5+0+0+0+0 4+1+0+0+0 3+2+0+0+0 получаем: 6+1 5+2 4+3 ...ну и всё...расчёт закончен!...  ...уморил...пивка хоть налей...  ...как на работу примут!... Удачи! |
| Автор: Tim 2 Апреля 2004, 17:39 |
| Слушай, ну такую штуку реализовать . |
| Автор: Мелкий 2 Апреля 2004, 17:51 | ||
дык программу нада написать?...или чего?...если прогу, то это в проге просто реализуется: глаза боятся... |
| Автор: Tim 2 Апреля 2004, 17:57 |
| Я тут еще в первой версии алгоритма баг нашел. Проявляется при попытке разложить число более 6: Х=6 (Х-1): 6=1+5 6=1+1+4 6=1+1+1+3 6=1+1+1+1+2 6=1+1+1+1+1+1 (Х-2): 6=2+4 6=2+2+2 Здесь 4 нужно опять через (Х-1) раскладывать, а то потеряется 6=2+1+3, 6=2+1+1+2, 6=2+1+1+1+1(это кстати нужно отсечь опять каким-то магическим образом, т.к. уже было.) |
| Автор: Мелкий 2 Апреля 2004, 18:18 |
| попробуй есчо такой алгоритм: 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 |
| короче http://aspn.activestate.com/ASPN/Cookbook/Python/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 | ||
Похоже, Доктору такая задача уже попадалась. Умеете вы, мужики, темки подкидывать. Чуть сам алгоритм придумывать не начал. Чур меня, чур! |
| Автор: Dr.Evil 4 Апреля 2004, 05:31 |
| я тоже было начал... западло такие вопросы на интервью получать... хотя если их интересовал ход мыслей а не ответ, то может и не так страшно... многое в этом мире уже придумано до нас ... а военный инженер - как говаривал Шурик Холопов - должен уметь пользоваться справочниками... ...и - добавляли мы - выговаривать слово ЛАБОЛАТОРИЯ... |
| Автор: Мелкий 4 Апреля 2004, 11:03 | ||
при этом делая шесть подъёмов-переворотом... |
| Автор: Tim 5 Апреля 2004, 11:26 | ||
Да нет интересовал не ход мыслей, а именно реализация. Во еще пара интересных вопросиков оттуда же: 1. Без использования третьей ячейки памяти обменять содержимое двух переменных. Здесь я догадался: Х=3; У=5; Х=Х+У; У=Х-У; Х=Х-У; Но это для целых, а в общем случае так: X=X XOR Y; Y=Y XOR X; X=X XOR Y; 2. Есть двунаправленная очередь, содержащая целые. Для очереди реализованы методы: взять элемент справа, взять элемент слева, положить элемент справа, положить элемент слева. Необходимо со 100% уверенностью подсчитать количество элементов в очереди, при условии, что нельзя выделить память для всех элементов, т.е. нельзя вытаскивать все элементы, пока очередь не опустеет и считать их в процессе вытаскивания, зато можно выделить память под конечное количество своих элементов. Мне сказали, что до сих пор решения не было. |
| Автор: Dr.Evil 5 Апреля 2004, 18:44 |
| а, понятно причем тут вероятность если известно что-то о природе данных в очереди - то, возможно, задача и решаема типа 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 |
| Да, чем уникальнее будет маркер, тем больше будет вероятность правильного обнаружения маркера, но это на 100% не потянет, а про характер данных в очереди ничего не говориться. Мож там и пять нулей подряд есть и шесть где-нибудь. |
| Автор: Tim 5 Апреля 2004, 18:53 |
| Да еще после того, как вроде бы обнаружил маркер нужно назать очередь отмотать и проверить попал ли ты туда, откуда начинал, а то вдруг это и маркер вообще. |
| Автор: Dr.Evil 5 Апреля 2004, 18:59 |
| да, согласен, это не 100% и отмотать надо может, ее вообще - отсортировать? или хотя бы найти min. max элемент? должна ли очередь остаться в первозданном виде? если известен максимум или минимум - маркером может быть число большее / меньшее. но если интервьюер сказал что задача пока никем не решена ( я правильно понял?) то, возможно, что цель вопроса была посмотреть - как испытуемый определяет/выясняет недостающие условия / requirements? |
| Автор: Scroller 6 Апреля 2004, 17:45 | ||
Сдается мне, что цель этих распальцованных дателей - просто послать Тима подальше. Но, похоже, люди интеллигентные... А от задачки про очередь как-то повеяло детской головоломкой про кораблики: стоят они, бедные, двумя караванами навстречу друг-другу, надо им разойтись, а место, где можно разминуться, только для одного. |
| Автор: Tim 6 Апреля 2004, 18:05 |
| Ну тут, на самом деле, есть две составляющие: 1. конечно хорошо, если у меня будут работать люди, которые если не участвовали в олимпиадах, то хотябы решениями таких задач интересовались. 2. приходит человек, говорит хочу зряплату 1,5к. Ему дают решать такие задачки, после чего дают 700 и будь счастлив сынок, что ты у нас работаешь, видал какие у нас спецы. |
| Автор: Dr.Evil 6 Апреля 2004, 20:34 |
| с вашего позволения - вот к чему пришел коллективный разум http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=1895&ixReplies=4 |
| Автор: Глеб 9 Апреля 2004, 17:01 |
| Господа, это из комбинаторики. Алгоритм разбиения чисел. В Можайке на 53 кафедре есть дока по таким алгоритмам преподаватель Ваулин Арис Ефимович. Он даже книгу написал по таким алгоритмам. Есть дальше направление - попробуйте придумать алгоритм разбиения множеств. )) Если еще будут вопросы, могу попробовать его вспомнить. |
| Автор: Scroller 11 Апреля 2004, 19:53 | ||
Интересно, как поможет комбинаторика, если в очереди все элементы будут одинаковыми. |
| Автор: Глеб 12 Апреля 2004, 16:08 |
| Моя реплика относится не к последней задаче. А к самой первой. |
| Автор: ADD 13 Апреля 2004, 09:10 | ||
Раз уж знаешь такую штуку как рекурсия, то 4 это 1+3, а дальше запускаешь анализ разложений тройки на слагаемые. Затем 4 это 2+2, и запускаешь ... , короче, ты понял. В результате: получаем цикл от 1 до Х-1, а внутри цикла рекурентный анализ. Идею понял?  |
| Автор: ADD 13 Апреля 2004, 09:19 | ||||
При делении 4/3 у него получилось 1+3, что повторяет 3+1. Этот метод работает, только тогда, когда на каждом шаге проходишь не более половины цикла. Отсюда и магическая цифра 2. В принципе, вариант подходящий. |
| Автор: Вован Питерский 16 Апреля 2004, 16:47 |
Алгоритм действия мужчины на Новый Год ! |
| Автор: Вован Питерский 17 Апреля 2004, 19:10 |
Еще один алгоритм решения проблем: |
| Автор: Вован Питерский 17 Апреля 2004, 19:28 |
Хотя мне эти алгоритмы нажоели еще в можайке |
| Автор: Vic 22 Января 2005, 19:41 |
| Срочно!!!!!! Кто встречал алгоритм, реализующий проверку: является ли данное число суммой других, заранее заданных (с выводом всех возможных, даже приблизительных результатов с заданной погрешностью !!!!) У кого есть мысли прошу их выразить, буду очень благодарен Пример: Заданы числа: { 3050,23 349,56 123,45 1567,49 10,45 ... 0,45 0,10 2056,34 134,47 } Можно ли число 45010,40 представить в виде их суммы, т.е. разложить на эти слагаемые ???? |
| Автор: Мелкий 23 Января 2005, 00:48 |
| Vic а числа можно использовать несколько раз?... ...по сути алгоритм простой - тупой перебор всех вариантов... |
| Автор: volder 24 Января 2005, 15:11 |
| Vic В общем то это стандартная задача о камнях (о рюкзаке) с единичными весовыми коэффициентами. Поэтому для решения задачи могут использованы любые известные методы дискретного математического программирования. |
| Автор: Vic 26 Января 2005, 00:26 |
| Спасибо Да числа повторяются. Что касается перебора,то долго ждать приходится, т.к. перебирать надо до ~ 10 в 6 степени чисел |
| Автор: volder 26 Января 2005, 13:31 | ||||
Vic
Eto ne menyaet typ zadachy
Da eto zadacha NP-hard |
| Автор: Мелкий 26 Января 2005, 13:38 | ||||
volder
так вот как ты называешься, тупой перебор!... Vic
дык уже подумай, как оптимизировать тупой перебор... |
| Автор: Вован Питерский 26 Января 2005, 14:42 |
| могу выслать если надо, тока там вариант для подготовки в путевой лист маршрута зная нужный пробег, т.е. подбор к пробегу - маршрута с километражом ускоряет вариант тупого перебора - это выход из очередного цикла перебора при условии уже превышения набранной суммы относительно нужного числа (ускоряет циклы капитально) удачи |
| Автор: Vic 27 Января 2005, 00:16 |
| Интересно будет посмотреть:) Благодарю |
| Автор: beloj 20 Февраля 2019, 11:48 |
| кончает порно эротика http://fuguchaulnes.com/erotika/ |