用递归计算函数F(n)。

Read the topic that I do not know what it is saying: The function F (n) determined on non-negative integers as follows: F (0) = 1; F (1) = 1; F (2n) = f (n); F (2n + 1) = F (n) + F (n + 1) Calculated F (n) by recursion. and my code:

读题，我不知道它在说什么:函数F (n)是由非负整数决定的:F (0) = 1;F(1)= 1;F (2n) = F (n);F (2n + 1) = F (n) + F (n + 1)通过递归计算F (n)和我的代码:

#include<iostream.h>
double TINH_F(int n)
{
    if(n == 0)
   {
      return 0;
   }
    if(n == 1)
    {
      return 1;
    }

     return (F(n+1) - F(2*n+1));
}

3 个解决方案

#1

This is obviously incorrect. A recursive function calls itself and includes a stopping condition:

这显然是不正确的。递归函数调用自身并包含停止条件:

#include<iostream.h>
double TINH_F(int n)
{
    if(n == 0)
   {
      return 0;
   }
    if(n == 1)
    {
      return 1;
    }

     // Note the function name change
     return (TINH_F(n+1) - TINH_F(2*n+1));
}

What should your function do if the integer passed in is negative? Will the recursion still work? Or should you throw an exception to indicate to callers that the contract is broken?

如果这个整数是负数，你的函数应该怎么做?递归仍然有效吗?或者你是否应该抛出一个异常来表明合同被打破了?

#2

int f(int n)
{
    if (n<0) return -1; // check if n is positive
    if (n<=1) return 1; // we can catch the first two cases in a single condition

    int half = n/2;

    if (n % 2 == 0) return f(half); // if n is even
    else return f(half) + f(half+1); // if n is odd
}

#3

Your last case says

你最后的情况

F (n) = F (n+1) + F(2 * n + 1), for all n > 1
F(n) = F(n+1) + F(2 * n+1)对所有n > 1。

If you read the definition carefully, this case is not mentioned anywhere.

如果你仔细阅读了这个定义，这个例子在任何地方都没有提到。

I believe you're being tricked by the naming of the parameter - you need four cases.

我相信你被这个参数的命名所欺骗了——你需要四个案例。

Let's break it down:

让我们分解:

F (0) = 1 (or 0 - your definition says 1, but the code says 0...)
F(0) = 1(或0 -你的定义是1，但代码是0…)
F (1) = 1
F(1)= 1
F (2n) = F (n)
F (2n) = F (n)
F (2n + 1) = F (n) + F (n + 1)
F (2n + 1) = F (n) + F (n + 1)

The first two cases are trivial.

前两个例子很简单。

The third case says that if the argument - let's call it m - is even, the result is F(m/2).

第三个例子是，如果这个参数，我们叫它m，它的结果是F(m/2)

The fourth case says that if the argument m is odd, the result is F(m/2) + F(m/2 + 1).
(Confirming the arithmetic left as an exercise.)

第四种情况是，如果参数m为奇数，则结果为F(m/2) + F(m/2 + 1)(确认为练习后的算术)。

In C++:

在c++中:

unsigned int TINH_F(unsigned int n)
{
    if(n == 0)
    {
        return 1;
    }
    else if(n == 1)
    {
        return 1;
    }
    else if (n % 2 == 0)
    {
        return TINH_F(n / 2);
    }
    else
    {
        return TINH_F(n/2) + TINH_F(n/2 + 1);
    }
}

#1