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

Комбинаторика! Число сочитаний - 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
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.08.2012, 04:27
Цитата Сообщение от kravam Посмотреть сообщение
mr_free, лови, сам решал когда-то
Эти способы считают правильно, но не пройдут по времени. Опишу здесь один способ, который подходит для этой задачи (метод динамического программирования). Я приведу пример вычислений в пределах 1..10 конфет, 1..10 ящиков.
Создаем массив a[10][10]. Для удобства индексацию массива буду называть так: нулевой индекс (номер) строки (столбца) буду называть первым индексом (номером), соответственно первый индекс (номер) массива буду называть вторым...
Пусть номер строки будет обозначать количество конфет, а номер столбца будет обозначать количество ящиков. Тогда изначально массив a[][] заполняем так:
Первый столбец заполняем 1. Первую строку заполняем так: 1 2 3 4 .... (значение элемента первой строки равно номеру столбца).
Затем основное заполнение массива:
C++
1
2
3
for(i=2; i<11; i++)// здесь индексация начинается со значения 2 и заканчивается значением 10 (по мною оговоренному условию - что нумерация (индексация) строк и столбцов начинается с 1, а не с 0). Будьте внимательны при реализации кода!!!
    for(j=2; j<11; j++)
        a[i][j]=a[i-1][j]+a[i][j-1];
В итоге получим массив с помощью которого очень быстро можно узнать сколько вариантов размещения X конфет в Y ящиках. Ответом будет являться значение a[X][Y].
Теперь как считать ответ для этой задачи. Рассмотрим (и разберемся) на примере N=6, S=5.
Всего вариантов размещения 6 конфет в 5 ящиках 210 (это значение берем из массива a[][]).
Теперь вычислим сколько из этих вариантов "плохие" (когда в каком-либо ящике больше 3 конфет). Рассмотрим варианты для 1-го ящика:
- В первом ящике все 6 конфет. В остальных 4-х ящиках 0 конфет. Это 1 "плохой" вариант.
- В первом ящике 5 конфет. В остальных 4-х ящиках 1 конфета. Это 4 "плохих" варианта (значение находим в массиве a[1][4]).
- В первом ящике 4 конфеты. В остальных 4-х ящиках 2 конфеты. Это 10 "плохих" варианта (значение находим в массиве a[2][4]).
Итого для первого ящика имеем 15 плохих варианта. Всего ящиков у нас 5. Значит плохих вариантов всего будет 15*5=75.
Ответ на вопрос: сколько вариантов размещения 6 конфет в 5 ящиках: 210-75=135.
Можно подвести итог: для того чтобы посчитать сколько вариантов размещения X конфет в Y ящиках. нужно вычислить:
a[X][Y] - (a[N/2-1][Y-1] + a[N/2-2][Y-1] + ..... + a[1][Y-1] + 1) * S
При реализации такого варианта с помощью массива размером 1000*1000 окажется что памяти не хватает. Но не обязательно заводить этот массив полностью. Я реализовывал решение с помощью массива a[2][1000], т.е. всего две строки (одна для хранения значений предыдущей строки, во второй расчитывал значение очередной строки).
Ну и не забудьте про длинную арифметику.
2
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru