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

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

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

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

08.08.2012, 19:55. Просмотров 2524. Ответов 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(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++
Здравствуйте! Я решаю задачи по дискретной математике на языке С.В интернете масса примеров задач на тему комбинаторики, но на языке...

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6444 / 3083 / 306
Регистрация: 04.12.2011
Сообщений: 8,494
Записей в блоге: 4
08.08.2012, 20:21     Комбинаторика! Число сочитаний #2
http://www.cyberforum.ru/cgi-bin/latex.cgi?{C_n}^k=\frac{n!}{(n-m)! \cdot k!}



C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
//Рекурсивная функция для подсчёта m!:
int fctrl(int m){
if(m==0||m==1) return 1;
return (m*fctrl( m-1));
}
 
int main()
{
int n, k;c=0;
cin>>n>>k;
c=fctrl(n)/(fctrl(n-k)*fctrl(k));
cout<<c;
return 0;
}
необходимые проверки вроде n<k, включите сами.
Принцип рекурсии состоит в том, что функции разрешено вызывать самую себя. Функция возвращающая значение - выражение результат которого подставляется в место вызова. В классическом примере - подсчете факториала, функция вызывается до тех пор пока аргумент не станет 1 и не наткнется на первое условие выхода из функции (нерекурсивная ветвь алгоритма).
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
08.08.2012, 20:47  [ТС]     Комбинаторика! Число сочитаний #3
Цитата Сообщение от IGPIGP Посмотреть сообщение
http://www.cyberforum.ru/cgi-bin/latex.cgi?{C_n}^k=\frac{n!}{(n-m)! \cdot k!}



C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
//Рекурсивная функция для подсчёта m!:
int fctrl(int m){
if(m==0||m==1) return 1;
return (m*fctrl( m-1));
}
 
int main()
{
int n, k;c=0;
cin>>n>>k;
c=fctrl(n)/(fctrl(n-k)*fctrl(k));
cout<<c;
return 0;
}
необходимые проверки вроде n<k, включите сами.
Принцип рекурсии состоит в том, что функции разрешено вызывать самую себя. Функция возвращающая значение - выражение результат которого подставляется в место вызова. В классическом примере - подсчете факториала, функция вызывается до тех пор пока аргумент не станет 1 и не наткнется на первое условие выхода из функции (нерекурсивная ветвь алгоритма).
Коротко и ясно, спасибо! Сам буду в следуйщий раз писать короче, а то написал прям статью! Сейчас по колдую, но вроде стало ясно А вот ссылка на саму задачу http://www.e-olimp.com/problems/65
Но лишь одно смущает, скорость работы, может есть вариант более быстрый?

Добавлено через 4 минуты
Да, и ваш вариант лобовой и не верный, аж четыре ошибки! Что не так?

Добавлено через 3 минуты
Да, и что за переменная m?
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6444 / 3083 / 306
Регистрация: 04.12.2011
Сообщений: 8,494
Записей в блоге: 4
08.08.2012, 21:02     Комбинаторика! Число сочитаний #4
Цитата Сообщение от IGPIGP Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
//Рекурсивная функция для подсчёта m!:
int fctrl(int m){
if(m==0||m==1) return 1;
return (m*fctrl( m-1));
}
int main()
{
int n, k;c=0;
cin>>n>>k;
c=fctrl(n)/(fctrl(n-k)*fctrl(k));
cout<<c;
return 0;
}
извините не компилировал.
вот с исправлениями:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
//Рекурсивная функция для подсчёта m!:
int fctrl(int m){
if(m==0||m==1) return 1;
return (m*fctrl( m-1));
}
int main()
{
int n, k, c=0;//тут запятая вмст кавычек
std::cin>>n>>k;//std 
c=fctrl(n)/(fctrl(n-k)*fctrl(k));
std::cout<<"\n"<<c;//std 
std::system("pause");//std - пауза 
return 0;
}
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
08.08.2012, 21:35  [ТС]     Комбинаторика! Число сочитаний #5
Разобрался со всем спасибо Но теперь хотелось бы еще подстроиться под задачу! Тесты теперь вообще не проходят, неверный ответ+ ошибка компиляции, как избавиться от ошибки компиляции? http://www.e-olimp.com/solutions/733293
Не верный ответ я знаю почему, поскольку не учел нечетные числа, но там есть тест с двойкой, и он видимо тоже не проходит, что нет так?
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
10.08.2012, 16:47  [ТС]     Комбинаторика! Число сочитаний #6
Ау, кто-то поможет?
-=ЮрА=-
Заблокирован
Автор FAQ
10.08.2012, 16:58     Комбинаторика! Число сочитаний #7
mr_free, вот пройди почитай
http://www.cyberforum.ru/blogs/34326/blog232.html
тебе надо СSN/2

Добавлено через 4 минуты
http://liveworkspace.org/code/f953d7...01a04a590ae0a7
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
10.08.2012, 18:41  [ТС]     Комбинаторика! Число сочитаний #8
Я знаю какая формула мне нужна (можно было посмотреть самое первое сообщение, сам код)!

Добавлено через 4 минуты
Но вообщем спасибо Будет время проверю! Посмотрите, пожалуйста, мой же вопрос (Работа со звуком! Ошибка! SOS!), может поможете?!
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.08.2012, 20:51     Комбинаторика! Число сочитаний #9
Цитата Сообщение от mr_free Посмотреть сообщение
объясните, пожалуйста, принцип рекурсии здесь
вы просто неправильно используйте условия выхода из рекурсии. вашу функцию надо немного переделать
C++
1
2
3
4
5
6
7
8
int rec(int n, int k)
{
   if (n < 1 || k < 0 || n < k)
      return 0;
   if(n == 1 || k == 0 || n == k)
      return 1;
   return rec(n - 1, k - 1) + rec(n - 1, k);
}
kravam
быдлокодер
1693 / 880 / 44
Регистрация: 04.06.2008
Сообщений: 5,439
10.08.2012, 22:11     Комбинаторика! Число сочитаний #10
Не советую использовать рекурсию в подобных задачах. Так, чисто для себя если, чтобы РАЗРОБРАТЬСЯ что и как, не более того.
-=ЮрА=-
Заблокирован
Автор FAQ
10.08.2012, 22:41     Комбинаторика! Число сочитаний #11
mr_free, по вашему вопросу, ещё раз приведу свой код, дабы вы поняли что в своём тесте я поставил
N = 65 а S = 5
Теперь смотрите отработку под
N = 4 S = 3
http://liveworkspace.org/code/96eed4...6146a9571c5fc7
Если хотите более понятный в плане логики код, тогда вот он, считает он также
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()
{
   char data[] = "4 3";
   int N = 0;
   int S = 0;
   if( sscanf(data,"%d %d",&N,&S) == EOF)
       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));
}
Для меня лишь непонятен ответ на том ресурсе 6
PS:Корректная формула числа сочетаний здесь http://ru.wikipedia.org/wiki/Сочетание
Миниатюры
Комбинаторика! Число сочитаний  
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
12.08.2012, 20:33  [ТС]     Комбинаторика! Число сочитаний #12
Благодарю, и простите что не отписался о том что разобрался!
-=ЮрА=-, а почему вам не понравился ответ на том ресурсе? вы имеете в виду e-olimp?
Да, и еще почему в данных задачах не стоит использовать рекурсию?
Хм, что-то я не понял ответа 4?
Ответ не правильный у вас поскольку число 3 не испьлзуеться при ришении задачи, это просто не нужный параметр,
в задачи идет подсчет числа сочитаний n/2 из n
-=ЮрА=-
12.08.2012, 20:45
  #13

Не по теме:

Цитата Сообщение от mr_free Посмотреть сообщение
Да, и еще почему в данных задачах не стоит использовать рекурсию?
- это была фраза karavam и я просто не стал её критиковать, по причине игнорирования мной данного пользователя. В том виде котором рекурсию подаля я её можно использовать. Ну а так да, рекурсия - это дело тонокое и надо так сказать для него "набить руку" (при сбое или недоработки логики окончания рекурсия может приводить к зацикливаниюалгоритма без какой-либо возможности что либо остановить в работающем "зацикленном" алгоритме)

kravam
быдлокодер
1693 / 880 / 44
Регистрация: 04.06.2008
Сообщений: 5,439
13.08.2012, 05:31     Комбинаторика! Число сочитаний #14
Цитата Сообщение от 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
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <windows.h>
#include <stdio.h>
#define kolichestvo_chisel 9
#define kolichestvo_drugih_chisel 7
using namespace std;
 
int kk= 0;
 
 
 
void func_recurs (int nomer_funktsii, int nomer_elementa, int kol_ostavshihsa_chisel,  int* stroka, int* array) {
 
 printf ("%x\n", &nomer_funktsii);
 kk++;
 
 for (int i= nomer_elementa; i< kolichestvo_chisel- kol_ostavshihsa_chisel+ 1; i++) {
 
  if (nomer_funktsii< kolichestvo_drugih_chisel- 1) {
   array [nomer_funktsii]= stroka [i];
   for (int j= 0; j< kk; j++)
    printf (" ");
   func_recurs (nomer_funktsii+ 1, i+ 1, kol_ostavshihsa_chisel- 1, stroka, array);
  }
 
  else {
   array [nomer_funktsii]= stroka [i];
//   for (int i= 0; i< kolichestvo_drugih_chisel; i++)
//    printf ("%d ", array [i] );
//    printf ("\n");
  }
 }
 
 kk--;
}
 
 
int main () {
 
 int stroka []= {21, 34, 20, 12, 3, 2, 7, 67, 56};
 int array [kolichestvo_drugih_chisel];
 func_recurs (0, 0, kolichestvo_drugih_chisel, stroka, array);
 
 
 
 getchar ();
 return 0;
}
И вывод смотри, эти ступеньки- эта глубина рекурсии. И как видишь, углубление происходит всё дальше и дальше в стек и однажды он переполнится (вправо по ступенькам)
...Я сделал, чтобы глубина рекурсии была не больше kolichestvo_drugih_chisel. Это фигня, это очень мало. Стек не переполнится. Но ведь это я СДЕЛАЛ. (Видишь, использовал ЦИКЛ+ рекурсию). А можно было бы и не сделать, обойтись одной рекурсией и пиши пропало, ступеньки вылетели бы туда непонятно куда и крах программы.

И да, время отладки она вылетала у меня не раз и не два из-за переполнения стека (ошибка трудноуловимая). А если ты вместо рекурсии используешь цикл, одной проблемой меньше.
Миниатюры
Комбинаторика! Число сочитаний  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.08.2012, 14:20     Комбинаторика! Число сочитаний
Еще ссылки по теме:

Перестановка.(Комбинаторика) - C++
Прошу помощи. Объясните пожалуйста тугодуму этот код. Какой день его пытаюсь понять. Не как не могу в нём разобраться. Вроде знаю как...

Покерная комбинаторика - C++
Добрый день, форумчане. Рад возможности стать членом общества программистов. Я чайник на все 234%. Болею задачей создания покерной...

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

Комбинаторика style - C++
Здравствуйте, помогите разобраться с задачей по комбинаторике. Условие: http://codeforces.com/problemset/problem/630/F Решение: ...

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


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

Или воспользуйтесь поиском по форуму:
mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
13.08.2012, 14:20  [ТС]     Комбинаторика! Число сочитаний #15
Хм, а ведь действительно так Вот наконец выдолась свободная минутка и можно дорешать задачу и подумать над замечанием! Благодарю за помощь! Если будут вопросы, обязательно задам!
P.s. тема пока не закрыта!

Добавлено через 2 часа 15 минут
Вот сейчас решаю задачку и вроде все сделал правильно, но при вводе любых четных чисел (n), всегда выводиться n! Что не так пишу, прошу делать замечания на представленом коде и не вносить другие переменные и т.п.? Подскажите, пожалуйста, с этим и вопрос снят!
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);
}
-=ЮрА=-, подскажи, ведь это твой метод решения
kravam, интересно а как насчет быстродействия даного метода? точность как я понял горантирована!
Yandex
Объявления
13.08.2012, 14:20     Комбинаторика! Число сочитаний
Ответ Создать тему
Опции темы

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