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

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

[1] 2 3  
Страниц: 3, Сообщений: 45  ( Перейти к первому непрочитанному сообщению )
« Предыдущая тема | Следующая тема » Подписка на эту тему | Отправить тему на e-mail | Версия для печати
Tim
  Дата 2 Апреля 2004, 11:41


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


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



В понедельник ездил, как сейчас модно говорить, на интервью sleep.gif . Предложили там несколько задачек. Одна из них мне до сих пор покоя не дает:
Для целого числа необходимо вывести все варианты разложения его на слагаемые без повторов.
Т.е., например для Х=4 должно получится 3+1, 2+2, 2+1+1, 1+1+1+1.
Представители 25-й кафедры на сцену smile.gif .

--------------------
Now let your mind do the walking...
© M.L.Gore
user posted image
 
     | наверх
Vic
Дата 2 Апреля 2004, 12:09


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


Профиль
Группа: Члены клуба
Сообщений: 240
ID пользователя: 1392
Регистрация: 11 Янв 2002



Самый простой способ для Х - это цклическое деление на 1, потом на 2, потом на 3 и т.д. до (Х-1), каждое предыдущее деление необходимо запоминать, т.к. полученное с его поощью разложение участвует в последующем, а уж строковое представление можно оформить и с "+", и с "-" или с ";"... wink.gif (Примечание: то, на что делишь и есть кличество раз, которое встречается данная цифра в разложении, а остаток - другое слагаемое.)
 
   | наверх
Tim
Дата 2 Апреля 2004, 12:28


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


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



QUOTE (Vic @ 2 Апр 2004, 12:09)
Самый простой способ для Х - это цклическое деление на 1, потом на 2, потом на 3 и т.д. до (Х-1), а уж строковое представление можно оформить и с "+", и с "-" или с ";"... wink.gif (Примечание: то, на что делишь и есть кличество раз, которое встречается данная цифра в разложении.)

Не подумайте, что дурак полный, но прошу прокомментировать:
Х=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
user posted image
 
     | наверх
Мелкий
Дата 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)...ну и т.д. biggrin.gif
думаю дальше поймёшь...вникать проста неохота... ph34r.gif

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

Интервью - это собеседование при приеме на работу у распальцованных работодателей.
Это уже ближе, но хотелось бы формализовать, как отфильтровать повторы:
Х=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
user posted image
 
     | наверх
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
user posted image
 
     | наверх
Мелкий
Дата 2 Апреля 2004, 13:47


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


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



значит делай, пока y<x/2...т.е. 3 уже больше 5/2... sausage.gif

--------------------
Хотели как лучше!...а получилось как всегда... :))
 
     | наверх
Tim
Дата 2 Апреля 2004, 15:05


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


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



QUOTE (Мелкий @ 2 Апр 2004, 13:47)
значит делай, пока y<x/2...т.е. 3 уже больше 5/2... sausage.gif

А причем здесь магическая цифра 2? Как формально описать условие окончания?

--------------------
Now let your mind do the walking...
© M.L.Gore
user posted image
 
     | наверх
Мелкий
  Дата 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... sausage.gif

А причем здесь магическая цифра 2? Как формально описать условие окончания?

иппонский бог...сам то немного додумывай!... ph34r.gif ...грю ведь, что думать неохота!... biggrin.gif

если ты переберёшь все варианты, то их будет в 2 раза больше...(например 2-3 и 3-2)...
значит отсекай их, например, если остаток будет меньше числа, то не бери такой вариант.
...ну или придумай другой алгоритм отсекания... (не крайней плоти... laugh.gif laugh.gif laugh.gif )

Х=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)
не канает, т.к. в любом случае остаток меньше...
осталось доказать, что таким образом ты отсекаешь повторяющиеся варианты!... biggrin.gif

зы. жопой чувствую, что отсекает!... laugh.gif dance.gif

--------------------
Хотели как лучше!...а получилось как всегда... :))
 
     | наверх
Tim
Дата 2 Апреля 2004, 16:21


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


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



QUOTE (Мелкий @ 2 Апр 2004, 16:04)
зы. жопой чувствую, что отсекает!... laugh.gif  dance.gif

Это конечно сильный аргумент biggrin.gif , но врядли подходящий.
QUOTE (Мелкий @ 2 Апр 2004, 16:04)
иппонский бог...сам то немного додумывай!...  ...грю ведь, что думать неохота!... 

Ладно,недумай(одним словом) дальше. dry.gif Не буду отвлекать.

--------------------
Now let your mind do the walking...
© M.L.Gore
user posted image
 
     | наверх
Мелкий
  Дата 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 - это тоже единственный вариант, т.к. оставшуюся единицу прибавлять кроме как к единицам не имеет смысла... ph34r.gif
дальше: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
...ну и всё...расчёт закончен!... eek.gif

...уморил...пивка хоть налей... beer.gif ...как на работу примут!... biggrin.gif
Удачи!

--------------------
Хотели как лучше!...а получилось как всегда... :))
 
     | наверх
Tim
Дата 2 Апреля 2004, 17:39


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


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



Слушай, ну такую штуку реализовать eek.gif .

--------------------
Now let your mind do the walking...
© M.L.Gore
user posted image
 
     | наверх
Мелкий
  Дата 2 Апреля 2004, 17:51


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


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



QUOTE (Tim @ 2 Апр 2004, 17:39)
Слушай, ну такую штуку реализовать eek.gif .

дык программу нада написать?...или чего?...если прогу, то это в проге просто реализуется: глаза боятся... beer.gif

--------------------
Хотели как лучше!...а получилось как всегда... :))
 
     | наверх
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
user posted image
 
     | наверх
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
[1] 2 3  
Страниц: 3, Сообщений: 45
« Назад в Клубная курилка

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