Вычислить стандартное отклонение рекурсивно

Question

#include<stdio.h>
#include<math.h>
double foo(int n, double mean, int n2){
    double square;
    if(n==1){
        return(1);
    }
    if(n!=0){

        return( (sqrt((n-mean)*(n-mean))+foo(n-1,mean,n2))/(sqrt(n2-1))  );
    }


}
int main(){
    int num;
    int n2;
    double mean;
    int i;
    int sum=0;

    printf("Enter the number: ");
    scanf("%d",&num);
    n2=num;
    for(i=1; num>=i; i++){
        sum=sum+i;
    }
    mean=(double)sum/num;
    printf("%lf ",mean);
    foo(num,mean,n2);    
    printf(" %lf ",foo(num,mean,n2));
}

Я хочу рассчитать стандартное отклонение. Формула: https://i.pinimg.com/originals/b5/7c/a0/b57ca00c2aabd05bcb722295734ba2e6.png

Answer 1

Это задание странное, так как это не проблема, которую нужно решать с помощью рекурсии. Хотя, это будет странно, это выполнимо.

Для n = 2 вы хотите

F1: SD(2) = sqrt(((2-mean)^2 + (1-mean)^2)/(2-1))

это можно записать как:

F2: (2-1) * SD(2)^2 = (2-mean)^2 + (1-mean)^2

Для n = 3 Вы хотите

F3: SD(3) = sqrt(((3-mean)^2 + (2-mean)^2 + (1-mean)^2)/(3-1))

Теперь вставьте (2-mean)^2 + (1-mean)^2 из F2 выше, и вы получите:

F4: SD(3) = sqrt(((3-mean)^2 + (2-1) * SD(2)^2)/(3-1))
                                       ^^^^^
                                 Here is the recursion

В более общем смысле формула будет:

SD(n) = sqrt(((n - mean)^2 + (n-1-1) * (SD(n-1))^2)/(n-1))

Таким образом, рекурсивный вызов будет выглядеть примерно так:

double foo(int n, double mean)
{
    if (n == 2) return sqrt(pow(2-mean, 2) + pow(1-mean, 2));
    return sqrt((pow(n-mean, 2) + (n-2)*pow(foo(n-1, mean), 2))/(n-1));
                                           // ^^^
                                           // recursive call
}

Не красиво, но выполнимо.

Итак, полная программа, которая имеет как рекурсивный метод, так и лучший l oop - Метод может быть:

#include <stdio.h>
#include <math.h>

// Recursive method
double foo(int n, double mean)
{
    if (n == 2) return sqrt(pow(2-mean, 2) + pow(1-mean, 2));
    return sqrt((pow(n-mean, 2) + (n-2)*pow(foo(n-1, mean), 2))/(n-1));
                                           // ^^^
                                           // recursive call
}

// Loop method
double bar(int n, double mean)
{
    double x = 0;

    for (int i = 1; i <=n; ++i)
    {
        x = x + pow(i-mean, 2);
    }
    x = x / (n - 1);
    return sqrt(x);
}


int main() {
    int n = 6;
    double mean = (n + 1)/2.0;
    printf("Recursive: %.20f\n", foo(n, mean));
    printf("Loop:      %.20f\n", bar(n, mean));
  return 0;
}

Вывод:

Recursive: 1.87082869338697066475
Loop:      1.87082869338697066475

Answer 2

Как вы указали в комментариях, вам разрешается использовать только одну (рекурсивную) функцию для расчета стандартного отклонения.

Поскольку часть формулы (в частности, взятие квадрата root) не повторяется, я рекомендую использовать хвостовую рекурсию с аккумулятором.

double foo(int i, int n, double mean, double acc)
{
    return i > 0
        ? foo(i - 1, n, mean, acc + pow(i-mean, 2))
        : sqrt(acc / (n-1));
}

Назовите его так:

double stddev = foo(num, num, mean, 0.0);

Результат:

1.870829

Answer 3

Прежде всего, среднее можно найти без использования для l oop:

mean = (num + 1) / 2

Теперь возвращаемся к проблеме рекурсии. То, что вы делаете - это квадратное укоренение и деление на каждом рекурсивном шаге, но вы должны сделать это только один раз. Обычно итеративный подход лучше, но вот рабочее решение для рекурсивного подхода:

double foo1(int n, double mean){
    double square = pow(n-mean,2);
    if(n==1){
        return square;
    }else{
        return square + foo1(n-1,mean);
    }
}

double foo(int n, double mean){
    return sqrt(foo1(n,mean)/(n-1));
}

Здесь у вас есть две функции: одна рекурсивно вычисляет сумму квадратов (foo1), а вторая - делит сумму по n-1 и возвращает его корень;

РЕДАКТИРОВАТЬ: я думаю, что итеративный подход гораздо проще реализовать, плюс это можно сделать с помощью одной функции

double foo(int n, double mean){
    double squareSum = 0;
    int i;
    for(i = 1; i<=n; i++){
        squareSum += pow(i-mean, 2);
    }
    return sqrt(squareSum/(n-1));
}