0

我有这个练习来自“思考 java，如何像计算机科学家一样思考”。艾伦 B 唐尼：

编写一个名为的方法maxInRange，它接受一个整数数组和一个索引范围（lowIndex和highIndex），并在数组中找到最大值，只考虑和之间的元素 lowIndex，highIndex包括两端。

这种方法应该是递归的。如果范围的长度是1，即如果lowIndex == highIndex，我们立即知道范围中的唯一元素必须是最大值。所以这是基本情况。

如果范围内有多个元素，我们可以将数组分成两部分，在每一部分中找到最大值，然后找到最大值中的最大值。

我在 python 中提出了一个接近但非常不准确的答案：

cycles=0

def max_in_range(lst,low,high):

    '''

    Could not be able to make it work correctly

    '''



    global cycles

    cycles+=1

    if low==high:

        #print "Cycles: ",cycles

        return lst

    else:

        max_left=max_in_range(lst[low:len(lst)/2+1],low+1,high)

        max_right=max_in_range(lst[len(lst)/2:len(lst)],low+1,high)

        return max_right if max_right>max_left else max_left



lst=[112,32,45,71238,9999,45,12,6,3]   # always Returns the mid element.

print max_in_range(lst,0,10)



def max(lst):

    global cycles

    cycles+=1

    if len(lst)==1:

        print "Cycles: ",cycles

        return lst[0]

    else:

        m=max(lst[1:])

        return m if m> lst[0] else lst[0]



print max(lst)

与问题要求的功能相比，该max功能非常简单，即该功能
是递归的，采用两个限制并在运行时拆分列表。该max_in_range函数始终
返回数组中的中间元素，即9999.

我需要一些关于如何满足问题要求的指示。在 Java 或 Python 或任何其他类似 C 的语言中。

4

2 回答 2

2

请参阅代码中的注释。

def max_in_range(lst, low, high):
    # If the length of the range is 1, the sole element in the range must be the maximum.
    if low == high:
        return lst[low]

    # break the array into two pieces, lst[low:low+1] / lst[low+1:high+1],
    # find the maximum in each of the pieces
    piece1_max = lst[low]
    piece2_max = max_in_range(lst, low + 1, high)

    # find the maximum of the maxima
    if piece1_max > piece2_max:
        return piece1_max
    else:
        return piece2_max

lst = [112,32,45,71238,9999,45,12,6,3]
print max_in_range(lst, 0, len(lst) - 1)
于 2013-07-17T03:21:16.087 回答
0

您需要将呼叫更改为：

print max_in_range(lst,0,len(lst))

这样您就不会像示例那样溢出数组。

但它的其余部分应该看起来像这样：

split = low + ((high - low) / 2)

max_left  = max_in_range(lst, low, split - 1)
max_right = max_in_range(lst, split, high)
于 2013-07-17T03:23:47.513 回答