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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ как решить СЛАУ http://www.cyberforum.ru/cpp-beginners/thread233276.html
Помогите пожалуйста с задачей (на С++): Вычислить вектор X, решив СЛАУ 0,34 x1+0,71 x2+0,63 x3=2,08 0,71 x1−0,65 x2−0,18 x3=0,17 1,17 x1−2,35 x2+0,75 x3=1,28 Найти модуль вектора ∣2X−3∣....
C++ поиск суммы элементов квадратной матрицы не могу решить задачу: Найти сумму элементов квадратной матрицы X(n,n), находящихся по периметру этой матрицы и сумму элементов на ее диагоналях. Если суммы равны, то каждый отрицательный элемент... http://www.cyberforum.ru/cpp-beginners/thread233274.html
Определение порядковых номеров в массиве C++
помогите с задачкой: Определить порядковые номера и значения первого положительного и последнего отрицательного элементов целочисленного массива X(n). Определить среднее арифметическое элементов...
C++ найти факториал чисел в диапазоне
помогите пжлст с решением задачи: Найти р!, где р – каждое третье простое число в диапазоне от n1 до n2 (функциями оформить определение факториала и проверку, является ли число простым). заранее...
C++ последняя лабораторка( http://www.cyberforum.ru/cpp-beginners/thread233268.html
Помогите написать программку, очень нужно сдать Выделить все одиннадцатиричные числа с лексикографическим возрастанием цифр. Нужно на Си чтоб считывала ввод с клавиатуры, а потом как в...
C++ Функция сравнивает две строки, игнорируя различия в регистрах Я студент 1 курса на зачёт сказали написать программку помогите!! не хочу вылететь из универа С++ Консоль 1. Функция сравнивает две строки, игнорируя различия в регистрах 2. Список... подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
24.01.2011, 12:49
А если так сделать, это будет считаться мемоизацией?
А что это за умные термины «энтропия» и «гистерезис» применительно к функциям языка программирования? Не могли бы вы пояснить что вы имели в виду?
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;
}
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru