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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Цикл http://www.cyberforum.ru/cpp-beginners/thread634878.html
Начал изучать C++ неделю назад. Теперь начал решать некоторые задачи. И возникли у меня некоторые сложности с циклами... Требуется ваша помощь... Задача: Переведите натуральное число из двоичной...
C++ Работа с фс Всем привет, мне необходимо посчитать количество файлов в директории и в зависимости от их количества разделить их на 4 или 8 папок. Я слышала есть библиотеки fstream и boost, но как правильно это... http://www.cyberforum.ru/cpp-beginners/thread634869.html
Конструктор копирования C++
Всем привет. У меня такая проблема: есть некий класс, допустим Test: class Test { protected: int value; public : Test(int v)
Случайные(псевдослучайные) числа C++
Здравствуйте! Я знаю, что было много тем по поводу рандомных чисел в С++.Но всё же. Возникла у меня проблема с получением большого кол-ва случайных(точнее псвдослучайных) чисел, которые меньше...
C++ Ошибка при вызове функции http://www.cyberforum.ru/cpp-beginners/thread634834.html
В функции NewWords вызывается функция correct,при отладке я не могу войти в эту функцию,к тому же потом не выводится элементы объекта класса words и ID в программе на данный момент вызываются лишь 2...
C++ генерирую случайные числа srand(time(NULL)); rand()%10; Всем привет, генерирую случайные числа, подскажите, пожалуйста, почему при запуске приложения числа постоянно генерируются? Как можно сделать так, чтобы при каждом... подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.08.2012, 22:39
Цитата Сообщение от mr_free Посмотреть сообщение
Какие ваши предложения, а то общаясь в теме мы так и не решили поставленую задачу, я предложил число сочетании, а Юра предложил факториал, но оба решения привели только до решения на 10%?
Задача, о которой идет речь в этой теме, не из простых. Решить ее не получится, используя только факториал (перестановки) или число сочетаний.

mr_free, Вы лучше для начала попробуйте придумать, как можно посчитать: сколько всего существует вариантов разложения X конфет в Y коробках. То есть, два разложения конфет по сундучкам считаются разными, если хотя бы в одном из сундучков количество конфет в первом разложении отличается от количества конфет в другом разложении (в том же сундучке).
Для начала пробуйте высчитать без этих ограничений:
В один сундучок помещается не более чем N/2 конфет.
Например дано:
X=3, Y=5. Ответ: 35.
или X=5, Y=4. Ответ: 56.
Как можно высчитать эти (такие) ответы, быстро, без перебора?
Если найдете нормальный алгоритм, для расчета таких ответов, то следующий шаг будет такой:
Как узнать сколько из всех вариантов разложений для заданных X и Y имеется вариантов, когда в каком-нибудь сундучке (я не ошибся - именно в сундучке, а не в сундучках), количество конфет превышает N/2.
Последний этап будет: подключить длинную арифметику. Пример: N=1000, S=1000, ответ:
102407581349474485716758125149041252219821244399069851691019131883587409310104187791446649709130510310073238315999901184 620774089900226239600902377488463078928150644831716032357425576195446361236636731045053576951106236563312734910523583661 277014762225639917872383823425835360392135266649937627338741376296817108762385527851350783015038442741536912522107608110 851410160731342265061585117791630982619171431145865621955125226489453994050734768013400256487859155469474414825833159918 291920659233455711760781697212150345896697202845432900845378883414330052264920148378983717511003499693031191564903557456 0
2
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru