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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Adriano_Che
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 6
#1

Динамическое программирование. Таблица. Набор букв на мобильнике - C++

16.01.2011, 13:04. Просмотров 1439. Ответов 8
Метки нет (Все метки)

Всем доброго времени суток! Очень очень нужна помощь в решении двух задач динамическим программированием:
1. Прямоугольная таблица имеет М строк и N столбцов. В каждой ее клетке записано натуральное число не больше 200. Нужно пройти из левого верхнего угла таблицы в правый нижний, на каждом шаге перемещаясь на 1 клетку вправо или вниз. Очевидно, таких путей много, и для каждого можно найти сумму чисел в пройденных клетках. Ясно, что среди этих сумм есть максимальная.
"Хорошими" считаются не только пути с максимально возможной суммой, но и пути, сумма которых отличается от максимальной не более чем на К. Количество "хороших" путей гарантированно не больше 10.
Найти максимально возможную сумму и количество "хороших" путей.

Вход. Первая строка входного текста содержит три целых числа М (2<М<200), N (2<N<200) и K (0<K<200). Каждая из следующих М строк задает N чисел в соответствующих клетках.
Выход. Первая строка текста должна содержать максимально возможную сумму, вторая — количество маршрутов, сумма чисел которых отличается от максимальной не более чем на K.

2.Существует следующий способ набора букв на мобильном телефоне. Клавише 2 сопоставлены буквы abc, клавише 3 def и т.д. При наборе текста одно нажатие на клавишу 2 порождает символ а, два подряд нажатия символ b, три подряд символ c; аналогично, одно нажатие на 3 порождает d, два подряд е и т.д. Если же нужно набрать две буквы а, то нажимают на 2, немного ждут и снова нажимают на 2.
Обобщим ситуацию. Пусть есть алфавит из N символов, который нужно сопоставить М клавишам (M<N). Для каждого символа алфавита известна частота его использования. Нужно задать соответствие символов алфавита клавишам так, чтобы символы с первого по некоторый к1-й соответствовали первой клавише, с (к1+1)-го по некоторый к2-й второй клавише и т.д., а среднее количество нажатий на клавиши (исходя из известных частот) было минимальным. Формально говоря, нужно минимизировать характеристику (сумма по i от 1 до N от (Fi*Ti)) , где Fi частота использования i-го символа согласно входным данным, Ti количество нажатий, нужное для набора i-го символа согласно построенному разбиению алфавита.

Вход. В первой строке текста записаны N и M, в следующих N строках — по одному целому числу, пропорциональному частоте использования символа (2<М≤100, М<N≤250).
Выход. Первая строка текста должна содержать найденную минимальную характеристику, а каждая из следующих М строк два числа (между ними пробел), которые задают диапазон символов, сопоставленных данной клавише.

Добавлено через 1 час 19 минут
Что касается задачи про числа-я нашёл максимальную сумму. Я не могу понять как найти "хороший" путь(( Вот код для нахождения максимального пути:
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
#include<iostream>
#include<stdio.h>
#include<conio.h>
using namespace std;
int main()
{
        int N, M, i, j, **a, **b;
        cin>>N>>M;
        a=new int*[M];
        b=new int*[M];
        for(i=0; i<M; i++)
        {
                a[i]=new int[N];
                b[i]=new int[N];
                for(j=0; j<N; j++)
                {
                        cin>>a[i][j];
                        b[i][j]=a[i][j];
                }
        }
        for (i=N-2;i>=0;i--)
            b[M-1][i]+=b[M-1][i+1];
        for(i=M-2; i>=0; i--)
        for(j=N-1; j>=0; j--)
        {
                int max=b[i+1][j];
                if(j<(N-1) && (b[i][j+1]>max))
                        max=b[i][j+1];
                b[i][j]+=max;
        }
        cout<<"max="<<b[0][0]<<endl;
        system("PAUSE");
        return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2011, 13:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Динамическое программирование. Таблица. Набор букв на мобильнике (C++):

Динамическое программирование - C++
Помогите пожалуйста,кто может, со следующими задачами, так как в С++ слабо разбираюсь, а к понедельнику надо сдать... 1. Определить...

Динамическое программирование - C++
Не понимаю динамических структур, списков, работы с ними. Посоветуйте источник изучения. Что-то вроде того что написано здесь...

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

Динамическое программирование! - C++
#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; int a, n, m; int main() { scanf(&quot; %d %d&quot;, &amp;n,...

Динамическое программирование - C++
На расстоянии n шагов от магазина стоит А. Каждую минуту он выбирает куда сделать шаг: к магазину или в противоположном направлении. ...

Динамическое программирование - C++
Усложнили задачу мне.... : Дан массив A. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 18:24 #2
1-ая. проверяйте:
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
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<stdio.h>
#include<conio.h>
using namespace std;
int rec(int **a, int **b, int sum, int x, int y, int K)
{
    if(sum>K)
        return 0;
    if(x==0 && y==0)
        return 1;
    int temp=0;
    if(x>0)
    {
        if(b[x-1][y]==b[x][y]-a[x][y])
            temp+=rec(a, b, sum, x-1, y, K);
        else
            temp+=rec(a, b, sum+a[x][y-1]-a[x-1][y], x-1, y, K);
    }
    if(y>0)
    {
        if(b[x][y-1]==b[x][y]-a[x][y])
            temp+=rec(a, b, sum, x, y-1, K);
        else
            temp+=rec(a, b, sum+a[x-1][y]-a[x][y-1], x, y-1, K);
    }
    return temp;
}
 
 
int main()
{
        int N, M, K, i, j, **a, **b;
        cin>>N>>M>>K;
        a=new int*[M];
        b=new int*[M];
        for(i=0; i<M; i++)
        {
                a[i]=new int[N];
                b[i]=new int[N];
                for(j=0; j<N; j++)
                {
                        cin>>a[i][j];
                        b[i][j]=a[i][j];
                }
        }
        for(i=1; i<N; i++)
            b[0][i]+=b[0][i-1];
        for(i=1; i<M; i++)
            b[i][0]+=b[i-1][0];
        for(i=1; i<M; i++)
            for(j=1; j<N; j++)
                if(b[i-1][j]>b[i][j-1])
                    b[i][j]+=b[i-1][j];
                else
                    b[i][j]+=b[i][j-1];
        cout<<"max="<<b[M-1][N-1]<<endl;
        cout<<"Good way: "<<rec(a, b, 0, M-1, N-1, K)-1<<endl;
        system("PAUSE");
        return 0;
}
1
Adriano_Che
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 6
16.01.2011, 19:59  [ТС] #3
Спасибо большое) Сейчас буду разбираться в рекурсии)) А по поводу второй есть хоть какие нибудь идеи?
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 20:20 #4
Adriano_Che, подсказка:
- вычисление максимальной суммы сделано динамикой (в отличие от кода который Вы привели, расчет начинается с начала, а не с конца).
- рекурсия только для вычисления количества "хороших" путей.
По-поводу второй: с ходу вижу рекурсию. Ссылку на тестирующую систему не дадите для этой задачи?
0
Adriano_Che
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 6
16.01.2011, 20:35  [ТС] #5
Можно хотя бы рекурсией... Тестирующая система:это конкретный пример с правильным решением?
Вот есть что то, если это то:
Вход:
5 3
3
2
5
7
1
Выход:
21
1 2
3 3
4 5
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 20:39 #6
Adriano_Che, Это один пример, а саму задачу куда будете сдавать?
0
Adriano_Che
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 6
17.01.2011, 19:37  [ТС] #7
Просто рассказывать преподу, что бы он допустил завтра к экзамену..(( У него я думаю тоже нет никакой такой системы, он просто будет верить наслово)

Добавлено через 1 час 56 минут
Ну так как там рекурсия?... Пожалуйста помогите..

Добавлено через 20 часов 58 минут
Эта задача всё ещё актуальна...Кто нибудь может помочь? Валерий, на вас видимо единственная надежда ...
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.01.2011, 23:14 #8
2-ая. Проверяйте:
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<conio.h>
using namespace std;
int N, M, *a, **mas_res, n_res, Res=-1, **mas_temp, n_temp=0;
void rec(int Sum, int i)
{
    if(i==N)
    {
        if(Res==-1)
        {
            for(int j=0; j<n_temp; j++)
            {
                mas_res[j][0]=mas_temp[j][0];
                mas_res[j][1]=mas_temp[j][1];
            }
            n_res=n_temp;
            mas_res[n_res-1][1]=N;
            Res=Sum;
        }
        else
        {
            if(Res>Sum)
            {
                for(int j=0; j<n_temp; j++)
                {
                    mas_res[j][0]=mas_temp[j][0];
                    mas_res[j][1]=mas_temp[j][1];
                }
                n_res=n_temp;
                Res=Sum;
                mas_res[n_res-1][1]=N;
            }
        }
    }
    int temp=0;
    for(int j=i; j<N; j++)
    {
        
        temp+=a[j]*(j-i+1);
        if(n_temp<M-1 || (n_temp==M-1 && j+1==N))
        {
            mas_temp[n_temp++][1]=j+1;
            if(n_temp<M)
                mas_temp[n_temp][0]=j+2;
            rec(Sum+temp, j+1);
            n_temp--;
        }
    }
}
 
int main()
{
        int i;
        cin>>N>>M;
        a=new int[N];
        for(i=0; i<N; i++)
            cin>>a[i];
        mas_res=new int*[M];
        mas_temp=new int*[M];
        for(i=0; i<M; i++)
        {
            mas_res[i]=new int[2];
            mas_temp[i]=new int[2];
        }
        mas_temp[0][0]=1;
        rec(0, 0);
        cout<<Res<<endl;
        for(i=0; i<n_res; i++)
            cout<<mas_res[i][0]<<" "<<mas_res[i][1]<<endl; 
        system("PAUSE");
        for (i=0; i<M; i++)
        {
            delete [] mas_res[i];
            delete [] mas_temp[i];
        }
        delete [] mas_res;
        delete [] mas_temp;
        return 0;
}
1
DrYea
0 / 0 / 0
Регистрация: 23.12.2013
Сообщений: 29
03.05.2015, 14:32 #9
а как рекурсивно это задать в задаче про кнопки мобильника?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2015, 14:32
Привет! Вот еще темы с ответами:

Динамическое программирование - C++
Подскажите что не так в решении. #include &lt;iostream&gt; #include &lt;stdio.h&gt; using namespace std; const int N = 5001; int...

Динамическое программирование - C++
Помогите решить задачу! Я что-то особо не соображу... 1.Написать программу, реализующую действия: а. сформировать ленточную матрицу...

ДП Динамическое программирование - C++
ограничение времени на тест: 0.5 сек. ограничение памяти на тест: 65536 KB. Рассмотрим все строки длины N, состоящие только из букв...

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


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

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

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