В прошлом видео про Алгоритмы была поставлена задача, разработать Алгоритм поиска самого длинного столбика среди 196 столбов, которые подвешены над землёй на разной высоте.
В этом видео я покажу одно из решений без кода. Попутно, я буду объяснять, что происходит на экране. Надеюсь, это натолкнёт на мысли.
Вопросы.
1) На какой высоте агент исследует столбики, как она меняется?
2) Какие координаты агент исключает из поиска? Может ли исключить координату самого высокого столбика по ошибке?
3) По какому Алгоритму агент исследует найденные столбики?
Я думаю что наверное самым простым алгоритмом будет то когда он будет только подниматься, тоисть каждый раз когда он упрется в какой то столб значит можно подниматься выше и уже искать столбы на том уровне высоты предыдущего столба и когда ему не будет куда упираться значит это и будет наивысший столб
Привет. Предположим, что первый столб, который встретит Агент начинается на высоте 2 и его длина 6, а второй, самый длинный, начинается на высоте 8 и его длина 14. Агент находит первый столб, поднимается на высоту 7 и продолжает поиски, второй столб он не находит, т.к. он на высоте 8. Продолжает движение по остальным 194 столбам, всё время поднимается выше и выше. Возвращается на второй круг уже на высоте 35 и опять пропускает самый высокий столб. Алгоритм не должен оставлять шанса пропустить самый высокий столб, иначе потеряется смысл.
Спасибо большое но этот алгоритм для нелетающих столбов 😂😂😂, а для летающих я ещё подумаю...
Есть два стула: как человек и как програмист(на пайтоне). 1.(как человек): Агент сначало считает кол-во блоков сверху вниз и сравнивает столбы. 2. Лень писать код.
Тут такое дело. Агент не знает где верхняя точка. Столб может быть где угодно от земли до неба. И да, нужно рассуждать, как человек, который дает указания роботу. У робота ограниченные возможности.
Агент должен разделить макимальную высоту которой может быть столбик на 2 и спросить есть ли столбики выше этой высоты. Если столбики есть, то он переходит к 3/4 максимальной высоты и спрашивает, есть ли столбики выше этой высоты, если столбики есть, то он переходит к 7/8 максимальной высоты. Если столбиков выше нет, то он опускается вниз и спрашивает есть ли стольики выше 5/8 максимальной высоты (умножаем знаменатель и числитель 3/4 на 2, получаем 6/8 и вычитаем 1). Если столбики выше 5/8 максимальной высоты есть, то агент страшивает есть ли стообики выше 11/16 максимальной высоты (5/8 = 10/16 +1/16). Так алгоритм все сильнее сужает диапазон своей "видимости" в конце концов приходя к 1 блоку который будет блоком столбика с максимальной высотой. Правда я не думаю что это будет работать учитывая что в видео у автора столбики поялвяются в воздухе. В целом тут может сработать тот же принцип что и при столбиках которые стоят на одной высоте. Алгоритм ищет высоту каждого столбика которые были обнаружены в середине. Выделяет из них самый высокий, и переходит к 3/4 максимальной высоты, просмотрев все столбики тут он может сравнить их с столбиком найденым в середине. Если максимальный столбик найденый в середине остается максимальным, то ничего не меняется и алгоритм начинает просматривать столбики на 7/8 от максимальной высоты. Если же столбик найденый на этой высоте больше чем столбик найденый в середине, и он меняется. Проверив все столбики на высоте 7/8 от максимальной высоты алгоритм может перейти вниз проверяя столбики на 1/4 и 1/8. Из минусов могу отметить что этот способ не подходит в том случае когда столбики слишком маленькие (например от 1 до 20), а максимальная высота скажем 2000 блоков. Если единственный столбик с высотой в 20 находится в промежутке между 1/2 и 3/4. Алгоритм рискует его не найти и остановиться на 19. С другой же стороны можно сделать так, что бы его поиск расходился в разные стороны словно образуя дерево. Это выглядело бы как поиск максимального элемента сначала во всех элементах в середине максимально возможной высоты, потом в 3/4 и 1/4, потом в 7/8, 5/8 и 1/8, 3/8. (15/16, 13/16), (11/16, 9/16) и (3/16, 1/16), (7/16, 5/16). 32, 64, 128 И так далее и так далее... Все зависит от того насколько маленькими могут быть ваши стообики и насколько высокой может быть максимальная высота. Можно так же добавить условие, что если один и тот же столбик встречается в 1/16 и 15/16, то уже не надо проверять наличие столбиков в промежутках ниже 15/16 и выше 1/16.
Во-первых, респект за такой комментарий. Написать его без серьезной работы мозга бы точно не получилось бы. Во-вторых, вопросов, по самому алгоритму у меня много. Агент ничего не знает про длину столбов и высоту, на которой они находятся. Знает только координату блока на земле, над которым этот столб находится. Спросить Агент ничего не может, он добывает информацию, исследуя пространство вокруг себя. Самый долгий алгоритм предполагает, что Агент исследует всё пространство (воздух) под каждым столбиком, пока не найдет сам столб и не измерит его длину. Такую программу я написал в видео с заданием. Вопрос был в том, как можно используя знания, накопленные Агентом, исследовать меньшее количество блоков вокруг. Фишка в том, что зная высоту хотя бы одного столба, можно исключить из проверки целые плоскости пространства. Я позже выложу разбор
Конечно я не програмист а кебешер но решение дам построить пол елси его нету заменить все блоки више пола на песок через 5 сек проверять каждий слой на наличие только 1 блока песка если больше проверять следующий когда будет найден нужний слой заменить блоки песка на опсидиан вот мы и позначили самий большой столб
Даний способ если делать на кб займёт секунд 12 наверно может менше а и ещо етот алгоритм щитает висоту столба ну какой столб самий большой если задача была найти самую високу точку то алгоритм не подойдёт
Задачу нужно решить, обладая ограниченными возможностями, управляя роботом Агентом. Он медленный, может исследовать блоки влево-вправо-назад-вперед-вверх-вниз. Изначально знает координату точки (блока) над которыми расположены столбы на произвольной высоте.