Autor Tema: ¿Es la sucesión conocida?

0 Usuarios y 1 Visitante están viendo este tema.

07 Marzo, 2008, 06:36 pm
Leído 3484 veces

*Rafa*

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 205
  • Karma: +0/-0
  • Sexo: Masculino
Hola.
Estaba realizando un programa en c++, y me surgió un problema. No importa que no se sepa de c++ ni de programación como veran.

Quisiera poder saber el resultado de la siguiente sucesión \( s(n) \).
\( s(1)=1 \)
\( s(2)=1 2 1 \)
\( s(3)=\underbrace{1 2 1 }_{s(2)} 3 \underbrace{1 2 1}_{s(2)} \)
\( s(4)=\underbrace{1 2 1 3 1 2 1}_{s(3)} 4 \underbrace{1 2 1 3 1 2 1}_{s(3)} \)
...
\( s(n)=s(n-1) n s(n-1) \)
El problema está, en que no me dejan usar la recursividad, es decir, para saber \( s(4) \), antes podría calcular \( s(3) \), \( s(2) \) y despues \( s(1) \). Pero esto no me lo permiten, debe ser mediante iteración.

Es como si nos pidieran el n-ésimo término de la sucesión de Fibonacci, y no nos dejaran calcular los anteriores términos.

Lo pregunto, porque quizás sea una sucesión conocida, y ustedes puedan orientarme en algo.

Saludos y gracias.

07 Marzo, 2008, 06:55 pm
Respuesta #1

León

  • Lathi
  • Mensajes: 903
  • Karma: +0/-0
  • Sexo: Masculino

Mmm... no creo que haya una fórmula cerrada para esa sucesión -aunque puedo estar equivocado.

¿Capaz que en lugar de iteraciones quieren que lo programes usando recursividad?

Basicamente, es definir en c++ las cosas como en matemática: \( s(n)=s(n-1) n s(n-1); s(1)=1 \) (una función que se llame a si misma).


07 Marzo, 2008, 07:01 pm
Respuesta #2

*Rafa*

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 205
  • Karma: +0/-0
  • Sexo: Masculino
Mil perdones, quise decir que no me dejan usar recursividad (las funciones no pueden llamarse a sí mismas); debe ser mediante iteración.
Para ilustrar un poco el tema, decir que la sucesión dada, nos dice que disco mover, en el famoso juego de las torres de hannoi; pero esto es solo por simple curiosidad  ;)

Por cierto, para \( s(3) \) por ejemplo, no tengo porque saber el número \( 1213121 \) entero (en realidad me da igual); sino que podríamos considerar a \( s(3) \), como una sucesión en sí misma independiente (y finita).
\( s_3(1)=1; \textsf{ }s_3(2)=2; \textsf{ }s_3(3)=1;... \)

Lo menciono, porque así podría resultar más fácil de calcular.

Gracias y saludos.

07 Marzo, 2008, 07:56 pm
Respuesta #3

León

  • Lathi
  • Mensajes: 903
  • Karma: +0/-0
  • Sexo: Masculino
Hola entonces lo podés hacer iterando. Va en C oxidado no compilable.
Código: [Seleccionar]
include <math.h>
...
int suc(n) {
  int i, s=1;
  for(i=1;i<n,i++) {
   s=s*pow(10,(int(log10(s))+int(log10(i))+2))+(i+1)*pow(10,int(log10(s))+1)+s;
  }
  return (s);
}

Feito, pero la idea está (en realidad es mejor hacerlo con cadenas de carácteres, no con números).

Corregí: un "i"->"(i+1)" y un "i<=n"->"i<n"

07 Marzo, 2008, 08:46 pm
Respuesta #4

*Rafa*

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 205
  • Karma: +0/-0
  • Sexo: Masculino
Código: [Seleccionar]
#include <math.h>
#include <iostream>
using namespace std;
int main() {
  int i, s=1, n;
  cout<<"n"<<endl;
  cin>>n;
  for(i=1; i<=n;i++) {
   s=s*pow(10,(int(log10(s))+int(log10(i))+2))+i*pow(10,int(log10(s))+1)+s;
  }
 cout<<s;
}
Hola, pues parece que la cosa no funciona. Para n=1, imprime:111; para n=2, imprime: 1112111; para n=3, imprime: -2147... (pero esto sabría arreglarlo, simplemente sobrepasa el límite).
Me gustaría si no es molestia, saber con que idea pusiste expresamente la operacion
Código: [Seleccionar]
s=s*pow(10,(int(log10(s))+int(log10(i))+2))+i*pow(10,int(log10(s))+1)+s; no la entiendo.

Muchas gracias de nuevo.

07 Marzo, 2008, 09:56 pm
Respuesta #5

Ked

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 945
  • Karma: +0/-0
  • Sexo: Masculino
El problema está, en que no me dejan usar la recursividad, es decir, para saber \( s(4) \), antes podría calcular \( s(3) \), \( s(2) \) y despues \( s(1) \). Pero esto no me lo permiten, debe ser mediante iteración.

Es como si nos pidieran el n-ésimo término de la sucesión de Fibonacci, y no nos dejaran calcular los anteriores términos.
¿Estás seguro que no te dejan hacer una iteración simplemente de 1 a n, e ir concatenando? Ahi no utilizarías llamadas recursivas, por lo que el programa es completamente iterativo.

Ah, eso es lo que te decía León en su mensaje anterior.

Tu secuencia es esta http://www.research.att.com/~njas/sequences/A082215

Al parecer se llaman "Zimin words".

Saludos

07 Marzo, 2008, 10:22 pm
Respuesta #6

Ked

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 945
  • Karma: +0/-0
  • Sexo: Masculino
El siguiente programa iterativo está escrito en C++ - aprovecho que existe la clase de los strings, para no complicarse la vida con los char*

Código: [Seleccionar]
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    int n;
   
    cout << "Introducir n > 0: ";
    cin >> n;
   
    for (int i=1; i <= n; i++)
    {
        char n = '0'+i; // Si i>9 (o sea si n es de más de 1 dígito) esto no funciona
        s = s + n + s;
    }
   
    cout << s << endl;
}

Si quieres se puede modificar para convertir de entero a string y que funcione siempre, tu dirás.

Saludos

07 Marzo, 2008, 10:48 pm
Respuesta #7

León

  • Lathi
  • Mensajes: 903
  • Karma: +0/-0
  • Sexo: Masculino
Uh, me pasé un rato desempolvando mi c++. Hice el programita pero no podía compilarlo... después me di cuenta de que era porque estaba usando el compilador equivocado :P.

En el otro programa hay que correr los índices un poco para que funcione (no sirve poner s=0 porque se desgracia un logaritmo por ahí: eso me pasa por no probarlo antes... obviamente un programa nunca funciona de una -por lo menos a mi no me pasa).

Lo pongo, ya que lo hice. Es casi igual al de Ked, pero funciona para n cualquier int. Los cuatro programas son fundamentalmente iguales.

Código: [Seleccionar]
#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main() {
  int i,n;
  string s;
  stringstream aux;

  cout<<"n:"<<endl;
  cin>>n;

  for(i=1; i<=n; i++) {
    aux << i;
    s+=aux.str()+s;
    aux.str("");
  }

  cout<<s<<endl;
}


PD: Ah, la idea de la operación esa que me preguntabas es concatenar las expresiones decimales de números enteros usando potencias de diez. Por ejemplo si quieres concatenar los números enteros "234" y "3123", lo que haces es 3123*103+234=3123234. Es exactamente eso lo que hacía... (Fíjate que [log10(x)]+1 es la cantidad de decimales de x.)


08 Marzo, 2008, 10:47 pm
Respuesta #8

*Rafa*

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 205
  • Karma: +0/-0
  • Sexo: Masculino
No tuve tiempo para agraderoslo, pero ahora sí, "la cosa" ha salido perfecta  ;D. Muchas gracias a los dos.

Saludos.