0

我在弄清楚为什么我的代码不起作用时遇到了一些麻烦，如果有人能指出我所缺少的，我将不胜感激。这是一个基本的算法问题：给定一组不同的排序整数，确定是否存在满足 a[i] = i 的元素（例如，a[3] = 3）。

我尝试使用打印语句对其进行调试，但它只调用一次 FindIndex 而不是递归。

这是代码：

import math

def FindIndex(SetToSearch, beginningIndex, endingIndex):
    """Searches a list of sorted integers to see if there is some a[i] == i

    Keyword Arguments:
    SetToSearch -- a list of disctinct sorted integers 
    beginningIndex -- start point of index to search
    endingIndex -- end point to search """
    # calculate midpoint of set
    midpointIndex = math.ceil((beginningIndex + endingIndex) / 2)
    midpoint = SetToSearch[int(midpointIndex)]
    print "beginningIndex: %s, endingIndex: %s" %(beginningIndex,endingIndex)
    print "midpointIndex: %s, midpoint: %s" % (midpointIndex, midpoint)
    # check whether ending index is greater then beginning index
    if (endingIndex > beginningIndex):
        return "There is no value in this set such that a[i] = i"
    if (endingIndex == beginningIndex):
        if SetToSearch[beginningIndex] == SetToSearch[endingIndex]:
            return "a[%s] is equal to %s" % [beginningIndex, beginningIndex]
    if (midpoint == midpointIndex):
        return "The value at index %d" % midpointIndex
    if (midpoint > midpointIndex):
        print "midpoint > midpointIndex evaluated to true and executed this"
        return FindIndex(SetToSearch, 0, midpointIndex)
    if (midpoint < midpointIndex):
        print "midpoint < midpointIndex evaluated to true and executed this"
        return FindIndex(SetToSearch, midpointIndex + 1, len(SetToSearch) -1)
    else:
        "Something is wrong with your program, because you should never see this!"

sampleSet = [-10, -8, -6, -5, -3, 1, 2, 3, 4, 9 ]
lastIndex = len(sampleSet) - 1

FindIndex(sampleSet,0,lastIndex)
4

4 回答 4

1

问题不在于递归。只是您的第一个条件始终为真：endingIndex始终大于beginningIndex. 该条件不递归地返回，因此函数到此结束。

于 2012-09-22T17:39:16.350 回答
0

首先，您必须添加return到第 48 行的开头。
其次，添加print到最后一行的开头。

于 2012-09-22T17:42:36.647 回答
0

首先，如果您看不到发生了什么，那是因为您需要打印返回的字符串：

print FindIndex(sampleSet,0,lastIndex)

现在，如果我运行它，我会得到：

beginningIndex: 0, endingIndex: 9
midpointIndex: 4.0, midpoint: -3
There is no value in this set such that a[i] = i

这意味着这if匹配：

# check whether ending index is greater then beginning index
if (endingIndex > beginningIndex):
    return "There is no value in this set such that a[i] = i"

...好吧，当然是这样 -endingIndex 应该总是大于beginningIndex！

为了将来参考，您是否打印了字符串？您是否看到输出行但不明白为什么要使用该分支？您是否尝试使用 单步执行代码pdb？

于 2012-09-22T17:43:22.213 回答
0

你可以使用for循环来做到这一点：

def find_index_equal_value(set):
    for i in range(0, len(set)):
        val = set[i]
        if(val == i):
           print "Index matches value."
于 2012-09-22T17:38:05.067 回答