Мне кажется, что думающие отличаются от минусующих тем, что не боятся задать вопрос.
А минусующие боятся, и мстят думающим за свой страх.
Что ж, мои соболезнования.
SuperGLUE содержит довольно сложные семантические задачи, такие как схемы Винограда:
Трофей не помещается в коричневый чемодан, потому что он слишком мал.
Что слишком мало?
Ответ: чемодан.
Хотелось бы позадавать ему всяких каверзных вопросов:
Трофей не помещается в коричневый чемодан, потому что он слишком мал. Кто слишком мал?
Трофей не помещается в коричневый чемодан, потому что он слишком велик. Что слишком велик?
Трофей не помещается в коричневый чемодан, потому что он слишком мал. Помещается ли чемодан в Тимофея?
Дружище, тебе очень нравится рекурсия. Мне тоже. Смотри.
Самый-самый классический кейс про рекурсию — DFS, обход дерева в глубину. Фишка в том, что приходтся возвращаться к развилкам, к тем данным, какие ты надыбал, впервые подойдя к развилке, и уходить из этой развилки с этими стартовыми данными в другую ветвь.
Это всегда хорошо работает, но не всегда нужно. Представь, что твоё дерево — бамбук. Развилок нет вообще, прёшь вверх до упора, упёрся — спрыгнул. Нет смысла запоминать ситуации на развилках, ведь развилок нет. Вот это-то и значит, что рекурсия тебе избыточна, достаточно итерации.
В данном случае отсутствие развилок — это природа жадного алгоритма. Ты откусываешь от n максимально возможное число фибоначчи, на другие не смотришь.
С Новым годом.
Вообще-то тут тоже бинарное представление: 100(в десятичной) записывается как 1000010100, подразумеваем (89)0000(8)0(3)00 — тут вместо еденичек в скобках веса соответствующих разрядов. Отмечу, что ряд фибоначчи тут начинается с 1,2,3,5… — меньшие веса здесь избыточны.
Когда-то такое представление рассматривали как код, выявляющий ошибки — в представлении числа не может быть двух еденичек подряд. А потом придумали код Хэмминга, код Соломона-Рида, и эту чепуху выбросили.
ps Если уж автор добрался до статьи в вики, он бы мог её прочитать.
Для любого заданного натурального числа его цекендорфово представление находится при помощи жадного алгоритма
Логика, как эпистемологический инструмент, изобретена независимо в трёх отдельных государствах: Греции (Аристотелем), Китае (императором Цинь Шихуанди) и Индии.
генератор звуковых частот, работавший на лампе накаливания
HP200A и вправду использовал лампочку в качестве терморезистора в цепи обратной связи, но процитированный текст — это классическое «у ней внутре неонка».
3*3*3*5*5*7*11*13*17*19*23*29*31*37*41*43*47 == 0xbfffdd7cc41833d5
— это максимальное число, умещающееся в uint64 и делящееся без остатка на _все_ нечетные от 3 до 47 включительно. Таким образом твой ошибочный код прервётся, выполнив (49-3)//2 == 23 взятий остатков — это максимум, любое другое uint64 даст меньше.
Ближайшее большое простое — 0xbfffdd7cc4183473, _правильный_ код проверки его на простоту потребует int(0xbfffdd7cc4183473**.5)//2-1 == 1859772841 взятий остатков, т.е. в 80_859_688 раз больше.
Верно, что у меня n^2, но неверно, что меньше никак. Можно разменять память на время:
хранить в ячейках dp кортежи (длина палиндрома, индекс первого символа палиндрома, индекс последнего). Получим в итоге кортеж про длиннейший палиндром — тогда крайний символ кладём на стек, а у строки обрубаем начало и конец, включая эти первый и последний символы; если её длина <= 1 — палиндром считай восстановлен, иначе — опять ищем max на обкорнаной строке.
Извращение, конечно.
from operator import itemgetter
def f(s: str) -> str:
def helper(s):
prev = [(0, i, i) for i in range(len(s))]
cur = [(1, i, i) for i in range(len(s))]
key = itemgetter(0)
for gap in range(1, len(s)):
cur, prev = [(prev[i][0] + 2, i, i + gap) if s[i] == ch
else max(cur[i:i + 2], key=key)
for i, ch in enumerate(s[gap:])], cur[1:-1]
return cur[0]
st = []
while len(s) > 1:
le, lo, hi = helper(s)
if le < 2:
s = s[lo:lo + le]
else:
st.append(s[lo])
s = s[lo + 1:hi]
return (''.join([*st, s, *st[::-1]]))
print(repr(f('aba')))
Ну и по памяти вовсе не обязательно тратить О(n^2):
def f(s: str) -> str:
prev, cur = [''] * len(s), s
for gap in range(1, len(s)):
cur, prev = [f'{ch}{prev[i]}{ch}' if s[i] == ch
else max(cur[i:i + 2], key=len)
for i, ch in enumerate(s[gap:])], cur[1:-1]
return (cur[0] if s else '')
Сразу же было решено отказаться от VBA поскольку я не программист от слова совсем.
Сейчас я веду учет в трех файлах — это DATA + файл с простыми вычислениями (BASIC)
А минусующие боятся, и мстят думающим за свой страх.
Что ж, мои соболезнования.
Хотелось бы позадавать ему всяких каверзных вопросов:
Это не пост, а коммент — но ты всё равно молодец!
Осталось подумать над чужими комментариями — и ты в клубе!
Самый-самый классический кейс про рекурсию — DFS, обход дерева в глубину. Фишка в том, что приходтся возвращаться к развилкам, к тем данным, какие ты надыбал, впервые подойдя к развилке, и уходить из этой развилки с этими стартовыми данными в другую ветвь.
Это всегда хорошо работает, но не всегда нужно. Представь, что твоё дерево — бамбук. Развилок нет вообще, прёшь вверх до упора, упёрся — спрыгнул. Нет смысла запоминать ситуации на развилках, ведь развилок нет. Вот это-то и значит, что рекурсия тебе избыточна, достаточно итерации.
В данном случае отсутствие развилок — это природа жадного алгоритма. Ты откусываешь от n максимально возможное число фибоначчи, на другие не смотришь.
С Новым годом.
Рекурсия выглядит уныло, если достаточно простой итерации.
Извиняюсь за стиль, ruby не мой профиль.
Когда-то такое представление рассматривали как код, выявляющий ошибки — в представлении числа не может быть двух еденичек подряд. А потом придумали код Хэмминга, код Соломона-Рида, и эту чепуху выбросили.
ps Если уж автор добрался до статьи в вики, он бы мог её прочитать.
Какой перебор, какая рекурсия, какой фибонаЧе?..
С Новым годом, гугл-переводчик.
Вам надо ещу поправить. К чему торопыжничать?
Фактчекинг в русскоязычном секторе интернета, как и в англоязычном, даёт основание полагать, что автор сего опуса — фантазёр.
HP200A и вправду использовал лампочку в качестве терморезистора в цепи обратной связи, но процитированный текст — это классическое «у ней внутре неонка».
3*3*3*5*5*7*11*13*17*19*23*29*31*37*41*43*47 == 0xbfffdd7cc41833d5
— это максимальное число, умещающееся в uint64 и делящееся без остатка на _все_ нечетные от 3 до 47 включительно. Таким образом твой ошибочный код прервётся, выполнив (49-3)//2 == 23 взятий остатков — это максимум, любое другое uint64 даст меньше.
Ближайшее большое простое — 0xbfffdd7cc4183473, _правильный_ код проверки его на простоту потребует int(0xbfffdd7cc4183473**.5)//2-1 == 1859772841 взятий остатков, т.е. в 80_859_688 раз больше.
Делаем выводы, расходимся )
Пацана взяли на слабо и поимели: босс от щедрот удвоил срока, но сделал его крайним. Пацан хотя бы смог это отрефлексировать. А наш мальчик терпит.
Тут я сообразил, что это — перевод (да, я смотрю текст прежде авторства). И вот что я скажу — в нашей культуре всё по другому. Наш мальчик терпит.
хранить в ячейках dp кортежи (длина палиндрома, индекс первого символа палиндрома, индекс последнего). Получим в итоге кортеж про длиннейший палиндром — тогда крайний символ кладём на стек, а у строки обрубаем начало и конец, включая эти первый и последний символы; если её длина <= 1 — палиндром считай восстановлен, иначе — опять ищем max на обкорнаной строке.
Извращение, конечно.
Растут аксиомы, не ведая стыда…