Оптимизировать функцию

@Niggainsoul · Регистрация: 20.10.2018

Студворк — интернет-сервис помощи студентам

Как можно оптимизировать (ускорить) следующий фрагмент кода?

C++
1
2
3
4
5
6
7
8
9
10
11
int F(int a, int b, int c)
{
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    else if (a > 20 || b > 20 || c > 20) return F(20, 20, 20);
    else if (a < b && b < c) return F(a, b - 1, c) + F(a, b, c - 1) - F(a, b - 1, c - 1);
    else
    {
        a--;
        return F(a, b - 1, c) + F(a, b, c - 1) - F(a, b - 1, c - 1) + F(a, b, c);
    }
}

@Niggainsoul · 26.02.2019, 12:35 **[ТС]**

Ivandur, спасибо! Но я туплю и не очень понимаю, как соединить этот код с вашим фрагментом

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
#include <iostream>
#include <fstream>
using namespace std;
 
int F(int a, int b, int c)
{
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    else if (a > 20 || b > 20 || c > 20) return F(20, 20, 20);
    else if (a < b && b < c) return F(a, b - 1, c) + F(a, b, c - 1) - F(a, b - 1, c - 1);
    else
    {
        a--;
        return F(a, b - 1, c) + F(a, b, c - 1) - F(a, b - 1, c - 1) + F(a, b, c);
    }
}
 
int main()
{
    int a, b, c;
    
    //ifstream fin;
    //fin.open("INPUT.TXT");
    cin >> a >> b >> c;
    //fin.close();
 
    //ofstream fout;
    //fout.open("OUTPUT.TXT");
    cout << F(a,b,c);
    //fout.close();
 
    return 0;
}

@valen10 · 26.02.2019, 13:15

Ivandur, ваш вариант так же выполняет полный обход дерева рекурсии и никак не ускоряет вычисления. Имеет смысл сохранять уже вычисленные значения в самой функции и брать уже известные числа из таблицы. Подробнее описал это в другой теме.

Niggainsoul, ответил вам в соседней теме. Зачем еще одну создали?

@Niggainsoul · 27.02.2019, 16:48 **[ТС]**

valen10, здравствуйте! Большое спасибо! Подскажите, пожалуйста, как избавиться от этих ошибок?

@valen10 · 27.02.2019, 17:13

Niggainsoul, похоже на конфликт имён. Возможно, где-то еще используется такое имя. Покажите полный код пожалуйста.

@Niggainsoul · 27.02.2019, 18:15 **[ТС]**

valen10, вот:

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
#include <iostream>
using namespace std;
 
static unsigned long long data[20 + 1][20 + 1][20 + 1];
static bool flag[20 + 1][20 + 1][20 + 1];
 
unsigned long long F(long a, long b, long c) 
{
    if (a <= 0 || b <= 0 || c <= 0) return 1;
 
    if (a > 20 || b > 20 || c > 20) return F(20, 20, 20);
 
    if (!flag[a][b][c]) {
        flag[a][b][c] = true;
        if (a < b && b < c) {
            data[a][b][c] = F(a, b - 1, c) + F(a, b, c - 1) - F(a, b - 1, c - 1);
        }
        else {
            data[a][b][c] = F(a - 1, b, c) + F(a - 1, b - 1, c) + F(a - 1, b, c - 1) - F(a - 1, b - 1, c - 1);
        }
    }
 
    return data[a][b][c];
}
 
int main()
{
    long a, b, c;
 
    //ifstream fin;
    //fin.open("INPUT.TXT");
    cin >> a >> b >> c; 
    //fin.close();
 
    //ofstream fout;
    //fout.open("OUTPUT.TXT");
    cout << F(a,b,c);
    //fout.close();
 
    return 0;
}

@valen10 · 27.02.2019, 20:43

Niggainsoul, так и есть, где-то в реализации STL от MS тоже есть такое имя. Чтобы исправить, сделайте одно из этих действий (на ваш выбор):
1. Измените имя data на какое-нибудь другое.
2. Добавьте два двоеточия перед этим именем ::data[a][b][c] внутри функции, чтобы разрешить конфликт имен.
3. Перенесите using namespace std; ниже, после функции F(), перед main().

Новые блоги и статьи Все статьи Все блоги /
Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	26.02.2019, 13:15
	Ivandur, ваш вариант так же выполняет полный обход дерева рекурсии и никак не ускоряет вычисления. Имеет смысл сохранять уже вычисленные значения в самой функции и брать уже известные числа из таблицы. Подробнее описал это в другой теме. Niggainsoul, ответил вам в соседней теме. Зачем еще одну создали? 0

@Niggainsoul 0 / 0 / 0 Регистрация: 20.10.2018 Сообщений: 104
	27.02.2019, 16:48 [ТС]
	valen10, здравствуйте! Большое спасибо! Подскажите, пожалуйста, как избавиться от этих ошибок? Миниатюры 0

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	27.02.2019, 17:13
	Niggainsoul, похоже на конфликт имён. Возможно, где-то еще используется такое имя. Покажите полный код пожалуйста. 0

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	27.02.2019, 20:43
	Niggainsoul, так и есть, где-то в реализации STL от MS тоже есть такое имя. Чтобы исправить, сделайте одно из этих действий (на ваш выбор): 1. Измените имя data на какое-нибудь другое. 2. Добавьте два двоеточия перед этим именем `::data[a][b][c]` внутри функции, чтобы разрешить конфликт имен. 3. Перенесите `using namespace std;` ниже, после функции F(), перед main(). 0

Опции темы