例题7-13 UVa1374猜想

[WangQiuc]

书中有一个猜想，每次总是使用”刚刚得到“的那个数。
这个猜想可以尝试用反证法证明，不知道是否正确。
假设目标数X最少需要d次乘除法求出，那么在解答树上，X位于深度d，则根据猜想假设，X一定由X(d-1)求出: X = X(d-1) +/- Xk，0 <= k <= d-1。
现在给出反例，X无法由Xd-1得到，但可以由另外路径中两个结点Xi, Xj得到，即X = Xi +/- Xj，0 <= i <= j < d-1，那么在另一条路径，0--i--j，X = X = Xi +/- Xj，那X可以在第j+1层就被求出，即只需要j+1 次乘除法就可以求出，与假设最少需要d(>j+1)次乘除法相悖，因此反例不存在。