Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/8: Рейтинг темы: голосов - 8, средняя оценка - 4.50
Adriano_Che
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 6
1

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

16.01.2011, 13:04. Просмотров 1522. Ответов 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
Ответы с готовыми решениями:

Динамическое программирование
Подскажите что не так в решении. #include &lt;iostream&gt; #include &lt;stdio.h&gt;...

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

Динамическое программирование
очень нужна реализация(завтра дедлайн) Будем называть натуральное число...

Динамическое программирование
Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт У...

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

8
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 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
Эксперт С++
4686 / 2512 / 751
Регистрация: 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
Эксперт С++
4686 / 2512 / 751
Регистрация: 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
Эксперт С++
4686 / 2512 / 751
Регистрация: 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
03.05.2015, 14:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2015, 14:32

Динамическое программирование
Есть такая задача: Дана схема стены, необходимо проверить можно ли построить...

Динамическое программирование
Помогите решить задачу! Я что-то особо не соображу... 1.Написать программу,...

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


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

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