Calculando uma raiz aninhada em C

9

Pediram-me para calcular a seguinte expressão raiz aninhada usando apenas recursão .

insira a descrição da imagem aqui

Eu escrevi o código abaixo que funciona, mas eles nos permitiram usar apenas uma função e 1 entrada npara esse fim, e não 2 como eu usei. Alguém pode me ajudar a transformar esse código em uma função que calculará a expressão? não pode usar nenhuma biblioteca, exceto as funções de <math.h>.

saída para 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
fonte
Alguém pode me ajudar a transformar esse código em uma função que calculará a expressão? que? Ajudá-lo a se livrar do helper?
4386427/04/04
Se os argumentos estiverem errados, eu chamaria abort()(de <stdlib.h>), e não retornaria silenciosamente 0.
Kaz
11
@chqrlieforyellowblockquotes Twisied. @pastaleg Que tal recursão inútil? 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 - Restabelece Monica
11
@ chux-ReinstateMonica: sim, um abuso mais simples das regras.
chqrlie 4/04
2
@ Open: Se o objetivo da tarefa fosse financiar uma expressão não recursiva da função, provavelmente não solicitaria que o problema fosse resolvido usando "apenas recursão". Certamente um loop simples calcularia o resultado facilmente. Embora eu esteja geralmente desconfiado quando essas perguntas são postadas no Stack Overflow sem o texto real da tarefa.
Eric Postpischil 04/04

Respostas:

7

Use os bits superiores de ncomo um contador:

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;
}

Naturalmente, isso funciona mal quando a inicial né Rou maior. Aqui está uma versão mais complicada que funciona com qualquer valor positivo de n. Funciona:

  • Quando né negativo, funciona como a versão acima, usando os bits superiores para contar.
  • Quando né positivo, se for menor que R, chama-se -npara avaliar a função como acima. Caso contrário, ele se chama R-1negado. Isso avalia a função como se fosse chamada com R-1. Isso produz o resultado correto porque a série para de mudar no formato de ponto flutuante após apenas algumas dezenas de iterações - as raízes quadradas dos números mais profundos ficam tão diluídas que não têm efeito. Portanto, a função tem o mesmo valor para todo num pequeno limite.
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
fonte
Boa idéia, mas assume ints de 32 bits :)
chqrlie 4/04
11
@chqrlieforyellowblockquotes: Nah, é por isso que Ré separado, para que possa ser ajustado. Antes de natingir 32, o valor de retorno para de mudar para IEEE-754 binary64 e, antes de atingir 256, o valor de retorno para de mudar para formatos razoáveis double. Por isso, estou considerando uma versão alternativa que transforma as entradas dos grampos acima R, mas ele precisa usar o bit de sinal e ainda estou trabalhando nisso.
Eric Postpischil 04/04
Existem outras funções de emparelhamento que você pode usar, mas nenhuma tão simples quanto a sua. Sua principal vantagem é que eles trabalham com precisão arbitrária, mas o OP nunca mencionou isso como um requisito.
Ruud Helderman 04/04
@chqrlieforyellowblockquotes: Feito. Agora produz a resposta correta para qualquer positivo, nindependentemente da largura de int.
Eric Postpischil 04/04
5

Sem transformar matematicamente a fórmula (não sei se é possível), você não pode realmente usar apenas um parâmetro, pois para cada elemento você precisa de duas informações: a etapa atual e a original n. No entanto, você pode trapacear . Uma maneira é codificar os dois números no intparâmetro (como mostrado por Eric ).

Outra maneira é armazenar o original nem uma variável local estática. Na primeira chamada que salvamos nnessa variável estática, iniciamos a recursão e, na última etapa, redefinimos para o valor sentinela:

// 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));
}

Aparentemente, o static int n = sentinelC não é padrão porque sentinelnão é uma constante de tempo de compilação em C (é estranho porque o gcc e o clang não reclamam, mesmo com -pedantic)

Você pode fazer isso:

enum Special { Sentinel = -1 };
static int n = Sentinel;
Bolov
fonte
Abordagem interessante, mas receio que o inicializador static int n = sentinel;não seja totalmente compatível com C porque sentinelnão é uma expressão constante conforme o Padrão C. Funciona em C ++ e é compilado com as versões atuais de gcc e clang no modo C, mas não no MSVC 2017, mas você provavelmente deve escrever em static int n = -1;see godbolt.org/z/8pEMnz
chqrlie
11
@chqrlieforyellowblockquotes ish. Obrigado por apontar isto. Comportamento interessante do compilador. Eu perguntei sobre isso nesta pergunta: stackoverflow.com/q/61037093/2805305
bolov 05/04
5

Esse problema implora por soluções distorcidas.

Aqui está um que usa uma única função usando um ou dois intargumentos:

  • se o primeiro argumento for positivo, ele calculará a expressão para esse valor
  • se o primeiro argumento for negativo, deve ser seguido por um segundo argumento e executa uma única etapa no cálculo, recorrendo à etapa anterior.
  • usa <stdarg.h>quais podem ou não ser permitidos.

Aqui está o código:

#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);
    }
}

Aqui está outra solução com uma única função, usando apenas <math.h>, mas abusando das regras de uma maneira diferente: usando uma 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));
    }
}

Outro, estritamente falando recursivo , mas com um nível de recursão único e sem outros truques. Como Eric comentou, ele usa um forloop que pode ser inválido sob as restrições do 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
fonte
Sim, isso funciona, eu acho. muito obrigado por toda a ajuda
Ronen Dvorkin 04/04
Por fim double rec_sqrt_series(int n), a IMO atende aos objetivos do OP usando o sinal como sinalizador de recursão. (Eu deixaria cair o elseque não é necessário como returnestá em if.)
chux - Restabelece Monica
11
@ chux-ReinstateMonica: elseé claro que é possível largar o arquivo, mas eu meio que gosto da simetria de ambos os ramos do ifretorno de um resultado, tipo de estilo de programação funcional.
chqrlie 4/04
@ chux-ReinstateMonica: Espero que o requisito da atribuição de "apenas recursão" exclua a iteração.
Eric Postpischil 04/04
@ EricPostpischil: sim, pensei o mesmo, mas não recebi feedback do OP.
chqrlie 4/04
0

Aqui está outra abordagem.

Depende de intter 32 bits. A idéia é usar os 32 bits superiores de 64 bits intpara

1) Veja se a chamada foi recursiva (ou uma chamada de "fora")

2) Salve o valor alvo nos 32 bits superiores durante a recursão

// 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
fonte