私の大学では、次のような問題があります。
アルゴリズムが永久に実行される0からn - 1までの整数の順列がある最小のnは?
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v;
v.push_back(3);
v.push_back(1);
v.push_back(0);
v.push_back(6);
v.push_back(2);
v.push_back(7);
v.push_back(5);
v.push_back(4);
int j = 0;
int i = 0;
for(i = 0; i < v.size(); i++)
{
if(v[i] > i)
{
j = i;
while( j < v.size() && v[j] >= j )
{
j = j + 1;
}
int temp = v[i];
v[i] = v[j];
v[j] = temp;
i = 0;
}
}
return 0;
}
順列 {3, 1, 0, 6, 2, 7, 5,4} を手動で見つけました。誰かが私の答えをチェックしたり、より小さなパーミュレーションを見つけたりしたら、私は感謝します.
私は多くの順列を試しましたが、総当たりではなく、論理的な選択によって、アルゴリズムがループする最小のシーケンスだと思います。