二进制问题一则

无心人 · 发表于 2008-3-20 17:24:52

您需要登录才可以下载或查看，没有账号？欢迎注册

×

有二进制数字M
二进制数字N
M, N二进制表示中的1数量相等

对M做变换，每次可交换相邻位数字
问是否总能把M变换成N
最少的次数是多少？

mathe · 发表于 2008-3-20 18:35:12

这个可行性是很容易证明的。
不过最少次数应该是一个计算机问题。看问题的规模如何。

无心人 · 发表于 2008-3-21 16:39:04

简单些
小于等于32位

northwolves · 发表于 2008-3-24 00:27:20

问是否总能把M变换成N
最少的次数是多少？

------------------
最少0次。应该问最坏情况下，最多的次数？

mathe · 发表于 2008-3-24 08:02:04

最多次数好解。应该就是0和1数目一样多（或只差一个），从1都是左边(N)变成1都在右边(M).如果1数目不超过0的数目,1的数目为u,0的数目为v(v=u或v=u+1),那么容易证明这时需要变换uv次。
而对于其它情况，也容易证明，uv次数变换肯定足够。

无心人 · 发表于 2008-3-24 15:51:27

是某些问题的变形

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 二进制问题一则