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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Adriano_Che
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 6
16.01.2011, 13:04     Динамическое программирование. Таблица. Набор букв на мобильнике #1
Всем доброго времени суток! Очень очень нужна помощь в решении двух задач динамическим программированием:
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++ Динамическое программирование
Динамическое программирование C++
Динамическое программирование C++
C++ Динамическое программирование
C++ Динамическое программирование
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++ Динамическое программирование

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

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

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