Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
154 / 153 / 29
Регистрация: 21.05.2010
Сообщений: 338

Понимание рекурсии

31.10.2013, 16:46. Показов 1193. Ответов 10
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго всем времени суток! В статье на Хабре "Как я завалил собеседование в Twitter" заинтересовала задачка. Для решения её сначала хочу найти крайний максимальный элемент с левой стороны и максимальный с правой (границы ямы). Т.к. справа у нас 2 элемента подряд со значениями 7 (элементы с индексами 6 и 7) - то мне нужно вернуть индекс 6. Но в моём коде, найдя индекс 6 и дойдя до return - вместо выхода из рекурсивного вызова метода - снова выполняет его. Не могу понять, почему. Вот собственно код:

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
class Program
    {
        private static int[] arr;
 
        static void Main()
        {
            arr = new[] {2, 5, 1, 2, 3, 4, 7, 7, 6}; // исходные данные.
 
            int left = GetLeft(0), // индекс крайнего максимального левого элемента, ближайшего к центру (левая граница ямы).
                right = GetRight(arr.Length - 1), // индекс крайнего максимального правого элемента, ближайшего к центру (правая граница ямы).
                sum = 0; // количество воды
 
            for (int i = left + 1; i < right - 1; i++)
                sum += Math.Min(arr[left], arr[right]) - arr[i]; // прибавляем к сумме разницу между минимальным значением границы и текущим значением.
            Console.WriteLine(sum);
            
            Console.WriteLine("Press <Enter> to exit.");
            Console.ReadLine();
        }
 
        /// <summary>
        /// Находит максимальный крайний левый индекс массива, приближённый к центру (яме).
        /// </summary>
        private static int GetLeft(int i)
        {
            if (i == arr.Length - 1)
                return i;
 
            if (arr[i] <= arr[i + 1])
                GetLeft(++i);
            return i;
        }
 
        /// <summary>
        /// Находит максимальный крайний правый индекс массива, приближённый к центру (яме).
        /// </summary>
        private static int GetRight(int i)
        {
            if (i == 0)
                return i;
 
            if (arr[i] <= arr[i - 1])
                GetRight(--i);
            return i; // здесь должно возвратить i = 6. Вместо этого - снова попадаем в метод GetRight.
        }
    }
Также, если в массив после элемента с индексом 1 добавить ещё один элемент со значением 5, сразу за ним - та же проблема.

p.s.: я понимаю, что на данном этапе решение задачи не совсем правильное, ибо "ям" может быть более одной, но в данный момент меня интересует корректность отработки рекурсивных методов. Чего-то я не понимаю, видимо.

Добавлено через 12 минут
в методе GetRight
C#
1
if (i == 0)
заменить на
C#
1
if (i == 1)
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
31.10.2013, 16:46
Ответы с готовыми решениями:

Понимание рекурсии
Ребята. Подскажите как можно понять рекурсию. Плотно застрял нна рекурсивных алгоритмах. Никак не могу понять принцип. Пытался рисовать...

Понимание программирования
Сообственно говоря вот такая ситуация. Программированием занимаюсь 6 месяцев. Очень нравится.Прошел через тестирование на курсы по...

Помощь в понимание Классов
SHT11_GPIO_IOProvider SHT11_IO = new SHT11_GPIO_IOProvider((Cpu.Pin)29, (Cpu.Pin)28); SensirionSHT11 SHT11 = new SensirionSHT11(SHT11_IO)...

10
208 / 164 / 29
Регистрация: 11.09.2013
Сообщений: 445
31.10.2013, 17:57
сложно вникнуть без комментариев в коде. к слову сказать, на хабре решение все равно неправильное. можно за один проход так:

весь воздух делаем водой. потом начинаем с верхнего ряда удаляем воду слева, потом справа. с каждым удаленным кубом уменьшаем счетчик воды. остается та, которая не может вытечь, а значение счетчика - ее количество
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
31.10.2013, 18:00
Цитата Сообщение от sezada Посмотреть сообщение
можно за один проход так:
весь воздух делаем водой. потом начинаем с верхнего ряда удаляем воду слева, потом справа.
Для того, чтобы заполнить весь воздух водой, нужно знать максимальную высоту, а это уже один обход.

Цитата Сообщение от sezada Посмотреть сообщение
на хабре решение все равно неправильное.
Неправильно считает?
0
154 / 153 / 29
Регистрация: 21.05.2010
Сообщений: 338
31.10.2013, 18:01  [ТС]
sezada, меня сейчас интересует не решение задачи, а почему, дойдя до строки 46, снова переходим к строке 44, притом значение i увеличивается.
0
208 / 164 / 29
Регистрация: 11.09.2013
Сообщений: 445
31.10.2013, 18:09
Цитата Сообщение от kolorotur Посмотреть сообщение
Неправильно считает?
да. пропустит более мелкие горбы, если они лежат вне границ локальных максимумов

Добавлено через 6 минут
Цитата Сообщение от Smems Посмотреть сообщение
меня сейчас интересует не решение задачи, а почему, дойдя до строки 46, снова переходим к строке 44, притом значение i увеличивается
скорее всего, в предыдущем вызове значение i было больше (вы ведь его уменьшаете, верно?). тк каждый вызов метода хранит свой набор локальных переменных, получаем результат. повторю: не могу помочь, потому что не хочу вникать в некомментированный код. простите, если обидел
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
31.10.2013, 18:11
Цитата Сообщение от sezada Посмотреть сообщение
да. пропустит более мелкие горбы, если они лежат вне границ локальных максимумов
Странно, сколько смотрю на алгоритм, не могу представить ситуацию, где подсчитает неправильно.
Можете показать простой пример массива, для которого не сработает?
0
208 / 164 / 29
Регистрация: 11.09.2013
Сообщений: 445
31.10.2013, 18:14
3 2 5 4 4 5 3 1

пропустит единичку воды по индексу 1 (считая от 0), если взять воду только между максимумами по индексам 2 и 5
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
31.10.2013, 18:25
Цитата Сообщение от sezada Посмотреть сообщение
пропустит единичку воды по индексу 1 (считая от 0), если взять воду только между максимумами по индексам 2 и 5
Разве?
Если на бумаге, то объем будет 0 1 0 1 1 0 0 0, если по алгоритму, то тоже 3.
0
208 / 164 / 29
Регистрация: 11.09.2013
Сообщений: 445
31.10.2013, 19:27
Цитата Сообщение от kolorotur Посмотреть сообщение
Разве?
Если на бумаге, то объем будет 0 1 0 1 1 0 0 0, если по алгоритму, то тоже 3.
да, Вы правы. я неправильно понял алгоритм. но мой тоже работает =Р
0
154 / 153 / 29
Регистрация: 21.05.2010
Сообщений: 338
01.11.2013, 12:31  [ТС]
Почему же при return i; не выходит из метода? Вернее, выходит и снова туда же... Под отладчиком хорошо видно и мне не понятно.
0
208 / 164 / 29
Регистрация: 11.09.2013
Сообщений: 445
01.11.2013, 15:39
Цитата Сообщение от Smems Посмотреть сообщение
Под отладчиком хорошо видно и мне не понятно.
найдите окно StackTrace. в нем будет видно, сколько раз вызывалась функция и в какой из вызовов Вы возвращаетесь
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
01.11.2013, 15:39
Помогаю со студенческими работами здесь

Понимание анонимных функций
Доброе время суток. Имеется делегат: delegate void StudentListHandler(object source,StudentListHandlerEventArgs args); Событие,...

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

Не понимание полиморфизма и статического поля на примере представленного кода
Здравствуйте, Объясните мне пожалуйста по следующему коду: using System; class Base { } class Derived : Base {

Система шифрования Вижинера: есть понимание сути, нет понимания кода
В системе шифрования Вижинера я вроде как разобралась, но как показала практика, правильно получается только на листе бумаги.Вот что у...

Рекурсии
Решить задачу в консольном режиме: Написать рекурсивную функцию для вычесления значения так называемой функции Аккермана для...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru