На cracklab'e был задан достаточно интересный вопрос, который я переместил сюда, так как там ему ответов похоже не светит. Речь идет об игрушке Fiver) (по ссылке Java Applet) и нужно написать программку, находящую минимальное(относительно количества нажатых кнопок) решение для заданного размера поля. Находящую естественно как можно более эффективно. Можно рассмотреть отдельно нахождение произвольного решения и нахождение минимального решения, но такое ощущение, что решение может быть только одно (с точностью до симметрии конечно) По крайней мере для n<=10 это точно так. У меня пока получился топорный метод со скоростью O(2^n) для поля n x n. Не знаю, есть ли что-то более быстрое. По идее эта задача тоже относится к виду "расставь что-то на доске" (как Задача о восьми Ферзях и Путешествие Коня), а значит вполне может существовать линейный алгоритм.
Вот решение перебором. Полезной работы всего пара строчек в main() , остальное в основном вывод на экран. Код (Text): #include <stdio.h> int countbits(int v) { int c = 0; for(;v;c++) { v &= v-1; } return c; } void printresult(int count, int a, int n) { int i, j, aold = 0, temp; int mask = (1<<n) - 1; printf("Solutions: %d\n\n", count); if(count==0)return; for(j=n-1;j>=0;j--) { temp = a; for(i=0; i<n; i++) { if(temp & 1) { printf("X"); } else { printf("O"); } temp = temp>>1; } printf("\n"); temp = a; a = (~(a ^ (a<<1) ^ (a>>1) ^ aold)) & mask; aold = temp; } } void main() { int i,j,a,aold,temp,minsolution,n; int mask, mincount, solcount = 0, count; printf("enter field dimension n: "); scanf("%d",&n); mask = (1<<n) - 1; mincount = n*n; for(i=mask;i>=0;i--) { aold = 0; a = i; count = 0; for(j=n-1;j>=0;j--) { count += countbits(a); temp = a; a = (~(a ^ (a<<1) ^ (a>>1) ^ aold)) & mask; aold = temp; } if(!a) { if(count<mincount) { mincount = count; minsolution = i; solcount++; } } } printresult(solcount, minsolution, n); getch(); }
Нахождение всех образующих решений требует O(n^3) действий и легко выполняется на бумаге даже при n порядка 10. Выбор оптимального - O(2^m), где m - размерность пространства решений. Ботайте линейную алгебру.
Действительно, задачу можно записать в виде системы линейных уравнений, об этом я не подумал. Получим матрицу размером n^2 x n^2, где нормальный Гаус даст скорость O(n^6). (хотя для Z_{2} должны быть и немного более быстрые методы) Выбирать из решений оптимальное видимо не придется, так как оно будет одно с точностью до симетрии. Интересно посчитать, начиная с какого n имеет смысл решать таким образом.
Гаусс здесь будет n x n - поскольку по первой строчке все определяется. Соотвественно для всех образующих в первой строчке смотрим невязки в последней и получаем матрицу n x n. Решая систему получаем все первые строчки и соотвественно все матрицы.
Вот еще похожая онлайн-головоломка: http://www.var.ru/bz/js/floor.html А еще в старой игрухе "Братья-Пилоты" была подобная, и в "Седьмом Госте" тоже. В RU.ALGORITHMS решение разбирали: http://groups.google.com/group/fido7.ru.algorithms/msg/290936fc164b79cf
RElf Вот еще похожая онлайн-головоломка: http://www.var.ru/bz/js/floor.html Не похожая, а именно она и есть В RU.ALGORITHMS решение разбирали: http://groups.google.com/group/fido7.ru.algorithms/msg/290936fc164b79cf Не знаю, как там была сформулирована задача, но решение разбирается явно от немного другой головоломки. А именно: при нажатие клетки переключаются весь столбец и вся строка, тогда как в Fiver только по одной клетке на север, юг, запад и восток. Тот вариант по-моему менее интересен, так как для любого четного n будет A=A^{-1} и при начальном векторе (0,0,...,0) и конечном (1,1,....,1) решение будет всегда одно - тривиальное (1,1,....,1). А так похоже действительно остается только решать систему размерностью n^2. Если конечно halyavin не объяснит его идею. AVE5 Ну допустим имею поле 3х3 как будет выглядеть матрица? До n равного как минимум 13-15 перебор будет быстрее.
