Еще хорошо бы доказать, что ваша стратегия взвешивания оптимальна. Например, в первом случае вы получаете ceil(log_3(N)) взвешиваний. С другой стороны, сделав K взвешиваний вы получаете 3^k возможных результатов (каждое взвешивание дает 3 исхода). Поэтому, чтобы каждая из N монет могла быть идентифицированна как фальшивка, вам надо чтобы 3^k >= N, т.е. k >= ceil(log_3(N)). Поэтому ваш способ точно оптимальный. В четвертом случае оценка снизу ceil(log_3(2*N)), потому что исходов в 2 раза больше - каждая их N монет может оказаться той самой и быть или легче или тяжелее. Вот в третьем варианте все сложно. Вроде как только для определения фальшивки получается тоже ceil(log_3(N)), но ваше решение требует больше взвешиваний, поэтому не очевидно, что оно оптимальное.
Интересно, какой золотой парашют он с собой прихватил? Вот, собственно, кто за все ошибки и отвечает, кто во всем и виноват-то, особо и не страдает от последствий. Его теперь как опытного руководителя с руками оторвут в других фирмах.
А простые роботяги - тех сокращают и фрукты с кофе в офисах оставшимся отменяют. Как же несправделив мир.
Слышали эту мантру "магазин, в который совсем не хочется заходить". Вам, может и нет. А меня передавленная активностями растянутая и заваленная тупым гриндом игра бесит. И раз люди эти ускорпители покупают, значит не только меня.
Потому что, к сожаленю, маркетинг работает. Ведь не спроста во всех ААА играх бюджет на раскрутку просто астрономический. С такими деньгами можно впарить и полную хрень. А среднестатистический покупатель не искушен. Он и не занет, что может быть по-нормальному. Всегда покупал только распиаренные игры, а они уже давно такие.
Если в игре есть ускорители прокачки, а в компании есть директор по монетизации (который, кстати, обвиняет токсичных геймеров в пустом хейте их игр), то как вы думаете, если у компании встанет выбор: улучшать ли геймплей или наоборот его растягивать и передавливать гриндом, какой она сделает выбор? Подсказка: именно выбор испортить жизнь токсичным геймерам повышает ожидаемую прибыль с внутриигрового магазина.
От печати инфляция. А если деньги "лежащие без дела" на вкладах у глупых граждан "временно" изъять, чтобы платить контрактникам, то вроде бы и денежная масса не растет и инфляции должно быть меньше.
Я так понимаю, что база там есть. Когда достигли 1. Но вот мы не знаем, достигает ли ее все состояния. В этом случае - это тоже реализация ДП. Вот только оно корректно если гипотеза выполняется. В противном случае оно виснет. Т.е. если гипотеза не выполняется, то тут просто нельзя было применять ДП. Но это все еще ДП "достигает ли это число 1".
Смотрте, ДП - это когда у вас задача решается через подзадачи. Для ДП вам надо параметризировать задачу и определить 3 вещи:
1) База: ответ для каких-то, обычно, маленьких задач.
2) Рекуррентное соотношение: как ответ к задаче можно пересчитать через ответы к другим задачам.
3) Ответ: какая из множества задач соотвествует вашей исходной.
Вот вся суть динамического программирования. А уже это можно реализовывать как вам удобнее: рекурсией с мемоизацией сверху вниз, циклами снизу-вверх, обходом в ширину с очередью или волновым алгоритмом. Хранить значения можно в матрице, хеш-таблице, сбалансированном дереве или даже в кеше. Можно хранить не все значения, а только последнюю строку или столбец. Можно параллельно считать несколько функций сразу.
Но это все еще остается динамическим программированием. ДП - это НЕ циклы рассчитывающие какую-то матрицу, хотя это частый вариант его реализации. ДП - подход к решению задач, если хотите.
Поэтому рекурсия с мемоизацией 100% соответствует какому-то ДП, потому что рекурсия имеет какую-то базу, задает какое-то рекурретное соотношение, а как вы его вызываете в программе - задает ответ.
в чём смысл этой гипотетической меры по заморозке вкладов?
Деньги государству в это сложное время нужнее, чем вам. Нет, у вас их, конечно, не забирают просто так, вам даже какие-то бумажки или даже электронные баллы (е-баллы) выдадут, с обещаниями - как только, так сразу поменять их на деньги. Но потом.
Там же вся игра - приставка к внутриигровому магазину. И вся эта защита нужна прежде всего, чтобы игроки не могли взломать игру и получать от нее удовольствие. Игрок, пока не занесет денег - должен страдать. В убисофте же работают аж специалисты по монетизации.
Рекурсия с мемоизацией ничем принципиально не отличается от алгоритма, полученного по методу динамического программирования. Так что можно считать любую рекурсию с мемоизацией ДП.
И какое это имеет отношение к обсуждаемой теме? А может и иметь приложение. Вот к этой конкретной задаче он применим и дает вот этот конкретный алгоритм. Который называют ДП.
Ну не говорят каждый раз "алгоритм решения задачи, основанный на методе динамического программирования". В обиходе называют вот этот конкретный алгоритм решения этой конкретной задачи Динамическим Программированием и все. И всем сразу понятно как и почему он работает.
И везде, где этот метод применяют для решения задачи появляется та самая "матрица" о которой вы говорите, ибо в методе ДП предусмотрено переиспользование решений подзадач.
Странно, что вы мне приводите ссылку на Википедию из моей же статьи.
Странно, что вы приведя эту ссылку, пропустили там целую секцию.
И я вам показал, что одной только матрицей тут не всегда можно обойтись.
Зачем искать какие-то ресурсы? Если хотите проверить, можно просто перемножить эти 2 матрицы хотя бы вручную.
Спасибо, но пападаю на ту же страницу с подпиской.
Требует платной подписки.
Так а где эта самая бесплатная версия-то есть вообще? Ссылку то дайте что ли.
Еще хорошо бы доказать, что ваша стратегия взвешивания оптимальна. Например, в первом случае вы получаете ceil(log_3(N)) взвешиваний. С другой стороны, сделав K взвешиваний вы получаете 3^k возможных результатов (каждое взвешивание дает 3 исхода). Поэтому, чтобы каждая из N монет могла быть идентифицированна как фальшивка, вам надо чтобы 3^k >= N, т.е. k >= ceil(log_3(N)). Поэтому ваш способ точно оптимальный. В четвертом случае оценка снизу ceil(log_3(2*N)), потому что исходов в 2 раза больше - каждая их N монет может оказаться той самой и быть или легче или тяжелее. Вот в третьем варианте все сложно. Вроде как только для определения фальшивки получается тоже ceil(log_3(N)), но ваше решение требует больше взвешиваний, поэтому не очевидно, что оно оптимальное.
Ноль рублей, ноль копеек. Ибо друзьям - все, врагам - закон.
Интересно, какой золотой парашют он с собой прихватил? Вот, собственно, кто за все ошибки и отвечает, кто во всем и виноват-то, особо и не страдает от последствий. Его теперь как опытного руководителя с руками оторвут в других фирмах.
А простые роботяги - тех сокращают и фрукты с кофе в офисах оставшимся отменяют. Как же несправделив мир.
Слышали эту мантру "магазин, в который совсем не хочется заходить". Вам, может и нет. А меня передавленная активностями растянутая и заваленная тупым гриндом игра бесит. И раз люди эти ускорпители покупают, значит не только меня.
А вы знатете, считаются ли среди этих 4 миллионов доносов выданные под пытками оговоры коллег и родственников?
Но эти средства не смогут тратить те, чьи вклады заморожены. Так что инфляция будет меньше.
Потому что, к сожаленю, маркетинг работает. Ведь не спроста во всех ААА играх бюджет на раскрутку просто астрономический. С такими деньгами можно впарить и полную хрень. А среднестатистический покупатель не искушен. Он и не занет, что может быть по-нормальному. Всегда покупал только распиаренные игры, а они уже давно такие.
Если в игре есть ускорители прокачки, а в компании есть директор по монетизации (который, кстати, обвиняет токсичных геймеров в пустом хейте их игр), то как вы думаете, если у компании встанет выбор: улучшать ли геймплей или наоборот его растягивать и передавливать гриндом, какой она сделает выбор? Подсказка: именно выбор испортить жизнь токсичным геймерам повышает ожидаемую прибыль с внутриигрового магазина.
От печати инфляция. А если деньги "лежащие без дела" на вкладах у глупых граждан "временно" изъять, чтобы платить контрактникам, то вроде бы и денежная масса не растет и инфляции должно быть меньше.
Я так понимаю, что база там есть. Когда достигли 1. Но вот мы не знаем, достигает ли ее все состояния. В этом случае - это тоже реализация ДП. Вот только оно корректно если гипотеза выполняется. В противном случае оно виснет. Т.е. если гипотеза не выполняется, то тут просто нельзя было применять ДП. Но это все еще ДП "достигает ли это число 1".
А как в такой рекурсии работает мемоизация? Если там нет базы, как она вообще останавливается?
Смотрте, ДП - это когда у вас задача решается через подзадачи. Для ДП вам надо параметризировать задачу и определить 3 вещи:
1) База: ответ для каких-то, обычно, маленьких задач.
2) Рекуррентное соотношение: как ответ к задаче можно пересчитать через ответы к другим задачам.
3) Ответ: какая из множества задач соотвествует вашей исходной.
Вот вся суть динамического программирования. А уже это можно реализовывать как вам удобнее: рекурсией с мемоизацией сверху вниз, циклами снизу-вверх, обходом в ширину с очередью или волновым алгоритмом. Хранить значения можно в матрице, хеш-таблице, сбалансированном дереве или даже в кеше. Можно хранить не все значения, а только последнюю строку или столбец. Можно параллельно считать несколько функций сразу.
Но это все еще остается динамическим программированием. ДП - это НЕ циклы рассчитывающие какую-то матрицу, хотя это частый вариант его реализации. ДП - подход к решению задач, если хотите.
Поэтому рекурсия с мемоизацией 100% соответствует какому-то ДП, потому что рекурсия имеет какую-то базу, задает какое-то рекурретное соотношение, а как вы его вызываете в программе - задает ответ.
Деньги государству в это сложное время нужнее, чем вам. Нет, у вас их, конечно, не забирают просто так, вам даже какие-то бумажки или даже электронные баллы (е-баллы) выдадут, с обещаниями - как только, так сразу поменять их на деньги. Но потом.
Там же вся игра - приставка к внутриигровому магазину. И вся эта защита нужна прежде всего, чтобы игроки не могли взломать игру и получать от нее удовольствие. Игрок, пока не занесет денег - должен страдать. В убисофте же работают аж специалисты по монетизации.
Рекурсия с мемоизацией ничем принципиально не отличается от алгоритма, полученного по методу динамического программирования. Так что можно считать любую рекурсию с мемоизацией ДП.
И какое это имеет отношение к обсуждаемой теме? А может и иметь приложение. Вот к этой конкретной задаче он применим и дает вот этот конкретный алгоритм. Который называют ДП.
Ну не говорят каждый раз "алгоритм решения задачи, основанный на методе динамического программирования". В обиходе называют вот этот конкретный алгоритм решения этой конкретной задачи Динамическим Программированием и все. И всем сразу понятно как и почему он работает.
И везде, где этот метод применяют для решения задачи появляется та самая "матрица" о которой вы говорите, ибо в методе ДП предусмотрено переиспользование решений подзадач.
Странно, что вы приведя эту ссылку, пропустили там целую секцию.
Я обошелся. И быстрее вашего решения на порядки.