Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: мат задача, комбинаторика  (Прочитано 26764 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mayor
Специалист

ru
Offline Offline

« : 22-03-2008 18:42 » 

мат задача, комбинаторика

условия задачки просты: сколькими способами можно разместить n одинаковых элементов, между m лунками?

решается тоже просто методом простой итерации ...

вопрос какой формулой она решается аналитически?

если нет формулы то как ее решить итеративно за n или m шагов?
Записан

1n c0de we trust
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 22-03-2008 19:46 » 

Mayor1, а что означает - "между m лунками"  ?
Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 22-03-2008 20:15 » 

Mayor1, поиск рулит, вики тоже в меру сил: Размещение Ага
Записан
Mayor
Специалист

ru
Offline Offline

« Ответ #3 : 23-03-2008 09:56 » 

Mayor1, поиск рулит, вики тоже в меру сил: Размещение Ага

неправильная ссылка - там размещаются не однородные элементы
в этой задаче однородные

Записан

1n c0de we trust
Mayor
Специалист

ru
Offline Offline

« Ответ #4 : 23-03-2008 09:58 » 

Mayor1, а что означает - "между m лунками"  ?

емкость или что тебе угодно, любая из m лунок может принять от 0 до n элементов ...
но по задаче сумма элементов в лунках равна n
Записан

1n c0de we trust
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #5 : 23-03-2008 10:34 » 

если представить в виде функции N(m,n) , то , вроде бы, выходит такое рекурсивное определение

N(m+1,n) == 3 * ( N(m,n)+ N(m-1,n-1)+...+ N(m-1,0))

где N(m,0) ==
  1 при m>0
  0 при m<=0

на рисунке: слева - m==2, n==3  ; справа: m==3, n==3


* mn.PNG (21.34 Кб - загружено 2939 раз.)
« Последнее редактирование: 23-03-2008 11:09 от Алексей1153++ » Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #6 : 23-03-2008 11:04 » 

вот, подправил


тогда

N(3,3) == N(2+1,3) == 3* ( N(2,3) + N(1,2) + N(1,1) +1 ) == 3*(4+1+1+1) == 21

не, всё равно фигня вышла (((
« Последнее редактирование: 23-03-2008 11:13 от Алексей1153++ » Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #7 : 23-03-2008 11:13 » 

Mayor1, ну, превращаем размещение в сочетание, если ничего не путаю.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #8 : 23-03-2008 11:17 » 

и понятно почему фигня - там повторные комбинации на рисунке, как их учесть - фик знает

Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #9 : 23-03-2008 11:31 » 

Вообще, по-моему, задачу нужно рассматривать не как размещение n позиций m по лункам, а как размещение m-1 лунок по n+1 позициям Улыбаюсь
Тогда требуется посчитать, каким числом способов можно вставить m-1 лунку на n+1 позицию "между элементами" (включая позицию "до всех" и "после всех"). Задача аналогична задаче нахождения количества возможных чисел из m+n-1 разрядов, содержащих (m-1) нулевых разрядов и n ненулевых разрядов. (Одну "лунку" в расчёт не принимаем, она всегда находится "в конце"). Иллюстрация примерно такая: <0> 1 <0> 1 <0> ... <0> 1 <0> 0, где <0> - возможное место вставки одного и более нулей. Если лунки тоже полагаем одинаковыми (в том смысле, что для двух лунок безразлично, в первой или во второй лежат все элементы) - вот тогда используем сочетание уже. Из твоей задачи одинаковость неочевидна Улыбаюсь
« Последнее редактирование: 23-03-2008 11:34 от Вад » Записан
Вахмурка
Помогающий

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #10 : 23-03-2008 13:15 » 

 Задача сводится к нахождению максимального значения n-разрадного числа + 1, с основанием исчесления m т. е. m^n . Если я правильно задание понял.
« Последнее редактирование: 23-03-2008 13:23 от Вахмурка » Записан

Программа – это мысли спрессованные в код.
Mayor
Специалист

ru
Offline Offline

« Ответ #11 : 23-03-2008 20:18 » 

Задача сводится к нахождению максимального значения n-разрадного числа + 1, с основанием исчесления m т. е. m^n . Если я правильно задание понял.

неа не правильно понял

формулу нашли, только я не понял как:
f(n,m) = (n+1)*(n+2)* ... (n+m-1) / m!    - как ее можно было вывести?

вот проверка для m==4:
Код:
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
int main() {
int elem,cell;
int count=0;
for (int elem=1;elem<10;elem++) {
count=0;
for (int q=0;q<=elem;q++) {
for (int z=0;z<=elem;z++) {
for (int x=0;x<=elem;x++) {
for ( int y=0;y<=elem;y++) {
if (x+y+z+q==elem) {
cout<<q<<"\t"<<z<<"\t"<<x<<"\t"<<y<<endl;
count++;
}
}
}
}
}
cout<<elem<<"\t"<<count<<endl<<endl;
}
}
Записан

1n c0de we trust
Вахмурка
Помогающий

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #12 : 23-03-2008 20:46 » 

  Если n - неоднородные элементы, то количество способов равно m^n где m - количество позиций. Если элементы однородные, то из этого выражения нужно вычесть все комбинации чисел которые выводятся друг из друга перестановкой цифр. Например при n =2 97 и 79 дают одну комбинацию, значит одно из них можно удалить. Всё усложняется при увелечении n. Например при n =3 нужно расматривать не только пары чисел, но и тройки. Отсюда рекурсивность формулы. Вот такие вот мысли.
Записан

Программа – это мысли спрессованные в код.
Вахмурка
Помогающий

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #13 : 23-03-2008 21:25 » 

 Есть типа ещё одна идея: сначало написать алгоритм, а потом по нему попробовать вывести формулу. Правдо мне такими вещами заниматься не приходилось.
Записан

Программа – это мысли спрессованные в код.
Вахмурка
Помогающий

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #14 : 23-03-2008 23:12 » 

Рекурсивно задача довольно таки просто решается: прдеставляем что пересыпаем элементы из одной лунки в другую. Если за количество позиций принять m то получается вот такой код:

Код:
class Test {
   static int metod ( int n, int m ) {
      if ( m == 1 )
         return 1 ;
      int k = 0 ;
      for ( ; n > 0 ; n -- )
         k += metod ( n, m - 1 ) ;
      return k + 1 ;
    }
}
« Последнее редактирование: 23-03-2008 23:27 от Вахмурка » Записан

Программа – это мысли спрессованные в код.
Mayor
Специалист

ru
Offline Offline

« Ответ #15 : 25-03-2008 08:24 » 

  Если n - неоднородные элементы, то количество способов равно m^n где m - количество позиций. Если элементы однородные, то из этого выражения нужно вычесть все комбинации чисел которые выводятся друг из друга перестановкой цифр. Например при n =2 97 и 79 дают одну комбинацию, значит одно из них можно удалить. Всё усложняется при увелечении n. Например при n =3 нужно расматривать не только пары чисел, но и тройки. Отсюда рекурсивность формулы. Вот такие вот мысли.

угу ... есть у кого идеи как можно было вывести эту формулу:
f(n,m)= ((n+m)!-n!)/n!
Записан

1n c0de we trust
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #16 : 25-03-2008 08:45 » 

Mayor1,  f(n,m)= ((n+m)!-n!)/n! = ((n+m)! / n!) - 1? Улыбаюсь Это точно так будет?
Записан
Sands
Помогающий

ua
Offline Offline

« Ответ #17 : 25-03-2008 09:01 » 

Mayor1, По моему формула немного ошибочна, потому что если взять 2 лунки и 2 элемента, то по цормуле выходит ((2+2)!-2!)/2!=(12-2)/2=5
но(если я правильно пощитал)таких размещений всего 3 - (2,0);(1,1);(0,2)
Записан
Mayor
Специалист

ru
Offline Offline

« Ответ #18 : 12-04-2008 16:12 » 

Mayor1, По моему формула немного ошибочна, потому что если взять 2 лунки и 2 элемента, то по цормуле выходит ((2+2)!-2!)/2!=(12-2)/2=5
но(если я правильно пощитал)таких размещений всего 3 - (2,0);(1,1);(0,2)

Да точно
F(n,m)=(n+1)*(n+2)*...(n+m-1)/((m-1)!)
это будет более правильный вариант
« Последнее редактирование: 12-04-2008 16:15 от Mayor » Записан

1n c0de we trust
Sands
Помогающий

ua
Offline Offline

« Ответ #19 : 13-04-2008 20:48 » new

Mayor1, Судя по формуле F(n,m)=(n+m-1)!/((m-1)!*(n)!) = C(m-1,n+m-1) Что собственно и было предложено Вадом,(ну почти так Улыбаюсь ) несколькими постами выше(если конечно я его правильно понял)
« Последнее редактирование: 13-04-2008 20:50 от Sands » Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines