Calcul d'une racine imbriquée en C

9

On m'a demandé de calculer l'expression racine imbriquée suivante en utilisant la récursivité uniquement.

entrez la description de l'image ici

J'ai écrit le code ci-dessous qui fonctionne, mais ils nous ont permis d' utiliser une seule fonction et 1 entrée nà cet effet et non 2 comme je l'ai utilisé. Quelqu'un peut-il m'aider à transformer ce code en une fonction qui calculera l'expression? ne peut pas utiliser n'importe quelle bibliothèque, sauf les fonctions de <math.h>.

sortie pour n = 10: 1.757932

double rec_sqrt_series(int n, int m) {
    if (n <= 0)
        return 0;
    if (m > n)
        return 0;
    return sqrt(m + rec_sqrt_series(n, m + 1));
}

double helper(int n) {
    return rec_sqrt_series(n, 1);
}
Ronen Dvorkin
la source
Quelqu'un peut-il m'aider à transformer ce code en une fonction qui calculera l'expression? quelle? Vous aider à vous débarrasser du helper?
4386427
Si les arguments sont erronés, j'appellerais abort()(de <stdlib.h>), ne retournerais pas silencieusement 0.
Kaz
1
@chqrlieforyellowblockquotes Twisied. @pastaleg Que diriez-vous d'une récursivité inutile? double nested_root(unsigned n) { double x = 0.0; if (n > 0) { x = nested_root(0); for (unsigned i = n; i > 0; i--) { x = sqrt(i + x); } } return x; }
chux
1
@ chux-ReinstateMonica: oui, un abus plus simple des règles.
chqrlie
2
@Oppen: Si l'objectif de l'affectation était de financer une expression non récursive de la fonction, elle ne demanderait probablement pas que le problème soit résolu en utilisant la «récursivité uniquement». Une simple boucle calculerait certainement le résultat facilement. Bien que je sois généralement méfiant lorsque ces questions sont publiées sur Stack Overflow sans le texte réel de l'affectation.
Eric Postpischil

Réponses:

7

Utilisez les bits supérieurs de ncomme compteur:

double rec_sqrt_series(int n)
{
    static const int R = 0x10000;
    return n/R < n%R ? sqrt(n/R+1 + rec_sqrt_series(n+R)) : 0;
}

Naturellement, cela fonctionne mal lorsque l'initiale nest Rou plus. Voici une version plus compliquée qui fonctionne pour toute valeur positive de n. Ça marche:

  • Quand nest négatif, cela fonctionne comme la version ci-dessus, en utilisant les bits supérieurs pour compter.
  • Quand nest positif, s'il est inférieur à R, il s'appelle avec -npour évaluer la fonction comme ci-dessus. Sinon, il s'appelle avec R-1nié. Cela évalue la fonction comme si elle était appelée avec R-1. Cela produit le résultat correct car la série cesse de changer au format à virgule flottante après seulement quelques dizaines d'itérations - les racines carrées des nombres plus profonds sont tellement diluées qu'elles n'ont aucun effet. Ainsi, la fonction a la même valeur pour tous nsur un petit seuil.
double rec_sqrt_series(int n)
{
    static const int R = 0x100;
    return
        0 < n ? n < R ? rec_sqrt_series(-n) : rec_sqrt_series(1-R)
              : n/R > n%R ? sqrt(-n/R+1 + rec_sqrt_series(n-R)) : 0;
}
Eric Postpischil
la source
Bonne idée, mais suppose des ints 32 bits :)
chqrlie
1
@chqrlieforyellowblockquotes: Non, c'est pourquoi Rest séparé, donc il peut être réglé. Avant d' natteindre 32, la valeur de retour cesse de changer pour IEEE-754 binaire64, et avant d'atteindre 256, la valeur de retour cesse de changer pour des formats raisonnables pour double. J'envisage donc une version alternative qui transforme les entrées de pinces ci R- dessus , mais elle doit utiliser le bit de signe, et je travaille toujours dessus.
Eric Postpischil
Il existe d' autres fonctions de couplage que vous pouvez utiliser, mais aucune n'est aussi simple que la vôtre. Leur principal avantage est généralement qu'ils fonctionnent avec une précision arbitraire, mais OP n'a jamais mentionné cela comme une exigence.
Ruud Helderman
@chqrlieforyellowblockquotes: Terminé. Produit maintenant la bonne réponse pour tout positif nquelle que soit la largeur de int.
Eric Postpischil
5

Sans transformer mathématiquement la formule (je ne sais pas si c'est possible), vous ne pouvez pas vraiment utiliser un seul paramètre, car pour chaque élément, vous avez besoin de deux informations: l'étape en cours et l'original n. Cependant, vous pouvez tricher . Une façon consiste à coder les deux nombres dans le intparamètre (comme indiqué par Eric ).

Une autre façon consiste à stocker l'original ndans une variable locale statique. Au premier appel, nous enregistrons ndans cette variable statique, nous démarrons la récursivité et à la dernière étape, nous la réinitialisons à la valeur sentinelle:

// fn(i) = sqrt(n + 1 - i + fn(i - 1))
// fn(1) = sqrt(n)
//
// note: has global state
double f(int i)
{
    static const int sentinel = -1;
    static int n = sentinel;

    // outside call
    if (n == sentinel)
    {
        n = i;
        return f(n);
    }

    // last step
    if (i == 1)
    {
        double r = sqrt(n);
        n = sentinel;
        return r;
    }

    return sqrt(n + 1 - i + f(i - 1));
}

Apparemment, ce static int n = sentineln'est pas du C standard car ce sentineln'est pas une constante de temps de compilation en C (c'est bizarre parce que gcc et clang ne se plaignent pas, même avec -pedantic)

Vous pouvez le faire à la place:

enum Special { Sentinel = -1 };
static int n = Sentinel;
bolov
la source
Approche intéressante, mais je crains que l'initialiseur static int n = sentinel;ne soit pas entièrement conforme en C car ce sentineln'est pas une expression constante selon la norme C. Il fonctionne en C ++, et il compile avec les versions actuelles de gcc et clang en mode C mais pas MSVC 2017, mais vous devriez probablement écrire static int n = -1;voir godbolt.org/z/8pEMnz
chqrlie
1
@chqrlieforyellowblockquotes ish. Merci de l'avoir signalé. Comportement intéressant du compilateur. J'ai posé des questions à ce sujet dans cette question: stackoverflow.com/q/61037093/2805305
bolov
5

Ce problème demande des solutions déformées.

En voici une qui utilise une seule fonction prenant un ou deux intarguments:

  • si le premier argument est positif, il calcule l'expression de cette valeur
  • si le premier argument est négatif, il doit être suivi d'un deuxième argument et effectue une seule étape du calcul, récursif pour l'étape précédente.
  • il utilise <stdarg.h>ce qui pourrait ou non être autorisé.

Voici le code:

#include <math.h>
#include <stdarg.h>

double rec_sqrt_series(int n, ...) {
    if (n < 0) {
        va_arg ap;
        va_start(ap, n);
        int m = va_arg(ap, int);
        va_end(ap);
        if (m > -n) {
            return 0.0;
        } else {
            return sqrt(m + rec_sqrt_series(n, m + 1));
        }
    } else {
        return rec_sqrt_series(-n, 1);
    }
}

Voici une autre solution avec une seule fonction, utilisant uniquement <math.h>, mais abusant des règles d'une manière différente: en utilisant une macro.

#include <math.h>

#define rec_sqrt_series(n)  (rec_sqrt_series)(n, 1)
double (rec_sqrt_series)(int n, int m) {
    if (m > n) {
        return 0.0;
    } else {
        return sqrt(m + (rec_sqrt_series)(n, m + 1));
    }
}

Encore un autre, à proprement parler récursif , mais avec un seul niveau de récursivité et sans autres astuces. Comme Eric l'a commenté, il utilise une forboucle qui pourrait être invalide sous les contraintes de l'OP:

double rec_sqrt_series(int n) {
    if (n > 0) {
        return rec_sqrt_series(-n);
    } else {
        double x = 0.0;
        for (int i = -n; i > 0; i--) {
            x = sqrt(i + x);
        }
        return x;
    }
}
chqrlie
la source
oui ça marche je suppose. merci beaucoup pour toute l'aide
Ronen Dvorkin
Enfin double rec_sqrt_series(int n), l'OMI atteint les objectifs de l'OP en utilisant le signe comme indicateur de récursivité. (Je laisse tomber le elsene pas nécessaire comme returnest en if.)
chux - Monica Réintégrer
1
@ chux-ReinstateMonica: laisser tomber le elseest possible bien sûr mais j'aime un peu la symétrie des deux branches du ifretour d'un résultat, sorte de style de programmation fonctionnel.
chqrlie
@ chux-ReinstateMonica: Je m'attends à ce que l'exigence de l'affectation de «récursivité seulement» empêche l'itération.
Eric Postpischil
@EricPostpischil: oui, je pensais la même chose, mais je n'ai pas reçu de commentaires de l'OP.
chqrlie
0

Voici une autre approche.

Il repose sur int32 bits. L'idée est d'utiliser les 32 bits supérieurs d'un 64 bits intpour

1) Voir si l'appel était un appel récursif (ou un appel de "l'extérieur")

2) Enregistrez la valeur cible dans les 32 bits supérieurs pendant la récursivité

// Calling convention:
// when calling this function 'n' must be a positive 32 bit integer value
// If 'n' is zero or less than zero the function have undefined behavior
double rec_sqrt_series(uint64_t n)
{
  if ((n >> 32) == 0)
  {
    // Not called by a recursive call
    // so start the recursion
    return rec_sqrt_series((n << 32) + 1);
  }

  // Called by a recursive call

  uint64_t rn = n & 0xffffffffU;

  if (rn == (n >> 32)) return sqrt(rn);      // Done - target reached

  return sqrt (rn + rec_sqrt_series(n+1));   // Do the recursive call
}
4386427
la source