Работа в Антарктике
Повертеть Иеремией Бентамом
Космические фотографии
Об утятах, чёрных дырах и всей Вселенной
Легенда о поединке Пересвета и Темир–Мурзы на Куликовом поле
Машинный перевод
Доказана инфляционная модель Вселенной 
Иероглифы древних майя
Равенство классов P и NP доказано (возможно)
Фантастические теории, которые стали научными фактами в 2012 году
Богомолы - котики будущего
Язык токи пона (или Токипона) - toki pona 
Занимательная лингвистика
О роли магнитного поля Земли
Добро пожаловать в науку 
эталон веса "теряет вес"
Япет и стена Япета
Экологическая катастрофа в Коми 
Паразиты и их хозяева
Бесплатное образование за рубежом
Пётр Алексеевич Кропоткин
HPV — вирус папилломы человека
NASA исследует возможность путешествий на скоростях больше скорости света, при этом, не разрушая ОТО.
Сколько вселенных может поместиться флешку?
Психофизиология
Научное образование в США и России
почему неверно выражение A>=B, если A=Истина, B=Ложь?
12 когнитивных предвзятостей, мешающих рационально мыслить.
Чересчур хорошего – уже плохо
Быстроглазости мух нашли объяснение
Микробы управляют своими хозяевами
Теперь понятно, почему зелёная плесень ядовита
Утро вечера мудренее, или идёмте по стопам Менделеева!
В том, что кабанье мясо нравится не всем, виновата наследственность
О ревности и зависти на работе
Американские учёные замахнулись на фотосинтез
Самцам большой панды не всё равно, когда заниматься сексом
Коварная микрофлора и двуликие иммунные клетки
Зелёные недотроги
Санитары леса, вернитесь!
Распространение ртути в мелких водоёмах: на безрыбье и жук – аккумулятор
Паучий шёлк – теплопроводник, не уступающий металлам
Фермент Cdk1 – наш козырь в борьбе с бесплодием
Не правым единым творит человек
Растения способны учуять болезнь соседа, хотя и далеко не сразу
У кого и что болит, тот на это и глядит
Сократив количество выкуренных сигарет, мозгу не помочь
Какая нам может быть польза от депрессии?
Homo homini lupus est
Постарайтесь понять, что чувствует любимый человек: вам зачтётсяРабота в АнтарктикеПовертеть Иеремией БентамомКосмические фотографииОб утятах, чёрных дырах и всей ВселеннойЛегенда о поединке Пересвета и Темир–Мурзы на Куликовом полеМашинный переводДоказана инфляционная модель Вселенной Иероглифы древних майяРавенство классов P и NP доказано (возможно)Фантастические теории, которые стали научными фактами в 2012 годуБогомолы - котики будущегоЯзык токи пона (или Токипона) - toki pona Занимательная лингвистикаО роли магнитного поля ЗемлиДобро пожаловать в науку эталон веса "теряет вес"Япет и стена ЯпетаЭкологическая катастрофа в Коми Паразиты и их хозяеваБесплатное образование за рубежомПётр Алексеевич КропоткинHPV — вирус папилломы человекаNASA исследует возможность путешествий на скоростях больше скорости света, при этом, не разрушая ОТО.Сколько вселенных может поместиться флешку?ПсихофизиологияНаучное образование в США и Россиипочему неверно выражение A>=B, если A=Истина, B=Ложь?12 когнитивных предвзятостей, мешающих рационально мыслить.Чересчур хорошего – уже плохоБыстроглазости мух нашли объяснениеМикробы управляют своими хозяевамиТеперь понятно, почему зелёная плесень ядовитаУтро вечера мудренее, или идёмте по стопам Менделеева!В том, что кабанье мясо нравится не всем, виновата наследственностьО ревности и зависти на работеАмериканские учёные замахнулись на фотосинтезСамцам большой панды не всё равно, когда заниматься сексомКоварная микрофлора и двуликие иммунные клеткиЗелёные недотрогиСанитары леса, вернитесь!Распространение ртути в мелких водоёмах: на безрыбье и жук – аккумуляторПаучий шёлк – теплопроводник, не уступающий металламФермент Cdk1 – наш козырь в борьбе с бесплодиемНе правым единым творит человекРастения способны учуять болезнь соседа, хотя и далеко не сразуУ кого и что болит, тот на это и глядитСократив количество выкуренных сигарет, мозгу не помочьКакая нам может быть польза от депрессии?Homo homini lupus estПостарайтесь понять, что чувствует любимый человек: вам зачтётся
2^k
Надо веса расставить, тогда можно как–то оценить. А без этого некорректно
Корректно все там.
а младший голосует или нет?
получается, что если разбойников больше трех, то никого убивать не будут, потому что кроме двух самых старших умрут все.
Неверно.
мм.. ну тогда объясни тупому. можно в личку.
если это мыслящие разбойники, тогда да, 2^k, поддерживаю…
k — это что?
а какие ещё бывают? там же сказано: на первом месте тяга к жизни, на втором к богатству
вроде при решении никаких неопределённостей не возникает
что такое k?
y = 2 * (n mod 2),
где mod — операция целочисленного деления.
Теперь рассказ.
Рассмотрим, кто как будет голосовать, если у него есть голова на плечах, по старшинству. Самый старший будет всегда голосовать «за». Он бы, сука, всех поубивал, но этого не допустит №2. Если они останутся вдвоём, то против себя он голосовать не будет. Остальных же он может смело валить без зазрения совести. Немного сложнее третьему — на него завистливо смотрят №1 и №2, поэтому, чтобы уравновесить их, ему нужен ещё 1 голос, соответственно он будет голосовать против убийства №4. Самому №4 привалила халява — он понимает, что №3 не будет против него голосовать, поэтому можно смело отправлять расход всех, кто младше. Номер 5 выживет, если будут живы №№ 6, 7 и 8. № №№10, 11, 12, 13, 14, 15, 16. И так далее.
Теперь будем в первый столбик писать, сколько у нас есть разбойников, а во второй — сколько их в таком случае выживет.
1 = 1
2 = 2
3 = 2
4 = 4
5 = 4
6 = 4
7 = 4
8 = 8
9 = 8
…
15 = 8
16 = 16
Эмпирическим путём понимаем, что число выживших будет равно максимальному 2^k, не превышающему n.
Помогите выразить решение функцией, потому что с целочисленным делением я протупил.
int maxsqr(int n)
{
int k = 1;
int r = 1;
if(n > 1)
{
while(r = 1)
{
k++;
if(pow(2, k + 1) > n)
{
r = pow(2, k);
}
}
}
return r;
}
Вот можно мне то же самое, но математической функцией?
целая часть от логарифма n по основанию 2
точно, логарифм! А «целая часть» можно как–то красиво математически написать? Хочется вот решение выразить одной лаконичной функцией, чтобы увидеть и кончить в трусы.
*=floor(log2(n))
y=2^k, k=max{log2(n), n
Z | log2(n) <= k}
я кончил, спасибо.
Ответ:
угу. но через floor() симпатичнее.
Исключение:
При n = 1 * = 1.
и здесь как бы нигде не сказано, что нужно взять целую часть от логарифма.
floor — не совсем математически. Второй вариант — предикат, и простейшая функция. Ну да, предикат не совсем правильный. Не n Э Z, а log2(n) Э Z.
Неверно. Верно — вот так:
ещё лучше использовать сдвиг вместо возведения в степень и двоичный поиск(для 64–х бит неплохая экономия). это если надо много раз считать максимальную степень двойки, не меньшей данного числа, а вообще, вроде бы, есть команда процессора такая даже.
почему, надо оба предиката.
Точно. Только от log2n надо взять целую часть.
Заминусуйте комментарий с неверным ответом, пожалуйста.
Эти скобочки с загогулинками внизу и означают «взять целую часть» — то же что floor, только значками. Ты же очень просил чтобы значками…
спасибо, буду знать!
Логичнее было бы убивать не младших, а слабейших.
Если n = 1, то 1, во всех остальных случаях двое. Потому что по заданному алгоритму «против» голосует только тот, чьё убийство сейчас реально обсуждают, а в этом случае по–ровну станет только на двоих — когда один будет за то, чтобы убить, а другой по ясной причине будет против этого.
Darth– во–первых, выше есть правильный ответ
во–вторых, рассмотрите n=4, особенно третьего участника и его рассуждения о том, что случится на следующем ходу, если четвёртого замочат
I wish I were smarter…
Ещё есть маза что 5 старших родились в один день, и тогда все формулы идут по пизде.
4 разбойника остались, потому что 2–й и первый всегда выживают, а третий может спасти свою задницу только спасая четвертого. четвертый и выше спастись, защитив следующего не могут потому что остаются в меньшинстве с ним вдвоем. Например 5 и 6 голосуя за спасение шестого против 1 2 3 и 4.