Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
diana1998
Заблокирован
#1

Подсчет Комбинаций - C++

31.10.2016, 13:23. Просмотров 174. Ответов 4
Метки нет (Все метки)

[ссылка удалена] решите, пожалуйста, эту задачку, заранее спасибо
Постановка задачи
Вы должны точно вычислить значение C(N, K) для заданного N а K. Обратите внимание, что хотя некоторые языки (Python и Java например) имеют встроенной длинной арифметикой, было бы хорошо, если вы найдете способ свести к минимуму промежуточные результаты в расчетах. Это будет иметь решающее значение для C/C++ иногда.

Если это слишком просто для вас, пожалуйста, попробуйте написать программу для перечисления комбинаций задача!

Входные данные будут содержать количество тест-кейсов.
Следующие строки содержат один тест, каждый в виде двух значений (N K).
Ответ должен содержать C(N, K) для каждого случая.
ответ должен быть таким же, как описано на сайте)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.10.2016, 13:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Подсчет Комбинаций (C++):

Перебор комбинаций - C++
Здравствуйте! Возникла такая задача. Дан одномерный массив из N цифр,нужно составить все возможные комбинации чисел из этих цифр(числа...

Генерация комбинаций из n по m - C++
Здравствуйте! Написала функцию для генерации комбинаций. Подскажите в чем ошибка, выдает не все варианты. int Generare(int Key, int...

Перебор комбинаций - C++
Доброго времени суток. Нашел в сети картинку - генератор речей. 4 столбика по 6 фраз в каждом. При переборе слева направо получается...

Генератор комбинаций с повторениями - C++
Вот код он выводит все комбинации с повторениями от 1 до 3 и можно увеличить до 9. Беда в том что он начинаем генерировать с 1 const int...

Перебор комбинаций с исключениями - C++
Здраствуйте!Хочу попробовать сделать задачу:есть число n которое указывает количество цифр и есть число k которое указывает количество...

Функция количества комбинаций - C++
Есть ли функция на C++ которая возвращает количество комбинаций для заданного числа элементов в excel это функция ЧИСЛКОМБ(число;...

4
SpBerkut
Объявлятель переменных
908 / 234 / 113
Регистрация: 24.09.2011
Сообщений: 875
Завершенные тесты: 2
31.10.2016, 13:38 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
 
unsigned long long C(unsigned n, unsigned k){
    if (n <= k) return n == k;
    unsigned d = k < n-k ? n-k : k;
    unsigned long long a = d + 1;
    for(unsigned j = 1; ++j <= n-d; a = a*(d+j)/j);
    return a;
}
 
int main()
{
    std::cout << C(50, 20);
}
0
Байт
Эксперт C
16553 / 10823 / 1640
Регистрация: 24.12.2010
Сообщений: 20,898
31.10.2016, 14:03 #3
Рекурсивный алгоритм
C++
1
2
3
4
5
6
int C(int n, int k)
{
 if (n==k) return 1;
 if (k==1) return n;
 return C(n-1, k-1) + C(n-1, k);
}
обладает значительно большим "запасом прочности" по переполнению.
Все промежуточные вычисления приводят к числам, меньшим итогового результата
0
SpBerkut
Объявлятель переменных
908 / 234 / 113
Регистрация: 24.09.2011
Сообщений: 875
Завершенные тесты: 2
31.10.2016, 14:10 #4
Байт, зело долго работает же.
0
Байт
Эксперт C
16553 / 10823 / 1640
Регистрация: 24.12.2010
Сообщений: 20,898
31.10.2016, 14:33 #5
Цитата Сообщение от SpBerkut Посмотреть сообщение
зело долго работает же.
Цитата Сообщение от diana1998 Посмотреть сообщение
свести к минимуму промежуточные результаты в расчетах.
Такая цель поставлена.
Я понял, что к минимуму надо свести размер промежуточных результатов. Чему способствует и преамбула о длинной арихметике.
Но еще лучше - динамическое программирование. Там алгоритм построен так, что нужные значения треугольника Паскаля вычисляются только по одному разу. Правда, памяти нужно чуток поболее. Но это вечная дилемма...

Добавлено через 10 минут
https://habrahabr.ru/post/274689/
1
31.10.2016, 14:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2016, 14:33
Привет! Вот еще темы с ответами:

Количество различных комбинаций - C++
Добра всем. Задача: есть &quot;слово&quot; нужно написать программу, которая подсчитала бы количество комбинаций букв этого слова, т.е. лсово, лосво...

Помогите с выводом комбинаций - C++
Вот есть код для вывода комбинаций символов. Но он почему то ничего не выводит на экран. В чём может быть проблема? #include&lt;stdio.h&gt; ...

Вычисление числа комбинаций - C++
Вопрос, конечно элементарный но сам запутался. Какое количество комбинаций можно получить из трех чисел. Вообщем похоже на бинарный код. ...

Разработать программу расчета комбинаций - C++
Помогите пожалуйста. Всю суть я постарался изложить на картинке П.5.18. Правил Запрещено размещать задания и решения в виде картинок...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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