幫我理解這個算法（簡單）

我剛做了一個隊列類，現在我不得不用它來做到這一點。幫我理解這個算法（簡單）

編寫一個C++程序來生成使用A，B和C作爲字母的所有字符串。

的字符串必須按以下順序生成：甲乙 Ç AA AB AC BA BB BC CA CB CC AAA AAB AAC ABA ABB ABC ACA ACB ACC 等

它應該這樣做，直到我的隊列溢出。

現在，我只是不明白老師建議使用的算法，這是這樣的。

從隊列中的A和B以及C開始。「刪除它顯示它然後添加添加添加」

添加添加的東西把我拋出，它是如何完成讓這些字母在這個特定的順序？

來源

2011-09-15 Tyler Pfaff

讓我們的行爲是：

For any token X, add XA, XB, and XC to the queue.

我們的流程是這樣的：

Start with a Queue 
A B C 

Pop (and display) off A 
B C 

Behave on token: "A" 
    add AA 
    add AB 
    add AC 
B C AA AB AC 

Pop (and display) off B 
C AA AB AC 
    add BA 
    add BB 
    add BC 
C AA AB AC BA BB BC

如果我們假裝我們的功能是

main() { 
    Queue q; 
    q.add("A"); 
    q.add("B"); 
    q.add("C"); 

    while(true) { 
     process(q.pop()); 
    } 
} 

process(String x, Queue q) { 
    display x; 
    q.add(x + "A"); 
    q.add(x + "B"); 
    q.add(x + "C"); 
}

現在明白了嗎？

來源

2011-09-15 21:44:24 corsiKa

嗯，隊列使用一個字符數組，所以我明白你在說什麼，但我不知道我怎麼能實現這個 –

這基本上是一個廣度優先搜索的工作原理。 –

@Tyler保留「頭」和「尾」位置計數器。當你「流行」時，把'myArray [head];'當作你彈出的，然後去'head ++;'來表示你正在移動它。當你添加到隊列中時，去'myArray [tail] = whatImAdding;'添加它，'tail ++'來表示它已經增長。當'tail'嘗試訪問不屬於數組的部分時，這會溢出。 – corsiKa

我認爲你的老師的意思是「添加A，添加B，添加C」。

假設在隊列中有A，B和C.您將第一個從隊列中彈出並打印出來。這應該打印A.然後你添加一個A.這給了你AA，你將其推回到隊列中。您還可以添加一個B，並將C添加到最後彈出的字符串（給您AB和AC），並將它們推回到隊列中。現在你的隊列包含[B，C，AA，AB，AC]。接下來，您將彈出B並執行相同的操作序列，以此類推，直到您的堆棧中的空間用完。

來源

2011-09-15 21:44:40 MAK

ABC

打印甲新的隊列狀態 BCAAA

打印乙新的隊列狀態 CAAABBB

打印Ç 新的隊列狀態 AAABBBCCC

打印甲新隊列狀態 AABBBCCCAAA

打印一個新隊列狀態 ABBBCCCAAAAAA

畫的新隊列狀態 BBBCCCAAAAAAAAA

這是我的週期的第一種解釋，但我一定要得到它錯了，因爲我去從1重複到3。

更新：在看到其他響應後肯定讀了最初的問題。

來源

2011-09-15 21:47:16 JonnyRo

幫我理解這個算法（簡單）

回答

相關問題