Здравствуйте, DSD, Вы писали:

DSD>все пассажиры умны — это что, автобус с РСДН-овцами? Мужики — это намек! Пора собирать большую реалку и переть куда-нить на экскурсию с пивом Заодно помучим водилу автобуса

Только остановки наоборот будут: останавливаться нужно, чтобы подобрать жаждущего, а не ссадить ненужного. И голосовать — останавливаться или нет, берем или нет, есть ли в руках пиво или нет. Интересно, кто первым голосовать будет?! Водитель?

Здравствуйте, Mikhail_T, Вы писали:

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

Это в корне неверно — например 100 ВСЕГДА сойдет на своей остановке и ни за какую их предыдущих голосовать не будет (ему от этого ничего не прибудет, хотя и не убудет ) => если в автобусе осанется 2 человека то на 99 остановке будет один голос за(99) и один проитив (100) => автобус остановится только на 100, и 99 не выйдет на своей остановке.

Здравствуйте, nikholas, Вы писали:

N>Здравствуйте, Mikhail_T, Вы писали:

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

N>Это в корне неверно — например 100 ВСЕГДА сойдет на своей остановке и ни за какую их предыдущих голосовать не будет (ему от этого ничего не прибудет, хотя и не убудет ) => если в автобусе осанется 2 человека то на 99 остановке будет один голос за(99) и один проитив (100) => автобус остановится только на 100, и 99 не выйдет на своей остановке.

На месте 100 я бы не был так уверен, например 99 и 98 тупые и всегда голосуют по принципу — не моя остановка, значит голосовать буду против. Если их на своих не высадить — автобус не остановится и на 100.

Здравствуйте, Apostate, Вы писали:

A>На месте 100 я бы не был так уверен, например 99 и 98 тупые и всегда голосуют по принципу — не моя остановка, значит голосовать буду против. Если их на своих не высадить — автобус не остановится и на 100.

Я думаю что логичным дополнением к условию будет то, что каждый стремится выйти как можно ближе к своей остановке, поэтому если человек проехал свою остановку то он будет голосовать за все оставшиеся.
Можно пытаться приплести сюда психологию, но думаю что очень малая часть участников данного форума является профессионалами в этой области.
Поэтому стоит пытаться решить задачу чисто математически.
Все пассажиры шибко умные и заранее могут определить где автобус остановится.

Хорошим доп. условием ИМХО будет такое: человек голосует за остановку в том и только в том случае, если при сравнении варианта остановки и не остановки для него более выгодным является вариант остановки
Под более выгодным мы понимаем меньшее расстояние от его остановки до ближайшей, на которой реально остановится автобус

При таких условиях набор остановок предопределен, правда налицо обратная связь: набор остановок -> кто когда выйдет -> знаем кто за что голосует -> набор остановок

При помощи итеративного алгоритма можно определить стратегию каждого.

При таких условиях для любого количества оставшихся пассажиров сужествует только одна последовательность остановок:
Если остался 1 (№100) — остановка на 100
Если осталось 2 (№99, 100) — остановка на 100
Если осталось 3 (№98, 99, 100) — остановка на 99 -> остался 1
Если осталось 4 — остановка 99, 100

Будем находить значения следующих функций(последовательностей? ... а вот назову как нравится )
в порядке убывания номера остановки:

S(N) — кол-во людей оставшихся в автобусе если произошла остановка в N (после остановки)
(S(100) = 0, S(99) = 1, S(98) = 1, ...)
P(N) — последовательность остановок после остановки в N
V(N) — кол-во людей с номерами >N, которые будут голосовать за остановку в N
START(N) — количество людей, начиная с которого остановка произойдет не позже, чем в N

Очевидно, что START(N) = (100 — N — V(N)) * 2 + 1

Рассматривая очередное N, используем следующий алгоритм для нахождения данных значений:
(Предполагаем, что для всех больших N мы уже все знаем)

S(N) — из общих соображений
Из тех же соображений — P(N)
Нахождение V(N) нетривиально но возможно — каждый из находящихся в автобусе может определить набор остановок если остановка в N произойдет и если ее не произойдет, и если первый вариант для него более выгодный — то проголосовать за остановку в N.

Будет время — реализую этот алгоритм и выложу результат

N>Будет время — реализую этот алгоритм и выложу результат

лучше почитай топик, писатель

Здравствуйте, Apostate, Вы писали:

N>>Будет время — реализую этот алгоритм и выложу результат

A>лучше почитай топик, писатель

Спасибо за совет, научусь читать — почитаю
Топик читал, но ответа на вопрос не нашел — потому и занялся графоманством

Здравствуйте, Apostate, Вы писали:


SS>>1 все пассажиры тупы и не делают прогнозы

A>Автобус проедет маршрут без остановок.

SS>>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать

A>Автобус проедет маршрут со всеми остановками.

A>


A>А вообще задача некорректна тем что не известно сколько времени экономит автобус на проезде остановки, и на сколько больше времени тратит пассажир если вышел не на своей.

Ты вот это считаешь задачей, да это просто набор слов.
Вообще, ну пусть он введет в постановку время экономии, что дальше.
Может сэмулировать каждого пассажира нейронной сетью и гнать их по маршруту дофига раз, правда и тут не ясно к чему стремится, если сетка простая, так-что в нее надо всадить хотя бы интелект младенца умеющего сходить с автобуса и который хочет сойти, а если не сойдет пристрелит N пассажиров тогда -N остановок, но существует вероятность того что будет убит водила и хана, придется перется пешком.

При такой постановке нужно еще ввести вероятностные функции(а может и функционалы) и критерий сравнения на них.
Тогда просчитать по критерию стоит ли пропускать остановку.

Зашибись задачка получилась

Здравствуйте, SanSoft, Вы писали:

SS>Давным давно в КВАНТЕ была вот какая задачка.

SS>По маршруту едет автобус. На маршруте имеется 100 остановок, для нашего удобства они пронумерованы от 1 до 100. В автобусе 100 пассажиров, для нашего удобства они опять таки пронумерованы от 1 до 100. В принципе каждому из пассажиров надо сойти на остановке номер которой совпадает с его собственным номером.

SS>Водитель, дабы ускорить движение, предложил следующий алгоритм. Ппри подъезде к каждой очередной остановке проводится голосование "останавливаться или ехать безостановочно". Решение принимается простым большинством голосов. Если пассажиру не удаётся сойти на своей остановке то он сходит на ближайшей к нужной.

SS>Вопрос — на каких остановках автобус будет останавливаться.

SS> все пассажиры умны и делают прогнозы о том как им лучше голосовать
SS>задача достаточно логическая и наверное может быть "запрограммирована" даже в Excele

Решим задачу исходя из дополнительных условий:
Единственным желанием каждого является желание выйти как можно ближе к своей остановке.
Все пассажиры умные и знают заранее набор остановок, поэтому они выходят на остановке, ближайшей к своей
Пассажир голосует за остановку только в том случае, если в результате остановки он сможет выйти ближе к своей.

Так как наиболее важным параметром является не пройденное число остановок а оставшееся до конечной, будем считать что автобус едет с остановки № N до остановки № 1.

Каждый пассажир будет рассуждать так: если в автобусе останется N человек, то первой остановкой может быть остановка с номером K, N/2<=K<=N. После этой остановки в автобусе останется N' человек, N'<K<=N — т.е. задача свелась сама к себе, только с меньшим числом людей.
Для любого числа людей меньше N я знаю набор остановок, поэтому определю остановку K по следующему алгоритму:
После остановке в K в автобусе может остаться от 0 до K-1 человек, для каждого кол-ва людей набор оставшихся остановок известен => каждый из оставшихся решит выходить ему или нет — найдем N'(K) (очевидно, что выходить будут все пассажиры с промежутка, поэтому надо найти пассажира с минимальным номером, который выйдет)
Если авт. не остановился на остановках с номерами > K', то если он не остановится и в K', следующая остановка будет в K'' (предполагаем известным, потому что мы итерируем по K') — каждый решит, что ему выгоднее — остановка в K' или ее отсутствие. Наибольшее K, за которое проголосует больше половины N и будет первой остановкой.

const unsigned amountLimit = 1000;

unsigned nextStop[amountLimit] = {0, 1, 1};
unsigned nextStopByStop[amountLimit] = {0, 1, 1};

unsigned getDistance(unsigned passNo, unsigned stopNo)
{
    if(stopNo <= passNo)
        return passNo - stopNo;
    unsigned prevStop;
    do 
    {
        prevStop = stopNo;
        stopNo = nextStopByStop[stopNo];
    } 
    while(stopNo > passNo);
    return min(passNo - stopNo, prevStop - passNo);
}

void main()
{
    unsigned amountPassangers;
    for(amountPassangers = 3; amountPassangers != amountLimit; ++amountPassangers)
    {
        int possibleStop;
        unsigned nextAmountPassangers[amountLimit];
        for(possibleStop = amountPassangers/2; possibleStop <= amountPassangers; ++possibleStop)
        {
            int nextAmount = 0;
            while(nextAmount - nextStop[nextAmount] < possibleStop - nextAmount)
                ++nextAmount;
            nextAmountPassangers[possibleStop] = --nextAmount;
            nextStopByStop[possibleStop] = nextStop[nextAmount];
        }
        unsigned stopNo = amountPassangers/2;
        for(possibleStop = amountPassangers/2 + 1; possibleStop != amountPassangers; ++possibleStop)
        {
            unsigned vouters = amountPassangers - possibleStop + 1;
            for(int passWithStop = 1; passWithStop != possibleStop; ++passWithStop)
            {
                unsigned distWithStop = getDistance(passWithStop, possibleStop);
                unsigned distWithoutStop = getDistance(passWithStop, stopNo);
                if(distWithStop < distWithoutStop)
                    vouters++;
            }
            if(2*vouters > amountPassangers)
                stopNo = possibleStop;

        }
        nextStop[amountPassangers] = stopNo;
        cout << amountPassangers << " : " << stopNo << " ";
        do 
        {
            stopNo = nextStopByStop[stopNo];
            cout << stopNo << " ";
        } 
        while(stopNo != 1);
        cout << "\n";
    }

}

И вот собственно ответ для 100: 37 70 84 91 96 99 100
На удивление непредсказуем!
Например для 127 пассажиров (и остановок) ответ 22 64 97 111 118 123 126 127

Здравствуйте, nikholas, Вы писали:

N>Каждый пассажир будет рассуждать так: если в автобусе останется N человек, то первой остановкой может быть остановка с номером K, N/2<=K<=N. После этой остановки в автобусе останется N' человек, N'<K<=N — т.е. задача свелась сама к себе, только с меньшим числом людей.

Мы диалектику учили не по Беллману

Первая остановка все-таки получается меньше N/2, то есть первоначальное предположение неверно. Но, кажется, оно не настолько критично. Кстати, 37 очень похоже на N/e.

Здравствуйте, desperado_gmbh, Вы писали:

_>Здравствуйте, nikholas, Вы писали:

N>>Каждый пассажир будет рассуждать так: если в автобусе останется N человек, то первой остановкой может быть остановка с номером K, N/2<=K<=N. После этой остановки в автобусе останется N' человек, N'<K<=N — т.е. задача свелась сама к себе, только с меньшим числом людей.

_>Мы диалектику учили не по Беллману

_>Первая остановка все-таки получается меньше N/2, то есть первоначальное предположение неверно.
См. мой ответ здесь

Автор: BUran
Дата: 13.06.03

_>Но, кажется, оно не настолько критично. Кстати, 37 очень похоже на N/e.
Ну-ну, а еще больше на 100*3/8,

Это задача из теории антагонистических игр, а на каких остановках будет тормозить автобус будет зависеть от того, каким из методов решения воспользуется каждый из пассажиров (например — методом миннимакса).
SanSoft, ты это хотел услышать

P. S. Читал не всю ветку, уж больно длинная. Простите, если повторил чей-то ответ