новая версия
public static boolean disco(boolean[] init, boolean[] target)
{
return recurse(init,boolean,0);
}
public static boolean recurse(boolean[] init, boolean[] target, int min)
{
if (min == init.length)
if (init == target)
return true;
else
return false;
boolean[] temp = "init with a change at min";
boolean a = recurse(init, target, min+1);
boolean b = recurse(temp, target, min+1);
return a||b;
}
новая новая версия
Я разбил его на три случая:
Случай 1 : длина% 3 = 0
Изменяя первую и вторую лампочки, вы можете повлиять на изменение только на 3-ю.
Тогда изменение на 4 и 5 сделает 6-го единственным измененным. Мы видим, что мы можем заменить каждую лампочку с индексом, делимым на 3.
Работая в обратном направлении (начиная с конца), мы можем сделать то же самое, но на этот раз это показывает, что мы можем заменить лампочки с индексами (i + 1), кратными 3.
Объединяя эти два, мы видим, что если мы хотим изменить индекс 0,1 mod 3, мы можем. Но затем, чтобы изменить 2, мы просто должны изменить соседнюю 0,1 пару, а затем сделать изменение средней. Так что во всех случаях они разрешимы.
Случай 2 : длина% 3 = 1
Как и в первом случае, но мы можем повлиять на единичные изменения в 0,2 мод 3, и, таким образом, сжать 1 мод 3 случая.
Дело 3 : длина% 3 = 2
Работа только вперед и назад приводит к случаям 0 mod 3. Единственные оставшиеся движения, которые мы имеем, вносят два изменения в луковицы (так как мы можем игнорировать любые изменения в позициях 0). Изменение 1 или 2 перевернет положение, окруженное двумя 0, тогда как изменение 0 поменяет четность в соседних блоках по 1,2, у которых есть 0 между ними (это проще, если вы рисуете). Но то, что я пока показал, это то, что все 0 можно исправить, и в любом смежном 1,2 вы можете исправить оба, если они неправильны, не меняя ничего другого. Если вы ошибаетесь, вы распространяете изменение на соседнюю пару из 1,2. Это изменение может быть перенесено в случае необходимости. Это означает, что любое четное количество ошибок в 1,2 позициях может быть исправлено, но нечетное число не может быть исправлено. Все ошибки в позиции 0 могут быть исправлены.
public static boolean disco(boolean[] init, boolean[] target)
{
if (init.length%3 == 0 || init.length%3 == 1)
return true;
return recurse(init,target,0, true);
}
public static boolean recurse(boolean[] init, boolean[] target, int index, boolean even)
{
if (index = init.length)
return even;
if (init[index] != target[index] && index%3 != 0)
even = !even;
return recurse(init, target, index+1, even);
}