Использование очереди с ограниченной емкостью для вывода списка строк по порядку?

Question

Мой профессор заставил нас написать единственную очередь char (без шаблонов, просто char), что я сделал без особых проблем.Теперь я использую его для написания драйвера (main ()), который будет распечатывать каждую комбинацию последовательности ABC.

Строки должны генерироваться в следующем порядке:

A
B
C
AA
AB
AC
BA
BB
BC
CA
CB
CC
AAA
AAB
AAC
ABA
ABB
ABC
ACA
ACB
ACC
etc.

MAX_SIZE = 10 для очереди, поэтому он должен выдавать исключение переполнения после примерно 25 строк.

вот подсказка:

Start with A and B and C in the queue.
“Remove it Display it then Add Add  Add ”

Что-то вроде, но я не понимаюкак заставить основную структуру управления переходить на длину символа каждый раз, когда вы знаете (например, когда все отдельные символы переходят в двойное, затем в тройное и т. д.).

Answer 1

Для начала отметим, что если у вас есть очередь строк, это не особенно сложно.Общий алгоритм - это поиск в графе строк в ширину:

1. Создать пустую очередь Q.
2. Вставить пустую строку в Q.
3. Loopдо готовности (ваше определение готово):
   1. Снимите с головы Q, назовите ее w.
   2. Напечатайте w.
   3. Вставьте wA, wB и wC в Q.

Проблема в том, что вы не можете вставить эти строки в очередь, не очень быстро исчерпав все свободное пространство.Тем не менее, если вам разрешено использовать несколько очередей, вы можете объединить очереди в одну гораздо большую очередь.Например, предположим, что у вас есть две очереди емкостью 3 каждая и вы хотите создать очередь емкостью 6. Чтобы сделать это, пометьте очереди как «левую очередь» и «правую очередь».По умолчанию вы вставляете в правую очередь, как показано здесь:

  Left            Right
  [ ] [ ] [ ]     [ ] [ ] [ ]         Enqueue A
  [ ] [ ] [ ]     [ ] [ ] [A]         Enqueue B
  [ ] [ ] [ ]     [ ] [A] [B]         Enqueue C
  [ ] [ ] [ ]     [A] [B] [C]

Теперь предположим, что в правой очереди недостаточно места.В этом случае удалите элемент из правой очереди (это будет самый старый элемент в объединенных очередях), затем поместите его в левую очередь:

  Left            Right
  [ ] [ ] [ ]     [A] [B] [C]         Enqueue D
  [ ] [ ] [A]     [B] [C] [D]         Enqueue E
  [ ] [A] [B]     [C] [D] [E]         Enqueue F
  [A] [B] [C]     [D] [E] [F]

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

  Left            Right
  [A] [B] [C]     [D] [E] [F]         Dequeue (yields A)
  [B] [C] [ ]     [D] [E] [F]         Dequeue (yields B)
  [C] [ ] [ ]     [D] [E] [F]         Dequeue (yields C)
  [ ] [ ] [ ]     [D] [E] [F]         Dequeue (yields D)
  [ ] [ ] [ ]     [ ] [E] [F]         Enqueue G
  [ ] [ ] [ ]     [E] [F] [G]         Enqueue H
  [ ] [ ] [E]     [F] [G] [H]         Dequeue (yields E)

Вы можете обобщить эту технику, объединив несколько очередей в длинную цепочку.Используя это, вы можете взять свою маленькую очередь, которая содержит всего 10 символов, и сформировать намного большую очередь, возможно, с емкостью 100 или 1000.

Так как это поможет?Ну, используя цепочечные очереди, вы можете смоделировать очередь строк!Чтобы вставить строку w, просто вставьте символы w, а затем маркер (скажем, $) в свою очередь.Например:

 Long Queue Contents       Operation
 $                         Dequeue once to get $, insert A, B, C
 A$B$C$                    Dequeue twice to get A$, insert AA, AB, AC
 B$C$AA$AB$AC$             Dequeue twice to get B$, insert BA, BB, BC
 C$AA$AB$AC$BA$BB$BC$

и т. Д.Используя эту комбинацию меньших очередей для имитации большей очереди, которая имитирует очередь строк (woohoo!), Вы можете решить проблему, используя первоначальный алгоритм.

Надеюсь, это поможет!

Answer 2

К вашему сведению, здесь используется только целочисленные вычисления.

size_t len = 1;

for (size_t i = 0; i < 5; ++i) {
    size_t x = 0;
    bool max = false;

    do {
        max = true;
        size_t y = x;
        for (size_t j = 0; j < len; ++j) {
            char c = 'A' + (y%3);
            y /= 3;
            if (c != 'C')
                max = false;
            std::cout << c;
        }
        std::cout << std::endl;

        x++;
    } while (!max);
    ++len;
}

Answer 3

Вот одно из решений.Достаточно просто.

Queue q;

q.enqueue('A');
q.enqueue('\n');
q.enqueue('B');
q.enqueue('\n');
q.enqueue('C');
q.enqueue('\n');

for (size_t i = 0; i < 25; ++i) {
    size_t len = 0;
    char str[256];
    char c;

    while ((c = q.dequeue()) != '\n')
        str[len++] = c;

    str[len] = '\0';

    std::cout << str << std::endl;

    for (size_t j = 0; j < len; ++j)
        q.enqueue(str[j]);

    q.enqueue('A');
    q.enqueue('\n');

    for (size_t j = 0; j < len; ++j)
        q.enqueue(str[j]);

    q.enqueue('B');
    q.enqueue('\n');

    for (size_t j = 0; j < len; ++j)
        q.enqueue(str[j]);

    q.enqueue('C');
    q.enqueue('\n');
}