使用递归查找平均值 [英] Find average using recursion

问题描述

我正在做一个练习，其内容如下：



创建一个函数，给出一个数字n，它们是从中获取数字的平均步数1到n得到数字1，例如：

 1 => 0步到1 
 2 => 1步到1 
 3 => 7个步骤到1 
 4 => 2个步骤到1 
 5 => 5步到达1 

然后平均Collat​​z功能表现如下：

 [B] averageCollat​​z（1）[/ B] == 0/1 == 0 
 [B] averageCollat​​z（2）[/ B] = =（0 + 1）/ 2 == 0.5 
 [B] averageCollat​​z（3）[/ B] ==（0 + 1 + 7）/ 3 == 2.6666 .. 
 [B] averageCollat​​z （4）[/ B] ==（0 + 1 + 7 + 2）/ 4 == 2.5 
 [B] averageCollat​​z（5）[/ B] ==（0 + 1 + 7 + 2 + 5 ）/ 5 == 3 
等... 

我做了这个代码



< pre lang =cs> unsigned int collat​​z（
const unsigned int n）
{
if （n == 1 ）
返回 0 ;
else if （n％ 2 ）
return 1 + collat​​z（n * 3 + 1 ）;
else
return 1 + collat​​z（n / 2 ）;
}

double averageCollat​​z（unsigned num）
{
double temp，total = 0 ;;

temp = collat​​z（num）;
if （num > 1 ）averageCollat​​z（num - 1 ）;
总计+ =临时;
return total / num;
}

但它不能正常工作¿我做错了？

解决方案

我认为问题在于你在每一步都进行划分。你需要在结束时只进行一次除法。



因此 averageCollat​​z 将被重命名为 sumCollat​​z ，最后一行是：

  return  total; 

然后你会：

  double  averageCollat​​z （ unsigned   int  num）
 {
  unsigned  steps = collat​​z（num）; 
  double  sum = sumCollat​​z（num）; 
  return  sum / steps; 
} 

您可能必须将n等于0的情况视为处理。

平均值是< br $> b $ b

a = 1 / m∙Σ _{k = 0} ^m x _k



作为一个系列，您可以定义以下内容：



1）a ₀ = x ₀

2）a _{n + 1} =（a _n ∙（n + 1）+ x _{n + 1} ）/（n + 2）



这有初始平均函数的问题：总和可能超出了数字限制，即术语a _n ∙（n + 1）与给定点的部分总和相同。



你现在可以重写上面的第二个词来



1）...

2）a _{n + 1} = a _n ∙（n + 1）/（n + 2）+ x _{n + 1} /（n + 2）



第二个术语有另一个问题：它很可能产生链计误差，计算机算术精度有限：术语（n + 1）/（n + 2）总是小于1并且朝向1，具有更大的数字n。在某些时候它对于计算机算术来说恰好是1，因此产生（稍微？）错误的结果。



对于你给出的问题，你必须决定上面的哪一个对于给定的问题，所提到的效果更差，因此为您的计算选择了另一个。如果你做迭代或递归方法并不重要，因为每个递归方法也总是可以迭代完成。



在我看来，递归是错误的方法，因为你容易填满堆栈。递归通常用于分而治之的方法，其导致仅或多或少的二进制搜索深度，而不是线性增长的堆栈到无穷大。从这个角度来看，递归对于这个问题来说真的是* *错误*的方法。



干杯

Andi



PS：另请参阅我对上面Collat​​z功能的评论。

I'm doing an exercise which reads as follows:

Create a function that given a number n the average of the steps they have to make the numbers from 1 to n to get to number 1, for example:

1 => 0 steps to get to 1
2 => 1 steps to get to 1
3 => 7 steps to get to 1
4 => 2 steps to get to 1
5 => 5 steps to get to 1

Then the average "Collatz" function would behave as follows:

[B]averageCollatz(1)[/B] == 0 / 1 == 0
[B]averageCollatz(2)[/B] == (0+1) / 2 == 0.5
[B]averageCollatz(3)[/B] == (0+1+7) / 3 == 2.6666..
[B]averageCollatz(4)[/B] == (0+1+7+2) / 4 == 2.5
[B]averageCollatz(5)[/B] == (0+1+7+2+5) / 5 == 3
etc...

I did this code

unsigned int collatz(
    const unsigned int n )
{
  if ( n == 1 )
    return 0;
  else if ( n % 2 )
    return 1 + collatz( n * 3 + 1 );
  else
    return 1 + collatz( n / 2 );
}

double averageCollatz(unsigned num)
{
    double temp, total = 0;;

	temp = collatz(num);
    if ( num > 1 ) averageCollatz(num - 1);
	  total += temp;
    return total / num;
}

But it does not work as it should ¿I'm doing wrong?

解决方案

I think that the problem is that you do the division at each step. You need to do the division only once at end.

Thus averageCollatz would be renamed sumCollatz and last line would be:

return total;

Then you would have:

double averageCollatz(unsigned int num)
{
    unsigned steps = collatz(num);
    double sum = sumCollatz(num);
    return sum / steps; 
}

You might have to treat the case for n equals to 0.

The average is the average

a = 1/m ∙ ∑_k=0^mx_k

As a series, you can define the following:

1) a₀ = x₀
2) a_n+1 = (a_n ∙ (n + 1) + x_n+1) / (n + 2)

This has the problem of the initial average function: the sum may go beyond the number limit, i.e. the term a_n ∙ (n + 1) is identical with the partial sum up to the given point.

You may now rewrite the second term above to

1) ...
2) a_n+1 = a_n ∙ (n + 1) / (n + 2) + x_n+1 / (n + 2)

This second term has another issue: it most likely produces chain-errors with the limited precision of computer arithmetic: the term (n + 1) / (n + 2) is always smaller than 1 and goes towards 1 with larger numbers n. At some point it is exactly 1 for the computer arithmetic and so produces (slightly?) wrong results.

For your given problem, you have to decide which of the above mentioned effect is worse for a given problem, and accordingly chose one of the other for your calculation. It does not matter if you do iterative or recursive approach since each recursive approach can always be done iteratively too.

In my eyes, recursion is the wrong approach here since you easily fill up the stack. Recursion is often used for divide-and-conquer approach which results in a more or less binary search depth only of the stack and not a linearly growing stack to "infinity". From that point of view, recursion is *really* the *wrong* approach for this problem.

Cheers
Andi

PS: See also my comment on the Collatz function above.

这篇关于使用递归查找平均值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！