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

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

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

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

16.01.2011, 13:04. Просмотров 1427. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2011, 13:04     Динамическое программирование. Таблица. Набор букв на мобильнике
Посмотрите здесь:

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 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;
}
Adriano_Che
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 6
16.01.2011, 19:59  [ТС]     Динамическое программирование. Таблица. Набор букв на мобильнике #3
Спасибо большое) Сейчас буду разбираться в рекурсии)) А по поводу второй есть хоть какие нибудь идеи?
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 20:20     Динамическое программирование. Таблица. Набор букв на мобильнике #4
Adriano_Che, подсказка:
- вычисление максимальной суммы сделано динамикой (в отличие от кода который Вы привели, расчет начинается с начала, а не с конца).
- рекурсия только для вычисления количества "хороших" путей.
По-поводу второй: с ходу вижу рекурсию. Ссылку на тестирующую систему не дадите для этой задачи?
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
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 20:39     Динамическое программирование. Таблица. Набор букв на мобильнике #6
Adriano_Che, Это один пример, а саму задачу куда будете сдавать?
Adriano_Che
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 6
17.01.2011, 19:37  [ТС]     Динамическое программирование. Таблица. Набор букв на мобильнике #7
Просто рассказывать преподу, что бы он допустил завтра к экзамену..(( У него я думаю тоже нет никакой такой системы, он просто будет верить наслово)

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

Добавлено через 20 часов 58 минут
Эта задача всё ещё актуальна...Кто нибудь может помочь? Валерий, на вас видимо единственная надежда ...
valeriikozlov
Эксперт C++
4669 / 2495 / 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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2015, 14:32     Динамическое программирование. Таблица. Набор букв на мобильнике
Еще ссылки по теме:

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

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

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

Динамическое программирование - C++
Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт У Пети есть полоска бумаги, разделенная на N клеток. Он хочет...

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


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

Или воспользуйтесь поиском по форуму:
DrYea
0 / 0 / 0
Регистрация: 23.12.2013
Сообщений: 29
03.05.2015, 14:32     Динамическое программирование. Таблица. Набор букв на мобильнике #9
а как рекурсивно это задать в задаче про кнопки мобильника?
Yandex
Объявления
03.05.2015, 14:32     Динамическое программирование. Таблица. Набор букв на мобильнике
Ответ Создать тему
Опции темы

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