找到你要的答案

Q:Finding minimum number of presses to shut down lamps

Q:找到最低数量的压力机关闭灯

I tried to solve a programming problem but my I was unable to see an efficient algorithm. Situation is like this: We have a set of n lamps which can be on (1) or off (0) like this: 1110001011101. That byte string means that there are 13 lamps forming a circle where first three lamps are on, then 3 next off and so on and circle mean that the last lamp is next to the first one.

Then we have been given an integer m>0. It means that in any turn we can choose a lamp and then it and its m adjacent lamps changes their state s to 1-s. I.e. if m=2 and lamp states are 1110001011101 then applying the process to the first lamp we get the sequence 0000001011110.

Now the question is that if the string of length about 2200 and m about 110 are fixed, how one can develop an algorithm that shut downs all the lamps with minimum number of turns?

我试图解决一个编程问题,但我无法看到一个有效的算法。情况是这样的:我们有一组N灯,可以在(1)或关闭(0)这样:1110001011101。该字节串意味着有13盏灯形成一个圆圈,前三盏灯上,然后3下,等等和圆圈意味着最后一盏灯旁边的第一个。

然后我们得到一个整数m & gt;0。这意味着,在任何我们可以选择一个灯,然后及其相邻灯状态的变化作即M = 2和灯状态1110001011101然后运用过程第一灯得到序列000000 1011110。

现在的问题是,如果字符串长度约2200和M约110是固定的,如何开发一个算法,关闭所有的灯与最低数量的匝数?

answer1: 回答1:

There's a general solution to flipping problems like this using linear algebra over Z/2Z (that is the field containing only the numbers 0 and 1).

Suppose there's N bulbs and N switches. Let M be an N by N matrix with a 1 in position i, j if pressing switch i toggles bulb j. Here your matrix will look like this for N=5, m=1:

1, 1, 0, 0, 1
1, 1, 1, 0, 0
0, 1, 1, 1, 0
0, 0, 1, 1, 1
1, 0, 0, 1, 1

Let x be a column vector of size N, where each entry is 0 or 1.

Then Mx (that is, the product of the matrix M and the vector x over Z/2Z) is a column vector of size N which is the result of pressing the switches corresponding to 1s in x. That's because in Z/2Z, multiplication is like "and" and addition is like "xor".

Let v be a column vector of size N, with v_i=1 if bulb i is initially lit. Then x solves the problem if it's a solution to the linear system Mx = v. It can be solved, for example, using gaussian elimination.

有这样的翻转使用线性代数在Z/2Z问题一般解(即字段只包含数字0和1)。

假设有N个灯泡和n个开关。设M是一个n×n矩阵与一个1的位置,如果按下开关我切换灯泡J.你矩阵将看起来像这样为N = 5,M = 1:

1, 1, 0, 0, 1
1, 1, 1, 0, 0
0, 1, 1, 1, 0
0, 0, 1, 1, 1
1, 0, 0, 1, 1

设x为大小n的列向量,其中每个条目为0或1。

然后Mx(即矩阵M的和向量x在Z/2Z产品)是一个大小为n,按对应1 X。这是因为Z/2Z开关结果列向量乘法像”和“加像“异或”。

设V是一个大小为n的列向量,与v_i = 1如果我最初点燃。然后X解决问题如果是解决线性系统的MX = V可以解决,例如,用高斯消去法。

answer2: 回答2:

This problem is similar to the well-known "lights out" problem. http://en.wikipedia.org/wiki/Lights_Out_%28game%29 One way to approach it is by using linear algebra. It's easier to understand with smaller numbers, say length = 5 and m = 1.

First note that choosing a lamp and changing it (and its neighbors') state twice has no effect. Second note that the order in which lamps (and their neighbors) are switch doesn't matter. So a strategy is just a set of lamps. We'll represent lamps that are chosen to be part of the strategy by 1 and lamps that are not chosen by 0. We place the 1's and 0's in a column vector, e.g., (0 1 1 0 1)^T where T is for transpose (rows become columns). That strategy means toggle the lamp in position 1 (starting at position 0, of course) and its two neighbors; then the lamp in position 2 and its two neighbors, and finally the lamp in position 4 and its two neighbors.

The effect of a strategy can be calculated by matrix multiplication over the field GF(2). GF(2) has just 2 elements, 0 and 1, with ordinary rules of arithmetic except for the rule 1 + 1 = 0. Then the effect of the strategy above is the result of matrix multiplication by a matrix with the result of choosing lamp i in the i-th column, in other words by a "circulant matrix` as follows:

[ 1 1 0 0 1 ] [0]   [0]
[ 1 1 1 0 0 ] [1]   [0]
[ 0 1 1 1 0 ] [1] = [0]
[ 0 0 1 1 1 ] [0]   [0]
[ 1 0 0 1 1 ] [1]   [1]

The result of the strategy (0 1 1 0 1)^T is to toggle only the light in the last position. So if you start with only the light in the last position lit, and apply the strategy, all the lights will be off.

In this simple case, we represent the initial configuration by a column vector b. The solution strategy is then a column vector x satisfying the matrix equation Ax = b.

The question now becomes, for given b, 1) is there an x satisfying Ax=b? 2) Is the solution x unique? If not, which x has the least 1's? 3) How can it be calculated?

The answers to the above questions will depend on the numbers "length" and "m" for the particular problem at hand. In the length = 5, m = 1 problem considered above, the theory of linear algebra tells us that there is a unique solution for any b. We can get solutions for b of the form (0 0 ... 1 ... 0)^T, in other words one 1 and the rest zero, by "rotating" the solution (0 1 1 0 1)^T. We can represent any solution uniquely as a linear combination of those solutions, so the strategy/solution with the minimum number of 1's is the same as the unique solution for any given initial state.

On the other hand, with length = 6 and m = 1, all three strategies (100100)^T, (010010)^T, and (001001)^T map to outcome (111111)^T, so that there is not a unique solution in some cases; by the theory of linear algebra, it follows that there is no solution in some other cases.

In general, we can tell whether solutions exist and are unique using Gaussian elimination. In the 5x5 case above, add row 0 to rows 1 and 4;

[ 1 1 0 0 1 ] [1 0 0 0 0]    [ 1 1 0 0 1 ] [1 0 0 0 0]
[ 1 1 1 0 0 ] [0 1 0 0 0]    [ 0 0 1 0 1 ] [1 1 0 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0] -> [ 0 1 1 1 0 ] [0 0 1 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0]    [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 1 0 0 1 1 ] [0 0 0 0 1]    [ 0 1 0 1 0 ] [1 0 0 0 1]

then swap rows 1 and 2; then add row 1 to row 0 and row 4,

[ 1 1 0 0 1 ] [1 0 0 0 0]    [ 1 0 1 1 1 ] [1 0 1 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0]    [ 0 1 1 1 0 ] [0 0 1 0 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0]    [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 0 1 0 1 0 ] [1 0 0 0 1]    [ 0 0 1 0 0 ] [1 0 1 0 1]

then add row 2 to rows 0, 1, 3, 4; then add row 3 to rows 1, 2;

[ 1 0 0 1 0 ] [0 1 1 0 0]    [ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 1 1 ] [1 1 1 0 0]    [ 0 1 0 0 1 ] [0 0 1 1 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 0 1 0 ] [1 1 0 1 0]    [ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1]    [ 0 0 0 0 1 ] [0 1 1 0 1]

and finally add row 4 to rows 1, 2:

[ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 0 0 ] [0 1 0 1 1]
[ 0 0 1 0 0 ] [1 0 1 0 1]
[ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1]

You can read off the basis of solutions in the columns of the right matrix. For example, the solution we used above is in the last column of the right matrix.

You should try Gaussian elimination in the length = 6, m = 1 case discussed above to see what happens.

In the given case (length = 2200, m = 110), I suspect that solutions always exist and are unique because the number of lamps toggled in one move is 221, which is relatively prime to 2200, but I suggest you use Gaussian elimination to find an explicit strategy for any starting position b. How would you minimize the number of moves if there were not a unique strategy?

这个问题类似于众所周知的“熄灯”问题。HTTP:/ /恩。维基百科。org /维基/ lights_out_ % 28game % 29个方法是利用线性代数。它更容易理解与较小的数字,说长度= 5和M = 1。

首先注意选择一盏灯并改变它(和它的邻居)两次状态没有影响。第二个注意点,灯(及其邻居)开关的顺序无关紧要。因此,战略只是一组灯。我们将代表灯具被选择的战略的一部分,1和灯,没有选择的0。我们把1和0在一个列向量,例如,(0 1 1 0 1)^其中T为转置(行变成列)。这一战略意味着开关灯在位置1(当然是在位置0)和它的两个邻居,然后在位置2和它的两个邻居的灯,最后灯在位置4和它的两个邻居。

一个策略的效果可以通过矩阵乘法计算领域GF(2)。GF(2)只有2个元素,0和1,与普通的算术规则,除规则1 + 1 = 0。然后对以上策略的效果是由一个选择灯我在第i列的结果矩阵的矩阵相乘的结果,换句话说,“循环矩阵`如下:

[ 1 1 0 0 1 ] [0]   [0]
[ 1 1 1 0 0 ] [1]   [0]
[ 0 1 1 1 0 ] [1] = [0]
[ 0 0 1 1 1 ] [0]   [0]
[ 1 0 0 1 1 ] [1]   [1]

该策略的结果(0,1,1,0 1)T是只切换到最后一个位置的光。所以,如果你开始只在最后一个位置的光点燃,并运用策略,所有的灯将关闭。

在这个简单的情况下,我们表示的初始配置由列向量B的解决方案策略,然后一个列向量x满足矩阵方程AX = B.

现在的问题是,对于给定的B,1)有一个令人满意的斧头= B?2)解决方案X独特吗?如果没有,哪一个x至少有1?3)如何计算?

上述问题的答案将取决于数字“长度”和“m”的特定问题在手。在长度= 5,m = 1的问题考虑上述,线性代数理论告诉我们,有一个独特的解决方案任何B。我们可以得到B的形式的解决方案(0)…1…0)换句话说,换句话说,一个1和其余零,通过“旋转”的解决方案(0,1,1,0,1),我们可以代表任何解决方案,唯一的线性组合这些解决方案,所以战略/解决方案的最低数量的1是相同的唯一解决方案,对于任何给定的初始状态。

另一方面,长度= 6和m = 1,所有这三个策略(100100)t,(010010)t,和(001001)t映射到结果(111111)t,因此,在某些情况下,有没有一个唯一的解决方案;由线性代数理论,它是在一些其他的情况下,没有解决方案。

在一般情况下,我们可以告诉解决方案是否存在和独特的高斯消除。在上面的5例,添加行0行1和4;

[ 1 1 0 0 1 ] [1 0 0 0 0]    [ 1 1 0 0 1 ] [1 0 0 0 0]
[ 1 1 1 0 0 ] [0 1 0 0 0]    [ 0 0 1 0 1 ] [1 1 0 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0] -> [ 0 1 1 1 0 ] [0 0 1 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0]    [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 1 0 0 1 1 ] [0 0 0 0 1]    [ 0 1 0 1 0 ] [1 0 0 0 1]

然后交换行1和2,然后在第行和第4行中添加行1,

[ 1 1 0 0 1 ] [1 0 0 0 0]    [ 1 0 1 1 1 ] [1 0 1 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0]    [ 0 1 1 1 0 ] [0 0 1 0 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0]    [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 0 1 0 1 0 ] [1 0 0 0 1]    [ 0 0 1 0 0 ] [1 0 1 0 1]

然后将行2添加到行0,1,3,4,然后将行第3行添加到第1行,2;

[ 1 0 0 1 0 ] [0 1 1 0 0]    [ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 1 1 ] [1 1 1 0 0]    [ 0 1 0 0 1 ] [0 0 1 1 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 0 1 0 ] [1 1 0 1 0]    [ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1]    [ 0 0 0 0 1 ] [0 1 1 0 1]

最后添加行4到行1,2:

[ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 0 0 ] [0 1 0 1 1]
[ 0 0 1 0 0 ] [1 0 1 0 1]
[ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1]

可以在右矩阵的列中读取解决方案的基础。例如,上面使用的解决方案是右矩阵的最后一列。

你应该尝试高斯消除的长度= 6,M = 1的情况下,上面讨论的,看看会发生什么。

在给定的情况下(长度= 2200,M = 110),我认为,解决方案总是存在的,是独一无二的因为灯切换在一个移动的号码是221,这是比较主要的2200个,但我建议你使用高斯消去法找到一个明确的战略,任何位置B.如果有没有一个独特的战略,尽量减少移动次数?

answer3: 回答3:

Well, your explanation doesn't make it clear if the lamps should be only turned off or "flipped" (i.e., 0's become 1's and 1's become 0's). Your example data just turns them off.

If that's the case, just set the 110 lamps to 0 - that would be quicker than querying their state before switching them off. Assuming your lamps are in an array called "lamps" and the starting lamp position is startPos:

// These first 2 lines added after Kolmar remark about adjacent lamps meaning lamps to the left and right.
startPos = startPos - m;
if (startPos < 0) startPos += lamps.length; 
for (int i=0; i <= m + 1; i++){
  if ((i + startPos) > lamps.length) startPos = 0;
  lamps[i + startPos] = 0;
}

If you need to "flip" the lamp's state, change the last line of the loop to:

  lamps[i + startPos] = 1-lamps[i + startPos];

那么,你的解释并没有明确,如果灯应该关闭或“翻转”(即,0的成为1的和1的成为0的)。你的例子数据只是把它们关掉。

如果是这样的话,只需设置110灯到0 -这将是比查询他们的状态,然后关掉他们快。假设你的灯是一个数组中的“灯”和启动灯的位置让:

// These first 2 lines added after Kolmar remark about adjacent lamps meaning lamps to the left and right.
startPos = startPos - m;
if (startPos < 0) startPos += lamps.length; 
for (int i=0; i <= m + 1; i++){
  if ((i + startPos) > lamps.length) startPos = 0;
  lamps[i + startPos] = 0;
}

如果你需要“翻转”灯的状态,改变循环的最后一行:

  lamps[i + startPos] = 1-lamps[i + startPos];
algorithm