A partir del título de este post ( http://foro.elhacker.net/programacion_cc/determinante_matriz_de_orden_n-t352910.0.html )  me entró la curiosidad de resolverlo de manera dinámica. Y la manera que se me ocurría para un algoritmo sencillo pues es la regla de Laplace o el desarrollo por menores complementarios de manera recursiva:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#define N 4
 
/* DETERMINANTE DE UNA MATRIZ de orden N - por MAFH */
 
typedef int ** matriz;
 
void visualizar_matriz (matriz matrix, int m, int n) {
    int i,j;
    for (i=0; i<m; i++) {
        for(j=0; j<n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}
 
matriz generar_matriz (int m, int n) {
    int i;
    matriz temp;
    if ((temp = (matriz) malloc(m*sizeof(int*))) == NULL)
        return NULL;
    for (i=0; i<m; i++)
        if ((temp[i] = (int *)malloc(n*sizeof(int))) == NULL)
            return NULL;
    return temp;
}
 
matriz copiar_matriz (matriz matrix, int m, int n) {
    int i,j;
    matriz temp = (matriz) generar_matriz(m,n);
    if (temp != NULL) {
		for (i=0; i<m; i++)
			for (j=0; j<n; j++)
				temp[i][j] = matrix[i][j];
    }
    return temp;
}
 
void liberar_matriz (matriz matrix, int m) {
    int i;
    for (i=0; i<m; i++)
        free(matrix[i]);
    free(matrix);
}
 
void rellenar_matriz (matriz matrix, int m, int n) {
    int i,j;
    for (i=0; i<m; i++)
        for(j=0; j<n; j++) {
            printf("Valor de matrix[%d,%d] = ", i, j);
            scanf("%d", &(matrix[i][j]));
        }
}
 
matriz adjunto_matriz (matriz matrix, int fila, int columna, int n) {
    matriz adjunto = (matriz) generar_matriz(n-1,n-1);
    if (adjunto != NULL) {
		int i, j, k=0, l=0;
		for (i=0; i<n; i++)
			for (j=0; j<n; j++) {
				if ((i != fila) && (j != columna)) {
					adjunto[k][l] = matrix[i][j];
					if (++l == n-1) {
						l=0;
						k++;
					}
				}
			}
    }
    return adjunto;
}
 
int determinante (matriz matrix, int n) {
    if (n == 1) {
        return matrix[0][0];
    } else {
        int j;
        int res = 0;
        for (j=0; j<n; j++){
            matriz adjunto = (matriz) adjunto_matriz(matrix, 0, j, n);
            if (adjunto == NULL) exit(1);
            res += pow(-1, (j%2))*matrix[0][j]*determinante(adjunto, n-1);
            liberar_matriz(adjunto,n-1);
        }
        return res;
    }
}
 
 
int main (int argc, char ** argv) {
    matriz m = (matriz) generar_matriz(N,N);
    rellenar_matriz(m,N,N);
    visualizar_matriz(m,N,N);
    printf("|M| = %d\n", determinante(m,N));
    liberar_matriz(m,N);
    return 0;
}
 

Aunque tenemos la constante N para el orden de la matriz, podemos utilizar una variable para que el usuario introduzca el orden, evidentemente.

Una ejecución del código con Valgrind:

Conclusión del desarrollo por menores:

Orden 1:
1 de orden 1
no llamadas recursivas

Orden 2:
2 de orden 1
2 = 2 llamadas recursivas

Orden 3:
3 de orden 2
2 de orden 1
3*2 = 6 llamadas recursivas

Orden 4:
4 de orden 3
3 de orden 2
2 de orden 1
4*3*2 = 24 llamadas recursivas

Orden 5:
5 de orden 4
4 de orden 3
3 de orden 2
2 de orden 1
5*4*3*2 = 120 llamadas recursivas

Orden n:
n de orden n-1
n-1 de orden n-2
.... de orden ...
3 de orden 2
2 de orden 1
n*(n-1)*(n-2)*(n-3)*...*(n-n+1) = (productorio desde i=n hasta 2 de i) = n! llamadas recursivas

Como conclusión a los resultados expuestos obtenemos que el número de llamadas recursivas que se realizan viene dado por:

Nº llamadas recursivas = Permutaciones(Orden) = Orden!

Como bien había dicho ghastlyX en respuesta al tema arriba enlazado.

---

Edit:

He tratado de lanzar el código con un determinante de orden 13 y evidentemente "no terminaba"...
Nº llamadas recursivas = P(13) = 13! = 6227020800

T(n) es exponencial y encima con los alojos y desalojos de memoria... Para morirse xD

Por otra parte, convendría generar los adjuntos con la misma matriz que se usa o de alguna manera sin generar otra matriz de tamaño n-1 para cada adjunto ._.

Bueno, he codificado un cliente-servidor UDP pero mi servidor no logra recibir el paquete datagrama enviado por el cliente ._.

¿Alguna ayudita?

ClienteUDP,java

package proyecto.socketudp;
import java.net.*;
/** Ejemplo que implementa un cliente de eco usando UDP. */
public class ClienteUDP {
	public static void main(String argv[]) {
		if (argv.length != 3) {
		System.err.println("Formato: ClienteUDP <maquina> <puerto> <mensaje>");
		System.exit(-1);
		}
		DatagramSocket sDatagram = null;
		try {
			// Creamos el socket no orientado a conexión
			// (en cualquier puerto libre)
			sDatagram = new DatagramSocket();
			// Establecemos un timeout de 30 segs
			sDatagram.setSoTimeout(30000);
			// Obtenemos la dirección IP del servidor
			// (recibida en el primer argumento por linea de comandos)
			InetAddress dirServidor = InetAddress.getByName(argv[0]);
			// Obtenemos el puerto del servidor
			// (recibido en el segundo argumento por linea de comandos)
			int puertoServidor = Integer.parseInt(argv[1]);
			// Obtenemos el mensaje
			// (tercer argumento de la linea de comandos)
			String mensaje = argv[2];
 
			byte[] envInfo = new byte[1024];
      		envInfo = mensaje.getBytes();
			// Preparamos el datagrama que vamos a enviar y lo enviamos
			DatagramPacket envPaquete = new DatagramPacket(
				envInfo, envInfo.length,
				dirServidor, puertoServidor
			);
			// Enviamos el datagrama
			sDatagram.send(envPaquete);
			System.out.println(
				"CLIENTE: Enviando "
				+ new String(envPaquete.getData()) + " a "
				+ envPaquete.getAddress().toString() + ":"
				+ envPaquete.getPort()
			);
 
			// Preparamos el datagrama de recepción
			byte[] recInfo = new byte[1024];
			DatagramPacket recPaquete = new DatagramPacket(recInfo, recInfo.length);
			// Recibimos el mensaje
			sDatagram.receive(recPaquete);
			System.out.println(
				"CLIENTE: Recibido "
				+ new String(recPaquete.getData(), 0, recPaquete.getLength())
				+ " de " + recPaquete.getAddress().toString() + ":"
				+ recPaquete.getPort()
			);
		} catch (SocketTimeoutException e) {
			System.err.println("30 segs sin recibir nada");
		} catch (Exception e) {
			System.err.println("Error: " + e.getMessage());
		} finally {
			// Cerramos el socket para liberar la conexión
			sDatagram.close();
		}
	}
}

ServidorUDP.java

package proyecto.socketudp;
 
import java.net.*;
/** Ejemplo que implementa un servidor de eco usando UDP. */
public class ServidorUDP {
    public static void main(String argv[]) throws SocketException {
        if (argv.length != 1) {
            System.err.println("Formato: ServidorUDP <puerto>");
            System.exit(-1);
        }
        try {
            // Creamos el socket datagrama
            DatagramSocket sDatagram = new DatagramSocket(Integer.parseInt(arv[0]));
            // Establecemos un timeout de 30 segs
            sDatagram.setSoTimeout(30000);
            byte array[] = new byte[1024];
            DatagramPacket dgramRec, dgramEnv = null;
            while (true) {
                // Preparamos un datagrama para recepción
                dgramRec = new DatagramPacket(array, array.length);
 
                // Recibimos el mensaje
                sDatagram.receive(dgramRec);
 
                // Recabamos informacion
                String mensaje = new String(dgramRec.getData());
                InetAddress dirCliente = dgramRec.getAddress();
                int puertoCliente = dgramRec.getPort();
 
                System.out.println(
                    "SERVIDOR: Recibido "
                    + new String(dgramRec.getData(), 0, dgramRec.getLength())
                    + " de " + dirCliente.toString() + ":"
                    + puertoCliente
                );
 
                // Preparamos el datagrama que vamos a enviar
                dgramEnv = new DatagramPacket(
                    mensaje.getBytes(), mensaje.getBytes().length,
                    dirCliente, puertoCliente
                );
 
                // Enviamos el mensaje
                sDatagram.send(dgramEnv);
                System.out.println(
                    "SERVIDOR: Enviando"
                    + new String(dgramEnv.getData(), 0, dgramEnv.getLength())
                    + " de " + dgramEnv.getAddress().toString() + ":"
                    + dgramEnv.getPort()
                );
            }
        } catch (SocketTimeoutException e) {
            System.err.println("30 segs sin recibir nada");
        } catch (Exception e) {
            System.err.println("Error: " + e.getMessage());
        }
    }
}

He estado entrando últimamente al foro y, concretamente, a este subforo y veo muchísimos códigos que están fuera de la etiqueda [ code ] y lo más irónico es que ni siquiera están identandos (con tabuladores).

Yo, claramente me niego a leer códigos de esas características. Os pido a todos aquellos que no sigáis esa norma o que no estéis acostumbrados a hacerlo, que la tratéis de cumplir. No tan solo porque debéis, sino porque de esa manera atraeréis a más usuarios para que os ayuden.

Es un quid pro cuo, si pides ayuda, trata de facilitar el trabajo

Ahora podéis criticarme, banearme, lapidarme... lo que deseéis. Pero solo deseaba dejar constancia de ese hecho.

Gracias por su atención.

Este pequeñito aporte va dedicado especialmente a aquellos que comienzan recién en la programación

Prerrequisitos (?)

→ Vectores
→ Saber qué es y cómo se lleva a cabo la búsqueda binaria

Adjunto el código del algoritmo no recursivo (Por: Rodrigo Burgos Domínguez.):
http://algorithmmx.blogspot.com.es/2011/11/algoritmo-de-busqueda-binaria.html

int busqueda_binaria(vector <int> list, int val){
   int der = list.size() - 1, izq = 0, m;
   while(izq <= der){
      m = (izq + der) / 2;
      if(m == list[val]) return m; //la posicion del valor
      if(m > list[val]) der = m – 1;
      else izq = m + 1;
   }
   return -1; // no se encontro el dato :P
}

Teniendo en cuenta que ya sabemos la lógica que sigue este algoritmo y su implementación arriba expuesta, vamos a pensar en hacerlo de forma recursiva, es decir, que la misma función vaya reduciendo el tamaño (N) del problema a un caso base, de tal manera, al conocer la solución del caso base, va a poder dar solución a cualquier problema de tamaño N.

Entonces el código sería el siguiente:

(utilizo int casting para no usar la librería math.h)

int BinarySearch(int x, int v[], int tam) {
 
    int RecursiveBinarySearch(int x, int v[], int i, int m, int d) {
        if (i>d) return -1;
        else if ( x == v[m] ) return m;
        else if ( x < v[m] ) return RecursiveBinarySearch(x, v, i, (int)((i+m-1)/2), (m-1));
        else return RecursiveBinarySearch(x, v, (m+1), (int)((d+m+1)/2), d);
    }
 
    int i = 0;
    int m = tam/2;
    int d = tam;
 
    return RecursiveBinarySearch(x, v, i, m, d);
 
}

Explicación general:

La premisa que tenemos es que nosotros tenemos que buscar un elemento x en un vector v de tamaño N que está previamente ordenado. Teniendo eso en cuenta podemos afirmar que cualquier subvector w de v de tamaño [0..N] también está ordenado.

Pues teniendo eso en cuenta vamos reduciendo el tamaño del problema (N) a la mitad en cada llamada recursiva. ¿Por qué? Porque si x no es el elemento medio del vector v de tamaño N, entonces verificamos si es menor o mayor que él. Si es menor, buscamos en el subvector de tamaño N/2 izquierdo, sino en el derecho.

Como véis, en este caso, el algoritmo se pasa de forma cíclica a forma recursiva casi sin pensar. ¿Por qué? Estamos ante una Tail Recursive Function (la autollamada es lo último que se hace) y podemos pensar en definitiva que estamos ejecutando un ciclo simplemente.

Podría aquí estar escribiendo horas y horas sobre algoritmos de búsqueda y ordenación pero no es plan xD

Decir simplemente que hay tener en cuenta que el vector en el que vayamos a buscar un elemento, debe estar previamente ordenado.

En este momento os preguntaréis: ¿Qué me conviene más, buscar directamente en un vector con la búsqueda lineal o es mejor ordenarlo previamente (quicksort) y luego aplicar búsqueda binaria? Bueno eso ya son temas de complejidad algorítmica y haciendo un pequeño estudio se puede sacar conclusiones.

Decir también que hay estructuras de datos eficientes para la búsqueda como lo son por ejemplo las Tablas Hash o los Árboles Binarios de Búsqueda, ABB (variante AVL), por ejemplo.

Bueno con esto y un bizcocho me despido.

¡Saludos!

Todos los comentarios serán bien recibidos

Bueno, estoy creando una shell básica en C y trato de crear el comando deltree. Lo que quiero hacer es poder diferenciar entre archivos y directorios para que cuando sea un directorio, hacer una llamada recursiva a la propia función. La idea, como todos sabréis, es yo le paso una ruta, y la función me borra todo el árbol de archivos y directorios cuya raíz es la ruta que le paso. (En el código no verifiqué todavía el argc, pero ahí no está el problema, sino en la struct stat que creo que no se actualiza correctamente.

El código:

// Includes de la shell
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <dirent.h>
#include <sys/dir.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <errno.h>
#define MAXENTRADA 2048
 
void deltree (char ** argv, int argc) {
    struct dirent *ent;
    struct stat fStat;
    DIR *dir = opendir(argv[1]);
    if(dir == NULL) {
        perror("Hubo un error");
    } else {
        while ( (ent=readdir(dir)) != NULL ) {
 
            if(strcmp(".",ent->d_name) == 0 ||
               strcmp("..",ent->d_name) == 0) continue;
 
            stat(ent->d_name, &fStat);
 
            if ( S_ISDIR(fStat.st_mode) )
                puts(ent->d_name);
 
        }
 
        closedir(dir);
        free(ent);
        ent = NULL;
 
    }
}
 

el stat(ent->d_name, &fStat); devuelve -1 pero cuando hago un stat("dir/archivo_válido", &fStat); funciona correctamente. Es decir, que cuando le paso un "string" a stat, funciona correctamente pero cuando le paso el d_name del struct dirent, su salida es -1...

¿Alguna ayudita para poder solucionar el código?

¡Gracias de antemano!

Lo primero que debo decir es que, como ya sabéis, la estructura ARRAY no existe primitivamente en Batch, pero es simulado su tipo de dato (array unidimensional) a través de un conjunto de scripts que nos va a permitir manejar dicha estructura.

Si no conoces la estructura array visita:

Array data type: http://en.wikipedia.org/wiki/Array_data_type
Array data structure: http://en.wikipedia.org/wiki/Array_data_structure

Como dije antes, trabajaremos con arrays unidimensionales.

Para generar dicha estructura usaremos adicionalmente una función para crear strings.

create_string.bat

A continuación, mostraré los scripts que nos permiten manejar la estructura. Los códigos se pueden mejorar (sort_array.bat optimizarlo a quicksort) y todavía se deben hacer algunos cambios a la estructura y quizás realizar una especificación para que no haya problemas a la hora de utilizarla. Finalmente veremos un ejemplo de como se comporta la estructura.

create_array.bat

show_array.bat

insert_array.bat

delete_array.bat

modify_array.bat

sort_array.bat

l_search_array.bat

b_search_array.bat

Como se puede apreciar, en ningún script se habilita la expansión de variables, por lo que deberemos habilitarla en nuestros scripts.

Aquí un ejemplo de cómo funciona la estructura array hasta el momento.

script.bat



Y con esto me despido... Comentarios, críticas, insultos, y demás locuras que se les ocurran serán excelentemente bienvenidas...

Recuerden que todavía está por perfeccionar para el uso "común" de todos nosotros

A mí, de momento, ya me ayudó a implementar el tipo SET o CONJUNTO


¡Saludos!

Un ejemplo de Unit - TAD Números Racionales - con implementación dinámica de punteros.

////////////////////////////////////////////////////////////
/////////////Nombre de Unidad: TAD Racionales///////////////
///////////////////Autor: Batchiano/////////////////////////
//////////////////////////////////////////////////////////
unit Racional;
 
interface
 
type
	tPRacional = ^tRacional; // Tipo puntero a racional
	tRacional = record // Tipo racional con un registro
		numerador,denominador:integer;
	end;
 
function CrearRacional(a,b:integer):tPRacional; { Crea un número racional }
function MostrarRacional(r:tPRacional):string; { Muestra un número racional }
function Numerador(r:tPRacional):integer; { Obtiene el numerador de un número racional }
function Denominador(r:tPRacional):integer; { Obtiene el denominador de un número racional }
function SumarRacional(r,s:tPRacional):tPRacional; { Suma dos números racionales }
function RestarRacional(r,s:tPRacional):tPRacional; { Resta el segundo número racional al primero }
function MultiplicarRacional(r,s:tPRacional):tPRacional; { Multiplica dos números racionales }
function DividirRacional(r,s:tPRacional):tPRacional; { Divide el primer número racional pasado por el segundo }
function SimplificarRacional(var r:tPRacional):tPRacional; { Simplifica un número racional }
function mcd(a,b:integer):integer; { Obtiene el m.c.d de dos enteros (en términos positivos) }
 
 
implementation
 
function min(a,b:integer):integer;
begin
	min:=a;
	if b<a then
		min:=b;
end;
 
function CrearRacional(a,b:integer):tPRacional;
begin
	new(CrearRacional);
	CrearRacional^.numerador := a;
	CrearRacional^.denominador := b;
end;
 
function MostrarRacional(r:tPRacional):string;
var num,den:string;
begin
	if ((numerador(r)>0) and (denominador(r)>0)) or ((numerador(r)<0) and (denominador(r)<0)) then begin
		str(abs(numerador(r)),num);
		str(abs(denominador(r)),den);
		MostrarRacional := num + '/' + den;
	end
	else begin
		str(abs(numerador(r)),num);
		str(abs(denominador(r)),den);
		MostrarRacional := '-' + num + '/' + den;
	end;
 
end;
 
function Numerador(r:tPRacional):integer;
begin
	numerador := r^.numerador;
end;
 
function Denominador(r:tPRacional):integer;
begin
	denominador := r^.denominador;
end;
 
function SimplificarRacional(var r:tPRacional):tPRacional;
var a,b:integer;
begin
	a:=abs(numerador(r));
	b:=abs(denominador(r));
	r^.numerador := numerador(r) div mcd(a,b);
	r^.denominador := denominador(r) div mcd(a,b);
	SimplificarRacional := r;
end;
 
function SumarRacional(r,s:tPRacional):tPRacional;
begin
	new(SumarRacional);
	SumarRacional^.denominador := denominador(r) * denominador(s);
	SumarRacional^.numerador := denominador(SumarRacional) div denominador(r) * numerador(r) + denominador(SumarRacional) div denominador(s) * numerador(s);
	SumarRacional := SimplificarRacional(SumarRacional);
end;
 
function RestarRacional(r,s:tPRacional):tPRacional;
begin
	new(RestarRacional);
	RestarRacional^.denominador := denominador(r) * denominador(s);
	RestarRacional^.numerador := denominador(RestarRacional) div denominador(r) * numerador(r) - denominador(RestarRacional) div denominador(s) * numerador(s);
	RestarRacional := SimplificarRacional(RestarRacional);
end;
 
function MultiplicarRacional(r,s:tPRacional):tPRacional;
begin
	new(MultiplicarRacional);
	MultiplicarRacional^.numerador := numerador(r) * numerador(s);
	MultiplicarRacional^.denominador := denominador(r) * denominador(s);
	MultiplicarRacional := SimplificarRacional(MultiplicarRacional);
end;
 
function DividirRacional(r,s:tPRacional):tPRacional;
begin
	new(DividirRacional);
	DividirRacional^.numerador := numerador(r) * denominador(s);
	DividirRacional^.denominador := denominador(r) * numerador(s);
	DividirRacional := SimplificarRacional(DividirRacional);
end;
 
function mcd(a,b:integer):integer;
var t:integer;
begin
	a:=abs(a);
	b:=abs(b);
	t:=min(a,b);
	while (t>1) and (((b mod t) <> 0) or ((a mod t) <> 0)) do begin
		t:=t-1;
	end;
	mcd := t;
end;
 
begin
 
end.
 

Otro más de comandos... (y último )

Reto iniciado por Batchiano

Reto Nº 12

Nombre:          Get IP from DNS
Dificultad:       4/10
Objetivo:         Crear un comando que, al enviar un DNS, devuelva la IP adjunta a dicho DNS
Indicaciones:  Es obligatorio utilizar FOR.
Pista:               PING.
Ejemplo:



Solución: MP

Aquí pueden comentar todo lo que quieran, sus dudas, avances o soluciones acerca del siguiente reto:

Reto iniciado por Batchiano

Reto Nº 11

Nombre:          Hex2Dec Batch Command
Dificultad:        3/10
Objetivo:         Crear un comando que convierta un número en hexadecimal a decimal.
Pista: El código es muy corto. Se aconseja pipear.
Ejemplo:



Solución:

@echo off
if "%1"=="" (goto syn) else (
	echo | set /a %1
	exit /b
)
 
:syn
echo Error de sintaxis. %0 [NUMERO EN HEXADECIMAL]

Pues he implementado una cuenta atrás en Batch... segurísimamente ya esté hecho... pero me apetecía pensar como hacerlo... opiniones... mejoras... aplicaciones para la cuenta atrás... ideas... críticas constructivas... todo bienvenido

Operadores lógicos...

::Cuenta atrás
::Batchiano
@echo off
setlocal enabledelayedexpansion
:menu
set /p h="Horas: "
set /p m="Minutos: "
set /p s="Segundos: "
for %%z in (h,m,s) do if not defined %%z (
	call :formato
)
if %h% GEQ 0 (
	if %m% GEQ 0 (
		if %m% LEQ 59 (
			if %s% GEQ 0 (
				if %s% LEQ 59 (
					call :contador
				) else (
					call :formato
				)
			) else (
				call :fomato
			)
		) else (
			call :formato
		)
	) else (
		call :formato
	)
) else (
	call :formato
)
goto :eof
 
:contador
cls
if %h% GEQ 0 (
	if %m% GEQ 0 (
		if %s% GEQ 0 (
			for /l %%a in (!h!,-1,0) do (
				for /l %%b in (!m!,-1,0) do (
					for /l %%c in (!s!,-1,0) do (
						echo Contador: %%a:%%b:%%c
						ping localhost -n 2 > nul
						cls
					)
					set s=59
				)
				set m=59
			)
		)
	)
)
goto :eof
 
:formato
echo Formato incorrecto. Vuelva a intentarlo
pause>nul & cls & call :menu