|
Tim |
Дата 2 Апреля 2004, 11:41 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
В понедельник ездил, как сейчас модно говорить, на интервью . Предложили там несколько задачек. Одна из них мне до сих пор покоя не дает: Для целого числа необходимо вывести все варианты разложения его на слагаемые без повторов. Т.е., например для Х=4 должно получится 3+1, 2+2, 2+1+1, 1+1+1+1. Представители 25-й кафедры на сцену .
-------------------- Now let your mind do the walking... © M.L.Gore
|
Vic |
Дата 2 Апреля 2004, 12:09 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 240
ID пользователя: 1392
Регистрация: 11 Янв 2002
|
Самый простой способ для Х - это цклическое деление на 1, потом на 2, потом на 3 и т.д. до (Х-1), каждое предыдущее деление необходимо запоминать, т.к. полученное с его поощью разложение участвует в последующем, а уж строковое представление можно оформить и с "+", и с "-" или с ";"... (Примечание: то, на что делишь и есть кличество раз, которое встречается данная цифра в разложении, а остаток - другое слагаемое.)
|
Tim |
Дата 2 Апреля 2004, 12:28 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
QUOTE (Vic @ 2 Апр 2004, 12:09) | Самый простой способ для Х - это цклическое деление на 1, потом на 2, потом на 3 и т.д. до (Х-1), а уж строковое представление можно оформить и с "+", и с "-" или с ";"... (Примечание: то, на что делишь и есть кличество раз, которое встречается данная цифра в разложении.) |
Не подумайте, что дурак полный, но прошу прокомментировать: Х=4: 1. Делим на 1: 4/1 = 4 получили 4(+0) 2. Делим на 2: 4/2 = 2 получили 2+2 3. Делим на 3 4/3 = 1 получили 1+1+1 ?
-------------------- Now let your mind do the walking... © M.L.Gore
|
Мелкий |
Дата 2 Апреля 2004, 12:42 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 1209
ID пользователя: 4829
Регистрация: 16 Дек 2003
|
а интервью - это приём на работу штоли?...
попробуй так: 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 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 240
ID пользователя: 1392
Регистрация: 11 Янв 2002
|
Молодец!!! Это ты сделал для 4. А в памяти у тебя уже должно быть тоже самое для 3 и 2. Осталось их тоже подставить. И все готово !!!!
|
Tim |
Дата 2 Апреля 2004, 13:26 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
QUOTE (Мелкий @ 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)...ну и т.д. думаю дальше поймёшь...вникать проста неохота... |
Интервью - это собеседование при приеме на работу у распальцованных работодателей. Это уже ближе, но хотелось бы формализовать, как отфильтровать повторы: Х=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 - опять повтор
-------------------- Now let your mind do the walking... © M.L.Gore
|
Tim |
Дата 2 Апреля 2004, 13:28 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
QUOTE (Vic @ 2 Апр 2004, 12:56) | Молодец!!! Это ты сделал для 4. А в памяти у тебя уже должно быть тоже самое для 3 и 2. Осталось их тоже подставить. И все готово !!!! | Я не очень понял какие слагаемые получатся путем деления 4/3
-------------------- Now let your mind do the walking... © M.L.Gore
|
Мелкий |
Дата 2 Апреля 2004, 13:47 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 1209
ID пользователя: 4829
Регистрация: 16 Дек 2003
|
значит делай, пока y<x/2...т.е. 3 уже больше 5/2...
-------------------- Хотели как лучше!...а получилось как всегда... :))
|
Tim |
Дата 2 Апреля 2004, 15:05 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
QUOTE (Мелкий @ 2 Апр 2004, 13:47) | значит делай, пока y<x/2...т.е. 3 уже больше 5/2... | А причем здесь магическая цифра 2? Как формально описать условие окончания?
-------------------- Now let your mind do the walking... © M.L.Gore
|
Мелкий |
Дата 2 Апреля 2004, 16:04 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 1209
ID пользователя: 4829
Регистрация: 16 Дек 2003
|
QUOTE (Tim @ 2 Апр 2004, 15:05) | QUOTE (Мелкий @ 2 Апр 2004, 13:47) | значит делай, пока y<x/2...т.е. 3 уже больше 5/2... |
А причем здесь магическая цифра 2? Как формально описать условие окончания? | иппонский бог...сам то немного додумывай!... ...грю ведь, что думать неохота!...
если ты переберёшь все варианты, то их будет в 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 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
QUOTE (Мелкий @ 2 Апр 2004, 16:04) | зы. жопой чувствую, что отсекает!... |
Это конечно сильный аргумент , но врядли подходящий.
QUOTE (Мелкий @ 2 Апр 2004, 16:04) | иппонский бог...сам то немного додумывай!... ...грю ведь, что думать неохота!... |
Ладно,недумай(одним словом) дальше. Не буду отвлекать.
-------------------- Now let your mind do the walking... © M.L.Gore
|
Мелкий |
Дата 2 Апреля 2004, 17:16 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 1209
ID пользователя: 4829
Регистрация: 16 Дек 2003
|
я те есчо одын алгоритм придумал! значит допустим нада разложить число 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 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
Слушай, ну такую штуку реализовать .
-------------------- Now let your mind do the walking... © M.L.Gore
|
Мелкий |
Дата 2 Апреля 2004, 17:51 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 1209
ID пользователя: 4829
Регистрация: 16 Дек 2003
|
QUOTE (Tim @ 2 Апр 2004, 17:39) | Слушай, ну такую штуку реализовать . | дык программу нада написать?...или чего?...если прогу, то это в проге просто реализуется: глаза боятся...
-------------------- Хотели как лучше!...а получилось как всегда... :))
|
Tim |
Дата 2 Апреля 2004, 17:57 |
|
|
Активный участник
Профиль
Группа: Члены клуба
Сообщений: 130
ID пользователя: 323
Регистрация: 4 Фев 2003
|
Я тут еще в первой версии алгоритма баг нашел. Проявляется при попытке разложить число более 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(это кстати нужно отсечь опять каким-то магическим образом, т.к. уже было.)
-------------------- Now let your mind do the walking... © M.L.Gore
|