Java或python中的范围的递归最大函数

我从'想象java，如何像计算机科学家那样思考'这个练习。由Allen乙唐尼：Java或python中的范围的递归最大函数

写称为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语言中。

来源

2013-07-17 Segfault

查看代码中的评论。

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-17 03:21:16 falsetru

哈哈，@falsetru，你的解决方案的工作，即使它的感觉就像作弊相当不错。我想，当问题说分裂名单，这意味着它应该在中间。但是，嘿，只要它有效。 – Segfault

嗨，你有没有在分裂你的方法和分裂一半的优势，就像丹尼尔下面你的例子。你的方法更快吗？ –

@VasileSurdu，两个版本的比较计数都是一样的。（通过在比较之前添加'print'语句或使用某个全局计数器来确认这一点）。 – falsetru

你需要你的电话更改为：

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-17 03:23:47 Daniel

我收到递归限制错误。 – Segfault

拆分计算错误，现在修复。 – Daniel

Java或python中的范围的递归最大函数

回答

相关问题