找鸡蛋：一个智力题的编程求解
有12个鸡蛋，其中有一个和其他不一样重（或重或轻），给你一个天平，只准你称3次，然后找出那个和其他不一样重的鸡蛋。并且知道它是比其他重还是比其他轻！
我想了半天，没想出来，感觉去上网查或问别人太没劲，就想着是否可以用搜索穷举出结果，我初步的想法是：
1 测试数据集 12
2 数据表示 composite 比较
3 行为集： 比较，剪枝，添加，判断，分组
4 规则：满足 与否
穷举各种分组策略，记录行为轨迹，对成功的，在其他11组上验证。
关键是行为集的定义
现在向大家求教，望不吝赐教！
[解决办法]
等看了答案就知道穷举法根本不可行
建议看看答案吧，看完答案能编出算法就不简单
[解决办法]
用递归的方法还是很容易实现的。
思路定好了，用什么语言都很容易实现。
比如说VB的代码就可以这样写：
Option Explicit
Private Sub cmdEgg12_Click()
Dim i As Long
Dim iMin As Long
Dim iMax As Long
Dim j As Long
Dim jMin As Long
Dim jMax As Long
Dim k As Long
Dim arrData() As Long
iMin = 0
iMax = 11
ReDim arrData(iMax)
For i = iMin To iMax
arrData(i) = 100
Next i
arrData(4) = 90
'arrData(7) = 110
jMin = iMin
jMax = Fix(iMax / 2)
Debug.Print vbCrLf
k = EggOut(arrData(), iMin, iMax, jMin, jMax)
Debug.Print "* " & iMin & "; " & iMax & "; " & jMin & "; " & jMax & "; " & k
End Sub
Private Function EggOut( _
arrData() As Long, _
ByRef iMin As Long, _
ByRef iMax As Long, _
ByRef jMin As Long, _
ByRef jMax As Long _
) As Long
Dim lngSum As Long
lngSum = 0
'' Sum it
lngSum = EggSum(arrData(), jMin, jMax)
Debug.Print "* " & jMin & " " & jMax & " " & lngSum
'' Same data?
If lngSum = ((jMax - jMin + 1) * 100) Then
iMin = jMax + 1
iMax = iMax
jMin = iMin
jMax = jMin + Fix((iMax - jMin) / 2)
'' Not the same?
Else
iMin = iMin
iMax = jMax
jMin = iMin
jMax = jMin + Fix((iMax - jMin) / 2)
End If
'' Continue?
If ((jMax - jMin) <> 1) Then
EggOut = EggOut(arrData(), iMin, iMax, jMin, jMax)
Else
'' Result
Debug.Print "*Result* " & jMin & " " & jMax & " " & lngSum
Debug.Print "*Result* " & jMin & " " & arrData(jMin) & "; " & jMin + 1 & " " & arrData(jMin + 1) & "; " & jMin + 2 & " " & arrData(jMin + 2)
End If
End Function
Private Function EggSum( _
arrData() As Long, _
iMin As Long, _
iMax As Long _
) As Long
Dim i As Long
Dim lngSum As Long
lngSum = 0
For i = iMin To iMax
lngSum = lngSum + arrData(i)
Next i
EggSum = lngSum
End Function
[解决办法]
如果想优化一下，那就写成这样：
Option Explicit
Private Sub cmdEgg12_Click()
Dim i As Long
Dim iMin As Long
Dim iMax As Long
Dim j As Long
Dim jMin As Long
Dim jMax As Long
Dim k As Long
Dim arrData() As Long
iMin = 0
iMax = 11
ReDim arrData(iMax)
For i = iMin To iMax
arrData(i) = 100
Next i
arrData(4) = 90
'arrData(7) = 110
'' Check ranage
jMin = iMin
jMax = jMin + Fix((iMax - jMin) / 2)
'' Debug
Debug.Print vbCrLf
k = EggOut(arrData(), iMin, iMax, jMin, jMax)
'' Debug
Debug.Print "* " & iMin & "; " & iMax & "; " & jMin & "; " & jMax & "; " & k
End Sub
Private Function EggOut( _
arrData() As Long, _
ByRef iMin As Long, _
ByRef iMax As Long, _
ByRef jMin As Long, _
ByRef jMax As Long _
) As Long
Dim lngSum As Long
lngSum = 0
'' Sum it
lngSum = EggSum(arrData(), jMin, jMax)
'' Debug
Debug.Print "* " & jMin & " " & jMax & " " & lngSum
'' Same data?
If lngSum = ((jMax - jMin + 1) * 100) Then
iMin = jMax + 1
iMax = iMax
'' Not the same?
Else
iMin = iMin
iMax = jMax
End If
'' Continue?
jMin = iMin
jMax = jMin + Fix((iMax - jMin) / 2)
If ((jMax - jMin) <> 1) Then
EggOut = EggOut(arrData(), iMin, iMax, jMin, jMax)
Else
'' Result
Debug.Print "*Result* " & jMin & " " & jMax & " " & lngSum
Debug.Print "*Result* " & jMin & " " & arrData(jMin) & "; " & jMin + 1 & " " & arrData(jMin + 1) & "; " & jMin + 2 & " " & arrData(jMin + 2)
End If
End Function
Private Function EggSum( _
arrData() As Long, _
iMin As Long, _
iMax As Long _
) As Long
Dim i As Long
Dim lngSum As Long
lngSum = 0
For i = iMin To iMax
lngSum = lngSum + arrData(i)
Next i
EggSum = lngSum
End Function
[解决办法]
人想都不一定明白呢！
不过好像已经有公式解决N个鸡蛋最少需要M次的公式了。
看看公式的推导可能有帮助。
[解决办法]
http://blog.csdn.net/pongba/archive/2008/06/13/2544933.aspx 称球
