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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
Зайченок
0 / 0 / 0
Регистрация: 29.12.2009
Сообщений: 13
#1

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

18.01.2010, 15:08. Просмотров 1646. Ответов 13
Метки нет (Все метки)

Очень нужна помощь в решении задач на С++ или С++ 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. Оценить временную сложность алгоритма по сравнению с методом перебора при поиске решения
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zim22
depict1
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
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
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
18.01.2010, 16:47     Динамическое програмирование #6
замени "рюкзачок" на "сумму в N рублей", а
вора на того, кто будет находить наименьшее количество монет.
и получишь Knapsack problem
Bloodykeeper
This party getting crazy!
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
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++
4663 / 2489 / 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
%- это отвечает за делитель, я правильно понимаю???????????

Огромное спасибо!!!!!!!!!!!!!!!
M128K145
Эксперт С++
8282 / 3501 / 143
Регистрация: 03.07.2009
Сообщений: 10,707
18.01.2010, 20:18     Динамическое програмирование #13
Цитата Сообщение от Зайченок Посмотреть сообщение
%- это отвечает за делитель
Остаток от деления на число
Код
123456%100 == 56
144%12 == 0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2017, 13:25     Динамическое програмирование
Еще ссылки по теме:

Програмирование под два ядра C++
програмирование колебаний нелинейного осцилятора в c++ C++
C++ С чего начать програмирование?
Програмирование физически процесов C++
програмирование ООП С++ C++

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

Или воспользуйтесь поиском по форуму:
Ak_Dmitry
0 / 0 / 0
Регистрация: 23.11.2015
Сообщений: 27
07.04.2017, 13:25     Динамическое програмирование #14
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
46
47
48
// dynamic.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <Cmath>
#include <math.h>
#include <vector>
#include <limits>
 
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}
 
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];
    std::cout << ???;
    system ("Pause");
}
Что вписать вместо ??? в cout, чтоб выдал какой-то результат?
Yandex
Объявления
07.04.2017, 13:25     Динамическое програмирование
Ответ Создать тему
Опции темы

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