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

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

Войти
Регистрация
Восстановить пароль
 
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
#1

Функция комбинаторики.... - C++

09.04.2009, 21:32. Просмотров 774. Ответов 5
Метки нет (Все метки)

Помогите написать программу, вычисляющую C(n,k)=n!/(k!*(n-k)!), где 1<=N,K,<=500...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.04.2009, 21:32     Функция комбинаторики....
Посмотрите здесь:

Реализация комбинаторики - C++
Задача имеет следующий вид. Есть набор строка символов неопределенной(заранее) длины. Нужно из данной строки подсчитать и вывести все...

Элементы Комбинаторики - C++
Даны натуральные числа a1,...a10. Предположим что имеется 10 монет достоинством a1,...,a10. Обозначим через bk число способов, которыми...

Работа с формулами комбинаторики - C++
Совершенно не представляю как это сделать, но нужно очень. Если кому по силам ... :cry: - Разработать класс для работы с формулами...

Реализовать рекурсивно алгоритм комбинаторики - C++
Всем привет! Хотелось бы реализовать рекурсивно следующий алгоритм комбинаторики: Ввод: abcd Вывод: abcd abc d ab cd

Программа с комбинаторики - C (Си)
Есть небольшая проблема . Решал дискретную математику . Но суть не в этом. Наткнулся на такую проблему. Нужно в программном виде решить...

Уравнения из комбинаторики! - Дискретная математика
Товарищи, кто чем сможет! Вроде просто , а у меня ну не как не получается. Решите уравнение! Вместо темного, неразборчивого фото -...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sigmaalgebra
9 / 9 / 0
Регистрация: 15.03.2009
Сообщений: 76
09.04.2009, 21:53     Функция комбинаторики.... #2
С(n,k)=n!/[(n-k)!k!] Хотим преобразовать так, чтобы было покороче. Тогда C(n,k)=[(k+1)*(k+1)*...*(n)]/k! либо если число (n-k)<k то сокращать надо с k: C(n,k)=[(n-k+1)*(n-k+2)*...*(n)]/(n-k)! Тогда программа будет выглядеть примерно так:

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
int faq(int n)
{
   int del=1,i=0;
   for(i=1;i<=n;i++)
   del=del*i;
   return del;
}
 
int C_n_k(int n,int k)
{
    int i=0,rez=1;del=1;
    if((n-k)<k)
    {
        for(i=1;(n-k-i)<=n;i++)
        {
            rez=rez*(n-k+i); 
        }
        del=faq((n-k));
        rez/=del; 
    }
    else
    {
       for(i=k+1;i<=n;i++)
           rez*=i; 
       del=faq(k);
       rez/=del; 
    }
    return rez;
}
примерно так. Я не тестила, не знаю как там на больших числах... Но вроде тут и без длинной арифметики можно обойтись.

Добавлено через 2 минуты 13 секунд
А вообще то наверное нет. Тут слабость в функции faq. Наверное надо пытаться в выдислении rez в цикле со множителями сокращать... Не знаю..
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
09.04.2009, 21:57  [ТС]     Функция комбинаторики.... #3
Спасибо тебе.... Но я это мог и сам сделать проблемы с длинной арифметикой... твоя функция faq не сможет посчитать 15! или 20!, не говоря об 100! или 200!...
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
09.04.2009, 22:52     Функция комбинаторики.... #4
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
#include <iostream>
typedef unsigned long long int ULL;
typedef long double LD;
 
ULL NOD(const ULL& a,const ULL& b)
{
    return a?NOD(b%a,a):b;
}
 
LD C_n_k(const ULL& n,const ULL& k)
{
    ULL numer=k+1;
    ULL denom=2;
    ULL temp,sumnum=1,sumdenom=1;
    while(numer<=n&&denom<=(n-k))
    {
        sumnum*=numer++;
        sumdenom*=denom++;
        temp=NOD(sumnum,sumdenom);
        sumnum/=temp;
        sumdenom/=temp;
    }
    while(numer<=n)
    {
        sumnum*=numer++;
        temp=NOD(sumnum,sumdenom);
        sumnum/=temp;
        sumdenom/=temp;
    }
    while(denom<=(n-k))
    {
        sumdenom*=denom++;
        temp=NOD(sumnum,sumdenom);
        sumnum/=temp;
        sumdenom/=temp;
    }
    return LD(sumnum)/sumdenom;
}
 
 
int main()
{
    std::cout<<C_n_k(200,100)<<std::endl;
    return 0;
}
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
17.09.2012, 17:41     Функция комбинаторики.... #5
Новенький, используй треугольник Паскаля. В его реализации необходимо только сложение из длинной арифметики.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.09.2012, 17:57     Функция комбинаторики....
Еще ссылки по теме:

Задача с комбинаторики - Комбинаторика
Сколькими способами можно разместить 10 одинаковых открыток в 4 почтовых ящиках так, чтобы: а) не было пустых ящиков б) во втором ящике...

Элементы комбинаторики - Комбинаторика
Доброго всем времени суток. Есть задача: Сколько существует десятичных чисел, сумма цифр которых равна: а) 2; б) 3; в) 4? С одной...

Элементы комбинаторики - Комбинаторика
1.Из группы в 10 человек надо выбрать 2-х для выполнения одной работы и 3 для другой. Сколькими способами это можно сделать? 2. Сколько...

Немного комбинаторики и планиметрии - Математика
1)Две стороны треугольника равны 50 и 96, а медиана, проведенная к третьей, равна 25. Найдите площадь треугольника. 2)От автостанции в...

Интересная задача из комбинаторики - Алгоритмы
как вывести формулу такого дела? есть число, допустим 10! я его раскладываю в к-значный массив. допустим в 5 значный. (целых чисел -...

Формула комбинаторики (сочетание) - VBA
Помогите написать VBA код формулы сочетания из комбинаторики. Код, который написал я, не рассчитывает факториал 0 (0! = 1). Ввиду этого я...


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

Или воспользуйтесь поиском по форуму:
-=ЮрА=-
Заблокирован
Автор FAQ
17.09.2012, 17:57     Функция комбинаторики.... #6
Новенький, посмотри сюда Мой блог : Эффективная формула вычисления числа сочетаний
Yandex
Объявления
17.09.2012, 17:57     Функция комбинаторики....
Ответ Создать тему
Опции темы

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