Избавиться от рекурсии

@ManyGames · Регистрация: 10.07.2018

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

Здравствуйте. У меня имеется рекурсивный метод:

Java
1
2
3
4
5
6
7
8
9
10
11
12
    static void dfs(int v, int last){
        if(g[v]) return;
        g[v] = true;
        d[v] = d[last]+1;
        if(d[v]>max){
            max=d[v];
            maxInd = v;
        }
        for(int u:graph[v]){
            dfs(u, v);
        }
    }

На acmp решение с применением этого метода получет ML, думаю, что чтоб избежать этого, нужно избавиться от рекурсии.
Как это сделать для данного метода? У меня не очень-то получается

@xoraxax · 06.08.2018, 05:41

На acmp решение с применением этого метода получет ML,
Чо?

@Aviz__ · 06.08.2018, 08:57

Сообщение от ManyGames

решение

чего решаешь то? что есть свое решение - это хорошо, но условие всей задачи приведи.

@ManyGames · 06.08.2018, 10:10 **[ТС]**

Сообщение от xoraxax

На acmp решение с применением этого метода получет ML,
Чо?

acmp - сайт с задачками
ML - Memory Limit Exceeded, превышение ограничений по памяти

Добавлено через 3 минуты
Вот задача на acmp:

И вот моё решение:

Java
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
import java.io.*;
import java.util.*;
 
public class Test{
 
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static ArrayList<Integer> graph[];
    static int n, m, maxInd;
    static long d[], max;
    static boolean g[];
 
    public static void main(String[] args) throws IOException {
        n = nextInt(); m = nextInt();
        graph = new ArrayList[n];
        d = new long[n];
        g = new boolean[n];
        for(int i = 0;i<n; i++) //инициализация
            graph[i] = new ArrayList<>();
        for(int i = 1; i<n; i++){
            int tmp = nextInt()-1;
            graph[tmp].add(i);
            graph[i].add(tmp);
        }
 
        //Первый dfs
        d[0] = -1;
        dfs(0, 0);
        Arrays.fill(g, false);
        //Второй dfs
        d[0] = -1;
        long z = max+1;
        max=0;
        dfs(maxInd, 0);
        System.out.println(max+1+(z*2)*(m-1));
    }
 
    static int nextInt() throws IOException {
        in.nextToken();
        return (int)in.nval;
    }
 
    static void dfs(int v, int last){
        if(g[v]) return;
        g[v] = true;
        d[v] = d[last]+1;
        if(d[v]>max){
            max=d[v];
            maxInd = v;
        }
        for(int u:graph[v]){
            dfs(u, v);
        }
    }
}

На codeforces такое решение прошло полностью, ибо там лимит по памяти 512 МБ

Добавлено через 4 минуты

Сообщение от ManyGames

Вот задача на acmp:

Тут

@Aviz__ · 06.08.2018, 10:15

Сообщение от ManyGames

Вот задача

тебе нужна помощь, а мы должны ходить по ссылке!? Приведи текст задачи здесь.

@ManyGames · 06.08.2018, 10:21 **[ТС]**

Пробовал избавиться от рекурсии при помощи очереди вот так:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static void dfs(int v, int last){
        LinkedList<Integer> qV = new LinkedList<>();
        LinkedList<Integer> qLast = new LinkedList<>();
        qV.offer(v);
        qLast.offer(last);
        while(!qV.isEmpty()){
            v = qV.pop();
            last = qLast.pop();
            if(g[v]) return;
            g[v] = true;
            d[v] = d[last]+1;
            if(d[v]>max){
                max=d[v];
                maxInd = v;
            }
            for(int u:graph[v]){
                if(!g[u]){
                    qV.offer(u);
                    qLast.offer(v);
                }
            }
        }
    }

Но все равно ML

Добавлено через 2 минуты

Сообщение от Aviz__

тебе нужна помощь, а мы должны ходить по ссылке!? Приведи текст задачи здесь.

В лаборатории теоретической пиротехники изучают новые технологии организации фейерверков. Фейерверк представляется как корневое дерево, а поскольку в мощном фейерверке его элементы также взрываются, порождая новые фейерверки, то ученые вводят операцию возведения корневого дерева в степень.

Корневое дерево содержит одну или несколько вершин. Одна из вершин выделена и называется корнем дерева, для каждой из остальных вершин ровно одна другая вершина является родителем. При этом от любой вершины можно добраться до корня, последовательно переходя от вершины к ее родителю. Вершина, которая не является родителем никакой другой вершины, называется листом. Если вершина x является родителем вершины y, то вершина y является ребенком вершины x. Будем говорить, что вершина и ее родитель соединены ребром.
Фейерверк задается своим базовым деревом T и мощностью m. Фейерверк представляется деревом, которое получается в результате возведения дерева T в степень m. Операция возведения дерева в степень устроена следующим образом. Если m = 1, то результат T1 — само дерево T. Для m > 1 рассмотрим дерево Tm – 1. Выполним следующую операцию: для каждого листа x дерева Tm – 1 создадим копию дерева T и назначим лист x родителем корня соответствующей копии. Получившееся дерево будет деревом Tm.
Путем в дереве называется последовательность вершин, в которой две соседние вершины соединены ребром. Все вершины в пути должны быть различны.
Для того, чтобы оценить красоту фейерверка, необходимо определить, какое максимальное количество вершин может содержать путь в дереве, которым представляется фейерверк
Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m.

Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа n и m – количество вершин в базовом дереве фейерверка T и его мощность (3 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000).
Вторая строка описывает дерево T и содержит (n – 1) целых чисел: p2, p3, …, pn – номера родителей вершин 2, 3, …, n, соответственно (1 ≤ pi ≤ i – 1).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – красоту фейерверка, представляемого деревом Tm.

Пример:
Ввод:
4 2
1 1 2
Вывод:
10

@Aviz__ · 06.08.2018, 11:49

а базовое дерево с числом узлов 5, какой вид должно иметь?
вид 1:
-------1
-----2---3
----4
---5
или вид 2:
-------1
-----2---3
---4------5
Вид 2, в плане красоты, при умножении, на мой взгляд, лучше.
И почему нужно без рекурсии?
Если, скажем, любое дерево растет, по виду 1, то при умножении, все проще))

@ManyGames · 06.08.2018, 13:51 **[ТС]**

Сообщение от Aviz__

а базовое дерево с числом узлов 5, какой вид должно иметь?

Базовое дерево нельзя строить произвольно, зависит от входных данных. Например, входные данные такие
5 2
1 1 3 3
То базовое дерево выглядит так:
------1
---2----3
------4---5
Я решаю так: храню граф в списке смежности graph и выполняю поиск диаметра дерева.
Для данного примера список смежности выглядит так:
1) 2, 3
2) -
3) 4, 5
4) -
5) -
Но, для того чтоб выполнить второй обход в глубину, храню его как неориентированный граф.
Сначала запускаю первый dfs от первой вершины и ищу самую удаленную, в примере самая удаленная - 5. Запоминаю расстояние до неё в переменную z(3). Потом от самой удаленной вершины запускаю ещё раз dfs, в примере от пятой вершины самая удаленная - вторая, расстояние до неё - 4. А далее по формуле ans = max+(z*2)*(m-1) (где max - диаметр дерева, z - расстояние от первой вершины до самой удаленной, m - из условия) вывожу ответ. В примере z = 3, max = 4. ans = 4+(3*2)*(2-1) = 4+6 = 10

На codeforces, повторюсь, такое решение прошло, а на acmp нет - ML. Но на codeforces по памяти ограничение в 512 Мб, а на acmp - всего 16.

Добавлено через 4 минуты
То есть я рассматриваю только базовое дерево, а ответ высчитываю по формуле

@Aviz__ · 06.08.2018, 13:54

так чем тебе рекурсия не мила?

@ManyGames · 06.08.2018, 13:56 **[ТС]**

Сообщение от ManyGames

На acmp решение с применением этого метода получет ML, думаю, что чтоб избежать этого, нужно избавиться от рекурсии.

Сообщение от Aviz__

так чем тебе рекурсия не мила?

Вероятно, стек при работе моего решения занимает много памяти, из-за этого решение не проходит
Но может я и ошибаюсь

@Aviz__ · 06.08.2018, 14:00

Сообщение от ManyGames

Вероятно

оптимизируй рекурсивный метод))

@ManyGames · 06.08.2018, 14:11 **[ТС]**

Там, где 205 Мб - рекурсивный dfs, а там, где 36 Мб - без рекурсии (метод, который я писал выше).
Вы все ещё думаете, что рекурсивный метод можно оптимизировать?)

@Aviz__ · 06.08.2018, 14:17

надеюсь, это поможет понять где у твоего рекурс метода засада https://www.cyberforum.ru/java/thread2250765.html - дебагер

@ManyGames · 06.08.2018, 14:37 **[ТС]**

Засада?.. Алгоритм я вычитал в книге Антти Лааксонена "Олимпиадное программирование", им же и воспользовался. Не думаю, что спортивный программист такого высокого уровня может издать книгу, в которой некоторые алгоритмы "с засадами".

@Aviz__ · 06.08.2018, 14:42

ManyGames, Ок! Удачи)). Когда на авторитетов перестанешь кивать, продолжим...

@snickers0137 · 28.11.2018, 17:10

Твое решение неправильно работает. Контрпример:
4 2
1 2 3
Ответ:8, а у тебя 12.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Programma_Boinc 01.01.2026 Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	06.08.2018, 05:41
	На acmp решение с применением этого метода получет ML, Чо? 0

@Aviz__ 2736 / 2046 / 506 Регистрация: 17.02.2014 Сообщений: 9,462
	06.08.2018, 11:49
	а базовое дерево с числом узлов 5, какой вид должно иметь? вид 1: -------1 -----2---3 ----4 ---5 или вид 2: -------1 -----2---3 ---4------5 Вид 2, в плане красоты, при умножении, на мой взгляд, лучше. И почему нужно без рекурсии? Если, скажем, любое дерево растет, по виду 1, то при умножении, все проще)) 0

@Aviz__ 2736 / 2046 / 506 Регистрация: 17.02.2014 Сообщений: 9,462
	06.08.2018, 13:54
	так чем тебе рекурсия не мила? 0

@ManyGames 10 / 11 / 2 Регистрация: 10.07.2018 Сообщений: 70 Записей в блоге: 1
	06.08.2018, 14:11 [ТС]
	Там, где 205 Мб - рекурсивный dfs, а там, где 36 Мб - без рекурсии (метод, который я писал выше). Вы все ещё думаете, что рекурсивный метод можно оптимизировать?) Миниатюры 0

@Aviz__ 2736 / 2046 / 506 Регистрация: 17.02.2014 Сообщений: 9,462
	06.08.2018, 14:17
	надеюсь, это поможет понять где у твоего рекурс метода засада https://www.cyberforum.ru/java/thread2250765.html - дебагер 0

@ManyGames 10 / 11 / 2 Регистрация: 10.07.2018 Сообщений: 70 Записей в блоге: 1
	06.08.2018, 14:37 [ТС]
	Засада?.. Алгоритм я вычитал в книге Антти Лааксонена "Олимпиадное программирование", им же и воспользовался. Не думаю, что спортивный программист такого высокого уровня может издать книгу, в которой некоторые алгоритмы "с засадами". 0

@Aviz__ 2736 / 2046 / 506 Регистрация: 17.02.2014 Сообщений: 9,462
	06.08.2018, 14:42
	ManyGames, Ок! Удачи)). Когда на авторитетов перестанешь кивать, продолжим... 1

@snickers0137 1 / 1 / 0 Регистрация: 28.07.2016 Сообщений: 9
	28.11.2018, 17:10
	Твое решение неправильно работает. Контрпример: 4 2 1 2 3 Ответ:8, а у тебя 12. 1