n разбойников ограбили караван. Уговор у них такой: голосуют за то, чтобы убить самого младшего, если «за» больше половины–убивают и продолжают голосование за следующего по возрасту(у всех возраст разный). Если не больше половины–делят поровну добычу и расходятся. Каждый разбойник, во–первых, очень не хочет умирать, а во–вторых, хочет как можно больше денег. Сколько разбойников осталось?

GD Star Rating
loading...

36 Responses to Логическая задача

  1. Ruhcuhc:

    Надо веса расставить, тогда можно как–то оценить. А без этого некорректно

  2. Peels:

    Корректно все там.

  3. Ruhcuhc:

    а младший голосует или нет?

  4. Ruhcuhc:

    получается, что если разбойников больше трех, то никого убивать не будут, потому что кроме двух самых старших умрут все.

  5. Peels:

    Неверно.

  6. Ruhcuhc:

    мм.. ну тогда объясни тупому. можно в личку.

  7. CbOn:

    если это мыслящие разбойники, тогда да, 2^k, поддерживаю…

  8. Ruhcuhc:

    k — это что?

  9. Dr4:

    а какие ещё бывают? там же сказано: на первом месте тяга к жизни, на втором к богатству
    вроде при решении никаких неопределённостей не возникает

  10. ErOn:

    что такое k?

  11. Voova:

    y = 2 * (n mod 2),
    где mod — операция целочисленного деления.

  12. Voova:

    Теперь рассказ.
    Рассмотрим, кто как будет голосовать, если у него есть голова на плечах, по старшинству. Самый старший будет всегда голосовать «за». Он бы, сука, всех поубивал, но этого не допустит №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.
    Помогите выразить решение функцией, потому что с целочисленным делением я протупил.

  13. Voova:

    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;
    }
    Вот можно мне то же самое, но математической функцией?

  14. Ruhcuhc:

    целая часть от логарифма n по основанию 2

  15. Voova:

    точно, логарифм! А «целая часть» можно как–то красиво математически написать? Хочется вот решение выразить одной лаконичной функцией, чтобы увидеть и кончить в трусы.

  16. Noev:

    *=floor(log2(n))

  17. Noev:

    y=2^k, k=max{log2(n), n Z | log2(n) <= k}

  18. Voova:

    я кончил, спасибо.

  19. Voova:

    угу. но через floor() симпатичнее.

  20. Voova:

    Исключение:
    При n = 1 * = 1.

  21. Voova:

    и здесь как бы нигде не сказано, что нужно взять целую часть от логарифма.

  22. Noev:

    floor — не совсем математически. Второй вариант — предикат, и простейшая функция. Ну да, предикат не совсем правильный. Не n Э Z, а log2(n) Э Z.

  23. Peels:

    Неверно. Верно — вот так:

    размер 72x28, 0.36 kb

  24. SMDummy:

    ещё лучше использовать сдвиг вместо возведения в степень и двоичный поиск(для 64–х бит неплохая экономия). это если надо много раз считать максимальную степень двойки, не меньшей данного числа, а вообще, вроде бы, есть команда процессора такая даже.

  25. Voova:

    почему, надо оба предиката.

  26. Voova:

    Точно. Только от log2n надо взять целую часть.
    Заминусуйте комментарий с неверным ответом, пожалуйста.

  27. Peels:

    Эти скобочки с загогулинками внизу и означают «взять целую часть» — то же что floor, только значками. Ты же очень просил чтобы значками…

  28. Voova:

    спасибо, буду знать!

  29. NiMonkey:

    Логичнее было бы убивать не младших, а слабейших.

  30. CiMoon:

    Если n = 1, то 1, во всех остальных случаях двое. Потому что по заданному алгоритму «против» голосует только тот, чьё убийство сейчас реально обсуждают, а в этом случае по–ровну станет только на двоих — когда один будет за то, чтобы убить, а другой по ясной причине будет против этого.

  31. Dr4:

    Darth– во–первых, выше есть правильный ответ
    во–вторых, рассмотрите n=4, особенно третьего участника и его рассуждения о том, что случится на следующем ходу, если четвёртого замочат

  32. CiMoon:

    I wish I were smarter…

  33. Xbiz:

    Ещё есть маза что 5 старших родились в один день, и тогда все формулы идут по пизде.

  34. OtMath:

    4 разбойника остались, потому что 2–й и первый всегда выживают, а третий может спасти свою задницу только спасая четвертого. четвертый и выше спастись, защитив следующего не могут потому что остаются в меньшинстве с ним вдвоем. Например 5 и 6 голосуя за спасение шестого против 1 2 3 и 4.

Добавить комментарий