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

Рекурсия с мемоизацией...треугольник - C++

Восстановить пароль Регистрация
 
Яна Грач
 Аватар для Яна Грач
9 / 2 / 0
Регистрация: 14.04.2010
Сообщений: 27
24.01.2011, 08:21     Рекурсия с мемоизацией...треугольник #1
Пути в числовом треугольнике начинаются от верхнего числа. От любого числа можно перейти к одному из двух соседних чисел в следующей строке. Вычислить максимальную среди сумм чисел, расположенных на путях, заканчивающихся каким-нибудь числом в основании треугольника, и найти один из путей с этой суммой. В следующем треугольнике он образован выделенными числами:
7
3 8
8
1 0
2 7 4 4
4 5 2 6 5
Есть программа с рекурсией, но по-моему мемоизацию сюда подключить нельзя.
Мемоизация работает только для функций не обладающих энтропией или гистерезисом, т.е. зависимость значения функции от значений аргументов должна быть строго однозначной.
Чтоб читал с файла и запоминал путь...по которому проходит максимально.
Уже все мозги сплавились........
Помогите, пожалуйста))))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.01.2011, 08:21     Рекурсия с мемоизацией...треугольник
Посмотрите здесь:

рекурсия C++
Рекурсия C++
C++ Рекурсия
C++ Рекурсия
Рекурсия C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2801 / 1577 / 247
Регистрация: 03.05.2010
Сообщений: 3,663
24.01.2011, 12:49     Рекурсия с мемоизацией...треугольник #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
80
81
82
83
84
85
86
87
88
89
//////////////////////////////////////////////////////////////////////////////////////
//Пути в числовом треугольнике начинаются от верхнего числа. От любого числа можно 
//перейти к одному из двух соседних чисел в следующей строке. Вычислить максимальную 
//среди сумм чисел, расположенных на путях, заканчивающихся каким-нибудь числом 
//в основании треугольника, и найти один из путей с этой суммой. В следующем 
//треугольнике он образован выделенными числами:
//7
//3 8
//8 1 0
//2 7 4 4
//4 5 2 6 5
//...программа с рекурсией,... мемоизацию сюда подключить...
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>  T_cols;
//////////////////////////////////////////////////////////////////////////////////////
int     sum_max = 0;
T_cols  cols_for_max;
//////////////////////////////////////////////////////////////////////////////////////
const int  TR_DIM              = 5;
const int  tr[TR_DIM][TR_DIM]  = {{7, 0, 0, 0, 0},
                                  {3, 8, 0, 0, 0},
                                  {8, 1, 0, 0, 0},
                                  {2, 7, 4, 4, 0},
                                  {4, 5, 2, 6, 5}};
//////////////////////////////////////////////////////////////////////////////////////
void  get_path
    (
        int      row      = 0,
        T_cols&  cols     = T_cols(), 
        int      sum_cur  = 0
    )
{
    if(row == 0)
    {        
        cols.push_back(0);
        sum_cur = tr[row][cols.back()];
    }
    
    if(row == TR_DIM - 1)
    {
        if(sum_cur > sum_max)
        {
            sum_max       = sum_cur;
            cols_for_max  = cols;
        }
        return;
    }
    int  row_new = row + 1;
 
    T_cols  cols_left(cols);                
    cols_left.push_back(cols.back());
    int  sum_cur_left = sum_cur + tr[row_new][cols_left.back()];
    get_path(row_new, cols_left, sum_cur_left);    
 
    T_cols  cols_right(cols);                
    cols_right.push_back(cols.back() + 1);
    int  sum_cur_right = sum_cur + tr[row_new][cols_right.back()];
    get_path(row_new, cols_right, sum_cur_right);
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    get_path();
    std::cout << "В заданном треугольнике "
              << std::endl;
    for(int i = 0; i < TR_DIM; ++i)
    {
        for(int j = 0; j <= i; ++j)
        {
            std::cout << tr[i][j]
                      << '\t';
        }
        std::cout << std::endl
                  << std::endl;
    }
    std::cout << "путь с максимальной суммой "
              << sum_max
              << " имеет индексы столбцов"
              << std::endl;
 
    std::copy(cols_for_max.begin(), cols_for_max.end(), 
              std::ostream_iterator<int>(std::cout, "\t"));
 
    std::cout << std::endl;
}
Яна Грач
 Аватар для Яна Грач
9 / 2 / 0
Регистрация: 14.04.2010
Сообщений: 27
27.01.2011, 12:30  [ТС]     Рекурсия с мемоизацией...треугольник #3
Зависимость значения функции от значений аргументов должна быть строго однозначной. Это я так понимаю свойства мемоизации...или условия её применения....
Спасибо)
Я уже тоже написала)
Keiichi
Сообщений: n/a
29.05.2012, 15:50     Рекурсия с мемоизацией...треугольник #4
Яна Грач, здравствуйте хотелось бы поинтересоваться не писали ли вы программу с помощью динамического программирования, если есть код буду очень признателен, если поделитесь.)
Яна Грач
 Аватар для Яна Грач
9 / 2 / 0
Регистрация: 14.04.2010
Сообщений: 27
29.05.2012, 16:56  [ТС]     Рекурсия с мемоизацией...треугольник #5
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
80
81
82
83
84
85
86
#include <stdio.h>
#include <cstdlib>
#include <iostream>
 
using namespace std;
FILE *f;
int n,Doc[100][100],F[100][100];//количество элементов в последней строке или высота треугольника
int booter[100][100];//двумерный массив треугольника
int i,x,j;//,S;//счетчики
 
void readdata() {
  f=fopen("input.txt","r");
  fscanf(f,"%d",&n);
  for(i=0;i<n;i++) {
    for(j=0;j<=i;j++) {
      fscanf(f,"%d",&booter[i][j]);
    };
  };
  fclose(f);
    for (i=0;i<n;i++)
    {
        for (j=0;j<=i;j++) printf ("%4d", booter[i][j]);
    printf("\n");
    }
    printf("\n------------------------\n");
};
 
void writedata() 
    {
    f=fopen("output.txt","w");
    fprintf (f,"%d", booter[0][0]);
 
    for (i=0;i<n;i++)
    {
        for (j=0;j<=i;j++) printf ("%4d", booter[i][j]);
    printf("\n");
    }
    printf("\n------------------------\n");
   
    for (i=0;i<n;i++)
    {
        for (j=0;j<=i;j++) printf ("%4d", Doc[i][j]);
    printf("\n");
    }
//    fclose(f);
    };
 
int rec()//фунция подсчета максимальной суммы
{
  for (i=n-2;i>=0;i--) 
    for (j=0;j<=i;j++) 
    {
        booter[i][j]+=(booter[i+1][j]>booter[i+1][j+1])?booter[i+1][j]:booter[i+1][j+1];
        Doc[i][j]=(booter[i+1][j]>booter[i+1][j+1])?0:1;
    }
 
}
 
int main(int argc, char* argv[])
{
    readdata();
    for (i=0;i<n;i++)
    {
        for (j=0;j<=i;j++)
        {
            F[i][j]=booter[i][j];
            }
        }
    rec(); 
 
    writedata();
 
    cout<<endl;
    j=0;
    for (i=0;i<n;i++)
    {
            cout<<" "<<F[i][j];
            if (Doc[i][j]==1)
            j++;
        }
    cout<<endl;
    cout<<"Max sum="<<booter[0][0]<<endl;
    cout<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}
Надо еще файлы создать, ну разберетесь)
Keiichi
Сообщений: n/a
29.05.2012, 18:48     Рекурсия с мемоизацией...треугольник #6
Яна Грач, благодарствую) разберусь)
Yandex
Объявления
29.05.2012, 18:48     Рекурсия с мемоизацией...треугольник
Ответ Создать тему
Опции темы

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