確定一個數是否爲的操作現場＃一個操作現場數

定義：確定一個數是否爲的操作現場＃一個操作現場數

它與恰好N個數位，其中的每一個是1和9之間（含）的整數。
數字形成一個序列，每個數字表示序列中下一位數字出現的位置。這是通過給出序列中下一個數字所在的數字右邊的位數來完成的。如有必要，計數從最右邊的數字回到最左邊。
數字中最左邊的數字是序列中的第一個數字，並且序列必須在該數字中的所有數字都恰好被使用一次之後返回到該數字。
沒有數字會在數字中出現一次以上。

檢查重複數字不是問題，但我似乎無法想出一個檢查「runaround」部分的好方法。我正在尋找更多的建議/僞代碼比實際的c + +。

來源

2010-11-15 john

功課？添加適當的標籤，如果是... – 2010-11-15 07:26:00

http://uva.onlinejudge.org/external/3/347.html – kennytm 2010-11-15 07:27:05

這似乎與排列矩陣有很多相同之處。儘管忽略了這一點，但通過保留一個位掩碼並運行N次，似乎很容易進行測試。如果每一個位被設置，你都很好。 – xscott 2010-11-15 07:30:13

如果將整數轉換爲字符串，它不應該有任何困難：您只需要一個運算符[]（即std :: string類提供的）和一個布爾數組來記錄哪個元素已經被檢查：

string value = input_integer; 
vector<bool> checked; 

int index = value[0]; 
checked[0] = true; 
bool done = false; 
while (!done) { 
    index = get_wrapped_index(value, index); 
    if (!checked[index]) 
     checked[index] = true; 
    else 
     return false; // not a roundaround 

    if allTrue(checked) && index == 0 
     done = true; 
} 
return true;

您必須代碼get_wrapped_index（字符串s，索引i），必須返回由s指定的整數[I]鑑於指定右環繞costraint問題。

來源

2010-11-15 07:35:55 Simone

我想你會想要初始化檢查到n個falses的向量，其中n是數字中的位數 - 否則過早返回索引0可能不會被誤認爲是錯誤的。 – 2010-11-15 07:41:25

是的，當然，但如果你使用std :: vector 這已經完成了。 – Simone 2010-11-15 07:53:59

因爲'value'是一個沒有'rotate_right_by'方法的標準字符串，所以'rotate_right_by（value，index）'作爲一個自由函數會更好 - 不是給出關於從std ::字符串「來添加一個方法。此外，該函數的簽名可以更深入地瞭解您的意圖語義：它實際上是否要旋轉字符串？還是隻更新'索引'？ – 2010-11-15 09:08:30

你有4條規則，因此只需編寫代碼來檢查每個規則。

該數字是N位數字。確定N是什麼。可以通過轉換爲每個數字的字符串或向量來完成。你可能需要使用10和10的mod（％）10幾次。
從一個數字移動到下一個數字的方法。所以，如果你的數字位置x的值爲y，則移動到x + y mod N，即（x + y）％N。當然，第一個位置被認爲是位置0。
您需要檢查您是否碰過每個位置，並且您沒有重複。這可能是一張支票。如果你達到一個數字，你所看到的，你知道之前，你有當且僅當這是第N次迭代的正確解決方案，你在索引0

12是失敗的。因爲雖然它在2次迭代後沒有達到索引0，但重新訪問索引1（2會將索引1從索引1帶回索引1）

11失敗，因爲如果還沒有完成所有迭代，則會看到另一個1 。

123是失敗的，因爲你太早回到1迭代。你不需要知道你沒有看到3，或者你回到索引0，只是說你太早看到另一個了。

285雖然工程。你看到2然後5然後8然後2.你在索引0，並有3次迭代。

您需要存儲可見數字的集合。向量是有點爭議，所以你可以使用std :: bitset，甚至只是一個布爾[10]會做這個例子，或向量。你也可以使用std :: set，後者的情況可以讓你檢查它的大小以查看你的迭代次數。

來源

2010-11-15 10:16:29 CashCow

確定一個數是否爲的操作現場＃一個操作現場數

回答

相關問題