Имеется двунаправленная очередь (можно взять элемент слева, поместить элемент слева, взять элемент справа, поместить элемент справа). В очереди лежат какие-то элементы — не обязательно числа.
Нужно определить, сколько элементов содержит очередь.

Очередь не должна измениться в процессе подсчета. Можно использовать лишь малое количество памяти.

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

I>Имеется двунаправленная очередь (можно взять элемент слева, поместить элемент слева, взять элемент справа, поместить элемент справа). В очереди лежат какие-то элементы — не обязательно числа.
I>Нужно определить, сколько элементов содержит очередь.

I>Очередь не должна измениться в процессе подсчета. Можно использовать лишь малое количество памяти.
Элементы уникальны? Что есть "малое количество памяти" константа?
Если элементы уникальны — достаточно памяти под один элемент. Запоминаем элемент например, слева.
Перемещаем его вправо. И так до тех пор, пока не придём к начальному элементу. Естественно, считаем количество перестановок.

            --------------------------------- 
очередь  /-- *QWERTYUIOP{ASDFGHJKL:"ASDFGHJK  <--\
         |  ---------------------------------     |
          \_______________________________________/

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

    ------------------------
     *QWERTYUIOP*QWERTYUIOP
    ------------------------

и

    --------------
     *QWERTYUIOP*
    --------------

т.е. циклическую последовательность.

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

I>>Очередь не должна измениться в процессе подсчета. Можно использовать лишь малое количество памяти.
Очередь не должна измениться в процессе подсчета = не должна измениться после подсчёта или не должна изменяться во время подсчёта?

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

I>Имеется двунаправленная очередь (можно взять элемент слева, поместить элемент слева, взять элемент справа, поместить элемент справа). В очереди лежат какие-то элементы — не обязательно числа.

пусть это не числа (любое множество с числом элементов >=1 и с операциями сравнения). Но для простоты будем считать, что там — целые числа, также будем считать, что число элементов в очереди конечно.

Пусть крайне-правый элемент равен 1, заменим его на 2 и будем циклически прокручивать его влево до тех пор, пока оттуда не вылезет 2, считаем число сдвигов N. Затем всю систему циклически прокручиваем вправо, меняем 2 на 1 (т.е. возвращаем очередь в исходное состояние), прокручиваем всю очередь опять влево на N, если в левом конце очереди вылезет 1, то ответ мы нашли, он равен N, затем восстанавливаем очередь, прокручивая ее вправо на N. Если вылезала двойка, значит размер не найден, опять заменяем 1 на 2, крутим все влево до тех пор, пока не появится 2 (но >N раз) и так далее.

Теперь то же самое, но в коде:

value roll_left(queue& q, int n=1)
{
    value r;
    for(int i=0;i<n;i++)
    {
        r=q.pop_left();
        q.push_right(r);
    }
    return r;
}
value roll_right(queue& q, int n=1)
{
    value r;
    for(int i=0;i<n;i++)
    {
        r=q.pop_right();
        q.push_left(r);
    }
    return r;
}

int size(queue q)
{
    int N=0;
    while(1)
    {
        value l=q.pop_right();
        q.push_right(l+1);
        int M=0;
        do
        {
            M++;
            r=roll_left(q);
        }while(r!=l+1 && M<=N);
        roll_right(q, M);
        q.pop_right();
        q.push_right(l);
        value r=roll_left(q, M);
        roll_right(q, M);
        if(r==l)
            return M;
        N=M;
    }
}

абсолютную правильность кода не гарантирую, оптимальность — тем более

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

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

I>>Имеется двунаправленная очередь (можно взять элемент слева, поместить элемент слева, взять элемент справа, поместить элемент справа). В очереди лежат какие-то элементы — не обязательно числа.

A>пусть это не числа (любое множество с числом элементов >=1 и с операциями сравнения). Но для простоты будем считать, что там — целые числа, также будем считать, что число элементов в очереди конечно.

A>Пусть крайне-правый элемент равен 1, заменим его на 2 и будем циклически прокручивать его влево до тех пор, пока оттуда не вылезет 2, считаем число сдвигов N. Затем всю систему циклически прокручиваем вправо, меняем 2 на 1 (т.е. возвращаем очередь в исходное состояние), прокручиваем всю очередь опять влево на N, если в левом конце очереди вылезет 1, то ответ мы нашли, он равен N, затем восстанавливаем очередь, прокручивая ее вправо на N. Если вылезала двойка, значит размер не найден, опять заменяем 1 на 2, крутим все влево до тех пор, пока не появится 2 (но >N раз) и так далее.

А как насчёт

111121111 ?

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

fAX>111121111 ?

точно так же:

1. 111121111 -> 111121112 — заменили элемент
2. -> 111211112 — прокрутили на N=5
3. -> 111121111 — вернули назад
4. -> 111111112 — прокрутили еще раз на N=5, опять вылезла двойка
5. -> 111121111 — вернули
6. -> 111121112 — опять заменили элемент
7. -> 111121112 — прокрутили на N=9>5
8. -> 111121111 — вернули назад
9. -> 111121111 — еще раз прокрутили на N=9, вылезла единица => return 9