| Autor |
Mensaje |
sebastianlalin
Nivel 0
Edad: 42
Registrado: 22 Sep 2008
Mensajes: 1
|
|
Hola.
Me pueden colaborar, como se desarrollaria paso a paso este algoritmo recursivo que me optimice hardware?
Dado un arreglo de enteros, que calculen:
- El mayor elemento del arreglo.
- La suma de los elementos del arreglo.
- La media de todos los elementos del arreglo.
Gracias
|
|
|
|
|
|
   |
    |
|
peterpunk
Nivel 4
Registrado: 30 Ago 2007
Mensajes: 73
Ubicación: Palermo
Carrera: Electrónica y Sistemas
|
|
Hola!
Si con desarrollo paso a paso te referís a que alguien te codifique perfectamente estas tres situaciones, creo estás errado... Si se te puede ayudar a mejorar algo que vos ya hayas hecho o "arreglar" algo que hayas hecho y no funcione y no te des cuenta de por qué? Pero hacerlo todo por vos, no creo que alguien lo haga, y tampoco creo que te ayude mucho...
Si no te referís al código y lo que necesitas es la algoritmia en pseudocodigo, lo principal es tratar de pensar cómo lo harías vos.
Por ejemplo. Te dan un papel con muchos números, cómo harías vos para saber cuál es el mayor? Leerías todos y los irías comparando... Algo así ese el primer ejemplo que planteas.
Un poco más refinado y orientado a la programación sería:
1-Leer la primera posición del arreglo y guardarla en una variable auxiliar, llamada "max", por ejemplo.
2-Leer la segunda posición del arreglo y compararla con "max". Si es menor o igual que max, pasa a la siguiente posición del arreglo y volves a comparar. Pero si es mayor, entonces guarda este nuevo valor en "max" y ahora pasa a la siguiente posición y volves a comparar.
3-Repetir hasta que no haya más elementos en el arreglo.
4-"max" va a ser el valor máximo del arreglo.
Las otras dos situaciones son de resolución muy similar.
No se si esto era lo que estabas preguntando...
Saludos,
Pedro
|
|
|
|
_________________
Me copé con las barras...
 
 
 
|
|
| |
  |
|
_facu
Nivel 3
Edad: 36
Registrado: 15 Oct 2007
Mensajes: 31
Ubicación: Villa Urquiza
Carrera: Sistemas
|
|
Create el arreglo, metele los valores desde el compilador o hace el programa para que los meta por teclado, es lo mismo.
Una vez que tenes el array hecho con los valores.
variables
max,prom,suma :integer;
PROGRAMA
begin
prom=0;
suma=0;
max=0;
Desde i:=0 hasta i := longitud del array
begin
Si array[i]>max entonces
max := array[i]
suma:= array[i] + suma
end
prom := (suma / longitud del array);
end.
Listo, ahi te quedaria el maximo valor en la variable "max", la suma en la variable "suma" y el promedio en la variable "prom".
|
|
|
|
|
|
  |
|
|
_facu
Nivel 3
Edad: 36
Registrado: 15 Oct 2007
Mensajes: 31
Ubicación: Villa Urquiza
Carrera: Sistemas
|
|
| Código:
|
variables
max,prom,suma :integer;
PROGRAMA
begin
prom=0;
suma=0;
max=0;
Desde i:=0 hasta i := longitud del array
begin
Si array[i]>max entonces
max := array[i]
suma:= array[i] + suma
end
prom := (suma / longitud del array);
end.
|
Ahi se ve mejor con los espacios
|
|
|
|
|
|
| |
|
|
Kartlan
Nivel 5
Edad: 43
Registrado: 09 Ago 2005
Mensajes: 176
Ubicación: Once
Carrera: Informática
|
|
En cuanto al enunciado hay algo que no me cierra, te piden resolverlo recursivamente? lo segundo que escribis es "optimizando hardware" te referis a que sea un algoritmo que no trabaje dos veces con cada elemento o que por ejemplo utilice instrucciones SIMD (Simple Instruction Multiple Data) que principalmente permiten realizar la misma operación con un vector de 2 long-long, 4 long, 8 int, 16 short, 32 byte (creo que se bancaba todos los basicos de C) en fin.
Despues... en cuanto a la solución creo que lo unico que ese te puede decir es lo que te comento peter... primero pensa como lo harias... despues escribi el cuentito en el lenguaje que te toque usar.
La version iterativa de _facu es correcta.... y no tiene sentido darte otra..
Si es que te lo piden recursivo y no te das cuenta de como hacerlo... pedi mas ayuda que me siento un ratito y algo sale...  trabajar al pedo no...
|
|
|
|
|
|
  |
 |
|
frsegovia
Nivel 8
Edad: 52
Registrado: 23 Ago 2005
Mensajes: 545
Ubicación: 34º44'48.93"S 58º13'36.11"O
Carrera: Civil y Informática
|
|
Si es para Algo I, el optimizar hardware tiene que referir a la primera opcion de Kartlan, o sea no trabajar 2 veces con el mismo elemento.
Armá el programa y que llame a una función recursiva que tendrá que recorrer el array y retornar suma, mayor y promedio. Despues fijate cómo obtener todos los valores con la misma función. 
|
|
|
|
_________________
...aunque en virtudes abunde, y se juzgue inobjetable,
cuando el humano se hunde, siempre busca un responsable...
...la hipocresía propasa, todo ejemplo en esta tierra,
al asesinato en masa, los hombres lo llaman guerra...
|
|
  |
|
|
Kartlan
Nivel 5
Edad: 43
Registrado: 09 Ago 2005
Mensajes: 176
Ubicación: Once
Carrera: Informática
|
|
Otra cosa que me acorde recien... recursividad y optimizar hardware medio que no van de la mano... Un algoritmo recursivo es elegante y simple pero a la hora de compararlo con su variante iterativa generalmente utiliza más memoria principalmente debido a que la llamada a una función no es tan simple como un "goto" ... pero salvo que quieras que te mareen con cosas de stack-pointer, ABI y otras yerbas lindas acerca de como es que un 1001011011011011011010101111011 puede significar suma 2 y 3 y guardalo en al variable A1 ... en fin... más adelante lo putearas/alabaras como es debido.
PD: la recursividad si puede tener mejor rendimiento en procesos puramente recursivos, en los cuales las estructuras de control requeridas para realizar el proceso iterativo son comparables con el tamaño que requiere el procesador para almacenar su estado antes de realizar la llamada a la función.... Me zarpe?... un poquito?
Para los interesados.... Org. de Computador (cosas del procesador) y/o Teoria de Algoritmos (cosas de algoritmos)...
En cuanto a como devolver el resultado depende del lenguaje...
En Pascal/Java podes usar variables por referencia.
En C++ podes usar elegantemente el std::pair<T> , para los que dicen ¿Cómo?: std::pair<int , std::pair<int> >
En C, te tenes que remangar, podes definir un struct o usar tres punteros a entero en la definición de la función, como sea es una linda practica de algoritmos lograr armar una función recursiva que lo resuelva... más que nada por que tenes que aprender a bucear la internet para ver "¿Cómo ser armar un reactor nuclear en mi lenguaje?" y limar un cacho la cabeza para aprender a pensar o pensar en aprender... no me acuerdo cual va primero.
|
|
|
|
|
|
| |
|
|
Kartlan
Nivel 5
Edad: 43
Registrado: 09 Ago 2005
Mensajes: 176
Ubicación: Once
Carrera: Informática
|
|
ups!: std::pair<int , std::pair<int> >
ups2!: todos los errores de ortografía que no corregí antes de poner enviar.
|
|
|
|
|
|
| |
|
|
Sebastian Santisi
Administrador Técnico
Edad: 42
Registrado: 23 Ago 2005
Mensajes: 17451
|
|
Por un lado, lo que plantea el que inició el thread, por como lo pidió, me da la sensación de que no tiene ni idea de qué le están hablando; por lo que la respuesta correcta no sé si está al nivel de lo que le están pidiendo para dicho curso.
Respondiéndole a Kartlan:
Estás confundido  . Si querés recursividad, y querés optimización del compilador en esa recursividad entonces te están hablando de recursividad de cola.
No hay compilador moderno que no lo optimice, y menor performance que un algoritmo iterativo, mis polainas .
|
|
|
|
_________________
 ![[tex] ${. \ \ \ \ \ \ \ \ \ .}$ [/tex]](images/latex/d678cf273c99d2546c259db3422b3d968b184721_0.png "[tex] ${. \ \ \ \ \ \ \ \ \ .}$ [/tex]") ![[tex] ${\Large Usá \LaTeX, no seas foro...}$ [/tex]](images/latex/1e6580e1ed9e054ddefd65c0551c670c44f57f38_0.png "[tex] ${\Large Usá \LaTeX, no seas foro...}$ [/tex]")
|
|
| |
 |
|
Kartlan
Nivel 5
Edad: 43
Registrado: 09 Ago 2005
Mensajes: 176
Ubicación: Once
Carrera: Informática
|
|
A ver.. a ver... esto esta ya completamente en otro ambito que no tiene nada que ver con lo que pregunto sebastianlalin... pero igual...
A penas lei tu respuesta Santisi, me puse a buscar a que llamabas recursividad de cola, y si es solamente "hacer los calculos antes de hacer el siguiente llamado" no hay mucha diferencia.
Si la optimización del compilador es encerrar el codigo de la función y hacer un bucle hasta "volver a llamar == false" , bueno... se me hace que lo unico que hace es esconder en una herramienta recursiva un algoritmo iterativo. << ¿Es esto lo que hace el compilador, o solo sabes que el compilador lo optimiza?
Si solo es eso, sigo pensando que la version iterativa de cualquier algoritmo (bien hecho) es mas rapida que su contraparte recursiva, siempre y cuando el over-head administrativo hecho a mano no supere el de las sucesivas llamadas a funciones.
Esperando los bifes... prontamente... Vamos que el 3er round es Programación Dinamica!!! muejejejejeje!!!!
|
|
|
|
|
|
| |
|
|
_facu
Nivel 3
Edad: 36
Registrado: 15 Oct 2007
Mensajes: 31
Ubicación: Villa Urquiza
Carrera: Sistemas
|
|
| Chicos no quiero joder, pero me parece que se fue un poco de mambo este mensaje jajajaja. El algoritmo que le pase, se lo di orientado a pascal y a nivel de algoritmos 1 correspondiendo a lo que masomenos piden a esta altura del cuatrimestre. No creo que sea algo mas complicado que eso...
|
|
|
|
|
|
| |
|
|
Sebastian Santisi
Administrador Técnico
Edad: 42
Registrado: 23 Ago 2005
Mensajes: 17451
|
|
| _facu escribió:
|
|
Chicos no quiero joder, pero me parece que se fue un poco de mambo este mensaje jajajaja. El algoritmo que le pase, se lo di orientado a pascal y a nivel de algoritmos 1 correspondiendo a lo que masomenos piden a esta altura del cuatrimestre. No creo que sea algo mas complicado que eso...
|
Pucha, mirá que en 75.02, Algoritmos I damos C y recursividad de cola es un tema que damos en la unidad 5 del programa.
Tomando en cuenta que sebastianlalin se expresó con modismos que lo delatan como un extranjero, yo no asumiría que sea de FIUBA; así que no me ataría al programa (o lo que te terminan dando) de 75.40 sino que abriría un poco la cabeza a qué se puede dar en otras universidades (o incluso en una materia análoga dentro del mismo edificio).
De todos modos; ojo, si te piden una solución recursiva y das una solución iterativa, me parece que mucho no tiene que ver.
(Por más que mi tono suela parecer agresivo muchas veces, leelo con la total onda; no es una cagada a pedos ni una burla, es una invitación a que no te cierres tanto a lo que te dieron, y leas un poco mejor lo que pidieron.)
Ahora, a los bifes :
| Kartlan escribió:
|
A ver.. a ver... esto esta ya completamente en otro ambito que no tiene nada que ver con lo que pregunto sebastianlalin... pero igual...
A penas lei tu respuesta Santisi, me puse a buscar a que llamabas recursividad de cola, y si es solamente "hacer los calculos antes de hacer el siguiente llamado" no hay mucha diferencia.
Si la optimización del compilador es encerrar el codigo de la función y hacer un bucle hasta "volver a llamar == false" , bueno... se me hace que lo unico que hace es esconder en una herramienta recursiva un algoritmo iterativo. << ¿Es esto lo que hace el compilador, o solo sabes que el compilador lo optimiza?
|
Es eso exactamente lo que hace; pero atento a los temas de Orga de Computadoras, por más que dos códigos puedan hacer exactamente lo mismo, de maneras similares, hay cosas que son más optimizables por el compilador porque lo dejás "darse cuenta" de cual es tu intención detrás.
¿Sí?; o sea, es cierto, la implementación a nivel máquina de una versión iterativa versus su versión de recursividad de cola, puede ser resuelta por el mismo código, el punto es que el compilador se apiole.
Por otro lado; ojo, yo dije "menor performance que un algoritmo iterativo, mis polainas" no dije que el recursivo fuera más rápido, dije que no iba a ser más lento, así que si bien puede darse yo no lo dije y me malinterpretaste.
Si usás recursividad de cola, el compilador tiene más chances de darse cuenta que cada iteración encapsula variables que no sobreviven al mismo salvo un valor de retorno; le estás dejando servida en bandeja la posibilidad de optimizar. Iterando, queda más tapada por otras cosas. Esto, por supuesto, en el caso que el compilador lo optimice, si no lo optimiza, es tan desastroso como una recursividad común.
Tu cuestionamiento es bien válido y es: ¿No es la recursividad de cola el paso previo a la eliminación de la recursividad?, y la respuesta es: Sí.
| Kartlan escribió:
|
Si solo es eso, sigo pensando que la version iterativa de cualquier algoritmo (bien hecho) es mas rapida que su contraparte recursiva, siempre y cuando el over-head administrativo hecho a mano no supere el de las sucesivas llamadas a funciones.
Esperando los bifes... prontamente... Vamos que el 3er round es Programación Dinamica!!! muejejejejeje!!!!
|
Parte de mi respuesta, y la dejo para este quotecito, también era: Y ojo, nadie te dice que el lenguaje pueda llegar a poseer iteraciones... en paradigma funcional no hay bucles y la iteración se tiene que hacer sí o sí con recursividad; si no sabés armar una recursividad de cola, probablemente tus cosas vayan a andar para atrás.
|
|
|
|
_________________
|
|
| |
|
|
|
|
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
