一道很有趣的难题，可能需要一些时间 [:-M]（图）

新用户

www.ddhw.com

我没有答案

Light Bulbs

Hollywood’s newest theater, the Atheneum of Culture and Movies, has a huge computer-operated marquee composed of thousands of light bulbs. Each row of bulbs is operated by a set of switches that are electronically controlled by a computer. Unfortunately, the electrician installed the wrong kind of switches, and tonight is the opening night. You must make the switches perform correctly.www.ddhw.com

A row of the marquee contains n light bulbs controlled by n switches. Bulbs and switches are numbered from 1 to n, left to right. Each bulb can either be ON or OFF. Each input case will contain the initial state and the desired final state for a single row of bulbs. www.ddhw.com

The original lighting plan was to have each switch control a single bulb. However the electrician’s error caused each switch to control two or three consecutive bulbs, as shown in Figure 1. The leftmost switch (i = 1) toggles the states of the two leftmost bulbs (1 and 2); the rightmost switch (i = n) toggles the states of the two rightmost bulbs (n – 1 and n). Each remaining switch (1 < i < n) toggles the states of the three bulbs with indices i – 1, i, and i + 1. (In the special case where there is a single bulb and a single switch, the switch simply toggles the state of that bulb.) Thus, if bulb 1 is ON and bulb 2 is OFF, flipping switch 1 will turn bulb 1 OFF and bulb 2 ON. The minimum cost of changing a row of bulbs from an initial configuration to a final configuration is the minimum number of switches that must be flipped to achieve the change. www.ddhw.com

You can represent the state of a row of bulbs in binary, where 0 means the bulb is OFF and 1 means the bulb is ON. For instance, 01100 represents a row of five bulbs in which the second and third bulbs are both ON. You could transform this state into 10000 by flipping switches 1, 4, and 5, but it would be less costly to simply flip switch 2.

You must determines the switches that must be flipped to change a row of light bulbs from its initial state to its desired final state with minimal cost. Some combinations of initial and final states may not be feasible. For compactness of representation, decimal integers are used instead of binary for the bulb configurations. Thus, 01100 and 10000 are represented by the decimal integers 12 and 16. www.ddhw.com

看样子题目要求挺高，能设计出一个方案。对于起始数字 -> 终了数字。给出最少次数的解法。

如果题目问的简单一点，什么样的 起始数字 -> 终了数字 一定无解？

 

 www.ddhw.com

 

  本贴由[新用户]最后编辑于：2006-8-13 12:19:38