征求一算法. (看来都嫌分少,这样吧再加300,一共400了) (100分)

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-15

• #1

数据结构版上深度优先亮象率颇高,也该给宽度优先一点地盘了.呵呵.
问题描述:
有N个硬币(1<=N<=255),有一些正面向上,另外一些背面向上,没有竖着的.可以对这些硬币进行
翻动,每次可以且仅可以翻动M个硬币(1<=M<=N).每次翻动必须翻M个硬币,不能多也不能少.
问最少翻多少次可以将所有硬币翻成同一面向上(既可以正面向上,也可以背面向上).
输入:
字符串s,由字符'0'或'1'构成,'0'表示背面向上,'1'表示正面向上.
整型M,表示一次翻动的硬币的数目.
输出:
每次翻动后的字符串,直到字符串为全'0'或全'1'.
如果无解,则提示用户无解.

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-15

• #2

呵呵,帮忙顶一下也好呀.

 

T

threego

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-15

• #3

没想太多，不过是不是可以考虑把N看成是N位的2进制数，然后用与和或的方法对其进行“翻动”，
这样算起来比较简单。

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-15

• #4

呵呵，楼上的建议不错.

 

P

Perseus

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-15

• #5

UP

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-15

• #6

由于本题不涉及硬币的排列顺序，我认为不必为每个硬币设置一个二进制状态，而是只要
知道某个时刻有多少个正面朝上/反面朝上的硬币即可，每次翻动时，只要考虑如何将M分配
到这两种硬币集合即可。（这个题和油瓶分油问题似乎有些相似）
初始状态：
硬币总数： N
正面朝上的硬币数： A (0<=A<=N)
每次翻动的硬币数： M (0<=M<=N)
目标状态： N枚硬币全部正面朝上或朝下。
策略：
将每次翻动的硬币数M分配到两个集合（正面朝上、反面朝上）中去，设翻动B枚正面朝上
的硬币（0<=B<=Min(M,正面朝上的硬币数)）。
如此操作之后，新的状态为：
正面朝上的硬币数: A'= A - B + (M-B) = A + M - 2*B //已经化简得够简单了吧
目标状态：
A'=0 or A'=N

 

L

LanderLiu

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-15

• #7

up

 

来

来如风

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-15

• #8

{看它N个硬币中（先申明一下，楼主揭贴以后能否把这些硬币给我？）那个面的数目少，
比如说正面的少，为A个，这时如果m<a那么肯定没有结果，如果m=a那么正好翻这a个就可以了，
如果m>a,那么看他是否小于n-a,如果是那么（m-a)为偶数的话可以成功，否则失败
如果m=n-a也可以正好翻过来，m}
哎，真罗嗦，简单点说吧，如果m等于其中的一面的话可以成功，如果m比其中一面大的次数为偶数时可以
成功，否则都是失败

 

M

MrMengyi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-15

• #9

是不是最小公倍数

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-15

• #10

>>如果m<a那么肯定没有结果
我的想法是，如果A>M，则让B=M——即只翻动一面的硬币，如此反复，直到A<=M为止。
到了A<=M，就可以进行搜索求解了。
上面给出的针对B的约束条件还不完全，应该是：
0<=B<=Min(M,A) AND M-B<=N-A （即：B>=M+A-N）

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-16

• #11

to creation-zy:
呵呵，不愧为版主，一番分析已经拨开了云雾。
to 来如风：
"比如说正面的少，为A个，这时如果m<a那么肯定没有结果"
举个例子吧，5个硬币，2个正面的（a=2），每次翻一个（m=1），满足m<a，但翻两次就得到结果了。

 

T

threego

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-16

• #12

每次都只翻一个肯定有解嘛。

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-16

• #13

可惜题目要求是,每次必须同时翻m个.

 

来

来如风

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-16

• #14

FT,是这个意思啊，
看错了，我也想那么简单话你不会发问的啊，呵呵，见笑了

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-16

• #15

呵呵，有建议就尽管说.
我用程序验证了一下,似乎有如下规律:
正面向上的A个,背面向上的B个.一次必须翻M个.
1.如果a=0或b=0则必定有解.
2.如果m=1,则必定有解.
3.如果a,b为一奇一偶,则只要m<a+b则必定有解.
4.如果a,b同为奇或同为偶,则m-a为偶时必定有解.
5.如果a,b同为奇或同为偶,则m-a为奇时必定无解(m<>1).
呵呵，也不知道总结的对不对,希望不要影响了各位大虾的思路.
另外,此题不是要求求是否有解,而是要解的过程.

 

L

liboy.com

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #16

问题的难点在于,每一次翻的钱不一定都是正面(或者反面),每次翻M个硬币,
可以翻面向上的,也可以翻面向下的.
就像玩魔方一下,为了把某个格先移到六面中的一面,需要先转到其他面,再转过来.

因此,需要采用搜索求解的方法,不断的探测.就像国际象棋八国皇后求解那些算法差不多.

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #17

to liboy.com:
呵呵，说对了一半.确实用搜索解.
但8皇后用的是深度优先,此题却适合用广度优先.

 

L

lhlh_0_0

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #18

当m=2,a=1时怎么翻

 

T

threego

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #19

能不能用递归的方法呀?

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #20

to lhlh_0_0:
对于串'100'满足a=1.
运行结果:
Input s: 100
Input m: 2
0: 100
1: 111