elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Entrar al Canal Oficial Telegram de elhacker.net


+  Foro de elhacker.net
|-+  Programación
| |-+  Scripting
| | |-+  Matkix - Escalonar matrices
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Matkix - Escalonar matrices  (Leído 945 veces)
vk496

Desconectado Desconectado

Mensajes: 205


Ver Perfil
Matkix - Escalonar matrices
« en: 12 Diciembre 2014, 23:00 pm »

Hace poco he acabado un trabajo de matemáticas y vengo para compartirlo con vosotros. Hace lo que dice el titulo: escalonar matrices.

Fiel a mis principios: Bash.

Código
  1. #!/bin/bash
  2.  
  3. #################################################################
  4. #                                                               #
  5. # # -*- ENCODING: UTF-8 -*-                                     #
  6. # Este script es software libre. Puede redistribuirlo y/o       #
  7. # modificar-lo bajo los términos de la Licencia Pública General #
  8. # de GNU según es publicada por la Free Software Foundation,    #
  9. # bien de la versión 3 de dicha Licencia o bien (según su       #
  10. # elección) de cualquier versión posterior.                     #
  11. #                                                               #
  12. # Si usted hace alguna modificación en esta aplicación,         #
  13. # deberá siempre mencionar al autor original de la misma.       #
  14. #                                                               #
  15. # Autor: Script creado por vk496                                #
  16. #                                                               #
  17. # Un saludo                                                     #
  18. #                                                               #
  19. #################################################################
  20.  
  21.  
  22. # Lo que hace este script es escalonar una matriz. No está optimizado para que la escalone ni mas rapido ni mas
  23. # eficiente, pero hace su trabajo (o eso me ha parecido después del debug.) A lo largo del programa habrá muchisimos
  24. # comentario para intentar explicar que hace cada cosa y como lo consigue, ya que el principal problema de esto es
  25. # que Bash no permite la declaración de arrays multidimensionales y es un poco lio. Vamos al grano
  26.  
  27.  
  28. if [ $# = 0 ]; then #Si no hay ningun parametro de entrada, muestra la ayuda y se sale
  29. echo "matkix v0.1 by vk496"
  30. echo "Uso: matkix [FILAS] [COLUMNAS] -R"
  31. echo
  32. echo "  [FILAS]      Numero de filas"
  33. echo "  [COLUMNAS]   Numero de columnas"
  34. echo "  -R|-r        Generar una matriz aleatoriamente"
  35. exit
  36. fi
  37.  
  38. # Existen tres funciones principales en el programa que toman datos de entrada para devolver una salida
  39. #
  40. # es_un_numero nos devuelve un {1,0} dependiendo de la entrada que le demos
  41. function es_un_numero {
  42. posible_numero=($1) #Cogemos el primer parametro y lo declaramos en forma de array
  43. # con la variable $posible_numero
  44. var=$(echo $posible_numero | sed 's/-//g' | sed 's/ //g') #Hacemos uso de 'sed' para eliminar cualquier
  45. # posible signo de numero negativo o espacio, y lo declaramos como $var
  46.  
  47. if [ "$var" -eq "$var" ] 2>/dev/null; then #Hacemos un poco de "trampa" en Bash. Aprovechamos los operadores
  48. # aritmeticos para igualar un numero a si mismos. Si es numero, siempre será igual a si mismo. Por el
  49. # contrario, si no lo es, nos devolverá un error en stderr, el cual ocultaremos con una redirección al
  50. # "vacio" (/dev/null)
  51. echo 1 #Es un numeros, devolvemos un 1
  52. else
  53. echo 0 #No es un numero, devolvemos un 0
  54. fi
  55. }
  56. # Es una funcion que siempre devolverá un resultado. Luego nos será util
  57.  
  58. # Por otra parte, esta nos devolverá la cantidad de ceros que hay en una fila si los contamos de izquierda a derecha
  59. function contador0 {
  60. declare -a ceros=($@) #Declaramos un array que tendrá como contenido todos los parametros que recibe contador0.
  61. # Esto se debe a que cada uno de los elementos de la matriz lo interpreta como parametros, por eso no
  62. # podemos coger solo el primero, tenemos que coger todos los de la fila. Cada elemento de la columna
  63. # se identifica como un elemento distinto en el array
  64.  
  65. total=0 #Consideramos que nuestra fila desde el principio no tiene nigún cero a la izquierda
  66.  
  67. for x in $(seq 0 $COLUMNAS); do #Un for para usar la x como identificador de cada elemento en el array. Como
  68. # sabemos seguro la cantidad de columnas que tiene nuestra fila, nos basta con una secuencia
  69.  
  70. if [ "${ceros[$x]}" = 0 ]; then #Si el elemento x de la array $ceros equivale a 0, significa que hemos
  71. # encontrado el primero cero. Se lo sumamos a $total
  72. let total=$total+1
  73. else
  74. break #De lo contrario, nos salimos de la iteracion
  75. fi
  76. done
  77.  
  78. # Analizamos nuestra variable $total. Si es mayor que cero, devolvemos como salida de contador0 la cantidad de 0
  79. if [ $total -gt 0 ]; then
  80. echo $total
  81. else
  82. echo "0" #Si no lo es, devolvemos un 0
  83. fi
  84. }
  85.  
  86. #Algoritmo para calcular el mcd de dos numeros. Se usará posteriormente en otra funcion
  87. function mcd {
  88. u=$1 #Primer numero como parametro
  89. v=$2 #Segundo numero como parametro
  90.  
  91. #Si el segundo parametro es vacio, tomará el valor del primero. Es decir, un mcd con dos numeros iguales
  92. if [ -z $v ]; then
  93. v=$u
  94. fi
  95.  
  96. if [ $v = 0 ]; then #Tenemos que tener en cuenta los 0, y evitarlos. De esta forma, solo manejamos los que
  97. # no sean 0
  98. v=$u
  99. fi
  100.  
  101. if [ $u = 0 ]; then #Lo mismo que la condicion de arriba pero para el otro parametro
  102. u=$v
  103. fi
  104.  
  105. while [ ! $u = $v ]; do #Mientras no sean iguales, repetir la accion hasta que lo sean
  106. if [ $u -lt $v ]; then #Si $u es menor que $v, restamos a $v el valor de $u
  107. let v=$v-$u
  108. elif [ $v -lt $u ]; then #Viceversa
  109. let u=$u-$v
  110. fi
  111.  
  112. done
  113.  
  114. echo $u #Es indiferente que valor devuelvolver ($u o $v). En cualquier caso, siempre será un valor distinto de
  115. # 0 mientras que ambos parametros no sean 0
  116.  
  117. }
  118.  
  119. #Dada una fila, esta funcion devolverá la fila simplificada. Muy util para evitar numeros gigantescos en los resultados
  120. function simplificar {
  121. valores=$@ #Guardamos en $valores todos los elementos de la fila
  122.  
  123. declare -a entrada=($valores) #Asignamos esos valores en un array.
  124. ceros=0 #Iniciamos variable del contador de ceros en la fila
  125. total=0 #Contamos todos los elementos de la fila
  126.  
  127. for x in "${entrada[@]}"; do #Para cada elemento del array...
  128. if echo $x | grep -q "-"; then #Comprobamos si es negativo o no
  129. entrada[total]=$(echo ${entrada[$total]}|sed 's/-//g') #En caso de serlo, eliminamos el signo
  130. # por ahora
  131. negativos="$negativos,$total" #Almacenos la posicion del array al que corresponde ese numero
  132. fi
  133.  
  134. if [ $x = 1 ]; then #Si tiene un 1, sabemos que no se puede simplificar. Devolvemos la fila tal como
  135. # está en en el parametro de entrada y nos salimos de la funcion
  136. echo $valores
  137. exit
  138. elif [ $x = 0 ]; then # en caso de ser un 0, añadimos una unidad al contador de ceros
  139. let ceros=$ceros+1
  140. fi
  141.  
  142. let total=$total+1 #Contamos los elemento totales
  143.  
  144. done
  145.  
  146. # Si $total es igual a $negativos, significa que toda la fila son ceros. No hay nada que hacer, nos salimos...
  147. if [ $total = $ceros ]; then
  148. echo $valores
  149. exit
  150. fi
  151.  
  152. # Tratamos cada elemento de la fila para encontrar un divisor comun
  153. for valor in "${entrada[@]}"; do
  154. # Conforme avancemos, vamos haciendo mcd del elemento actual con el resultado de su antecesor
  155. #
  156. comun=$(mcd $valor $comun) #La propiedad de mcd permite hacerlo de esta forma mediante iteracion sin
  157. # tener que hacer una funcion para n elementos. Cuanto mas facil, mejor :)
  158. done
  159. # En el peor de los casos, no hay ningun numero comun a todos los de la fila. En ese caso, $comun vale 1
  160.  
  161. if [ $comun = 1 ]; then #Si $comun es 1, no tiene sentido seguir. Nos salimos...
  162. echo $valores
  163. exit
  164. fi
  165.  
  166. y=0 #Necesitamos un contador para definir cada uno de los elementos de la array segun la posicion en la misma
  167. for valor in "${entrada[@]}"; do
  168. entrada[y]=$(echo "$valor/$comun"|bc) #Dividimos cada uno de los elementos por su numero comun a
  169. # todos ellos
  170. let y=$y+1
  171. done
  172.  
  173. # Devolvemos los signos a los numeros que lo tuviesen. Hacemos iteracion para cada uno de los elementos de
  174. # la lista
  175. for posicion in $(echo $negativos | sed 's/,/ /g'); do
  176. entrada[posicion]=$(echo "-${entrada[$posicion]}") #Reasignamos el elemento del array segun
  177. # corresponde a la lista de los negativos. Recordemos que $negativos no almacena el valor, sino
  178. # la posicion de dichos elementos
  179. done
  180.  
  181. echo "${entrada[@]}" #Si hemos llegado hasta este punto
  182. }
  183.  
  184. # Esta es la funcion central de este programa. Ella es la que se encarga de escalonar las matrices. Como parametros
  185. # de entrada tenemos dos matrices. Mediante calculos, nos devolverá otra matriz, que será la reducida en base a las
  186. # dos de entrada
  187. function reducir {
  188. total=$@ #La variabe total, al igual que en "es_un_numero{}", toma todos los parametros (las dos filas)
  189. numero=$(echo $total | awk -F' ' '{print NF}') # Al estar las dos filas juntas tenemos que separarlas.
  190. # Para ello, sacamos el numero total de elementos que hay (los delimitadores son espacios en una array)
  191.  
  192. # ----------------------------------------------
  193. # |     Usamos bc para operaciones basicas     |
  194. # ----------------------------------------------
  195. #   |
  196. #     |
  197. #     v
  198. f1=$(echo $total | cut -d" " -f-$(echo $numero/2 | bc)) #Como sabemos el numero total de elementos, y SIEMPRE
  199. # va a ser par, cogemos los primeros n/2 elementos, que corresponden a la primera fila. Para ellos,
  200. # usamos cut y como delimitador el espacio, cogiendo desde el elemto 1 hasta el n
  201.  
  202. f2=$(echo $total | cut -d" " -f$(echo $numero/2+1 | bc )-$numero) #Exactamente lo mismo pero para la segnda
  203. # fila. Sin embargos, cogemos a partir del elemento posterior a n (n+1) hasta $numero (ultimo elemento)
  204.  
  205.  
  206. declare -a trozo0=($f1) #Tenemos a $f1 como variable. La declaramos como matriz en $trozo0
  207. declare -a trozo1=($f2) #Lo mismo para $f2
  208.  
  209. x=${trozo0[$fila]} #El pivote de la fila que cogeremos para operar cumple una relacion con el numero de la
  210. # fila en el que nos encontramos. Por ejemplo: Si cogemos la tercera fila, sabemos que el que hará de
  211. # pivote será el tercer de dicha fila. Por tanto, cogemos exclusivamnete ese elemento
  212.  
  213. y=${trozo1[$fila]} # El mismo caso para la fila que será operada.
  214.  
  215. if [ $y = 0 ]; then # Si en el elemento de la fila que será operada tenemos un 0 (el elemento que está debajo
  216. # del pivote), devolvemos la fila operada tal cual y nos salimos
  217. echo $f2
  218. exit
  219. fi
  220.  
  221. IFS=" "
  222. for ((i=0;i<=$COLUMNAS;i++)); do #Para cada uno de los elementos de la fila
  223. F1=$(echo $y*${trozo0[$i]}|bc) #Multiplicamos el elemento de abajo por el pivote de arriba
  224. F2=$(echo $x*${trozo1[$i]}|bc) #Multiplicamos el pivote por el elemento de abajo
  225. OPERADA=$(echo "$OPERADA $(echo "$F1 - $F2"|bc)") #Dejamos la resta de ambos en la variable OPERADA. Es
  226. # importante mencionar que esta variable es creciente, y que aunque en la primera iteracion
  227. # no tenga ningun valor, se representa como un espacio vacio. Esto nos permite añadir elementos
  228. # a la fila de forma consecutiva hasta concluir con la fila operada por las dos filas de entrada
  229. # (fila y fila_posterior)
  230. done
  231.  
  232. echo $OPERADA #Devolvemos la fila operada de la funcion
  233. unset OPERADA #Debido a que es incrementativa, borramos su contenido para su posible posterior uso.
  234. }
  235.  
  236. #Obligamos a definir un numero concreto de filas. Si no está como parámetro, nos salimos con error
  237. if [ -z $1 ]; then
  238. echo No hay filas
  239. exit 1
  240. else
  241. FILAS=$1 #De lo contrario, definimos $FILAS y continuamos
  242. fi
  243.  
  244. # Restamos una unidad a la variabe filas. Esto se debe a que el primer elemento de un array se identifica con
  245. # un 0, mientras que los "humanos" empezamos por el 1
  246. FILAS=$(echo $FILAS-1 |bc)
  247.  
  248. # Exactamente lo mismo que con las filas...
  249. if [ -z $2 ]; then
  250. echo No hay columnas
  251. exit 1
  252. else
  253. COLUMNAS=$2
  254. fi
  255.  
  256. # Mas de lo mismo....
  257. COLUMNAS=$(echo $COLUMNAS-1 |bc)
  258.  
  259. if $(echo $@ | grep -qi "\-r"); then #Si tenemos el parámetro "-r", generamos aleatoriamente numeros positivos 0-9
  260. for fila in $(seq 0 $FILAS); do #Para cada una de las filas
  261. for columna in $(seq 0 $COLUMNAS); do #Para cada columna de cada fila
  262. subfila[columna]="$(shuf -i 0-9 -n 1)" #Creamos una array para la fila con numeros aleatorios
  263. done
  264.  
  265. matriz[fila]=${subfila[@]} #Cuando acabamos con una fila, todos los elementos de la array "subfila"
  266. # pasan a ser solo un elemento de la array "matriz"
  267. done
  268. echo
  269. else #Si no tenemos el parametro "-r", nosotros mismos introducimos la matriz
  270. IFS="\t" #Hacemos que el delimitador de la iteración sea un salto de linea en vez del espacio. Es importante
  271. # hacer esto por que no sabemos cual es la longitud de la matriz hasta que el usuario no pulse
  272. # ENTER para escribir la siguiente fila
  273. z=0
  274. while true; do #Entramos en el loop para leer las filas
  275. while true; do #Entramos en otro loop, pero esta vez para verificar lo que introduce el usuario
  276. echo -n "F$(echo $z+1 |bc): " #Formalidades... Simplemente para saber cual es la fila que
  277. # estamos escribiendo
  278. read -a linea #Leemos lo que introduce el usuario
  279.  
  280. # Hacemos uso de awk para contar los espacios (empieza a contar a partir del 1, por lo que
  281. # nos devuelve la cantidad de elementos). Obligamos a que el numero total de elementos
  282. # equivalga a la cantidad de columnas predefinidas por el usuario
  283. if [ ! $(echo $linea | awk -F' ' '{ print NF }') = $(echo $COLUMNAS+1|bc) ]; then
  284. echo No coinciden las columnas
  285. echo
  286. continue #Como no coincide, regresamos al verificador para que haga la fila otra vez
  287. fi
  288.  
  289. # Hacemos uso de la funcion es_un_numero() para saber cuando tenemos que salir del verificador
  290. if [ $(es_un_numero $linea) = 1 ]; then #Si es un numero, salimos del verificador
  291. break
  292. else
  293. echo No es un numero
  294. echo
  295. fi
  296. done
  297.  
  298. subfila=($linea) #Exactamente lo mismo que con el parámetro "-r". Solo que esta vez usamos la variabe
  299. # que ha escrito el usuario y no una matriz
  300. matriz[z]=${subfila[@]} #Mas de lo mismo para crear la matriz
  301.  
  302. #
  303. if [ $z = $FILAS ]; then #Cuando se han introducido todas las fila que ha definido el usuario, podemos
  304. # salir del loop, por lo que habremos terminado la creación de la matriz
  305. break
  306. fi
  307.  
  308. let z=$z+1
  309. done
  310. unset IFS #En adelante, no nos interesa tener como delimitador de la iteraciones un salto de linea, por lo que
  311. # borramos esa variabe
  312. clear #Borramos todo lo anterior de la pantalla
  313. fi
  314.  
  315. echo
  316. # Imprimimos en pantalla la matriz que tenemos actualmente mediante una iteracion
  317. for fila in $(seq 0 $FILAS); do
  318. echo "${matriz[fila]}"
  319. backup[fila]="${matriz[fila]}" #creamos una copia de la matriz sin escalonar
  320. done
  321. echo
  322. echo -n "SAGE_Original=matrix(QQ,["
  323. for num in $(seq 0 $FILAS); do
  324.  
  325. echo -n "[$(echo ${backup[$num]}| tr " " , )]"
  326. if [ ! $num = $FILAS ]; then #No ponemos coma cuando estamos en la ultima fila
  327. echo -n ","
  328. fi
  329. done
  330.  
  331. echo "]); SAGE_Original.echelon_form()"
  332. echo
  333. echo ------------------
  334. echo
  335.  
  336. matriz[0]=$(simplificar ${matriz[0]}) #Tratamos al primer elemento, ya que posteriormente no se toca a lo largo de la
  337. # iteracion
  338.  
  339. for fila in $(seq 0 $FILAS); do #Para cada una de las filas...
  340. matriz[fila]=$(simplificar ${matriz[$fila]})
  341.  
  342. # A continuacion, hacemos la segunda iteracion que nos permitirá "recorrer" la matriz de forma que podamos
  343. # operar con ella. Como tenemos que escalonar las filas de la matriz, sabemos que jugamos con la variabe filas,
  344. # por lo que $COLUMNAS pasa a un segundo plano. De antemano nos encontramos en una fila concreta ($fila), por
  345. # lo que nuestro objetivo es recorrer todas las demas filas "por debajo" de esta. Es por ello que el recorrido
  346. # se realiza desde la fila posterior ($fila+1) hasta la última fila declarada por el usuario
  347. for fila_posterior in $(seq $(echo $fila+1 | bc) $FILAS); do
  348.  
  349. if [ "$fila" -gt "$COLUMNAS" ]; then #Cuando la fila actual supera la COLUMNAS TOTALES de la matriz,
  350. # nos salimos de esta iteracion para evitar errores. Esto pasa cuando hay mas filas que columnas
  351. break
  352. fi
  353.  
  354. matriz[fila_posterior]=$(simplificar ${matriz[$fila_posterior]}) #Simplificamos la matriz posterior
  355. # que será operada con la actual para escalonar
  356.  
  357. # Si nos encontramos en el caso en el que la fila posterior está escalonada respecto a la actual
  358. # (comparando sus cantidades de ceros a partir de la izquierda), simplemente tenemos que intercambiarlas
  359. if [ "$(contador0 ${matriz[$fila]})" -gt "$(contador0 ${matriz[$fila_posterior]})" ]; then
  360.  
  361. #Lo hacemos mediante una variable de deshecho "$basura"
  362. basura="${matriz[$fila]}"
  363. matriz[fila]="${matriz[$fila_posterior]}"
  364. matriz[fila_posterior]="$basura"
  365. # echo "Cambio F$fila  con F$fila_posterior"
  366. fi
  367.  
  368. matriz[$fila_posterior]=$(reducir ${matriz[$fila]} ${matriz[$fila_posterior]}) #Escalonamos
  369. done
  370. done
  371.  
  372. for num in $(seq 0 $FILAS); do #Mostramos la matriz
  373. echo "${matriz[num]}"
  374. done
  375.  
  376. # echo
  377. # echo -n "declare -a matriz=("
  378. # for num in $(seq 0 $FILAS); do
  379. # echo -n "'${backup[$num]}'"
  380. # if [ ! $num = $FILAS ]; then
  381. # echo -n " "
  382. # fi
  383. # done
  384. # echo ")"
  385. # echo
  386. # Esto de arriba es util durante el desarrollo cuando una mtriz hace cosas raras, para cogerla y ver donde falla.
  387.  
  388. echo
  389. echo -n "SAGE_Resuleta=matrix(QQ,["
  390. for num in $(seq 0 $FILAS); do
  391.  
  392. echo -n "[$(echo ${matriz[$num]}| tr " " , )]"
  393. if [ ! $num = $FILAS ]; then #No ponemos coma cuando estamos en la ultima fila
  394. echo -n ","
  395. fi
  396. done
  397.  echo "]); SAGE_Resuleta.echelon_form()"

Salu2


« Última modificación: 13 Diciembre 2014, 00:39 am por Eleкtro » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
matrices en C#
Programación General
volterra 4 8,798 Último mensaje 18 Mayo 2010, 06:26 am
por Og.
matrices
Programación C/C++
aral90 2 1,410 Último mensaje 9 Diciembre 2011, 20:13 pm
por aral90
matrices
.NET (C#, VB.NET, ASP)
legomanticore 4 2,422 Último mensaje 14 Mayo 2012, 03:02 am
por $Edu$
matrices en c
Programación C/C++
ALONSOQ 9 3,364 Último mensaje 27 Junio 2012, 05:15 am
por twins
matrices
Programación C/C++
lorderick 3 2,051 Último mensaje 8 Septiembre 2012, 05:12 am
por CSQCasimiro
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines