递归查找基序列

Question

findStartRec(goal, count)从初始值递归地向前搜索 ，并返回达到或超过目标的最小整数值。你知道吗

前提条件是goal >= 0和count > 0。如果从0开始的double（x*2）和add 5（+5）序列不能达到count步中的目标，那么尝试从1开始。你知道吗

继续此过程，直到程序在count steps中找到一个达到或超过目标的起始值'N'，然后返回该起始值。你知道吗

示例：

findStartRec( 100, 3 ) returns '9'

这是我到目前为止得出的结论

def findStartRec(goal, count, sequence=0, itter=0):
    if sequence == goal and count == 0:
        print("Sequence: ", sequence, "Itter: ", itter)
        return sequence, itter
    else:
        while count > 0:
            sequence = (itter * 2) + 5
            count = count + 1
            #return findStartRec(goal, count + 1, sequence, itter)
        else:
            return findStartRec(goal, count, sequence, itter + 1)

Answer 1

这显然是一个硬件问题，所以我会用迂腐的方式来解释。我建议OP或其他感兴趣的人阅读这篇文章，如果他们真的想成为一名专业程序员和/或计算机科学家的话。TLDR人员可以跳到最后一节来查看最终的解决方案。我将带您了解解决此问题时的思考过程，希望您将来可以学习如何处理递归。你知道吗

定义基本情况

您迈出了正确的第一步，即首先定义基本情况。不幸的是，你没有完全正确。基本情况是当我们达到或超过目标时（即当我们的序列达到或超过目标时）。我怎么知道的？它在问题陈述中说：

Continue this process until the program finds a starting value 'N' that does reach or exceed goal in count steps, and return that start value.

当这种情况发生时，您需要返回开始序列的任何位置。基本情况如下：

if sequence >= goal: # base case, return start when we reach or exceed the goal                                                                                                                                                    
    return start

请注意函数接口如何没有start值。我们要加上它，这就引出了下一点，那就是递归助手函数。递归中的一个常见模式是创建一个helper函数，因为我们希望通过递归调用传递额外的参数，但不希望更改原始接口。所以我们想要这样的东西：

def findStartRec(goal, count):
    return findStartRecHelper(goal, count, start=0)

def findStartRecHelper(goal, count, start):
    if sequence >= goal: # base case (no recursion)                                                                                                                                                     
        return start

定义递归案例

我们需要考虑两种不同的情况。你知道吗

If the double (x * 2) and add 5 ( + 5) sequence starting at 0 cannot reach the goal in count steps, then try starting at 1.

1）第一种情况是电流count达到0。如果我们达到0，那么我们必须尝试从1开始，如果失败，则尝试从2开始，并不断重复，直到找到一个达到或超过目标的值。你知道吗

Continue this process until the program finds a starting value

请注意，我们还必须跟踪原始计数，以便知道从何处重新开始。这意味着我们需要helper函数中的另一个变量，我们将count重命名为cur_count，以避免混淆。cur_count将在每次递归调用中递减，original_count将只是一个不变量，它等于传递给findStartRec的原始count（但我们仍然需要某种方法来跟踪它）。你知道吗

2）第二种情况自然是count不等于0。这意味着我们需要为序列中的下一个值递归调用helper函数。所以我们要做这个问题所暗示的事情。这也有子类，但是在我们到达之前不要担心它。你知道吗

定义第一个递归案例：

这种情况下cur_count == 0。注意，我向接口添加了两个参数，cur_count和original_count。现在我们的解决方案是这样的：

def findStartRec(goal, count):
    return findStartRecHelper(goal, cur_count=count, original_count=count, start=0, sequence=0)

def findStartRecHelper(goal, cur_count, original_count, start, sequence):
    if sequence >= goal: # base case (no recursion)                                                                                                                                                     
        return start
    elif cur_count == 0:
        # Didn't reach the goal, but ran out of tries. Increment the start (N) and restart                                                                                                          
        return findStartRecHelper(goal=goal, # invariant                                                                                                                                            
                                  cur_count=original_count, # Restart at original_count                                                                                                         
                                  original_count=original_count, # invariant                                                                                                                        
                                  start=start+1, # try the next start                                                                                                                               
                                  sequence=0) # restart sequence at 0

这就是递归的含义：它是一个调用自身的函数。findStartRecHelper正在调用自己。请注意，在原来的帖子中，没有递归…

定义第二个递归案例

在第二个案子里有两个子案子。第一个子类是whencur_count == original_count。这意味着我们跟踪的sequence是0。第二个子类是when cur_count != original_count，因此sequence应该由我们前面的递归调用定义。此外，我们需要将cur_count减少1，因为我们刚刚更新了sequence。因此，我们将写下修改sequence的这两种情况：

if cur_count == original_count:
    # Sequence is 0, so use start * 2 + 5                                                                                                                                               
    sequence = start * 2 + 5
else:
    # Sequence is not 0                                                                                                                                                                 
    sequence = sequence * 2 + 5
# Return the next iteration                                                                                                                                                                 
return findStartRecHelper(goal=goal, # invariant
                          cur_count=cur_count-1, # Note we've decremented by 1
                          original_count=original_count, # invariant
                          start=start,
                          sequence=sequence)

综合起来：

最终解决方案：

def findStartRec(goal, count):
    return findStartRecHelper(goal, cur_count=count, original_count=count, start=0, sequence=0)

def findStartRecHelper(goal, cur_count, original_count, start, sequence):
    if sequence >= goal: # base case (no recursion)                                                                                                                                                     
        return start
    elif cur_count == 0:
        # Didn't reach the goal, but ran out of tries. Increment the start (N) and restart                                                                                                          
        return findStartRecHelper(goal=goal, # invariant                                                                                                                                            
                                  cur_count=original_count, # Restart at original_count                                                                                                             
                                  original_count=original_count, # invariant                                                                                                                        
                                  start=start+1, # try the next start                                                                                                                               
                                  sequence=0) # restart sequence at 0                                                                                                                               
    else:
        if cur_count == original_count:
            # Sequence is 0, so use start * 2 + 5                                                                                                                                               
            sequence = start * 2 + 5
        else:
            # Sequence is not 0                                                                                                                                                                 
            sequence = sequence * 2 + 5
        # Return the next iteration                                                                                                                                                                 
        return findStartRecHelper(goal=goal, # invariant                                                                                                                                            
                                  cur_count=cur_count-1, # Note we decrement by one                                                                                                                 
                                  original_count=original_count, # invariant                                                                                                                        
                                  start=start,  
                                  sequence=sequence)

print("Result: ", findStartRec(100, 3))

这将输出：

Result: 9

根据需要。你知道吗

现在的问题和你将来的研究。

Answer 2

我不太确定预期的结果应该是什么，但是在FindStartRec函数的第2行，将“&；改为”和“将结果从0,0（0,0）改为（100,4,5,0）。你知道吗

希望这是你所期望的结果。你知道吗