2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Разбить число не слагаемые
Сообщение06.01.2013, 16:52 
Помогите плз решить в общем виде задачу:
Разбить натуральное число $N$ на $k$ РАЗНЫЕ,ЦЕЛЫЕ слагаемые $N_i$ таким образом чтобы их произведение было максимальным, т. е найти все $N_i,  i=1,...,k$ такие что $$ \prod\limits_{i=1}^k N_i \to \max$$ ,при $$\sum\limits_{i=1}^k N_i=N $$
Подойдет любое решение можно даже на нескольких примеров,главное объяснить,когда я решал задачу разбиения на $k$ слагаемых любых(т.е которые могут повторятся) то пришел к выводу что чем больше слагаемых тем лучше и что эти слагаемые должны состоять из 2-ек и 3-ек,а как быть тут?

 
 
 
 Re: Логическая задача
Сообщение06.01.2013, 17:24 
Аватара пользователя
Stotch в сообщении #667955 писал(а):
пришел к выводу что чем больше слагаемых тем лучше и что эти слагаемые должны сосотоять из 2-ек и 3-ек,а как быть тут?
По условию, каждое слагаемое - не более одного раза
Так что двигатся дальше. К четвёркам, пятёркам...

 
 
 
 Re: Логическая задача
Сообщение06.01.2013, 18:04 
Т.е нужно сначала разложить число на 2 и 3?а потом складывать эти двойки и тройки чтобы получались разные числа и чтобы их было как можно больше?я еще не совсем понимаю как определить сколько должно быть 2-ек и троек? в случае когда числа могут быть любые

 
 
 
 Re: Логическая задача
Сообщение06.01.2013, 19:02 
Stotch в сообщении #667987 писал(а):
я еще не совсем понимаю как определить сколько должно быть 2-ек и троек? в случае когда числа могут быть любые
Как Вы думаете, наличие трех двоек оправдано? Нельзя ли их заменить на что-то более выгодное? Но здесь совсем другая задача.
Stotch в сообщении #667955 писал(а):
чем больше слагаемых тем лучше
Согласен. Но не единички, конечно. Т.е $2+3+4+\cdots$ Пока сумма не станет больше либо равна нашему числу. А если больше, то..

 
 
 
 Re: Логическая задача
Сообщение06.01.2013, 19:23 
вот сижу и пришел к выводу что троек должно быть больше,но в каком соотношении?
а вот когда мы на разные слагаемые раслкадываем что делать когда сумма становится больше нашего числа?
вот например 17=2+3+4+5+x что вместо x должно быть?тройку нельзя,нужно что то делать с 4 и 5?но что?и как это определить и доказать?

 
 
 
 Re: Логическая задача
Сообщение06.01.2013, 19:45 
Добавляйте теперь единицы к имеющимся слагаемым.

 
 
 
 Re: Логическая задача
Сообщение06.01.2013, 20:03 
Аватара пользователя
Stotch в сообщении #667987 писал(а):
еще не совсем понимаю как определить сколько должно быть 2-ек и троек?

А слово РАЗНЫЕ в условии понимаете?

 
 
 
 Re: Логическая задача
Сообщение07.01.2013, 01:17 
я говорил про двойки и тройки в задачи когда числа могут быть любые,так в ткой задачи определить количество двоек и троек?т.е я правильно понимаю что 17=2+4+5+6 и эти числа дадут максимальное произведение?а какой общий алгоритм?

 
 
 
 Re: Логическая задача
Сообщение07.01.2013, 08:36 
Аватара пользователя
 i  Stotch, формулы на форуме следует записывать ТеХом. Инструкции здесь или здесь (или в этом видеоролике).

 
 
 
 Re: Логическая задача
Сообщение07.01.2013, 15:29 
Stotch в сообщении #668191 писал(а):
т.е я правильно понимаю что 17=2+4+5+6 и эти числа дадут максимальное произведение?
Для 17 — да.

Возможно, алгоритм можно увидеть, рассмотрев другие, кроме 17, числа.

 
 
 
 Re: Логическая задача
Сообщение07.01.2013, 16:22 
arseniiv в сообщении #668431 писал(а):
Возможно, алгоритм можно увидеть, рассмотрев другие, кроме 17, числа.
Похоже, алгоритм будет в точности такой же, как для 17.
Пусть наше $n$ равно $s+k$, где $s=2+3+\dots+j$ и $k\le j$. Тогда искомое представление $2+3+\dots+(j-k)+(j-k+2)+(j-k+3)+\dots+(s+1)$

 
 
 
 Re: Логическая задача
Сообщение07.01.2013, 17:16 
Иногда лучшее представление начинается с 3. Например, $34 = 3 + 4 + 5 + 6 + 7 + 9$. Вот факты для чисел до 50:

\begin{array}{ccc} \text{Число} & & \text{Слагаемые} \\ 1 & \to & 1 \\ 2 & \to & 2 \\ 3 & \to & 3 \\ 4 & \to & 4 \\ 5 & \to & 3, 2 \\ 6 & \to & 4, 2 \\ 7 & \to & 4, 3 \\ 8 & \to & 5, 3 \\ 9 & \to & 4, 3, 2 \\ 10 & \to & 5, 3, 2 \\ 11 & \to & 5, 4, 2 \\ 12 & \to & 5, 4, 3 \\ 13 & \to & 6, 4, 3 \\ 14 & \to & 5, 4, 3, 2 \\ 15 & \to & 6, 4, 3, 2 \\ 16 & \to & 6, 5, 3, 2 \\ 17 & \to & 6, 5, 4, 2 \\ 18 & \to & 6, 5, 4, 3 \\ 19 & \to & 7, 5, 4, 3 \\ 20 & \to & 6, 5, 4, 3, 2 \\ 21 & \to & 7, 5, 4, 3, 2 \\ 22 & \to & 7, 6, 4, 3, 2 \\ 23 & \to & 7, 6, 5, 3, 2 \\ 24 & \to & 7, 6, 5, 4, 2 \\ 25 & \to & 7, 6, 5, 4, 3 \\ 26 & \to & 8, 6, 5, 4, 3 \\ 27 & \to & 7, 6, 5, 4, 3, 2 \\ 28 & \to & 8, 6, 5, 4, 3, 2 \\ 29 & \to & 8, 7, 5, 4, 3, 2 \end{array}

\begin{array}{ccc} \text{Число} & & \text{Слагаемые} \\ 30 & \to & 8, 7, 6, 4, 3, 2 \\ 31 & \to & 8, 7, 6, 5, 3, 2 \\ 32 & \to & 8, 7, 6, 5, 4, 2 \\ 33 & \to & 8, 7, 6, 5, 4, 3 \\ 34 & \to & 9, 7, 6, 5, 4, 3 \\ 35 & \to & 8, 7, 6, 5, 4, 3, 2 \\ 36 & \to & 9, 7, 6, 5, 4, 3, 2 \\ 37 & \to & 9, 8, 6, 5, 4, 3, 2 \\ 38 & \to & 9, 8, 7, 5, 4, 3, 2 \\ 39 & \to & 9, 8, 7, 6, 4, 3, 2 \\ 40 & \to & 9, 8, 7, 6, 5, 3, 2 \\ 41 & \to & 9, 8, 7, 6, 5, 4, 2 \\ 42 & \to & 9, 8, 7, 6, 5, 4, 3 \\ 43 & \to & 10, 8, 7, 6, 5, 4, 3 \\ 44 & \to & 9, 8, 7, 6, 5, 4, 3, 2 \\ 45 & \to & 10, 8, 7, 6, 5, 4, 3, 2 \\ 46 & \to & 10, 9, 7, 6, 5, 4, 3, 2 \\ 47 & \to & 10, 9, 8, 6, 5, 4, 3, 2 \\ 48 & \to & 10, 9, 8, 7, 5, 4, 3, 2 \\ 49 & \to & 10, 9, 8, 7, 6, 4, 3, 2 \\ 50 & \to & 10, 9, 8, 7, 6, 5, 3, 2 \end{array}

Алгоритм видится такой: заполняем слагаемые числами $2,3,4,\ldots$, пока возможно, а потом прибавляем к ним единицы, идя от большего слагаемого к меньшему. Если единицы не кончились за первый проход, делаем ещё один. Остаётся только доказать, что он верный.

-- Пн янв 07, 2013 20:17:17 --

(Прошу простить за обратный порядок слагаемых. Надеюсь, он не мешает.)

 
 
 
 Re: Логическая задача
Сообщение07.01.2013, 17:25 
Shadow в сообщении #668009 писал(а):
$2+3+4+\cdots$ Пока сумма не станет больше либо равна нашему числу. А если больше, то..
убираем избыточное число. Если избыточное 1, убираем двойку и увеличиваем наибольшее на 1. Результат такой же, как у arseniiv,VAL. А вот совсем строгое доказательство не получается у меня. Слишком много "очевидно, что :D "

 
 
 
 Re: Логическая задача
Сообщение07.01.2013, 17:41 
arseniiv в сообщении #668466 писал(а):
Иногда лучшее представление начинается с 3.
Разумеется.
Цитата:
Если единицы не кончились за первый проход, делаем ещё один.
Угу.
Этот случай я прозевал (забыл, что слагаемые с двойки идут).
Он возникает в точности для чисел на 2 меньших треугольных.

 
 
 
 Re: Логическая задача
Сообщение07.01.2013, 18:02 
Кстати, в задаче число слагаемых ровно заданное $k$. А мы, если не ошибаюсь, решали задачу для всех разбиений… :?

Если $k = 2$, то лучше чем на почти равные половины ($n \mapsto (\lfloor \frac{n-1}2 \rfloor, \lfloor \frac n2 \rfloor + 1)$) не разбить, но это и так понятно.

(Оказывается, всё просто, хотя установил это не я. Впрочем, мой алгоритм всё равно остаётся применим, если не ошибаюсь.)

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group