Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
#1

Комбинаторика! Число сочитаний - C++

08.08.2012, 19:55. Просмотров 2539. Ответов 40
Метки нет (Все метки)

Доброго времени суток. Так как я глубоко начинающий программист, столкнулся с проблемой решения задач по комбинаторике (на данный момент формула числа сочитаний). Каким образом можно записать эту формулу на С++, знаю имееться много способов (через рекурсию и т.д.)? Можете, пожалуйста, написать реализацию и объяснить? Вот пример через рекурсию, но никак не пойму принцип работы, объясните? Сама задача вот, на тестах неверный ответ, а на других лимит времени исчерпан, проверил не правильный ответ на нечетных числах и на числе 2, объясните, пожалуйста, принцип рекурсии здесь, а не просто решите задачу! Пожалуйста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream.h>
#include <stdio.h>
int rec(int n, int k)
{
    if(n==k)
        return 1;
    if(k==1)
        return n;
    return rec(n-1, k-1)+rec(n-1, k);
}
 
int main()
{
    int n, k;
    cin>>n>>k;
    k=n/2;
    cout<<rec(n,k);
 
 
return 0;
}
П.с. Простите что задаю столь глупый вопрос, но увы никто не может мне объснить (поскольку таких просто нет, мой учитель в лицее не имеет желания работать, все приходиться розпрашивать, но почти всегда ответ один: "Ты этого не знаешь иди почитай эту книгу!", я уже прочитал за эти 2 года огромное количество книг, начиная от основ программирования и заканчивая дискретной математикой. А два других учителя, пока никак со мной не связаны из вузов. Вот и не знаю как же мне программистом стать, если никто не может объяснить!), поэтому буду часто спрашивать. Обидно ведь, когда посылают на олимпиаду, а там все задачи на листочке решил (математически), а как написать программу не знаешь
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.08.2012, 19:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Комбинаторика! Число сочитаний (C++):

Комбинаторика, вычислить число сочетаний C(N, K) - C++
When I was in army, sometimes (about once a week) our unit was faced a charming alternative: most of the hands are to be sent to...

Комбинаторика.Подсчитать число размещений с повторениями - C++
#pragma hdstop #pragma argsused #include &lt;math.h&gt; #include &lt;tchar.h&gt; #include &lt;iostream.h&gt; #include &lt;conio.h&gt; Long double fact...

комбинаторика - C++
Здравствуйте! Я решаю задачи по дискретной математике на языке С.В интернете масса примеров задач на тему комбинаторики, но на языке...

Комбинаторика на С++ - C++
Нужно составить программу, или скорее функцию, которая для заданного натурального числа k выводит все возможные произведения k чисел с...

Комбинаторика - C++
От пользователя требуется ввести n. Результат должен быть таким:

Комбинаторика - C++
Здравствуйте все. В данный момент дпополнительно решил заняться комбинаторикой, столкнулся с задачей, и никак не могу её решить.Суть...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
-=ЮрА=-
13.08.2012, 14:50     Комбинаторика! Число сочитаний
  #16

Не по теме:

Цитата Сообщение от mr_free Посмотреть сообщение
Вот сейчас решаю задачку и вроде все сделал правильно, но при вводе любых четных чисел (n), всегда выводиться n! Что не так пишу, прошу делать замечания на представленом коде и не вносить другие переменные и т.п.? Подскажите, пожалуйста, с этим и вопрос снят!
- покажи мне что ты вводишь и что получаешь

mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
13.08.2012, 15:47  [ТС] #17
-=ЮрА=-, скрин сделать не могу, но вот что я ввожу и что получаю:
Код
Ввожу: 4 3
Получаю: 4
Ввожу: 4 2
Получаю: 4
Ввожу: 5 2
Получаю 7.5
Ввожу: 6 2
Получаю 6
kravam
быдлокодер
1694 / 881 / 44
Регистрация: 04.06.2008
Сообщений: 5,441
13.08.2012, 16:01 #18
Цитата Сообщение от mr_free Посмотреть сообщение
интересно а как насчет быстродействия даного метода? точность как я понял горантирована!
Не ну как- точность гарантирована настолько, насколько она вообще может быт гарантирована при работаешь с дробными числами (если работаешь с ними). Не более, но и не менее.

Насчёт скорости- чёрт его знает, откровеннно говоря. Тут надо хорошо разбираться в этом чтобы делать какие-то выводы. Вот подсчёт факориала рекурсией
C++
1
2
3
4
5
6
int fact(int n)  {
 if(n <= 1)
   return 1;
 else 
 return n * fact(n - 1);
}
А вот в цикле
C++
1
2
3
4
5
6
int fact(int n)  {
 int fact_= 1;
 for (int i= 1; i<= n; i++)
  fact_*= i;
 return fact_;
}
Явно тут нет выигрыша во времени ни в каком варианте. А вот неявно неплохой выигрыш, вот эта инструкция:
C++
1
return n * fact(n - 1);
Как ты знаешь, все переменные размещаются в ячейках памяти. И с ними происходят операции, задействуя регистры. А вот здесь можно предположить, что операции будут происходить СРАЗУ С РЕГИСТРОМ EAX (это много быстрее, нежели работать с памятью), ибо вот это значение fact(n - 1) будет всякий раз по окончании функции оказываться в регистре. И его сразу можно множить на n

Но это только предположения. Ничто не мешает компилятору задействовать ячейку памяти для данной задачи (под возвращаемое значение) и тогда скорость упадёт.
Ну и так далее.

+++++++++++++++++++++++++++++++++++++++++++++++++++

Уж лучше проверь руками. Наверное, есть какие-то специальные функции чтобы узнать, сколько времени длится та или иная программа. Но я парень простой, я бы сделал примерно так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main () {
 
 for (int i= 0; i< 100; i++)
  for (int i= 0; i< 100; i++)
   for (int i= 0; i< 100; i++)
    for (int i= 0; i< 100; i++)
     fact (5);
 
 system ("pause");
 
 
 for (int i= 0; i< 100; i++)
  for (int i= 0; i< 100; i++)
   for (int i= 0; i< 100; i++)
    for (int i= 0; i< 100; i++)
     fact_ (5);
 
 system ("pause");
 
 return 0;
}
Смысл понятен, я думаю. Время отслеживается на раз, знай фиксируй.
-=ЮрА=-
Заблокирован
Автор FAQ
13.08.2012, 16:06 #19
Цитата Сообщение от mr_free Посмотреть сообщение
if(1 < (n = 1))
- это не мой код!Я такой ошибки не делал, тут что должно быть, ммм??

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
if(1 < (n -= 1))
- если изменяем мои коды, не надо удивлять что рабоатет потом не верно, поправь а потом посмотрим будет баг или нет...
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
13.08.2012, 16:18  [ТС] #20
-=ЮрА=-, также само работает программа, а это я изменял от безвыходности, поскольку не сильно понимаю сокращенные записи!

Добавлено через 6 минут
Забылся там, после этого изменения будет такой ответ для тестов:
Код
Вводим 4 2
Получаем 24
-=ЮрА=-
Заблокирован
Автор FAQ
13.08.2012, 16:20 #21
Цитата Сообщение от mr_free Посмотреть сообщение
-=ЮрА=-, также само работает программа, а это я изменял от безвыходности, поскольку не сильно понимаю сокращенные записи!
- я не знаю что ты менял и почему у нас разные отработки, вот ещё раз мой же код под ручной ввод(в котором абсолютно ничего не менял)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;
 
double fact(unsigned long n);
double C   (unsigned long n, unsigned long k);
 
int main()
{
    int N = 0;
    int S = 0;
    cout<<"Enter N S : ";;
    if(!(cin>>N>>S))
       cout<<"Error in input\n";
    else
       cout<<"Input  : "<<N<<" "<<S<<endl;
    if(N < S)
       cout<<"Incorrect input params\n";
    else
       cout<<"Output : "<<C(N, S)<<endl;
    return 0;
}
 
double fact(unsigned long n)
{
    double c = (n < 1) ?  1 : n;
    if(1  < (n -= 1))
        c *= fact(n);
    return c;
}
 
double C(unsigned long n, unsigned long k)
{
    return fact(n)/(fact(k)*fact(n - k));
}
Миниатюры
Комбинаторика! Число сочитаний  
-=ЮрА=-
Заблокирован
Автор FAQ
13.08.2012, 16:23 #22
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
double fact(unsigned long n)
{
* * double c = (n < 1) ? *1 : n;
* * if(1 *< (n -= 1))
* * * * c *= fact(n);
* * return c;
}
- это расчёт факториала
Это расчёт числа сочетаний
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
return fact(n)/(fact(k)*fact(n - k));
n!/(k!*(n - k)!)
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
13.08.2012, 16:36  [ТС] #23
-=ЮрА=-, это я все понял! Единственное что я поменял так это, не ручной ввод и все + подстроился под задачу, в ней вводиться n k( вообще не к чему), я создаю левую переменную s=n/2, как надо по задачи и остальное не трогаю меняю лишь k на s! Наверно что-то не так с s=n/2 и сдесь идет сбой вычисления?
Вот мой код еще раз: (гляньте, пожалуйста)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
double fact(unsigned long n);
double C   (unsigned long n, unsigned long s);
int main()
{
    unsigned long n,k;
    cin>>n>>k;
    unsigned long s=n/2;
    cout<<C(n,s);
    return 0;
}
double fact( unsigned long n)
{  double c = (n < 1) ?  1 : n;
    if(1  < (n -= 1))
        c *= fact(n);
    return c;
}
double C (unsigned long n, unsigned long s)
{
    return fact(n)/fact(s)*fact(n-s);
}
-=ЮрА=-
Заблокирован
Автор FAQ
13.08.2012, 16:59 #24
mr_free, ты понимаешь что всегда подставляешь N и S = N/2, смысл вообще ввода переменной k???Уже готовый код привёл готовый код в посте 21, поставим вопрос по другом - что тебя не устаривает в его отработке?

Добавлено через 1 минуту
Цитата Сообщение от mr_free Посмотреть сообщение
cin>>n>>k;
* * unsigned long s=n/2;
cout<<C(n,s);
- вот как у тебя участвует в расчётах k
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
13.08.2012, 21:15  [ТС] #25
k в расчетах не участвует, в условие просто дано k, а в дальнейшем при ришение оно не где не используеться!
-=ЮрА=-
Заблокирован
Автор FAQ
14.08.2012, 11:05 #26
Цитата Сообщение от mr_free Посмотреть сообщение
k в расчетах не участвует, в условие просто дано k, а в дальнейшем при ришение оно не где не используеться!
да нет тут ты не прав
Пораскинув ещё раз мозгами пришёл к выводу что число способов равно просто факториалу числа ящиков, а не числу сочетаний
Смотри по примеру в той ссылке 4 шара 3 ящика
Шары 1 2 3 4
Возможные варианты размещений
ящик1 1 4 12 12 1 2
ящик2 23 23 3 4 2 1
ящик3 4 1 4 3 34 34
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
 
double fact(unsigned long n);
 
int main()
{
    int N = 0;
    int S = 0;
    cout<<"Enter N S : ";;
    if(!(cin>>N>>S))
       cout<<"Error in input\n";
    else
       cout<<"Input  : "<<N<<" "<<S<<endl;
    if(N < S)
       cout<<"Incorrect input params\n";
    else
       cout<<"Output : "<<fact(S)<<endl;
    return 0;
}
 
double fact(unsigned long n)
{
    double c = (n < 1) ?  1 : n;
    if(1  < (n -= 1))
        c *= fact(n);
    return c;
}
Миниатюры
Комбинаторика! Число сочитаний  
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
14.08.2012, 17:49  [ТС] #27
-=ЮрА=-, только там конфеты и я отправил два ваших варианта решения, но в этих решениях ответ засчитан только один (первый)! Что не так?
-=ЮрА=-
14.08.2012, 17:57
  #28

Не по теме:

Цитата Сообщение от mr_free Посмотреть сообщение
-=ЮрА=-, только там конфеты и я отправил два ваших варианта решения, но в этих решениях ответ засчитан только один (первый)! Что не так?
- ну я бегло тогда условие читанул, конфеты шары, какая разница. Напиши конкретно какие результаты защитаны какие не защитаны...

mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
14.08.2012, 18:06  [ТС] #29
Из 50 тестов засчитано одно, вывода какой именно тест засчитан нет, наверное, это 4 3!

-=ЮрА=-, Какие есть размышления?
-=ЮрА=-
14.08.2012, 20:45     Комбинаторика! Число сочитаний
  #30

Не по теме:

Цитата Сообщение от mr_free Посмотреть сообщение
Из 50 тестов засчитано одно, вывода какой именно тест засчитан нет, наверное, это 4 3!
- http://www.e-olimp.com/problems/65
Пример входных данных
4 3
Пример выходных данных
6
Посмотри на отработку последнего кода!

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2012, 20:45
Привет! Вот еще темы с ответами:

Комбинаторика - C++
Доброго всем времени суток!Помогите пожалуйста с решением такой задачи.Дана последовательность вещественных чисел.Пользователь вводит...

Комбинаторика - C++
Помогите написать алгоритм для вычисления количество непустых последовательностей из ряда чисел. Или кинте ссылочку, где почитать. Что я...

Комбинаторика в программировании - C++
есть алфавит длинны Х; длинна слова Y; написать код(лучше на с++) который будет составлять и выводить все возможные варианты слов. ...

Комбинаторика. Сочетания - C++
Добрый день! Прошу помочь со следующей задачкой: генерация сочетания по номеру(порядок лексикографический). Толковое объяснение нашел...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.08.2012, 20:45
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru