domingo, 7 de julio de 2019

Fibonacci

Version iterativa
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;

int fibonacci( int n ) {
    if( n == 0 || n == 1 ) {
       return n;
    }
    
    //  prev2 -> prev1 -> fib (prev1 + prev2)
    int prev2 = 0;
    int prev1 = 1;
    int fib;
    for(int i = 2; i <= n; i++) {
        fib = prev1 + prev2;
        prev2 = prev1;
        prev1 = fib;
    }
    
    return fib;
}
 
int main() {
    for(int i = 0; i < 10; i++) {
        cout << "fib " << i << " = " << fibonacci(i) << endl;
    }

    return 0;
}

sábado, 6 de julio de 2019

Decimal a binario

Version recursiva
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
using namespace std;

string binario(int x) {
    string s = (x > 1) ? binario(x / 2) : "";
    s += to_string(x % 2);
    return s;
}

int main() {
    for(int i = 0; i < 256; i++) {
        cout << i << " " << binario(i) << endl;
    }
}

domingo, 2 de mayo de 2010

Strings 2

Olvidé mencionar previamente un caso usual de error.

Se trata de suponer que por haber pedido memoria para un string, en un arreglo de char, ya es posible trabajar con las funciones relacionadas con strings (strlen, strcpy, etc).

Un código de ejemplo:
  char *s;
  s = (char*) malloc( 100 + 1 ); 
// mas tipico: (char*) malloc(strlen(otrostring)+1);

// intento fallido 1
  printf( "Valor inicial: %s\n" );  // muestra basura

// intento fallido 2
  strcat( s, "1234" );  // ademas del 1234 se ve basura

// etc


Las funciones relacionadas con strings trabajan suponiendo que tienes un arreglo unidimensional de caracteres que terminan en 0. Siempre suponen eso. Trabajan asi.

Cuando se pide memoria, con malloc, ya se tiene un arreglo unidimensional de caracteres, pero aun te falta la segunda parte (que terminen en 0) para usar las funciones relacionadas con strings.

El printf que se muestra arriba generalmente muestra basura, que no es mas que el contenido actual de la memoria que se pidio. Se esta pidiendo que muestre un string (%s), pero aun no se tiene uno.

Luego se hace strcat, nuevamente usando una función de strings, pero de nuevo se es "castigado" por no haber tenido un string para trabajar.

La solucion? Convierta su memoria pedida en un string:
  char *s;
  s = (char*) malloc( 100 + 1 ); // o (char*) malloc(strlen(otrostring)+1);
  s[0] = '\0';  // ahora si hay un string

  printf( "Valor inicial: %s\n" );

  strcat( s, "1234" );

domingo, 11 de abril de 2010

if( &other != this )

Cuando se escribe el operator =, hay que protegerse contra la asignación de una variable consigo misma, por ejemplo:
a = a;
Esto cobra mas importancia si "a" es un objeto de una clase que tiene algun puntero al interior, porque a veces el operator= lo primero que hace es borrar el puntero guardado.

La fórmula, usualmente es una construcción de este estilo:

MiClase& operator=( MiClase& otro ) {
if( &otro != this ) {
...
}
return *this;
}


De este modo, el hacer
a = a;
hará nada, pues en ese caso, &other y this apuntaran a la misma direccion de memoria.

Strings

Definición
Los strings en C "no existen" como tipo, pero se toma una convención: Los strings son arreglos unidimensionales de caracteres que terminan en el caracter ASCII 0 ('\0').

Si se cumple con esta definición. se cuenta con una coleccion de funciones para trabajar con strings (strlen(), para calcular el largo, strcpy(), para copiar el contenido de un string a otro, etc. )

Caso especial: String literal
Los strings literales usan la comilla doble. El compilador transforma los string literales en arreglos unidimensionales con un 0 al final.

Definir una variable asi:
char *s = { 'h', 'o', 'l', 'a', '\0' };

es similar a haberlo hecho asi:
char *s = "hola";


Errores comunes:
- No dejar espacio suficiente para el caracter de fin.
char str[4];

strcpy( str, "hola" ); // <-- "hola" -> 5 caracteres, str -> espacio solo para 4

- Creer que un string ya tiene memoria por solo haber definido un puntero a char.

char *str;  // <-- no hay solicitud de memoria  strcpy( str, "problemas" );

pero, la definicion y la inicializacion inmediata sí solicita memoria
char *str = "no hay problemas";  // solicitud de memoria implicita

Punteros

Definición

Los punteros (o apuntadores) son variables que pueden guardar direcciones de memoria.

Dado esto, el lenguaje C ofrece varias alternativas para que un puntero adquiera un valor.

Al definir un puntero, éste ya tiene un valor. Si es una variable global, el valor es 0, si es una variable local (también llamadas automaticas), el valor no está definido y son la fuente de muchos problemas para quienes comienzan a programar en C o C++.


{
int *p; // que valor tiene p?
...
}


Maneras de asignar un puntero

- Asignar la dirección de memoria de otro objeto (usar el operador unario &)

{
int a;
int *p = &a;
...
}


- Asignar alguna dirección de memoria conocida (muy poco portable, peligroso, no recomendable)

{
int *p = 0x321;
...
}

- Solicitar memoria

{
int *p = (int *) malloc( sizeof(int) ); // a la C
int *q = new int; // a la C++
...
}

- Copiar la direccion de memoria que otro puntero guarda

{
int x;
int *p = &x; // direccion de x
int *q = p; // direccion de x
...
}