<p><strong>这显然是一个硬件问题,所以我会用迂腐的方式来解释。我建议OP或其他感兴趣的人阅读这篇文章,如果他们真的想成为一名专业程序员和/或计算机科学家的话。TLDR人员可以跳到最后一节来查看最终的解决方案。</strong>我将带您了解解决此问题时的思考过程,希望您将来可以学习如何处理递归。你知道吗</p>
<h2>定义基本情况</h2>
<p>您迈出了正确的第一步,即首先定义基本情况。不幸的是,你没有完全正确。基本情况是当我们达到或超过目标时(即当我们的序列达到或超过目标时)。我怎么知道的?它在问题陈述中说:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>当这种情况发生时,您需要返回<em>开始</em>序列的任何位置。基本情况如下:</p>
<pre><code>if sequence >= goal: # base case, return start when we reach or exceed the goal
return start
</code></pre>
<p>请注意函数接口如何没有<code>start</code>值。我们要加上它,这就引出了下一点,那就是<strong>递归助手函数。递归中的一个常见模式是创建一个helper函数,因为我们希望通过递归调用传递额外的参数,但不希望更改原始接口。所以我们想要这样的东西:</p>
<pre><code>def findStartRec(goal, count):
return findStartRecHelper(goal, count, start=0)
def findStartRecHelper(goal, count, start):
if sequence >= goal: # base case (no recursion)
return start
</code></pre>
<h2>定义递归案例</h2>
我们需要考虑两种不同的情况。你知道吗</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>1)第一种情况是电流<code>count</code>达到0。如果我们达到0,那么我们必须尝试从<code>1</code>开始,如果失败,则尝试从<code>2</code>开始,并不断重复,直到找到一个达到或超过目标的值。你知道吗</p>
<blockquote>
<p>Continue this process until the program finds a starting value</p>
</blockquote>
<p>请注意,我们还必须跟踪<em>原始</em>计数,以便知道从何处重新开始。这意味着我们需要helper函数中的另一个变量,我们将<code>count</code>重命名为<code>cur_count</code>,以避免混淆。<code>cur_count</code>将在每次递归调用中递减,<code>original_count</code>将只是一个不变量,它等于传递给<code>findStartRec</code>的原始<code>count</code>(但我们仍然需要某种方法来跟踪它)。你知道吗</p>
<p>2)第二种情况自然是count不等于0。这意味着我们需要为序列中的下一个值递归调用helper函数。所以我们要做这个问题所暗示的事情。这也有子类,但是在我们到达之前不要担心它。你知道吗</p>
<h2>定义第一个递归案例:</h2>
<p>这种情况下<code>cur_count == 0</code>。注意,我向接口添加了两个参数,<code>cur_count</code>和<code>original_count</code>。现在我们的解决方案是这样的:</p>
<pre><code>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
</code></pre>
<p><strong>这就是递归的含义:它是一个调用自身的函数。<code>findStartRecHelper</code>正在调用自己。请注意,在原来的帖子中,没有递归…</strong></p>
<h2>定义第二个递归案例</h2>
<p>在第二个案子里有两个子案子。第一个子类是when<code>cur_count == original_count</code>。这意味着我们跟踪的<code>sequence</code>是0。第二个子类是when <code>cur_count != original_count</code>,因此<code>sequence</code>应该由我们前面的递归调用定义。此外,我们需要将<code>cur_count</code>减少1,因为我们刚刚更新了<code>sequence</code>。因此,我们将写下修改<code>sequence</code>的这两种情况:</p>
<pre><code>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)
</code></pre>
<h2>综合起来:</h2>
<p>最终解决方案:</p>
<pre><code>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))
</code></pre>
<p>这将输出:</p>
<pre><code>Result: 9
</code></pre>
<p>根据需要。你知道吗</p>
<p>现在的问题和你将来的研究。</strong></p>