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

Рекурсия с мемоизацией...треугольник - 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
Эксперт С++
3040 / 1685 / 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;
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru