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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
08.08.2012, 19:55     Комбинаторика! Число сочитаний #1
Доброго времени суток. Так как я глубоко начинающий программист, столкнулся с проблемой решения задач по комбинаторике (на данный момент формула числа сочитаний). Каким образом можно записать эту формулу на С++, знаю имееться много способов (через рекурсию и т.д.)? Можете, пожалуйста, написать реализацию и объяснить? Вот пример через рекурсию, но никак не пойму принцип работы, объясните? Сама задача вот, на тестах неверный ответ, а на других лимит времени исчерпан, проверил не правильный ответ на нечетных числах и на числе 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++
C++ Комбинаторика на С++
комбинаторика в программировании C++
C++ Комбинаторика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6167 / 2896 / 282
Регистрация: 04.12.2011
Сообщений: 7,697
Записей в блоге: 3
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
 Аватар для 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
Комп_Оратор)
 Аватар для IGPIGP
6167 / 2896 / 282
Регистрация: 04.12.2011
Сообщений: 7,697
Записей в блоге: 3
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
 Аватар для 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
 Аватар для 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
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
10.08.2012, 18:41  [ТС]     Комбинаторика! Число сочитаний #8
Я знаю какая формула мне нужна (можно было посмотреть самое первое сообщение, сам код)!

Добавлено через 4 минуты
Но вообщем спасибо Будет время проверю! Посмотрите, пожалуйста, мой же вопрос (Работа со звуком! Ошибка! SOS!), может поможете?!
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 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
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
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
 Аватар для 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
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
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. Это фигня, это очень мало. Стек не переполнится. Но ведь это я СДЕЛАЛ. (Видишь, использовал ЦИКЛ+ рекурсию). А можно было бы и не сделать, обойтись одной рекурсией и пиши пропало, ступеньки вылетели бы туда непонятно куда и крах программы.

И да, время отладки она вылетала у меня не раз и не два из-за переполнения стека (ошибка трудноуловимая). А если ты вместо рекурсии используешь цикл, одной проблемой меньше.
Миниатюры
Комбинаторика! Число сочитаний  
mr_free
 Аватар для 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, интересно а как насчет быстродействия даного метода? точность как я понял горантирована!
-=ЮрА=-
13.08.2012, 14:50
  #16

Не по теме:

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

mr_free
 Аватар для 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
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
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))
- если изменяем мои коды, не надо удивлять что рабоатет потом не верно, поправь а потом посмотрим будет баг или нет...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.08.2012, 16:18     Комбинаторика! Число сочитаний
Еще ссылки по теме:

Комбинаторика C++
C++ Комбинаторика. Сочетания
Комбинаторика.Подсчитать число размещений с повторениями C++

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

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

Добавлено через 6 минут
Забылся там, после этого изменения будет такой ответ для тестов:
Код
Вводим 4 2
Получаем 24
Yandex
Объявления
13.08.2012, 16:18     Комбинаторика! Число сочитаний
Ответ Создать тему
Опции темы

Текущее время: 21:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru