递归算法伪代码

-1

我想创建一个将在O（logn）复杂度中执行的递归伪代码，我希望它找到较低的f（i）< 0和f [1 .... n]，其中f 1）> 0和f（n）的0 <递归算法伪代码

prodedure fanc(A[n] , p , q) //(this is my array,first digit of A ,last digit of A) 
if A[n/2] >= 0 
    return fanc(A[n/2] , A[n/2] , A[n-1]) 
else 
    return fanc(A[n/2] , A[0] , A[n/2 -1]) 
if p<q 
    print p 
else 
    print q

我知道，不知何故我必须结束递归。另外，我想知道我是否在正确的道路上，如果你对这个问题有什么好的想法！

更好文本分配的从https://stackoverflow.com/questions/42935621/algorithm-in-ologn复制：

让的整数函数f：{1,2,3 ... N}是单调的并且在{1,2,3定义。假设f（1）> 0和f（n）< 0.我们希望找到最小的整数我与f（i）< 0.设计一个算法为此目的运行在O（logn ）。

来源

2017-03-26 Mikel

你可以扩展你的问题的描述，并添加几个简单的例子吗？一般情况下，当你遇到一个可以解决的问题时，例如'1！'，当计算阶乘时结束递归。使用过程中的if语句对其进行测试。 – Svaberg

相同http://stackoverflow.com/questions/42935621/algorithm-in-ologn？这个问题本周已出现多次。 –

@Svaberg的描述与Paul Hankin提供的问题相同！ http://stackoverflow.com/questions/42935621/algorithm-in-ologn。是的，我知道，但我不知道我怎么可以在我的算法内置！我会在这个过程中做一些事情，像是一个真实的标志，并在我的算法达到可解决的子问题时停止递归？我想和我不知道是否可以定义在哪个可解决的问题，我想停止。我希望你明白我想说的是什么 – Mikel

你几乎在那里，你必须使它相对于p和q（从和到）不是n。然后，如果从==到你找到了解决方案。这假设在[1 ... n]范围内始终存在解决方案。

function firstNegative(f, from, to) { 
    if (from == to) 
     return from; 
    next = from + (to - from)/2; 
    if (f(next) >= 0) 
     return firstNegative(f, next + 1, to); 
    else 
     return firstNegative(f, from, next); 
} 
print firstNegative(f, 1, n);

来源

2017-03-26 03:30:14 maraca

谢谢你的答案！你能解释我为什么要创建下一个变量吗？这似乎与递归中的二分搜索有点不同，我错了吗？ – Mikel

下一个变量是from和to之间的中间值。从0开始只是/ 2。 – maraca

Okey！谢谢！！ – Mikel

递归算法伪代码

回答

相关问题