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

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

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

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

18.01.2010, 15:08. Просмотров 1721. Ответов 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. Оценить временную сложность алгоритма по сравнению с методом перебора при поиске решения
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.01.2010, 15:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Динамическое програмирование (C++):

програмирование с++ - C++
Ребята, извените если написал не туда просто не знаю куда. Может кто нибудь помочь у меня сесия начинается, задали задание домой по...

програмирование ООП С++ - C++
проблема такая в Visual Studio при компиляции выскакивает такая ошибка (fatal error C1083: Не удается открыть файл включение: iostream.h:...

Програмирование ATmega8 - C++
У меня курсовой проект по микропроцессорам на тему электронные напольные весы с индикатором с применением МК. Я применяю четыри датчика...

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

Програмирование физически процесов - C++
Задача о теле брошенном под углом к горизонту дан угол альфа начальная скорость и сопротивление среды масса обьекта как не решая...

Обьектно ориентированное програмирование - C++
Помогите пожалуста решить прогу. Меня недопускают к сесии срочно задача нада Составить описание класса для представления комплексных...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 15:18  [ТС] #3
Цитата Сообщение от zim22 Посмотреть сообщение
это вариация задачи о воре с рюкзачком.
Knapsack problem
Сори!!! Это в каком смысле????????
0
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
18.01.2010, 16:05 #4
Цитата Сообщение от Зайченок Посмотреть сообщение
Это в каком смысле????????
что в каком смысле?
0
Зайченок
0 / 0 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 16:31  [ТС] #5
В каком смысле это задача о воре с рюкзачком
0
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
18.01.2010, 16:47 #6
замени "рюкзачок" на "сумму в N рублей", а
вора на того, кто будет находить наименьшее количество монет.
и получишь Knapsack problem
0
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 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 17:34  [ТС] #8
Да! Большое спасибо!!! Это здорова
А может есть какие каментарии по поводу этой задачи

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

Скорее всего её придется защищать
0
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
18.01.2010, 17:48 #9
Цитата Сообщение от Зайченок Посмотреть сообщение
Требование.
1. Разработать алгоритм прямого перебора всех вариантов и выбора оптимального решения
2. Описать математически решение задачи методом динамического программирования
3. Реалзовать алгоритм динамического программирования на С++ или С++ Builder языке программирования
4. Оценить временную сложность алгоритма по сравнению с методом перебора при поиске решения
я думаю тебе прямая дорога во фриланс раздел.
0
Зайченок
0 / 0 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 18:13  [ТС] #10
Это Не помогает.
Мне нужен листинг (код) программы, а с остльным разберусь
0
valeriikozlov
Эксперт C++
4670 / 2496 / 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 / 0
Регистрация: 29.12.2009
Сообщений: 13
18.01.2010, 19:37  [ТС] #12
%- это отвечает за делитель, я правильно понимаю???????????

Огромное спасибо!!!!!!!!!!!!!!!
0
M128K145
Эксперт С++
8288 / 3508 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
18.01.2010, 20:18 #13
Цитата Сообщение от Зайченок Посмотреть сообщение
%- это отвечает за делитель
Остаток от деления на число
Код
123456%100 == 56
144%12 == 0
0
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, чтоб выдал какой-то результат?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2017, 13:25
Привет! Вот еще темы с ответами:

Мат. програмирование. контрольная - C++
1. Даны координаты трех точек на плоскости. Если они могут быть вершинами разностороннего треугольника, то вывести в порядке возрастания...

С чего начать програмирование? - C++
Я занимаюсь в основном в Веб среде. И решил расширить свои знания на C++. Дело в том что теорему запомнить сложно. Практика учет очень...

Програмирование на С++ разветляющихся вычислительных процессов - C++
Помогите бедной девушке решить задачку на С++,сама не справляюсь!:cry: Выяснить, у какого из трех прямоугольных треугольников площадь...

програмирование колебаний нелинейного осцилятора в c++ - C++
Помогите пожалуйста...дали тему курсовой - моделирование колебаний нелинейного осцилятора,а я даже не представляю как это делать..в...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.04.2017, 13:25
Ответ Создать тему
Опции темы

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