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

Динамическое програмирование - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
Зайченок
0 / 0 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 15:08     Динамическое програмирование #1
Очень нужна помощь в решении задач на С++ или С++ Builder
Помогите кто сможет,последняя надежда на вас
Очень буду рада!
Большое спасибо заранее!!!!!!

Задача 1. Из диапазона [A; B] найти числа, имеющие K делителей
Например К=3 Диапозон 12345 подходит число 4 т.к. у него 3 делителя это 1,2,4

Задача 2. Две команды проводят серию игр до 6 побед одной из команд. Первая команда побеждает вторую с вероятностью 2/3. Ничья не допускается. Определить, у какой команды больше шансов на победу при счете 1:3.

Задача 11. Имеются монеты достоинством 2,3,4,5 копеек. Найти наименьшее количество монет, которыми можно разменять сумму в N рублей.

Требование.
1. Разработать алгоритм прямого перебора всех вариантов и выбора оптимального решения
2. Описать математически решение задачи методом динамического программирования
3. Реалзовать алгоритм динамического программирования на С++ или С++ Builder языке программирования
4. Оценить временную сложность алгоритма по сравнению с методом перебора при поиске решения
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.01.2010, 15:08     Динамическое програмирование
Посмотрите здесь:

Програмирование с использованием функций C++
Програмирование с использованием функций C++
C++ програмирование ветвлящихся алгоритмов
C++ [C++] програмирование ATmega8
C++ програмирование с++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
18.01.2010, 15:12     Динамическое програмирование #2
Цитата Сообщение от Зайченок Посмотреть сообщение
Задача 11. Имеются монеты достоинством 2,3,4,5 копеек. Найти наименьшее количество монет, которыми можно разменять сумму в N рублей.
это вариация задачи о воре с рюкзачком.
Knapsack problem
Зайченок
0 / 0 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 15:18  [ТС]     Динамическое програмирование #3
Цитата Сообщение от zim22 Посмотреть сообщение
это вариация задачи о воре с рюкзачком.
Knapsack problem
Сори!!! Это в каком смысле????????
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
18.01.2010, 16:05     Динамическое програмирование #4
Цитата Сообщение от Зайченок Посмотреть сообщение
Это в каком смысле????????
что в каком смысле?
Зайченок
0 / 0 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 16:31  [ТС]     Динамическое програмирование #5
В каком смысле это задача о воре с рюкзачком
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
18.01.2010, 16:47     Динамическое програмирование #6
замени "рюкзачок" на "сумму в N рублей", а
вора на того, кто будет находить наименьшее количество монет.
и получишь Knapsack problem
Bloodykeeper
This party getting crazy!
 Аватар для Bloodykeeper
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
18.01.2010, 16:55     Динамическое програмирование #7
вот я нарыл чтото о Knapsack может быть поможет:
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
#include <vector>
#include <limits>
 
int knapsack2(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
    size_t n = wts.size();
    std::vector<std::vector<int> > dp(W + 1);
    for (int i = 0; i <= W; i++)
    {
        dp[i].resize(n + 1);
        dp[i][0] = 0;
    }
    for (size_t i = 0; i <= n; i++)
    {
        dp[0][i] = 0;
    }
    for (size_t j = 1; j <= n; j++)
    {
        for (int w = 1; w <= W; w++)
        {
            if (wts[j-1] <= w)
            {
                dp[w][j] = std::max(dp[w][j - 1], dp[w - wts[j-1]][j - 1] + cost[j-1]);
            } else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[W][n];
}
Зайченок
0 / 0 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 17:34  [ТС]     Динамическое програмирование #8
Да! Большое спасибо!!! Это здорова
А может есть какие каментарии по поводу этой задачи

Задача 1. Из диапазона [A; B] найти числа, имеющие K делителей
Например К=3 Диапозон 12345 подходит число 4 т.к. у него 3 делителя это 1,2,4

Скорее всего её придется защищать
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
18.01.2010, 17:48     Динамическое програмирование #9
Цитата Сообщение от Зайченок Посмотреть сообщение
Требование.
1. Разработать алгоритм прямого перебора всех вариантов и выбора оптимального решения
2. Описать математически решение задачи методом динамического программирования
3. Реалзовать алгоритм динамического программирования на С++ или С++ Builder языке программирования
4. Оценить временную сложность алгоритма по сравнению с методом перебора при поиске решения
я думаю тебе прямая дорога во фриланс раздел.
Зайченок
0 / 0 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 18:13  [ТС]     Динамическое програмирование #10
Это Не помогает.
Мне нужен листинг (код) программы, а с остльным разберусь
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.01.2010, 19:23     Динамическое програмирование #11
Цитата Сообщение от Зайченок Посмотреть сообщение
Мне нужен листинг (код) программы, а с остльным разберусь
Для первой задачи.
Ну тогда даю Вам просто функцию, в параметры которой задается целое число, а возвращается кол-во его делителей:
C
1
2
3
4
5
6
7
8
int col_del(int a)
{
    int col=2, i;
    for(i=2; i<=a/2; i++)
        if(a%i==0)
            col++;
    return col;
}
Перебирая все числа из диапазона и вызывая для каждого из них данную функцию, делайте сравнение возвращаемых значений этой функции с числом К.
Зайченок
0 / 0 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 19:37  [ТС]     Динамическое програмирование #12
%- это отвечает за делитель, я правильно понимаю???????????

Огромное спасибо!!!!!!!!!!!!!!!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.01.2010, 20:18     Динамическое програмирование
Еще ссылки по теме:

Програмирование физически процесов C++
програмирование ООП С++ C++
Програмирование с использованием структур C++

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

Или воспользуйтесь поиском по форуму:
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
18.01.2010, 20:18     Динамическое програмирование #13
Цитата Сообщение от Зайченок Посмотреть сообщение
%- это отвечает за делитель
Остаток от деления на число
Код
123456%100 == 56
144%12 == 0
Yandex
Объявления
18.01.2010, 20:18     Динамическое програмирование
Ответ Создать тему
Опции темы

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