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

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #21

to threego:
如果将题目的目标改为全部为正面向上,此题到可以考虑递归,不但可以考虑递归,甚至可以
考虑用动态规划来递推(没仔细考虑就这么认为了,如果错了,别扔鸡蛋就行了).
但现在目标状态有可能有两个,可以是全1,也可以是全0.

 

F

forsoft

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #22

程序员杂志2000年最几期我忘了,编程擂台上的类似(可说是一模一样的题目,当时我用VB就做了一个),csdn.net也有代码下载.
你到上面下载吧.在外地出差,不能给你寄代码啊.

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #23

to forsoft:
呵呵，真是巧了,csdn上的题目也是全正全反都可以的吗?
我不急着要结果,只是想多见见各位大虾所用的算法.期待大家的程序,这里也有残酷的测试数据
等着拿这400分的大虾.

 

F

forsoft

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #24

to LeeChange：
最终目标就是一个最值问题嘛？《程序员》杂志上有过几个类似问题。从试刊开如不久就有了一个类似问题。我出差回去给你寄个。现在忙啊：）

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #25

呵呵，我不急.
是呀就是一个求最值问题,求最值的方法大约有:
深度优先
广度优先
分支定界
双向广度优先
A
A*
爬山法
贪心法
线性规划
动态规划
网络流
...
呵呵,写不动了.

 

Z

zhukewen

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #26

先说一个无解的情况：
有1反1正2个硬币，要求每次翻2个。

 

Z

zhukewen

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #27

推而广之，奇数个正奇数个反要求翻偶数次无解

 

天

天真

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #28

A,B中取最小值
n := B mod m;
if n mod 2 = 0 then
次数= B mod m +2
else
无解，
不知道对不对，呵呵

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #29

呵呵，关键是步骤.

 

天

天真

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #30

步聚，我写不出说，举个例子吧
A:= 108;
b := 123;
于是我们选108
假设M：10；
于是我们翻10次A，于是A就剩下8了
于是我们翻4个A，6个B，
这时又剩下了10A了，
再翻一下A，就OK了：）

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #31

to 天真:
我用程序验证了一下,你的翻法是错的.你一共要翻12次.实际上只需要11次.
a=108, b=123, m=10
第一次翻9个a,1个b a=100, b=121
后面十次都是全部翻a.
另外:不是要人来推算,而是要程序推.

 

叶

叶不归

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #32

我认为是这样的：
设m个正面，n个反面，每次翻v个
如果 n大于v就不断减去v
while n > vdo
Dec(n, v);
这时的n只要能被v、v-2、v-4、...、(v-2*i)所组合（不限使用次数），就有解，且为最小解。
而翻动的次序是反向的，就是说先将n组合为v的倍数，再循环减。
比如：m=10, n=10, v=6
那么次序为 5, 6（5表示对n翻5个）
比如：m=10, n=24, v=11
那么次序为 5, 7, 11, 11 (n的变化为24-25-22-11-0)
编程想来不难。

 

叶

叶不归

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #33

当然，在编程时应该先进行循环减，得到的n有如下情况
(v-n) mod 2 = 0 或 (v mod 2=1) 则有解，否则无解
（这个表示可被组合或 不能被直接组合但v为奇数则绝对有解，因为可以利用1 ！！）

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #34

to 叶不归:
m=10, n=24, v=11只需要翻两次.
第一次翻5个正面的,6个反面的,翻过后 m=11, n=23
第二次翻11个正面的. m=0, n=34.得解

 

叶

叶不归

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #35

推论，最小解x（翻动次数）为：
当 n mod v = 0 , x= n/v;
否则如果 (v - (n mod v)) mod 2 = 0 , x= n/v + 1 ----- 可被组合
否则如果 v mod 2 = 1 , x = n/v + 2 ---------无法一次组合但v为奇

 

叶

叶不归

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #36

to LeeChange：
我的解是将n变为0,不是把m变为0.

 

H

hmzz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #37

请大家要考虑到zhukewen所说的情况哟，做程序的一定要有逆向思维的习惯。

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #38

to 叶兄:
第一行有反例 m=8 n=24 v=8, 一次就行,不需要n/v的三次.

 

叶

叶不归

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #39

to LeeChange：
唉，你没明白我的意思，我是说：
我的解是将n变为0,不是把m变为0.----- 只有把n-->0才算解，
如果你要m-->0也算解的话，不妨判断一下n,m大小，如果
n>m，就把n,m对调一下：if n>m then
n<-->m，这样得出解就是一次了。

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-17

• #40

to 叶大虾:
这样做,最少步数不一定能保证.