#!/bin/bash
#################################################################
# #
# # -*- ENCODING: UTF-8 -*- #
# Este script es software libre. Puede redistribuirlo y/o #
# modificar-lo bajo los términos de la Licencia Pública General #
# de GNU según es publicada por la Free Software Foundation, #
# bien de la versión 3 de dicha Licencia o bien (según su #
# elección) de cualquier versión posterior. #
# #
# Si usted hace alguna modificación en esta aplicación, #
# deberá siempre mencionar al autor original de la misma. #
# #
# Autor: Script creado por vk496 #
# #
# Un saludo #
# #
#################################################################
# Lo que hace este script es escalonar una matriz. No está optimizado para que la escalone ni mas rapido ni mas
# eficiente, pero hace su trabajo (o eso me ha parecido después del debug.) A lo largo del programa habrá muchisimos
# comentario para intentar explicar que hace cada cosa y como lo consigue, ya que el principal problema de esto es
# que Bash no permite la declaración de arrays multidimensionales y es un poco lio. Vamos al grano
if [ $# = 0 ]; then #Si no hay ningun parametro de entrada, muestra la ayuda y se sale
echo "matkix v0.1 by vk496"
echo "Uso: matkix [FILAS] [COLUMNAS] -R"
echo
echo " [FILAS] Numero de filas"
echo " [COLUMNAS] Numero de columnas"
echo " -R|-r Generar una matriz aleatoriamente"
exit
fi
# Existen tres funciones principales en el programa que toman datos de entrada para devolver una salida
#
# es_un_numero nos devuelve un {1,0} dependiendo de la entrada que le demos
function es_un_numero {
posible_numero=($1) #Cogemos el primer parametro y lo declaramos en forma de array
# con la variable $posible_numero
var=$(echo $posible_numero | sed 's/-//g' | sed 's/ //g') #Hacemos uso de 'sed' para eliminar cualquier
# posible signo de numero negativo o espacio, y lo declaramos como $var
if [ "$var" -eq "$var" ] 2>/dev/null; then #Hacemos un poco de "trampa" en Bash. Aprovechamos los operadores
# aritmeticos para igualar un numero a si mismos. Si es numero, siempre será igual a si mismo. Por el
# contrario, si no lo es, nos devolverá un error en stderr, el cual ocultaremos con una redirección al
# "vacio" (/dev/null)
echo 1 #Es un numeros, devolvemos un 1
else
echo 0 #No es un numero, devolvemos un 0
fi
}
# Es una funcion que siempre devolverá un resultado. Luego nos será util
# Por otra parte, esta nos devolverá la cantidad de ceros que hay en una fila si los contamos de izquierda a derecha
function contador0 {
declare -a ceros=($@) #Declaramos un array que tendrá como contenido todos los parametros que recibe contador0.
# Esto se debe a que cada uno de los elementos de la matriz lo interpreta como parametros, por eso no
# podemos coger solo el primero, tenemos que coger todos los de la fila. Cada elemento de la columna
# se identifica como un elemento distinto en el array
total=0 #Consideramos que nuestra fila desde el principio no tiene nigún cero a la izquierda
for x in $(seq 0 $COLUMNAS); do #Un for para usar la x como identificador de cada elemento en el array. Como
# sabemos seguro la cantidad de columnas que tiene nuestra fila, nos basta con una secuencia
if [ "${ceros[$x]}" = 0 ]; then #Si el elemento x de la array $ceros equivale a 0, significa que hemos
# encontrado el primero cero. Se lo sumamos a $total
let total=$total+1
else
break #De lo contrario, nos salimos de la iteracion
fi
done
# Analizamos nuestra variable $total. Si es mayor que cero, devolvemos como salida de contador0 la cantidad de 0
if [ $total -gt 0 ]; then
echo $total
else
echo "0" #Si no lo es, devolvemos un 0
fi
}
#Algoritmo para calcular el mcd de dos numeros. Se usará posteriormente en otra funcion
function mcd {
u=$1 #Primer numero como parametro
v=$2 #Segundo numero como parametro
#Si el segundo parametro es vacio, tomará el valor del primero. Es decir, un mcd con dos numeros iguales
if [ -z $v ]; then
v=$u
fi
if [ $v = 0 ]; then #Tenemos que tener en cuenta los 0, y evitarlos. De esta forma, solo manejamos los que
# no sean 0
v=$u
fi
if [ $u = 0 ]; then #Lo mismo que la condicion de arriba pero para el otro parametro
u=$v
fi
while [ ! $u = $v ]; do #Mientras no sean iguales, repetir la accion hasta que lo sean
if [ $u -lt $v ]; then #Si $u es menor que $v, restamos a $v el valor de $u
let v=$v-$u
elif [ $v -lt $u ]; then #Viceversa
let u=$u-$v
fi
done
echo $u #Es indiferente que valor devuelvolver ($u o $v). En cualquier caso, siempre será un valor distinto de
# 0 mientras que ambos parametros no sean 0
}
#Dada una fila, esta funcion devolverá la fila simplificada. Muy util para evitar numeros gigantescos en los resultados
function simplificar {
valores=$@ #Guardamos en $valores todos los elementos de la fila
declare -a entrada=($valores) #Asignamos esos valores en un array.
ceros=0 #Iniciamos variable del contador de ceros en la fila
total=0 #Contamos todos los elementos de la fila
for x in "${entrada[@]}"; do #Para cada elemento del array...
if echo $x | grep -q "-"; then #Comprobamos si es negativo o no
entrada[total]=$(echo ${entrada[$total]}|sed 's/-//g') #En caso de serlo, eliminamos el signo
# por ahora
negativos="$negativos,$total" #Almacenos la posicion del array al que corresponde ese numero
fi
if [ $x = 1 ]; then #Si tiene un 1, sabemos que no se puede simplificar. Devolvemos la fila tal como
# está en en el parametro de entrada y nos salimos de la funcion
echo $valores
exit
elif [ $x = 0 ]; then # en caso de ser un 0, añadimos una unidad al contador de ceros
let ceros=$ceros+1
fi
let total=$total+1 #Contamos los elemento totales
done
# Si $total es igual a $negativos, significa que toda la fila son ceros. No hay nada que hacer, nos salimos...
if [ $total = $ceros ]; then
echo $valores
exit
fi
# Tratamos cada elemento de la fila para encontrar un divisor comun
for valor in "${entrada[@]}"; do
# Conforme avancemos, vamos haciendo mcd del elemento actual con el resultado de su antecesor
#
comun=$(mcd $valor $comun) #La propiedad de mcd permite hacerlo de esta forma mediante iteracion sin
# tener que hacer una funcion para n elementos. Cuanto mas facil, mejor :)
done
# En el peor de los casos, no hay ningun numero comun a todos los de la fila. En ese caso, $comun vale 1
if [ $comun = 1 ]; then #Si $comun es 1, no tiene sentido seguir. Nos salimos...
echo $valores
exit
fi
y=0 #Necesitamos un contador para definir cada uno de los elementos de la array segun la posicion en la misma
for valor in "${entrada[@]}"; do
entrada[y]=$(echo "$valor/$comun"|bc) #Dividimos cada uno de los elementos por su numero comun a
# todos ellos
let y=$y+1
done
# Devolvemos los signos a los numeros que lo tuviesen. Hacemos iteracion para cada uno de los elementos de
# la lista
for posicion in $(echo $negativos | sed 's/,/ /g'); do
entrada[posicion]=$(echo "-${entrada[$posicion]}") #Reasignamos el elemento del array segun
# corresponde a la lista de los negativos. Recordemos que $negativos no almacena el valor, sino
# la posicion de dichos elementos
done
echo "${entrada[@]}" #Si hemos llegado hasta este punto
}
# Esta es la funcion central de este programa. Ella es la que se encarga de escalonar las matrices. Como parametros
# de entrada tenemos dos matrices. Mediante calculos, nos devolverá otra matriz, que será la reducida en base a las
# dos de entrada
function reducir {
total=$@ #La variabe total, al igual que en "es_un_numero{}", toma todos los parametros (las dos filas)
numero=$(echo $total | awk -F' ' '{print NF}') # Al estar las dos filas juntas tenemos que separarlas.
# Para ello, sacamos el numero total de elementos que hay (los delimitadores son espacios en una array)
# ----------------------------------------------
# | Usamos bc para operaciones basicas |
# ----------------------------------------------
# |
# |
# v
f1=$(echo $total | cut -d" " -f-$(echo $numero/2 | bc)) #Como sabemos el numero total de elementos, y SIEMPRE
# va a ser par, cogemos los primeros n/2 elementos, que corresponden a la primera fila. Para ellos,
# usamos cut y como delimitador el espacio, cogiendo desde el elemto 1 hasta el n
f2=$(echo $total | cut -d" " -f$(echo $numero/2+1 | bc )-$numero) #Exactamente lo mismo pero para la segnda
# fila. Sin embargos, cogemos a partir del elemento posterior a n (n+1) hasta $numero (ultimo elemento)
declare -a trozo0=($f1) #Tenemos a $f1 como variable. La declaramos como matriz en $trozo0
declare -a trozo1=($f2) #Lo mismo para $f2
x=${trozo0[$fila]} #El pivote de la fila que cogeremos para operar cumple una relacion con el numero de la
# fila en el que nos encontramos. Por ejemplo: Si cogemos la tercera fila, sabemos que el que hará de
# pivote será el tercer de dicha fila. Por tanto, cogemos exclusivamnete ese elemento
y=${trozo1[$fila]} # El mismo caso para la fila que será operada.
if [ $y = 0 ]; then # Si en el elemento de la fila que será operada tenemos un 0 (el elemento que está debajo
# del pivote), devolvemos la fila operada tal cual y nos salimos
echo $f2
exit
fi
IFS=" "
for ((i=0;i<=$COLUMNAS;i++)); do #Para cada uno de los elementos de la fila
F1=$(echo $y*${trozo0[$i]}|bc) #Multiplicamos el elemento de abajo por el pivote de arriba
F2=$(echo $x*${trozo1[$i]}|bc) #Multiplicamos el pivote por el elemento de abajo
OPERADA=$(echo "$OPERADA $(echo "$F1 - $F2"|bc)") #Dejamos la resta de ambos en la variable OPERADA. Es
# importante mencionar que esta variable es creciente, y que aunque en la primera iteracion
# no tenga ningun valor, se representa como un espacio vacio. Esto nos permite añadir elementos
# a la fila de forma consecutiva hasta concluir con la fila operada por las dos filas de entrada
# (fila y fila_posterior)
done
echo $OPERADA #Devolvemos la fila operada de la funcion
unset OPERADA #Debido a que es incrementativa, borramos su contenido para su posible posterior uso.
}
#Obligamos a definir un numero concreto de filas. Si no está como parámetro, nos salimos con error
if [ -z $1 ]; then
echo No hay filas
exit 1
else
FILAS=$1 #De lo contrario, definimos $FILAS y continuamos
fi
# Restamos una unidad a la variabe filas. Esto se debe a que el primer elemento de un array se identifica con
# un 0, mientras que los "humanos" empezamos por el 1
FILAS=$(echo $FILAS-1 |bc)
# Exactamente lo mismo que con las filas...
if [ -z $2 ]; then
echo No hay columnas
exit 1
else
COLUMNAS=$2
fi
# Mas de lo mismo....
COLUMNAS=$(echo $COLUMNAS-1 |bc)
if $(echo $@ | grep -qi "\-r"); then #Si tenemos el parámetro "-r", generamos aleatoriamente numeros positivos 0-9
for fila in $(seq 0 $FILAS); do #Para cada una de las filas
for columna in $(seq 0 $COLUMNAS); do #Para cada columna de cada fila
subfila[columna]="$(shuf -i 0-9 -n 1)" #Creamos una array para la fila con numeros aleatorios
done
matriz[fila]=${subfila[@]} #Cuando acabamos con una fila, todos los elementos de la array "subfila"
# pasan a ser solo un elemento de la array "matriz"
done
echo
else #Si no tenemos el parametro "-r", nosotros mismos introducimos la matriz
IFS="\t" #Hacemos que el delimitador de la iteración sea un salto de linea en vez del espacio. Es importante
# hacer esto por que no sabemos cual es la longitud de la matriz hasta que el usuario no pulse
# ENTER para escribir la siguiente fila
z=0
while true; do #Entramos en el loop para leer las filas
while true; do #Entramos en otro loop, pero esta vez para verificar lo que introduce el usuario
echo -n "F$(echo $z+1 |bc): " #Formalidades... Simplemente para saber cual es la fila que
# estamos escribiendo
read -a linea #Leemos lo que introduce el usuario
# Hacemos uso de awk para contar los espacios (empieza a contar a partir del 1, por lo que
# nos devuelve la cantidad de elementos). Obligamos a que el numero total de elementos
# equivalga a la cantidad de columnas predefinidas por el usuario
if [ ! $(echo $linea | awk -F' ' '{ print NF }') = $(echo $COLUMNAS+1|bc) ]; then
echo No coinciden las columnas
echo
continue #Como no coincide, regresamos al verificador para que haga la fila otra vez
fi
# Hacemos uso de la funcion es_un_numero() para saber cuando tenemos que salir del verificador
if [ $(es_un_numero $linea) = 1 ]; then #Si es un numero, salimos del verificador
break
else
echo No es un numero
echo
fi
done
subfila=($linea) #Exactamente lo mismo que con el parámetro "-r". Solo que esta vez usamos la variabe
# que ha escrito el usuario y no una matriz
matriz[z]=${subfila[@]} #Mas de lo mismo para crear la matriz
#
if [ $z = $FILAS ]; then #Cuando se han introducido todas las fila que ha definido el usuario, podemos
# salir del loop, por lo que habremos terminado la creación de la matriz
break
fi
let z=$z+1
done
unset IFS #En adelante, no nos interesa tener como delimitador de la iteraciones un salto de linea, por lo que
# borramos esa variabe
clear #Borramos todo lo anterior de la pantalla
fi
echo
# Imprimimos en pantalla la matriz que tenemos actualmente mediante una iteracion
for fila in $(seq 0 $FILAS); do
echo "${matriz[fila]}"
backup[fila]="${matriz[fila]}" #creamos una copia de la matriz sin escalonar
done
echo
echo -n "SAGE_Original=matrix(QQ,["
for num in $(seq 0 $FILAS); do
echo -n "[$(echo ${backup[$num]}| tr " " , )]"
if [ ! $num = $FILAS ]; then #No ponemos coma cuando estamos en la ultima fila
echo -n ","
fi
done
echo "]); SAGE_Original.echelon_form()"
echo
echo ------------------
echo
matriz[0]=$(simplificar ${matriz[0]}) #Tratamos al primer elemento, ya que posteriormente no se toca a lo largo de la
# iteracion
for fila in $(seq 0 $FILAS); do #Para cada una de las filas...
matriz[fila]=$(simplificar ${matriz[$fila]})
# A continuacion, hacemos la segunda iteracion que nos permitirá "recorrer" la matriz de forma que podamos
# operar con ella. Como tenemos que escalonar las filas de la matriz, sabemos que jugamos con la variabe filas,
# por lo que $COLUMNAS pasa a un segundo plano. De antemano nos encontramos en una fila concreta ($fila), por
# lo que nuestro objetivo es recorrer todas las demas filas "por debajo" de esta. Es por ello que el recorrido
# se realiza desde la fila posterior ($fila+1) hasta la última fila declarada por el usuario
for fila_posterior in $(seq $(echo $fila+1 | bc) $FILAS); do
if [ "$fila" -gt "$COLUMNAS" ]; then #Cuando la fila actual supera la COLUMNAS TOTALES de la matriz,
# nos salimos de esta iteracion para evitar errores. Esto pasa cuando hay mas filas que columnas
break
fi
matriz[fila_posterior]=$(simplificar ${matriz[$fila_posterior]}) #Simplificamos la matriz posterior
# que será operada con la actual para escalonar
# Si nos encontramos en el caso en el que la fila posterior está escalonada respecto a la actual
# (comparando sus cantidades de ceros a partir de la izquierda), simplemente tenemos que intercambiarlas
if [ "$(contador0 ${matriz[$fila]})" -gt "$(contador0 ${matriz[$fila_posterior]})" ]; then
#Lo hacemos mediante una variable de deshecho "$basura"
basura="${matriz[$fila]}"
matriz[fila]="${matriz[$fila_posterior]}"
matriz[fila_posterior]="$basura"
# echo "Cambio F$fila con F$fila_posterior"
fi
matriz[$fila_posterior]=$(reducir ${matriz[$fila]} ${matriz[$fila_posterior]}) #Escalonamos
done
done
for num in $(seq 0 $FILAS); do #Mostramos la matriz
echo "${matriz[num]}"
done
# echo
# echo -n "declare -a matriz=("
# for num in $(seq 0 $FILAS); do
# echo -n "'${backup[$num]}'"
# if [ ! $num = $FILAS ]; then
# echo -n " "
# fi
# done
# echo ")"
# echo
# Esto de arriba es util durante el desarrollo cuando una mtriz hace cosas raras, para cogerla y ver donde falla.
echo
echo -n "SAGE_Resuleta=matrix(QQ,["
for num in $(seq 0 $FILAS); do
echo -n "[$(echo ${matriz[$num]}| tr " " , )]"
if [ ! $num = $FILAS ]; then #No ponemos coma cuando estamos en la ultima fila
echo -n ","
fi
done
echo "]); SAGE_Resuleta.echelon_form()"