1

我必须创建一个递归函数，以递归方式查找从 0 到 n 的个数。

所以 f(16) = 9

(1,10,11,12,13,14,15,16)

这显然是家庭作业，所以如果你没有发布任何代码，我将不胜感激，只是它背后的原因。

到目前为止，我的推理是，如果你对一个数字进行 %10，它会告诉你最低有效位是否为 1，如果你将整数除以 10，你就会失去那个数字。

所以我猜这个方法可以是检查if number%10 == 1然后用 f(n/10) 调用函数，但是我在实际的实现中迷失了方向。

如果您能评论您将使用哪种方法，我将不胜感激，它必须是递归的，因为它是家庭作业，程序方法是微不足道的。

4

3 回答 3

2

对于这些类型的问题，我发现编写某种显示模式的图表很有帮助。例如，如果按十数，您知道第一组 (0-9) 包含一个 1。

(0-9) -- 1
(10-19) -- 11
(21-29) -- 1
| | -- 1
(100-109) -- 11
(110-119) -- 21
(120-129) -- 11
| | -- 11
(200-209) -- 1
(210-219) -- 11
(220-229) -- 1
| | -- 1
...
(1000-1009) 等...

这可能需要一段时间，但这将帮助您找到模式，以便您提出更系统的答案。我不想给你太多帮助，因为这是一个家庭作业问题，但这是我在解决创造性数学问题时采用的方法。

于 2012-08-26T23:42:18.667 回答
1

你的方法是完全正确的。对于每个数字，您都需要一个以十进制表示形式返回“个数”的函数。对此的递归表示（请注意，您也可以迭代地执行此操作）。

像所有递归函数一样，您需要您的最终状态捕获，即，如果输入 = 0 返回 0。除此之外（不完全放弃）您只需将当前结果添加到子结果：

 if number==0
     return 0
 if number%10==1
     return myFunc(number/10) + 1
 else
     return myFunc(number/10)

但是，正如我之前所说，没有必要使用递归。迭代解决方案在这里可能更好，因为该函数相对于位数是线性的。

于 2012-08-26T23:39:10.580 回答
1

你的问题有两个部分。

  1. 在 number 中找到个数。
  2. 在所有小于它（但大于零）的数字中找到一个数。

第一部分：

如果最右边的数字是 1，则number % 10 == 1. 如果数字 > 9，您需要检查其他数字，您可以通过对整数除以 10 后的数字进行相同的测试来做到这一点。如果数字 <= 9，那么这会给你零。

所以你的 OnesInNumber 函数有点像：

  1. 如果数字 == 0，则返回 0。
  2. 否则调用 OnesInNumber on number / 10。
  3. 如果number % 10 == 1将该结果加 1。
  4. 返回结果。

例如，当1被调用时给你，，，，，当被调用时给你10，等等。112303212211

你的 OnesInZeroUntil 函数就像：

  1. 如果数字 <= 0，则返回 0。
  2. 否则调用 OnesInZeroUntil on number - 1。
  3. 添加OnesInNumber(number)到此。
  4. 返回结果。

所以你有一个递归函数可以计算出一个数字1中的个数，另一个递归函数可以计算出1每个数字中的个数，直到那个数字，建立在第一个函数的基础上。

如果您没有要求我们不这样做，这足以编写一个快速的 2 个函数。

（提示：如果你的老师还没有要求它，看看你是否可以在没有递归的情况下解决这个问题。每个递归函数都可以重写为非递归形式，这是一项实用技能这样做有些人教递归似乎没有涵盖）。

于 2012-08-26T23:45:08.900 回答