Imprimir Página - Problemas sencillos de programación para resolver

Lenguajes de programación para PC => Visual Basic => Mensaje iniciado por: Picuino en 26 de Marzo de 2014, 11:55:24

Título: Problemas sencillos de programación para resolver
Publicado por: Picuino en 26 de Marzo de 2014, 11:55:24

Este no es el hilo adecuado, pero es que no hay un subforo para otros lenguajes de programación para PC.

En este blog tratan el tema de qué es lo que piden las empresas cuando buscan programadores:
http://juanmacias.net/2013/01/hay-programadores-en-espana-o-monos/

Casi al final del artículo aparece este sencillo problema, con comentario sobre su dificultad:

Citar

CHOCO-LATE. Escribe un algoritmo en cualquier lenguaje de programación (uno de los 20 que aparecen aqui:http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html ) que cuente del 1 al 100 y que muestre por pantalla “CHOCO” cuando el número sea divisible por 3, “LATE” cuando se divisible por 5 y “CHOCOLATE” cuando sea divisible por 15.

La mayoría de los que respondieron a la pregunta lo hicieron de forma incorrecta y ninguno dio una respuesta mejor o igual a la que había dado yo. Y no fallaron por que no supieran programar, fallaron por que no leyeron correctamente el problema, no hicieron un análisis exhaustivo, simplemente se pusieron a programar.

Bueno, me ha picado la curiosidad y me he puesto a programar en Python una solución:

Código: [Seleccionar]

print "\n".join([str(i)+" "+"CHOCO"*((i%3)==0)+"LATE"*((i%5)==0) for i in range(1,101)])

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: BrunoF en 26 de Marzo de 2014, 12:53:35

Me parece que el enunciado puede resultar capcioso.

Uno podría interpetar que, por ejemplo, ante el número 15 podría imprimirse como: CHOCO, CHOCOLATECHOCOLATE o CHOCHOLATE para dicho número, según como interprete el enunciado.

CHOCO resultaría porque el número 15 es divisible por 3, lo que imprimiría CHOCO y dejaría de analizar el resto de las condiciones.

CHOCOLATECHOCOLATE resultaría porque el número 15 cumple las tres condiciones, divisible por 3 (aporta CHOCO), divisible por 5 (aporta LATE) y divisible por 15 (aporta nuevamente CHOCOLATE).

CHOCOLATE resultaría de que al ser el número 15 divisible por 3 y por 5, cada uno aportaría CHOCO y LATE respectivamente, y se omitiría el divisible por 15

Sinceramente creo que es más un truco de la lengua que un verdadero problema algorítimco.

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: rivale en 26 de Marzo de 2014, 13:18:42

Por lo que entiendo primero se verifica que sea divisible por 3 y aporta choco y cuando es 5 aporta el late, entonces cuando es 15, ambos aportan y da chocolate.

algo asi:

Código: C

for(int i=1;i<101;i++
{
        if((i%3)==0)printf("Choco");
        if((i%5)==0)printf("late");
        if(((i%5)==0) || ((i%3)==0))printf("\n");
}

aunque también podría ser choco+late+chocolate por el 3,5 y 15.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: SavageChicken en 26 de Marzo de 2014, 13:52:41

Comparto Plenamente lo dicho por Bruno.

El enunciado no es del todo claro en al menos indicar que en caso de ser divisible por 3 y por 5 ( en cuyo caso es divisible también por 15) si se desea que obtenga CHOCOLATE o en su defecto CHOCOLATECHOCOLATE por cumplir con lo solicitado.

Aunque también comparto que en muchos casos el programador se pone a programar sin tratar de comprender bien cual es el problema planteado.

Salud 8)

Cita de: BrunoF en 26 de Marzo de 2014, 12:53:35

Me parece que el enunciado puede resultar capcioso.

Uno podría interpetar que, por ejemplo, ante el número 15 podría imprimirse como: CHOCO, CHOCOLATECHOCOLATE o CHOCHOLATE para dicho número, según como interprete el enunciado.

CHOCO resultaría porque el número 15 es divisible por 3, lo que imprimiría CHOCO y dejaría de analizar el resto de las condiciones.

CHOCOLATECHOCOLATE resultaría porque el número 15 cumple las tres condiciones, divisible por 3 (aporta CHOCO), divisible por 5 (aporta LATE) y divisible por 15 (aporta nuevamente CHOCOLATE).

CHOCOLATE resultaría de que al ser el número 15 divisible por 3 y por 5, cada uno aportaría CHOCO y LATE respectivamente, y se omitiría el divisible por 15

Sinceramente creo que es más un truco de la lengua que un verdadero problema algorítimco.

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 26 de Marzo de 2014, 14:12:57

Otra versión del mismo programa publicado en esta página:
http://skiel85.blogspot.com.es/2010/02/entrevistas-con-tests-de-programacion.html

Citar

Escriba un programa que imprima los números del 1 al 100. Pero para los múltiplos de 3 imprima "Fizz" en lugar del número y para los múltiplos de 5 imprima "Buzz". Para los números que son múltiplos de ambos imprima "FizzBuzz"

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 26 de Marzo de 2014, 14:13:23

Solución en Python:

Código: [Seleccionar]

for i in range(1, 101):
    a = ((i%3)==0)
    b = ((i%5)==0)
    if a or b: print "Fizz" * a + "Buzz" * b
    else: print i

Resultado:

Código: [Seleccionar]

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz

Título: Re: Problemas sencillos de programación para resolver
Publicado por: rivale en 26 de Marzo de 2014, 14:15:55

Cita de: Picuino en 26 de Marzo de 2014, 14:13:23

Otra versión del mismo programa:

http://skiel85.blogspot.com.es/2010/02/entrevistas-con-tests-de-programacion.html

Citar
Escriba un programa que imprima los números del 1 al 100. Pero para los múltiplos de 3 imprima "Fizz" en lugar del número y para los múltiplos de 5 imprima "Buzz". Para los números que son múltiplos de ambos imprima "FizzBuzz"

Saludos.

en esa versión si se entiende que solo sería una vez la palabra cuando sea múltiplo de 15, tambien dice que se debe imprimir el número, así esta mejor redactado

Título: Re: Problemas sencillos de programación para resolver
Publicado por: rivale en 26 de Marzo de 2014, 14:18:46

un mejor test que esos sería el del concurso que hizo Nocturno, y que queden contratados solo los primeros lugares :mrgreen:

http://www.micropic.es/mpblog/2013/06/resultados-primer-concurso-de-programacion-numeros-romanos/ (http://www.micropic.es/mpblog/2013/06/resultados-primer-concurso-de-programacion-numeros-romanos/).

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 26 de Marzo de 2014, 14:28:02

Una página que te hace test para conocer tus habilidades como programador:
https://codility.com/c/intro/demo9YYR32-7XK

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 26 de Marzo de 2014, 14:40:29

A ver quien se atreve con este programa un poco complejo:

Hay que ordenar la siguiente lista de 500 números aleatorios:

Código: [Seleccionar]

Para que podamos comparar algoritmos con diferentes lenguajes de programación, el tiempo de ejecución se debe contar de la siguiente manera:
Cada vez que comparemos dos números, se suma uno a la variable tics
Cada vez que se copie un número a otra posición, se suma uno a la variable tics
Al final del programa, el que menos tics tenga es el algoritmo más eficiente.

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 26 de Marzo de 2014, 15:06:22

Una solución en python con el algoritmo de selección directa (es un algoritmo lento):

Comparaciones = 124750
Movimientos = 1497
Tics = 126247

Código: Python

"""Algoritmo de ordenacion de datos por Seleccion directa"""
def seleccion_directa(datos):
   comps = 0
   moves = 0
   for i in range(0, len(datos)-1):
      min_data = i
      for j in range(i+1, len(datos)):
         comps += 1
         if datos[j] < datos[min_data]:
            min_data = j
      moves += 3
      temp = datos[i]
      datos[i] = datos[min_data]
      datos[min_data] = temp
      
   return comps, moves
 
 
datos = [
   1497, 2094, 8094, 3331, 1126, 0736, 5999, 9688, 3593, 3353,
   3555, 9778, 4371, 2817, 9020, 2504, 6217, 2796, 8904, 0764,
   6700, 4105, 4468, 8504, 3201, 7426, 8780, 7518, 8846, 6228,
   3026, 2895, 3145, 1950, 4887, 0542, 8124, 3730, 7725, 4798, 
   8733, 1024, 7326,  669, 5985, 4882, 5867, 2991, 4641, 1964, 
   9245, 0501, 6406, 9280, 7916, 9477, 7166, 5616, 5183, 6264, 
   1024, 6136, 1894, 2402, 6529, 9646, 9749, 1208,  909, 6844, 
   7741, 2101, 8181, 8332, 1594, 9510, 9052, 1812, 1105, 3009, 
   5306, 4086, 6918, 5059, 6416, 7600, 7700, 4758, 7016, 3580, 
   7689, 5376, 7879, 1153,  945, 8274,  790, 8415, 9890, 1811, 
   5117, 5787, 3264, 6903,  555, 1337, 5062, 5881, 3592, 5533, 
   6056, 9723, 5849, 0352, 7148, 6921, 4568, 2615, 7105, 4869, 
   4685, 2987,   86, 6671, 8651, 3713, 6700, 5162, 6996, 8931, 
   7627, 1921, 6782, 2964, 1723, 2496, 6492, 1102, 3194, 6286, 
   9070, 8809, 8284, 3924, 6185, 6910, 9044, 4132, 0421, 6176, 
   0003, 4527, 7189,  268, 7978, 3881, 2497, 1252, 2330, 4674, 
   6657, 3652, 7182, 1810, 2569, 1545, 1963, 3168, 3266, 6167, 
   9575, 0200, 7064, 3931, 6748, 8158, 4523, 2391, 4649, 4348, 
   8598, 3430, 4983, 9916, 5575, 2091, 5675, 8954, 0761, 3242, 
   7649, 3842, 6078, 1123, 8144, 1939, 4487, 6824, 5786, 4455, 
   9169, 2353, 7104, 0014, 3532, 6235, 3737, 3446, 8497, 1608, 
   5947, 9078, 0411, 9139, 2823, 3858, 7542, 2447,  629,  799, 
    932, 2034, 7641, 6301, 9415, 0024, 8822, 4243, 5918, 7770, 
   3517, 3742, 8472, 9127, 3351, 8108, 6206, 9826, 9462, 3508, 
     94, 8209, 5372, 9358, 0223, 7268, 9840, 8529,  771, 3572, 
   9937, 7143, 3051, 8448, 5031, 4636, 8590, 3294, 5210, 5741, 
   3634, 9242, 8400, 5990, 8113, 1154, 1555, 5658, 9085, 9179, 
   8736, 4712, 6754, 5967, 6848, 7139, 9501, 6505, 5333, 3315, 
   7737, 7527, 5977, 6657, 2070, 1140, 5534, 9133, 7690, 5258, 
   6915,  792, 9924, 9933, 9601, 5346, 9188, 2199, 1091, 7259, 
   4932,  242, 8314, 8326, 1129, 7811, 1933, 4677, 4867, 3075, 
   3132,  810, 9029,  727, 9055, 5940, 1442, 5141,  459,  627, 
   9792, 3026, 8012, 8760, 5954, 2642, 2583, 7230, 3431, 2174, 
   8984, 4221, 2782, 7529, 6415, 2073, 9761, 5659, 6208,  559, 
   3602, 6420, 5917,  489, 4267, 0675, 4343, 4515, 3388, 5903, 
   7493, 3408, 5463, 7913, 7004, 1043, 5956, 8239, 4803, 6724, 
   6532, 8070,  550, 7118, 2546, 4519, 7225, 7742, 9187, 6297, 
   8010,  691,   27, 2058, 4568, 5860, 2821, 9680, 5322, 3375, 
   7767, 2586, 8182, 0500, 2286, 9836, 4814, 5092,  969, 7444, 
   5085,  487, 8035, 3482, 4246, 0361, 7185, 3827, 6742, 6705, 
   4416, 2750,  989, 4263, 9161, 7310, 6412, 5782, 1174, 0307, 
   4382, 0464, 7345, 5385, 5629, 0465, 8815, 2334, 9408, 1466, 
   3045, 8856, 4975, 5449, 1861, 7048, 9815, 8885, 5492, 5345, 
   3349, 6925, 6863, 1659, 6273, 8183,  341, 3461,  952, 2726, 
   6124, 3483, 6073, 1571, 4614, 8278, 3868, 7124, 8762, 8298, 
   5478, 6643, 7519, 9364, 4932, 2554, 1261, 9594, 7183, 0345, 
   3712, 6647, 9640,  370, 8654, 4381, 7962, 4694, 2931, 5007, 
    685, 6414, 5349, 4396, 5994, 7944, 5011, 2190, 3240, 9377, 
   4256, 8256, 6413, 9956, 2922, 1004, 2709, 0215, 5639, 7081, 
   8260, 2812, 6636, 2429, 4114, 4715, 6381, 6933, 2137,  378,
]
 
 
#main program
comps, moves = seleccion_directa(datos)
print "Comparaciones =", comps
print "Movimientos =", moves
print "Tics =", comps + moves
print "Datos = [\n  ",
print "".join(["%04d" % datos[i] + ", " + "\n   "*((i+1)%10==0) for i in range(0, len(datos))]),
print "]"

Resultado:

Código: [Seleccionar]

Comparaciones = 124750
Movimientos = 1497
Tics = 126247
Datos = [
   0003, 0012, 0020, 0027, 0086, 0094, 0128, 0141, 0147, 0199, 
   0229, 0234, 0241, 0242, 0265, 0268, 0273, 0308, 0309, 0320, 
   0321, 0341, 0354, 0370, 0378, 0445, 0459, 0478, 0487, 0489, 
   0497, 0500, 0550, 0555, 0559, 0627, 0629, 0669, 0685, 0691, 
   0727, 0771, 0790, 0792, 0799, 0810, 0909, 0932, 0945, 0952, 
   0969, 0989, 1004, 1024, 1024, 1043, 1091, 1102, 1105, 1123, 
   1126, 1129, 1140, 1153, 1154, 1174, 1208, 1252, 1261, 1337, 
   1442, 1466, 1497, 1545, 1555, 1571, 1594, 1608, 1659, 1723, 
   1810, 1811, 1812, 1861, 1894, 1921, 1933, 1939, 1950, 1963, 
   1964, 2034, 2058, 2070, 2073, 2091, 2094, 2101, 2137, 2174, 
   2190, 2199, 2286, 2330, 2334, 2353, 2391, 2402, 2429, 2447, 
   2496, 2497, 2504, 2546, 2554, 2569, 2583, 2586, 2615, 2642, 
   2709, 2726, 2750, 2782, 2796, 2812, 2817, 2821, 2823, 2895, 
   2922, 2931, 2964, 2987, 2991, 3009, 3026, 3026, 3045, 3051, 
   3075, 3132, 3145, 3168, 3194, 3201, 3240, 3242, 3264, 3266, 
   3294, 3315, 3331, 3349, 3351, 3353, 3375, 3388, 3408, 3430, 
   3431, 3446, 3461, 3482, 3483, 3508, 3517, 3532, 3555, 3572, 
   3580, 3592, 3593, 3602, 3634, 3652, 3712, 3713, 3730, 3737, 
   3742, 3827, 3842, 3858, 3868, 3881, 3924, 3931, 4086, 4105, 
   4114, 4132, 4221, 4243, 4246, 4256, 4263, 4267, 4343, 4348, 
   4371, 4381, 4382, 4396, 4416, 4455, 4468, 4487, 4515, 4519, 
   4523, 4527, 4568, 4568, 4614, 4636, 4641, 4649, 4674, 4677, 
   4685, 4694, 4712, 4715, 4758, 4798, 4803, 4814, 4867, 4869, 
   4882, 4887, 4932, 4932, 4975, 4983, 5007, 5011, 5031, 5059, 
   5062, 5085, 5092, 5117, 5141, 5162, 5183, 5210, 5258, 5306, 
   5322, 5333, 5345, 5346, 5349, 5372, 5376, 5385, 5449, 5463, 
   5478, 5492, 5533, 5534, 5575, 5616, 5629, 5639, 5658, 5659, 
   5675, 5741, 5782, 5786, 5787, 5849, 5860, 5867, 5881, 5903, 
   5917, 5918, 5940, 5947, 5954, 5956, 5967, 5977, 5985, 5990, 
   5994, 5999, 6056, 6073, 6078, 6124, 6136, 6167, 6176, 6185, 
   6206, 6208, 6217, 6228, 6235, 6264, 6273, 6286, 6297, 6301, 
   6381, 6406, 6412, 6413, 6414, 6415, 6416, 6420, 6492, 6505, 
   6529, 6532, 6636, 6643, 6647, 6657, 6657, 6671, 6700, 6700, 
   6705, 6724, 6742, 6748, 6754, 6782, 6824, 6844, 6848, 6863, 
   6903, 6910, 6915, 6918, 6921, 6925, 6933, 6996, 7004, 7016, 
   7048, 7064, 7081, 7104, 7105, 7118, 7124, 7139, 7143, 7148, 
   7166, 7182, 7183, 7185, 7189, 7225, 7230, 7259, 7268, 7310, 
   7326, 7345, 7426, 7444, 7493, 7518, 7519, 7527, 7529, 7542, 
   7600, 7627, 7641, 7649, 7689, 7690, 7700, 7725, 7737, 7741, 
   7742, 7767, 7770, 7811, 7879, 7913, 7916, 7944, 7962, 7978, 
   8010, 8012, 8035, 8070, 8094, 8108, 8113, 8124, 8144, 8158, 
   8181, 8182, 8183, 8209, 8239, 8256, 8260, 8274, 8278, 8284, 
   8298, 8314, 8326, 8332, 8400, 8415, 8448, 8472, 8497, 8504, 
   8529, 8590, 8598, 8651, 8654, 8733, 8736, 8760, 8762, 8780, 
   8809, 8815, 8822, 8846, 8856, 8885, 8904, 8931, 8954, 8984, 
   9020, 9029, 9044, 9052, 9055, 9070, 9078, 9085, 9127, 9133, 
   9139, 9161, 9169, 9179, 9187, 9188, 9242, 9245, 9280, 9358, 
   9364, 9377, 9408, 9415, 9462, 9477, 9501, 9510, 9575, 9594, 
   9601, 9640, 9646, 9680, 9688, 9723, 9749, 9761, 9778, 9792, 
   9815, 9826, 9836, 9840, 9890, 9916, 9924, 9933, 9937, 9956, 
    ]

Saludos

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 27 de Marzo de 2014, 06:16:27

Otro programa para ordenar.
Este se basa en el algoritmo de la inserción binaria. Realiza menos comparaciones entre elementos, pero hace más movimientos entre ellos.

El resultado es un algoritmo en teoría más rápido con sólo 67337 tics frente a los 126247 tics del algoritmo anterior:
Comparaciones = 3790
Movimientos = 63547
Total = 67337

En la práctica el algoritmo maneja muchos datos auxiliares que lo ralentizan. Si la comparación o movimiento de los datos no cuesta mucho, estos cálculos adicionales también deberán tenerse en cuenta.

Código: Python

"""Algoritmo de ordenacion de datos por insercion binaria"""
def insercion_binaria(data):
   comps = 0
   moves = 0
 
   for i in range(1, len(data)):
      moves += 1
      temp = data[i]
      
      pos1 = 0
      pos2 = i-1
      while(pos1 <= pos2):
         medio = (pos1 + pos2) // 2
         comps += 1
         if data[medio] > temp:
            pos2 = medio - 1
         else:
            pos1 = medio + 1
      j = i - 1
      while (j >= pos1):
          moves += 1
          data[j+1] = data[j]
          j -= 1
      moves += 1
      data[pos1] = temp
   return comps, moves
 
 
data = [
   1497, 2094, 8094, 3331, 1126, 0736, 5999, 9688, 3593, 3353,
   3555, 9778, 4371, 2817, 9020, 2504, 6217, 2796, 8904, 0764,
   6700, 4105, 4468, 8504, 3201, 7426, 8780, 7518, 8846, 6228,
   3026, 2895, 3145, 1950, 4887, 0542, 8124, 3730, 7725, 4798, 
   8733, 1024, 7326,  669, 5985, 4882, 5867, 2991, 4641, 1964, 
   9245, 0501, 6406, 9280, 7916, 9477, 7166, 5616, 5183, 6264, 
   1024, 6136, 1894, 2402, 6529, 9646, 9749, 1208,  909, 6844, 
   7741, 2101, 8181, 8332, 1594, 9510, 9052, 1812, 1105, 3009, 
   5306, 4086, 6918, 5059, 6416, 7600, 7700, 4758, 7016, 3580, 
   7689, 5376, 7879, 1153,  945, 8274,  790, 8415, 9890, 1811, 
   5117, 5787, 3264, 6903,  555, 1337, 5062, 5881, 3592, 5533, 
   6056, 9723, 5849, 0352, 7148, 6921, 4568, 2615, 7105, 4869, 
   4685, 2987,   86, 6671, 8651, 3713, 6700, 5162, 6996, 8931, 
   7627, 1921, 6782, 2964, 1723, 2496, 6492, 1102, 3194, 6286, 
   9070, 8809, 8284, 3924, 6185, 6910, 9044, 4132, 0421, 6176, 
   0003, 4527, 7189,  268, 7978, 3881, 2497, 1252, 2330, 4674, 
   6657, 3652, 7182, 1810, 2569, 1545, 1963, 3168, 3266, 6167, 
   9575, 0200, 7064, 3931, 6748, 8158, 4523, 2391, 4649, 4348, 
   8598, 3430, 4983, 9916, 5575, 2091, 5675, 8954, 0761, 3242, 
   7649, 3842, 6078, 1123, 8144, 1939, 4487, 6824, 5786, 4455, 
   9169, 2353, 7104, 0014, 3532, 6235, 3737, 3446, 8497, 1608, 
   5947, 9078, 0411, 9139, 2823, 3858, 7542, 2447,  629,  799, 
    932, 2034, 7641, 6301, 9415, 0024, 8822, 4243, 5918, 7770, 
   3517, 3742, 8472, 9127, 3351, 8108, 6206, 9826, 9462, 3508, 
     94, 8209, 5372, 9358, 0223, 7268, 9840, 8529,  771, 3572, 
   9937, 7143, 3051, 8448, 5031, 4636, 8590, 3294, 5210, 5741, 
   3634, 9242, 8400, 5990, 8113, 1154, 1555, 5658, 9085, 9179, 
   8736, 4712, 6754, 5967, 6848, 7139, 9501, 6505, 5333, 3315, 
   7737, 7527, 5977, 6657, 2070, 1140, 5534, 9133, 7690, 5258, 
   6915,  792, 9924, 9933, 9601, 5346, 9188, 2199, 1091, 7259, 
   4932,  242, 8314, 8326, 1129, 7811, 1933, 4677, 4867, 3075, 
   3132,  810, 9029,  727, 9055, 5940, 1442, 5141,  459,  627, 
   9792, 3026, 8012, 8760, 5954, 2642, 2583, 7230, 3431, 2174, 
   8984, 4221, 2782, 7529, 6415, 2073, 9761, 5659, 6208,  559, 
   3602, 6420, 5917,  489, 4267, 0675, 4343, 4515, 3388, 5903, 
   7493, 3408, 5463, 7913, 7004, 1043, 5956, 8239, 4803, 6724, 
   6532, 8070,  550, 7118, 2546, 4519, 7225, 7742, 9187, 6297, 
   8010,  691,   27, 2058, 4568, 5860, 2821, 9680, 5322, 3375, 
   7767, 2586, 8182, 0500, 2286, 9836, 4814, 5092,  969, 7444, 
   5085,  487, 8035, 3482, 4246, 0361, 7185, 3827, 6742, 6705, 
   4416, 2750,  989, 4263, 9161, 7310, 6412, 5782, 1174, 0307, 
   4382, 0464, 7345, 5385, 5629, 0465, 8815, 2334, 9408, 1466, 
   3045, 8856, 4975, 5449, 1861, 7048, 9815, 8885, 5492, 5345, 
   3349, 6925, 6863, 1659, 6273, 8183,  341, 3461,  952, 2726, 
   6124, 3483, 6073, 1571, 4614, 8278, 3868, 7124, 8762, 8298, 
   5478, 6643, 7519, 9364, 4932, 2554, 1261, 9594, 7183, 0345, 
   3712, 6647, 9640,  370, 8654, 4381, 7962, 4694, 2931, 5007, 
    685, 6414, 5349, 4396, 5994, 7944, 5011, 2190, 3240, 9377, 
   4256, 8256, 6413, 9956, 2922, 1004, 2709, 0215, 5639, 7081, 
   8260, 2812, 6636, 2429, 4114, 4715, 6381, 6933, 2137,  378,
]
 
 
#main program
comps, moves = insercion_binaria(data)
print "Comparaciones =", comps
print "Movimientos =", moves
print "Tics =", comps + moves
print "Data = [\n  ",
print "".join(["%04d" % data[i] + ", " + "\n   "*((i+1)%10==0) for i in range(0, len(data))]),
print "]"

Resultado:

Código: [Seleccionar]

Comparaciones = 3790
Movimientos = 63547
Tics = 67337
Data = [
   0003, 0012, 0020, 0027, 0086, 0094, 0128, 0141, 0147, 0199, 
   0229, 0234, 0241, 0242, 0265, 0268, 0273, 0308, 0309, 0320, 
   0321, 0341, 0354, 0370, 0378, 0445, 0459, 0478, 0487, 0489, 
   0497, 0500, 0550, 0555, 0559, 0627, 0629, 0669, 0685, 0691, 
   0727, 0771, 0790, 0792, 0799, 0810, 0909, 0932, 0945, 0952, 
   0969, 0989, 1004, 1024, 1024, 1043, 1091, 1102, 1105, 1123, 
   1126, 1129, 1140, 1153, 1154, 1174, 1208, 1252, 1261, 1337, 
   1442, 1466, 1497, 1545, 1555, 1571, 1594, 1608, 1659, 1723, 
   1810, 1811, 1812, 1861, 1894, 1921, 1933, 1939, 1950, 1963, 
   1964, 2034, 2058, 2070, 2073, 2091, 2094, 2101, 2137, 2174, 
   2190, 2199, 2286, 2330, 2334, 2353, 2391, 2402, 2429, 2447, 
   2496, 2497, 2504, 2546, 2554, 2569, 2583, 2586, 2615, 2642, 
   2709, 2726, 2750, 2782, 2796, 2812, 2817, 2821, 2823, 2895, 
   2922, 2931, 2964, 2987, 2991, 3009, 3026, 3026, 3045, 3051, 
   3075, 3132, 3145, 3168, 3194, 3201, 3240, 3242, 3264, 3266, 
   3294, 3315, 3331, 3349, 3351, 3353, 3375, 3388, 3408, 3430, 
   3431, 3446, 3461, 3482, 3483, 3508, 3517, 3532, 3555, 3572, 
   3580, 3592, 3593, 3602, 3634, 3652, 3712, 3713, 3730, 3737, 
   3742, 3827, 3842, 3858, 3868, 3881, 3924, 3931, 4086, 4105, 
   4114, 4132, 4221, 4243, 4246, 4256, 4263, 4267, 4343, 4348, 
   4371, 4381, 4382, 4396, 4416, 4455, 4468, 4487, 4515, 4519, 
   4523, 4527, 4568, 4568, 4614, 4636, 4641, 4649, 4674, 4677, 
   4685, 4694, 4712, 4715, 4758, 4798, 4803, 4814, 4867, 4869, 
   4882, 4887, 4932, 4932, 4975, 4983, 5007, 5011, 5031, 5059, 
   5062, 5085, 5092, 5117, 5141, 5162, 5183, 5210, 5258, 5306, 
   5322, 5333, 5345, 5346, 5349, 5372, 5376, 5385, 5449, 5463, 
   5478, 5492, 5533, 5534, 5575, 5616, 5629, 5639, 5658, 5659, 
   5675, 5741, 5782, 5786, 5787, 5849, 5860, 5867, 5881, 5903, 
   5917, 5918, 5940, 5947, 5954, 5956, 5967, 5977, 5985, 5990, 
   5994, 5999, 6056, 6073, 6078, 6124, 6136, 6167, 6176, 6185, 
   6206, 6208, 6217, 6228, 6235, 6264, 6273, 6286, 6297, 6301, 
   6381, 6406, 6412, 6413, 6414, 6415, 6416, 6420, 6492, 6505, 
   6529, 6532, 6636, 6643, 6647, 6657, 6657, 6671, 6700, 6700, 
   6705, 6724, 6742, 6748, 6754, 6782, 6824, 6844, 6848, 6863, 
   6903, 6910, 6915, 6918, 6921, 6925, 6933, 6996, 7004, 7016, 
   7048, 7064, 7081, 7104, 7105, 7118, 7124, 7139, 7143, 7148, 
   7166, 7182, 7183, 7185, 7189, 7225, 7230, 7259, 7268, 7310, 
   7326, 7345, 7426, 7444, 7493, 7518, 7519, 7527, 7529, 7542, 
   7600, 7627, 7641, 7649, 7689, 7690, 7700, 7725, 7737, 7741, 
   7742, 7767, 7770, 7811, 7879, 7913, 7916, 7944, 7962, 7978, 
   8010, 8012, 8035, 8070, 8094, 8108, 8113, 8124, 8144, 8158, 
   8181, 8182, 8183, 8209, 8239, 8256, 8260, 8274, 8278, 8284, 
   8298, 8314, 8326, 8332, 8400, 8415, 8448, 8472, 8497, 8504, 
   8529, 8590, 8598, 8651, 8654, 8733, 8736, 8760, 8762, 8780, 
   8809, 8815, 8822, 8846, 8856, 8885, 8904, 8931, 8954, 8984, 
   9020, 9029, 9044, 9052, 9055, 9070, 9078, 9085, 9127, 9133, 
   9139, 9161, 9169, 9179, 9187, 9188, 9242, 9245, 9280, 9358, 
   9364, 9377, 9408, 9415, 9462, 9477, 9501, 9510, 9575, 9594, 
   9601, 9640, 9646, 9680, 9688, 9723, 9749, 9761, 9778, 9792, 
   9815, 9826, 9836, 9840, 9890, 9916, 9924, 9933, 9937, 9956, 
    ]

Título: Re: Problemas sencillos de programación para resolver
Publicado por: rivale en 27 de Marzo de 2014, 12:40:36

Tengo este código

no esta tan optimizado como creí, me dió 126572 ticks

Código: C

int compara(int val1, int val2, long *t);
void printvector(int *v,int len);
void move(int *val1,int *val2, long *t);
 
int main(int argc, char* argv[])
{
        char a;
        int i=0,j=0;
        int len=500;            
        int temp;
        long ticks=0;
        char str[80];
 
        int m1[500]={
   1497, 2094, 8094, 3331, 1126, 0736, 5999, 9688, 3593, 3353,
   3555, 9778, 4371, 2817, 9020, 2504, 6217, 2796, 8904, 0764,
   6700, 4105, 4468, 8504, 3201, 7426, 8780, 7518, 8846, 6228,
   3026, 2895, 3145, 1950, 4887, 0542, 8124, 3730, 7725, 4798, 
   8733, 1024, 7326,  669, 5985, 4882, 5867, 2991, 4641, 1964, 
   9245, 0501, 6406, 9280, 7916, 9477, 7166, 5616, 5183, 6264, 
   1024, 6136, 1894, 2402, 6529, 9646, 9749, 1208,  909, 6844, 
   7741, 2101, 8181, 8332, 1594, 9510, 9052, 1812, 1105, 3009, 
   5306, 4086, 6918, 5059, 6416, 7600, 7700, 4758, 7016, 3580, 
   7689, 5376, 7879, 1153,  945, 8274,  790, 8415, 9890, 1811, 
   5117, 5787, 3264, 6903,  555, 1337, 5062, 5881, 3592, 5533, 
   6056, 9723, 5849, 0352, 7148, 6921, 4568, 2615, 7105, 4869, 
   4685, 2987,   86, 6671, 8651, 3713, 6700, 5162, 6996, 8931, 
   7627, 1921, 6782, 2964, 1723, 2496, 6492, 1102, 3194, 6286, 
   9070, 8809, 8284, 3924, 6185, 6910, 9044, 4132, 0421, 6176, 
   0003, 4527, 7189,  268, 7978, 3881, 2497, 1252, 2330, 4674, 
   6657, 3652, 7182, 1810, 2569, 1545, 1963, 3168, 3266, 6167, 
   9575, 0200, 7064, 3931, 6748, 8158, 4523, 2391, 4649, 4348, 
   8598, 3430, 4983, 9916, 5575, 2091, 5675, 8954, 0761, 3242, 
   7649, 3842, 6078, 1123, 8144, 1939, 4487, 6824, 5786, 4455, 
   9169, 2353, 7104, 0014, 3532, 6235, 3737, 3446, 8497, 1608, 
   5947, 9078, 0411, 9139, 2823, 3858, 7542, 2447,  629,  799, 
    932, 2034, 7641, 6301, 9415, 0024, 8822, 4243, 5918, 7770, 
   3517, 3742, 8472, 9127, 3351, 8108, 6206, 9826, 9462, 3508, 
     94, 8209, 5372, 9358, 0223, 7268, 9840, 8529,  771, 3572, 
   9937, 7143, 3051, 8448, 5031, 4636, 8590, 3294, 5210, 5741, 
   3634, 9242, 8400, 5990, 8113, 1154, 1555, 5658, 9085, 9179, 
   8736, 4712, 6754, 5967, 6848, 7139, 9501, 6505, 5333, 3315, 
   7737, 7527, 5977, 6657, 2070, 1140, 5534, 9133, 7690, 5258, 
   6915,  792, 9924, 9933, 9601, 5346, 9188, 2199, 1091, 7259, 
   4932,  242, 8314, 8326, 1129, 7811, 1933, 4677, 4867, 3075, 
   3132,  810, 9029,  727, 9055, 5940, 1442, 5141,  459,  627, 
   9792, 3026, 8012, 8760, 5954, 2642, 2583, 7230, 3431, 2174, 
   8984, 4221, 2782, 7529, 6415, 2073, 9761, 5659, 6208,  559, 
   3602, 6420, 5917,  489, 4267, 0675, 4343, 4515, 3388, 5903, 
   7493, 3408, 5463, 7913, 7004, 1043, 5956, 8239, 4803, 6724, 
   6532, 8070,  550, 7118, 2546, 4519, 7225, 7742, 9187, 6297, 
   8010,  691,   27, 2058, 4568, 5860, 2821, 9680, 5322, 3375, 
   7767, 2586, 8182, 0500, 2286, 9836, 4814, 5092,  969, 7444, 
   5085,  487, 8035, 3482, 4246, 0361, 7185, 3827, 6742, 6705, 
   4416, 2750,  989, 4263, 9161, 7310, 6412, 5782, 1174, 0307, 
   4382, 0464, 7345, 5385, 5629, 0465, 8815, 2334, 9408, 1466, 
   3045, 8856, 4975, 5449, 1861, 7048, 9815, 8885, 5492, 5345, 
   3349, 6925, 6863, 1659, 6273, 8183,  341, 3461,  952, 2726, 
   6124, 3483, 6073, 1571, 4614, 8278, 3868, 7124, 8762, 8298, 
   5478, 6643, 7519, 9364, 4932, 2554, 1261, 9594, 7183, 0345, 
   3712, 6647, 9640,  370, 8654, 4381, 7962, 4694, 2931, 5007, 
    685, 6414, 5349, 4396, 5994, 7944, 5011, 2190, 3240, 9377, 
   4256, 8256, 6413, 9956, 2922, 1004, 2709, 0215, 5639, 7081, 
   8260, 2812, 6636, 2429, 4114, 4715, 6381, 6933, 2137,  378,
        };
 
 
        
         printvector(m1,len);
//      
        for(i=1;i<(len);i++)
        {               
                if(compara(m1[i],m1[i-1],&ticks))
                {                       
                        j=i-1;
                        move(&temp,&m1[i],&ticks);                      
                        move(&m1[i],&m1[i-1],&ticks);
                
                        while((j>=1))
                        {                       
                                if(!compara(temp,m1[j-1],&ticks))
                                {                                       
                                        
                                        break;
                                }       
                                move(&m1[j],&m1[j-1],&ticks);
                                j--;                            
                                
                        }
                        move(&m1[j],&temp,&ticks);
                }
        
                
        }
        printvector(m1,len);
        sprintf(str,"ticks:%d\n;",ticks);
                printf(str);
        
 
        a=getchar();
        return 0;
}
 
 
int compara(int val1, int val2, long *t)
{
        *t=*t+1;
        if(val1<val2)return 1;
        else return 0;
}
 
 
void printvector(int *v,int len)
{
        int i;
                char outt[20];
 
        for(i=0;i<(len);i++)
        {
                sprintf(outt,"%i;",v[i]);
                printf(outt);
                        
        }
        printf("\n");
}
 
void move(int *val1,int *val2, long *t)
{
        
        *val1=*val2;
        *t=*t+1;
}

Título: Re: Problemas sencillos de programación para resolver
Publicado por: SavageChicken en 27 de Marzo de 2014, 13:50:28

Tengo entendido que uno de los métodos más pobres es el algoritmo burbuja.
Aquí hay amplia información al respecto e información de su rendimiento frente a otros algoritmos.

http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja

Salud 8)

Título: Re: Problemas sencillos de programación para resolver
Publicado por: SavageChicken en 27 de Marzo de 2014, 13:53:50

Aquí información de una buena cantidad de métodos de ordenamiento.

http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento

Salud 8)

Título: Re: Problemas sencillos de programación para resolver
Publicado por: rivale en 27 de Marzo de 2014, 13:55:34

creo que ese es el que hice (el de burbuja), creo que el mas eficiente era uno que se llama "rápido".

aca viene explicado:

http://blog.zerial.org/ficheros/Informe_Ordenamiento.pdf (http://blog.zerial.org/ficheros/Informe_Ordenamiento.pdf)

Título: Re: Problemas sencillos de programación para resolver
Publicado por: PalitroqueZ en 27 de Marzo de 2014, 14:01:16

para mi, el mejor código programado es aquel que haga exactamente lo que debe hacer sin importar si se lleva 10 lineas o 100 lineas, la eficiencia es algo dificil de conseguir estos dias con tanto framework y capas de portabilidad. si quiero velocidad me voy por ensamblador

Título: Re: Problemas sencillos de programación para resolver
Publicado por: rivale en 27 de Marzo de 2014, 14:05:39

Cita de: PalitroqueZ en 27 de Marzo de 2014, 14:01:16

para mi, el mejor código programado es aquel que haga exactamente lo que debe hacer, la eficiencia es algo dificil de conseguir estos dias con tanto framework y capas de portabilidad. si quiero velocidad me voy por ensamblador

Eso sería dentro de un micro, pero si estas realizando un programa para PC o para algún teléfono, a veces si es necesario optimizar el código para tratar de reducir el consumo del procesador

Título: Re: Problemas sencillos de programación para resolver
Publicado por: PalitroqueZ en 27 de Marzo de 2014, 14:14:34

Cita de: rivale en 27 de Marzo de 2014, 14:05:39

Cita de: PalitroqueZ en 27 de Marzo de 2014, 14:01:16
para mi, el mejor código programado es aquel que haga exactamente lo que debe hacer, la eficiencia es algo dificil de conseguir estos dias con tanto framework y capas de portabilidad. si quiero velocidad me voy por ensamblador

Eso sería dentro de un micro, pero si estas realizando un programa para PC o para algún teléfono, a veces si es necesario optimizar el código para tratar de reducir el consumo del procesador

mas bien lo decía precisamente por eso, podremos reducir el código hasta el mínimo ideal, pero tendriamos que tomar en cuenta, el consumo de recursos que utiliza el net framework (para el visual studio) o el JVM (para el caso de java).

en el caso de los microcontroladores, la unica razón valida que veo para optimizar el código, es la limitación de hardware

Título: Re: Problemas sencillos de programación para resolver
Publicado por: rivale en 27 de Marzo de 2014, 14:19:41

Cita de: PalitroqueZ en 27 de Marzo de 2014, 14:14:34

mas bien lo decía precisamente por eso, podremos reducir el código hasta el mínimo ideal, pero tendriamos que tomar en cuenta, el consumo de recursos que utiliza el net framework (para el visual studio) o el JVM (para el caso de java).

en el caso de los microcontroladores, la unica razón valida que veo para optimizar el código, es la limitación de hardware

++;
:mrgreen:

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 27 de Marzo de 2014, 18:46:25

Los algoritmos que he puesto hasta ahora son algoritmos lentos.
Los algoritmos lentos tienen una complejidad O(n^2), que significa que el número de operaciones que necesitan para ordenar la lista depende del cuadrado del número de elementos de la lista.
Para una lista de 500 elementos, los algoritmos lentos necesitan un número de operaciones proporcional a 500^2 = 250000.

ALGORITMOS LENTOS:

Método de burbuja:
Como rivale ha comprobado, es mejor no utilizarlo nunca. Es demasiado lento.

Selección directa:
Busco el elemento más pequeño dentro de la lista de elementos no ordenados y lo coloco en otro montón.
Repito el primer paso hasta que todos los elementos estén ordenados.

Inserción directa:
Tomo el primer elemento de la lista. Busco cual es su lugar dentro de los elementos que ya están ordenados y lo coloco ahí.
Repito el primer paso hasta que todos los elementos estén ordenados.

Inserción binaria:
Es una variación del método anterior que mejora su velocidad. A la hora de buscar el sitio que le corresponde a un elemento dentro de la lista de elementos ordenados, puedo ir mirando uno a uno o hacerlo de forma binaria:
Miro en el medio de la lista de elementos ordenados. Si el elemento es mayor, descarto la mitad más pequeña y me quedo con la otra. Repito el proceso hasta encontrar su sitio. Como la lista se divide por la mitad en cada búsqueda, es mucho más rápido que buscar uno a uno su puesto.

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 27 de Marzo de 2014, 19:05:40

La ventaja del método de selección es que siempre tarda lo mismo, independientemente de cómo estén ordenados los elementos en la lista. De hecho en ocasiones puede ser más lento que el algoritmo de burbuja (en el caso de elementos casi ordenados).

Por su parte el método de inserción es muy rápido cuando la lista está ya ordenada, pero lento cuando la lista está desordenada (igual que el método de burbuja).

Algoritmo Shell o Shellsort:
Este algoritmo que está a medio camino entre los lentos y los rápidos. Es una mejora del algoritmo de inserción que pretende darle más velocidad en el caso de que los elementos estén desordenados.
Al igual que el algoritmo de inserción, su tiempo de ejecución depende de la ordenación de los elementos de la lista.

La desventaja que tiene es que resulta más difícil de implementar que los métodos anteriores.

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 27 de Marzo de 2014, 19:31:24

Algoritmo de ordenación Shellsort
Este algoritmo empieza de verdad a mejorar las cosas. No es tan bueno como los algoritmos rápidos, pero mejora bastante los algoritmos lentos en el caso de datos desordenados:

Comparaciones = 5936
Movimientos = 8984
Tics = 14920

Código del programa en Python:

Código: Python

"""Algoritmo de ordenacion de datos Shellsort"""
def shellsort(datos):
   comps = 0
   moves = 0
 
   p = len(datos) // 2
   while(p>0):
      for i in range(p, len(datos)):
         moves += 1
         temp = datos[i]
         j = i
 
         while (j >= p and temp < datos[j-p]):
            comps += 1
            moves += 1
            datos[j] = datos[j - p]
            j -= p
         comps += 1
         moves += 1
         datos[j] = temp
         
      if (p == 2):
         p = 1
      else:
         p = int(p / 2.2)
 
   return comps, moves
 
 
datos = [
   1497, 2094, 8094, 3331, 1126, 0736, 5999, 9688, 3593, 3353,
   3555, 9778, 4371, 2817, 9020, 2504, 6217, 2796, 8904, 0764,
   6700, 4105, 4468, 8504, 3201, 7426, 8780, 7518, 8846, 6228,
   3026, 2895, 3145, 1950, 4887, 0542, 8124, 3730, 7725, 4798, 
   8733, 1024, 7326,  669, 5985, 4882, 5867, 2991, 4641, 1964, 
   9245, 0501, 6406, 9280, 7916, 9477, 7166, 5616, 5183, 6264, 
   1024, 6136, 1894, 2402, 6529, 9646, 9749, 1208,  909, 6844, 
   7741, 2101, 8181, 8332, 1594, 9510, 9052, 1812, 1105, 3009, 
   5306, 4086, 6918, 5059, 6416, 7600, 7700, 4758, 7016, 3580, 
   7689, 5376, 7879, 1153,  945, 8274,  790, 8415, 9890, 1811, 
   5117, 5787, 3264, 6903,  555, 1337, 5062, 5881, 3592, 5533, 
   6056, 9723, 5849, 0352, 7148, 6921, 4568, 2615, 7105, 4869, 
   4685, 2987,   86, 6671, 8651, 3713, 6700, 5162, 6996, 8931, 
   7627, 1921, 6782, 2964, 1723, 2496, 6492, 1102, 3194, 6286, 
   9070, 8809, 8284, 3924, 6185, 6910, 9044, 4132, 0421, 6176, 
   0003, 4527, 7189,  268, 7978, 3881, 2497, 1252, 2330, 4674, 
   6657, 3652, 7182, 1810, 2569, 1545, 1963, 3168, 3266, 6167, 
   9575, 0200, 7064, 3931, 6748, 8158, 4523, 2391, 4649, 4348, 
   8598, 3430, 4983, 9916, 5575, 2091, 5675, 8954, 0761, 3242, 
   7649, 3842, 6078, 1123, 8144, 1939, 4487, 6824, 5786, 4455, 
   9169, 2353, 7104, 0014, 3532, 6235, 3737, 3446, 8497, 1608, 
   5947, 9078, 0411, 9139, 2823, 3858, 7542, 2447,  629,  799, 
    932, 2034, 7641, 6301, 9415, 0024, 8822, 4243, 5918, 7770, 
   3517, 3742, 8472, 9127, 3351, 8108, 6206, 9826, 9462, 3508, 
     94, 8209, 5372, 9358, 0223, 7268, 9840, 8529,  771, 3572, 
   9937, 7143, 3051, 8448, 5031, 4636, 8590, 3294, 5210, 5741, 
   3634, 9242, 8400, 5990, 8113, 1154, 1555, 5658, 9085, 9179, 
   8736, 4712, 6754, 5967, 6848, 7139, 9501, 6505, 5333, 3315, 
   7737, 7527, 5977, 6657, 2070, 1140, 5534, 9133, 7690, 5258, 
   6915,  792, 9924, 9933, 9601, 5346, 9188, 2199, 1091, 7259, 
   4932,  242, 8314, 8326, 1129, 7811, 1933, 4677, 4867, 3075, 
   3132,  810, 9029,  727, 9055, 5940, 1442, 5141,  459,  627, 
   9792, 3026, 8012, 8760, 5954, 2642, 2583, 7230, 3431, 2174, 
   8984, 4221, 2782, 7529, 6415, 2073, 9761, 5659, 6208,  559, 
   3602, 6420, 5917,  489, 4267, 0675, 4343, 4515, 3388, 5903, 
   7493, 3408, 5463, 7913, 7004, 1043, 5956, 8239, 4803, 6724, 
   6532, 8070,  550, 7118, 2546, 4519, 7225, 7742, 9187, 6297, 
   8010,  691,   27, 2058, 4568, 5860, 2821, 9680, 5322, 3375, 
   7767, 2586, 8182, 0500, 2286, 9836, 4814, 5092,  969, 7444, 
   5085,  487, 8035, 3482, 4246, 0361, 7185, 3827, 6742, 6705, 
   4416, 2750,  989, 4263, 9161, 7310, 6412, 5782, 1174, 0307, 
   4382, 0464, 7345, 5385, 5629, 0465, 8815, 2334, 9408, 1466, 
   3045, 8856, 4975, 5449, 1861, 7048, 9815, 8885, 5492, 5345, 
   3349, 6925, 6863, 1659, 6273, 8183,  341, 3461,  952, 2726, 
   6124, 3483, 6073, 1571, 4614, 8278, 3868, 7124, 8762, 8298, 
   5478, 6643, 7519, 9364, 4932, 2554, 1261, 9594, 7183, 0345, 
   3712, 6647, 9640,  370, 8654, 4381, 7962, 4694, 2931, 5007, 
    685, 6414, 5349, 4396, 5994, 7944, 5011, 2190, 3240, 9377, 
   4256, 8256, 6413, 9956, 2922, 1004, 2709, 0215, 5639, 7081, 
   8260, 2812, 6636, 2429, 4114, 4715, 6381, 6933, 2137,  378,
]
 
 
#main program
comps, moves = shellsort(datos)
print "Comparaciones =", comps
print "Movimientos =", moves
print "Tics =", comps + moves
print "Datos = [\n  ",
print "".join(["%04d" % datos[i] + ", " + "\n   "*((i+1)%10==0) for i in range(0, len(datos))]),
print "]"

Resultado:

Código: [Seleccionar]

Comparaciones = 5936
Movimientos = 8984
Tics = 14920
Datos = [
   0003, 0012, 0020, 0027, 0086, 0094, 0128, 0141, 0147, 0199, 
   0229, 0234, 0241, 0242, 0265, 0268, 0273, 0308, 0309, 0320, 
   0321, 0341, 0354, 0370, 0378, 0445, 0459, 0478, 0487, 0489, 
   0497, 0500, 0550, 0555, 0559, 0627, 0629, 0669, 0685, 0691, 
   0727, 0771, 0790, 0792, 0799, 0810, 0909, 0932, 0945, 0952, 
   0969, 0989, 1004, 1024, 1024, 1043, 1091, 1102, 1105, 1123, 
   1126, 1129, 1140, 1153, 1154, 1174, 1208, 1252, 1261, 1337, 
   1442, 1466, 1497, 1545, 1555, 1571, 1594, 1608, 1659, 1723, 
   1810, 1811, 1812, 1861, 1894, 1921, 1933, 1939, 1950, 1963, 
   1964, 2034, 2058, 2070, 2073, 2091, 2094, 2101, 2137, 2174, 
   2190, 2199, 2286, 2330, 2334, 2353, 2391, 2402, 2429, 2447, 
   2496, 2497, 2504, 2546, 2554, 2569, 2583, 2586, 2615, 2642, 
   2709, 2726, 2750, 2782, 2796, 2812, 2817, 2821, 2823, 2895, 
   2922, 2931, 2964, 2987, 2991, 3009, 3026, 3026, 3045, 3051, 
   3075, 3132, 3145, 3168, 3194, 3201, 3240, 3242, 3264, 3266, 
   3294, 3315, 3331, 3349, 3351, 3353, 3375, 3388, 3408, 3430, 
   3431, 3446, 3461, 3482, 3483, 3508, 3517, 3532, 3555, 3572, 
   3580, 3592, 3593, 3602, 3634, 3652, 3712, 3713, 3730, 3737, 
   3742, 3827, 3842, 3858, 3868, 3881, 3924, 3931, 4086, 4105, 
   4114, 4132, 4221, 4243, 4246, 4256, 4263, 4267, 4343, 4348, 
   4371, 4381, 4382, 4396, 4416, 4455, 4468, 4487, 4515, 4519, 
   4523, 4527, 4568, 4568, 4614, 4636, 4641, 4649, 4674, 4677, 
   4685, 4694, 4712, 4715, 4758, 4798, 4803, 4814, 4867, 4869, 
   4882, 4887, 4932, 4932, 4975, 4983, 5007, 5011, 5031, 5059, 
   5062, 5085, 5092, 5117, 5141, 5162, 5183, 5210, 5258, 5306, 
   5322, 5333, 5345, 5346, 5349, 5372, 5376, 5385, 5449, 5463, 
   5478, 5492, 5533, 5534, 5575, 5616, 5629, 5639, 5658, 5659, 
   5675, 5741, 5782, 5786, 5787, 5849, 5860, 5867, 5881, 5903, 
   5917, 5918, 5940, 5947, 5954, 5956, 5967, 5977, 5985, 5990, 
   5994, 5999, 6056, 6073, 6078, 6124, 6136, 6167, 6176, 6185, 
   6206, 6208, 6217, 6228, 6235, 6264, 6273, 6286, 6297, 6301, 
   6381, 6406, 6412, 6413, 6414, 6415, 6416, 6420, 6492, 6505, 
   6529, 6532, 6636, 6643, 6647, 6657, 6657, 6671, 6700, 6700, 
   6705, 6724, 6742, 6748, 6754, 6782, 6824, 6844, 6848, 6863, 
   6903, 6910, 6915, 6918, 6921, 6925, 6933, 6996, 7004, 7016, 
   7048, 7064, 7081, 7104, 7105, 7118, 7124, 7139, 7143, 7148, 
   7166, 7182, 7183, 7185, 7189, 7225, 7230, 7259, 7268, 7310, 
   7326, 7345, 7426, 7444, 7493, 7518, 7519, 7527, 7529, 7542, 
   7600, 7627, 7641, 7649, 7689, 7690, 7700, 7725, 7737, 7741, 
   7742, 7767, 7770, 7811, 7879, 7913, 7916, 7944, 7962, 7978, 
   8010, 8012, 8035, 8070, 8094, 8108, 8113, 8124, 8144, 8158, 
   8181, 8182, 8183, 8209, 8239, 8256, 8260, 8274, 8278, 8284, 
   8298, 8314, 8326, 8332, 8400, 8415, 8448, 8472, 8497, 8504, 
   8529, 8590, 8598, 8651, 8654, 8733, 8736, 8760, 8762, 8780, 
   8809, 8815, 8822, 8846, 8856, 8885, 8904, 8931, 8954, 8984, 
   9020, 9029, 9044, 9052, 9055, 9070, 9078, 9085, 9127, 9133, 
   9139, 9161, 9169, 9179, 9187, 9188, 9242, 9245, 9280, 9358, 
   9364, 9377, 9408, 9415, 9462, 9477, 9501, 9510, 9575, 9594, 
   9601, 9640, 9646, 9680, 9688, 9723, 9749, 9761, 9778, 9792, 
   9815, 9826, 9836, 9840, 9890, 9916, 9924, 9933, 9937, 9956, 
    ]

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 28 de Marzo de 2014, 07:35:45

Métodos rápidos de ordenación

Estos métodos tienen una complejidad computacional O(n·Log n). Esto significa que el número de operaciones necesarias para ordenar los elementos de la lista, es proporcional al número de elementos de la lista multiplicado por el logaritmo del número de elementos.
Para nuestro caso n=500 y el número de operaciones necesarias para ordenar la lista será proporcional a 500·Log 500 = 3107 operaciones.

Método HeapSort
Este método es bastante rápido y tiene una velocidad de ordenación constante, independientemente de cómo estén desordenados los datos.
Se basa en realizar dos tipos de operaciones. Primero se ordenan los datos en una estructura de montículo (http://es.wikipedia.org/wiki/Mont%C3%ADculo_%28inform%C3%A1tica%29). A continuación se ordena la estructura en montículo en una lista ordenada.
Este método no es recursivo.

Método QuickSort
Este es el que se considera método más rápido de ordenación de datos en memoria (sin necesidad de utilizar una memoria externa)
Para datos aleatorios tiene la mayor velocidad. Como inconveniente se puede comentar que la velocidad puede bajar mucho en ciertos casos particulares.
Por otro lado este es un algoritmo recursivo, por lo que será necesario guardar información extra sobre el punto en el que estamos trabajando. En microcontroladores con poca memoria esto puede ser una desventaja.

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 30 de Marzo de 2014, 05:05:04

Algoritmo de ordenación Heapsort:

Este algoritmo tiene la ventaja de presentar siempre un comportamiento rápido, independientemente de la ordenación de los datos de entrada:

Comparaciones = 7431
Movimientos = 6554
Tics = 13985

Código del programa en Python:

Código: Python

"""Algoritmo de ordenacion de datos Heapsort"""
def heapsort(datos):
   global n_comp, n_moves
   n_comp = n_moves  = 0
 
   # Crea la estructura de monticulo
   tam = len(datos)
   puntero = int((len(datos)-1)/2)
   while puntero>=0:
      cribar(datos, puntero, tam-1)
      puntero -= 1
 
   # Ordena monticulo
   puntero = len(datos)-1
   while puntero>0:
      n_moves += 3
      temp = datos[puntero]
      datos[puntero] = datos[0]
      datos[0] = temp
      puntero -= 1
      cribar(datos, 0, puntero)
   return n_comp, n_moves
   
 
def cribar(datos, datos_min, datos_max):
   global n_comp, n_moves
   down = datos_min * 2 + 1
   if (down > datos_max):
      return
   n_moves += 1
   temp = datos[datos_min]
   while down <= datos_max:
      if down < datos_max:
         n_comp += 1
         if datos[down+1] > datos[down]:
            down += 1
      n_comp += 1
      if temp > datos[down]:
         break
      n_moves += 1
      datos[datos_min] = datos[down]
      datos_min = down
      down = down * 2 + 1
   n_moves += 1
   datos[datos_min] = temp
 
 
datos = [
   1497, 2094, 8094, 3331, 1126, 0736, 5999, 9688, 3593, 3353,
   3555, 9778, 4371, 2817, 9020, 2504, 6217, 2796, 8904, 0764,
   6700, 4105, 4468, 8504, 3201, 7426, 8780, 7518, 8846, 6228,
   3026, 2895, 3145, 1950, 4887, 0542, 8124, 3730, 7725, 4798, 
   8733, 1024, 7326,  669, 5985, 4882, 5867, 2991, 4641, 1964, 
   9245, 0501, 6406, 9280, 7916, 9477, 7166, 5616, 5183, 6264, 
   1024, 6136, 1894, 2402, 6529, 9646, 9749, 1208,  909, 6844, 
   7741, 2101, 8181, 8332, 1594, 9510, 9052, 1812, 1105, 3009, 
   5306, 4086, 6918, 5059, 6416, 7600, 7700, 4758, 7016, 3580, 
   7689, 5376, 7879, 1153,  945, 8274,  790, 8415, 9890, 1811, 
   5117, 5787, 3264, 6903,  555, 1337, 5062, 5881, 3592, 5533, 
   6056, 9723, 5849, 0352, 7148, 6921, 4568, 2615, 7105, 4869, 
   4685, 2987,   86, 6671, 8651, 3713, 6700, 5162, 6996, 8931, 
   7627, 1921, 6782, 2964, 1723, 2496, 6492, 1102, 3194, 6286, 
   9070, 8809, 8284, 3924, 6185, 6910, 9044, 4132, 0421, 6176, 
   0003, 4527, 7189,  268, 7978, 3881, 2497, 1252, 2330, 4674, 
   6657, 3652, 7182, 1810, 2569, 1545, 1963, 3168, 3266, 6167, 
   9575, 0200, 7064, 3931, 6748, 8158, 4523, 2391, 4649, 4348, 
   8598, 3430, 4983, 9916, 5575, 2091, 5675, 8954, 0761, 3242, 
   7649, 3842, 6078, 1123, 8144, 1939, 4487, 6824, 5786, 4455, 
   9169, 2353, 7104, 0014, 3532, 6235, 3737, 3446, 8497, 1608, 
   5947, 9078, 0411, 9139, 2823, 3858, 7542, 2447,  629,  799, 
    932, 2034, 7641, 6301, 9415, 0024, 8822, 4243, 5918, 7770, 
   3517, 3742, 8472, 9127, 3351, 8108, 6206, 9826, 9462, 3508, 
     94, 8209, 5372, 9358, 0223, 7268, 9840, 8529,  771, 3572, 
   9937, 7143, 3051, 8448, 5031, 4636, 8590, 3294, 5210, 5741, 
   3634, 9242, 8400, 5990, 8113, 1154, 1555, 5658, 9085, 9179, 
   8736, 4712, 6754, 5967, 6848, 7139, 9501, 6505, 5333, 3315, 
   7737, 7527, 5977, 6657, 2070, 1140, 5534, 9133, 7690, 5258, 
   6915,  792, 9924, 9933, 9601, 5346, 9188, 2199, 1091, 7259, 
   4932,  242, 8314, 8326, 1129, 7811, 1933, 4677, 4867, 3075, 
   3132,  810, 9029,  727, 9055, 5940, 1442, 5141,  459,  627, 
   9792, 3026, 8012, 8760, 5954, 2642, 2583, 7230, 3431, 2174, 
   8984, 4221, 2782, 7529, 6415, 2073, 9761, 5659, 6208,  559, 
   3602, 6420, 5917,  489, 4267, 0675, 4343, 4515, 3388, 5903, 
   7493, 3408, 5463, 7913, 7004, 1043, 5956, 8239, 4803, 6724, 
   6532, 8070,  550, 7118, 2546, 4519, 7225, 7742, 9187, 6297, 
   8010,  691,   27, 2058, 4568, 5860, 2821, 9680, 5322, 3375, 
   7767, 2586, 8182, 0500, 2286, 9836, 4814, 5092,  969, 7444, 
   5085,  487, 8035, 3482, 4246, 0361, 7185, 3827, 6742, 6705, 
   4416, 2750,  989, 4263, 9161, 7310, 6412, 5782, 1174, 0307, 
   4382, 0464, 7345, 5385, 5629, 0465, 8815, 2334, 9408, 1466, 
   3045, 8856, 4975, 5449, 1861, 7048, 9815, 8885, 5492, 5345, 
   3349, 6925, 6863, 1659, 6273, 8183,  341, 3461,  952, 2726, 
   6124, 3483, 6073, 1571, 4614, 8278, 3868, 7124, 8762, 8298, 
   5478, 6643, 7519, 9364, 4932, 2554, 1261, 9594, 7183, 0345, 
   3712, 6647, 9640,  370, 8654, 4381, 7962, 4694, 2931, 5007, 
    685, 6414, 5349, 4396, 5994, 7944, 5011, 2190, 3240, 9377, 
   4256, 8256, 6413, 9956, 2922, 1004, 2709, 0215, 5639, 7081, 
   8260, 2812, 6636, 2429, 4114, 4715, 6381, 6933, 2137,  378,
]
 
 
#main program
n_comp, n_moves = heapsort(datos)
print "Comparaciones =", n_comp 
print "Movimientos =", n_moves
print "Tics =", n_comp + n_moves
print "Datos = [\n  ",
print "".join(["%04d" % datos[i] + ", " + "\n   "*((i+1)%10==0) for i in range(0, len(datos))]),
print "]"

Resultado:

Código: [Seleccionar]

Comparaciones = 7431
Movimientos = 6554
Tics = 13985
Datos = [
   0003, 0012, 0020, 0027, 0086, 0094, 0128, 0141, 0147, 0199, 
   0229, 0234, 0241, 0242, 0265, 0268, 0273, 0308, 0309, 0320, 
   0321, 0341, 0354, 0370, 0378, 0445, 0459, 0478, 0487, 0489, 
   0497, 0500, 0550, 0555, 0559, 0627, 0629, 0669, 0685, 0691, 
   0727, 0771, 0790, 0792, 0799, 0810, 0909, 0932, 0945, 0952, 
   0969, 0989, 1004, 1024, 1024, 1043, 1091, 1102, 1105, 1123, 
   1126, 1129, 1140, 1153, 1154, 1174, 1208, 1252, 1261, 1337, 
   1442, 1466, 1497, 1545, 1555, 1571, 1594, 1608, 1659, 1723, 
   1810, 1811, 1812, 1861, 1894, 1921, 1933, 1939, 1950, 1963, 
   1964, 2034, 2058, 2070, 2073, 2091, 2094, 2101, 2137, 2174, 
   2190, 2199, 2286, 2330, 2334, 2353, 2391, 2402, 2429, 2447, 
   2496, 2497, 2504, 2546, 2554, 2569, 2583, 2586, 2615, 2642, 
   2709, 2726, 2750, 2782, 2796, 2812, 2817, 2821, 2823, 2895, 
   2922, 2931, 2964, 2987, 2991, 3009, 3026, 3026, 3045, 3051, 
   3075, 3132, 3145, 3168, 3194, 3201, 3240, 3242, 3264, 3266, 
   3294, 3315, 3331, 3349, 3351, 3353, 3375, 3388, 3408, 3430, 
   3431, 3446, 3461, 3482, 3483, 3508, 3517, 3532, 3555, 3572, 
   3580, 3592, 3593, 3602, 3634, 3652, 3712, 3713, 3730, 3737, 
   3742, 3827, 3842, 3858, 3868, 3881, 3924, 3931, 4086, 4105, 
   4114, 4132, 4221, 4243, 4246, 4256, 4263, 4267, 4343, 4348, 
   4371, 4381, 4382, 4396, 4416, 4455, 4468, 4487, 4515, 4519, 
   4523, 4527, 4568, 4568, 4614, 4636, 4641, 4649, 4674, 4677, 
   4685, 4694, 4712, 4715, 4758, 4798, 4803, 4814, 4867, 4869, 
   4882, 4887, 4932, 4932, 4975, 4983, 5007, 5011, 5031, 5059, 
   5062, 5085, 5092, 5117, 5141, 5162, 5183, 5210, 5258, 5306, 
   5322, 5333, 5345, 5346, 5349, 5372, 5376, 5385, 5449, 5463, 
   5478, 5492, 5533, 5534, 5575, 5616, 5629, 5639, 5658, 5659, 
   5675, 5741, 5782, 5786, 5787, 5849, 5860, 5867, 5881, 5903, 
   5917, 5918, 5940, 5947, 5954, 5956, 5967, 5977, 5985, 5990, 
   5994, 5999, 6056, 6073, 6078, 6124, 6136, 6167, 6176, 6185, 
   6206, 6208, 6217, 6228, 6235, 6264, 6273, 6286, 6297, 6301, 
   6381, 6406, 6412, 6413, 6414, 6415, 6416, 6420, 6492, 6505, 
   6529, 6532, 6636, 6643, 6647, 6657, 6657, 6671, 6700, 6700, 
   6705, 6724, 6742, 6748, 6754, 6782, 6824, 6844, 6848, 6863, 
   6903, 6910, 6915, 6918, 6921, 6925, 6933, 6996, 7004, 7016, 
   7048, 7064, 7081, 7104, 7105, 7118, 7124, 7139, 7143, 7148, 
   7166, 7182, 7183, 7185, 7189, 7225, 7230, 7259, 7268, 7310, 
   7326, 7345, 7426, 7444, 7493, 7518, 7519, 7527, 7529, 7542, 
   7600, 7627, 7641, 7649, 7689, 7690, 7700, 7725, 7737, 7741, 
   7742, 7767, 7770, 7811, 7879, 7913, 7916, 7944, 7962, 7978, 
   8010, 8012, 8035, 8070, 8094, 8108, 8113, 8124, 8144, 8158, 
   8181, 8182, 8183, 8209, 8239, 8256, 8260, 8274, 8278, 8284, 
   8298, 8314, 8326, 8332, 8400, 8415, 8448, 8472, 8497, 8504, 
   8529, 8590, 8598, 8651, 8654, 8733, 8736, 8760, 8762, 8780, 
   8809, 8815, 8822, 8846, 8856, 8885, 8904, 8931, 8954, 8984, 
   9020, 9029, 9044, 9052, 9055, 9070, 9078, 9085, 9127, 9133, 
   9139, 9161, 9169, 9179, 9187, 9188, 9242, 9245, 9280, 9358, 
   9364, 9377, 9408, 9415, 9462, 9477, 9501, 9510, 9575, 9594, 
   9601, 9640, 9646, 9680, 9688, 9723, 9749, 9761, 9778, 9792, 
   9815, 9826, 9836, 9840, 9890, 9916, 9924, 9933, 9937, 9956, 
    ]

Saludos.

Título: Re: Problemas sencillos de programación para resolver
Publicado por: Picuino en 30 de Marzo de 2014, 05:19:49

Algoritmo de ordenación Quicksort:

Este algoritmo es el rey de los algoritmos de ordenación.
Tiene dos desventajas:
Es un algoritmo recursivo, por lo que necesita una pila o conjunto de datos para almacenar la posición de los subconjuntos que quedan por ordenar. La pila tiene un tamaño proporcional al logaritmo base dos del número de elementos a ordenar. Por ejemplo para 500 elementos, el logaritmo base 2 es casi 9 (hacen falta 9 bits para almacenar el número 500) y el número de datos a almacenar serán 2*9 = 18 punteros a la lista de datos.

Otra desventaja consiste en que con ciertas ordenaciones particulares de la lista de datos, la velocidad se reduce bastante. Este caso es muy particular y en la práctica es muy difícil que ocurra con datos ordenados de forma aleatoria.

Ahora los resultados :shock:

Comparaciones = 5537
Movimientos = 3219
Tics = 8756

Código del programa en Python:

Código: Python

"""Algoritmo de ordenacion de datos Quicksort"""
def quicksort(datos):
   global n_comp, n_moves
   n_comp = n_moves = 0
   quicksort_2(datos, 0, len(datos)-1)
   return n_comp, n_moves
 
 
def quicksort_2(datos, min_pos, max_pos):
   """Funcion auxiliar del algoritmo de ordenacion Quicksort"""
   global n_comp, n_moves
 
   # Condicion de salida recusiva
   if min_pos >= max_pos:
      return
 
   imin_pos = min_pos
   imax_pos = max_pos
   mid = datos[int((min_pos+max_pos)/2)]
 
   while imin_pos <= imax_pos:
      while datos[imin_pos] < mid:
         n_comp += 1
         imin_pos += 1
      n_comp += 1
 
      while datos[imax_pos] > mid:
         n_comp += 1
         imax_pos -=1
      n_comp += 1
 
      if imin_pos == imax_pos:
         imin_pos += 1
         imax_pos -= 1
         break
 
      if imin_pos < imax_pos:
         n_moves +=3
         temp = datos[imin_pos]
         datos[imin_pos] = datos[imax_pos]
         datos[imax_pos] = temp
         imin_pos += 1
         imax_pos -=1
 
   # Ordena primero el subconjunto mas pequenio para ahorrar saltos recursivos
   if imax_pos-min_pos < max_pos-imin_pos:
      quicksort_2(datos, min_pos, imax_pos)
      quicksort_2(datos, imin_pos, max_pos)
   else:
      quicksort_2(datos, imin_pos, max_pos)
      quicksort_2(datos, min_pos, imax_pos)
 
 
datos = [
   1497, 2094, 8094, 3331, 1126, 0736, 5999, 9688, 3593, 3353,
   3555, 9778, 4371, 2817, 9020, 2504, 6217, 2796, 8904, 0764,
   6700, 4105, 4468, 8504, 3201, 7426, 8780, 7518, 8846, 6228,
   3026, 2895, 3145, 1950, 4887, 0542, 8124, 3730, 7725, 4798, 
   8733, 1024, 7326,  669, 5985, 4882, 5867, 2991, 4641, 1964, 
   9245, 0501, 6406, 9280, 7916, 9477, 7166, 5616, 5183, 6264, 
   1024, 6136, 1894, 2402, 6529, 9646, 9749, 1208,  909, 6844, 
   7741, 2101, 8181, 8332, 1594, 9510, 9052, 1812, 1105, 3009, 
   5306, 4086, 6918, 5059, 6416, 7600, 7700, 4758, 7016, 3580, 
   7689, 5376, 7879, 1153,  945, 8274,  790, 8415, 9890, 1811, 
   5117, 5787, 3264, 6903,  555, 1337, 5062, 5881, 3592, 5533, 
   6056, 9723, 5849, 0352, 7148, 6921, 4568, 2615, 7105, 4869, 
   4685, 2987,   86, 6671, 8651, 3713, 6700, 5162, 6996, 8931, 
   7627, 1921, 6782, 2964, 1723, 2496, 6492, 1102, 3194, 6286, 
   9070, 8809, 8284, 3924, 6185, 6910, 9044, 4132, 0421, 6176, 
   0003, 4527, 7189,  268, 7978, 3881, 2497, 1252, 2330, 4674, 
   6657, 3652, 7182, 1810, 2569, 1545, 1963, 3168, 3266, 6167, 
   9575, 0200, 7064, 3931, 6748, 8158, 4523, 2391, 4649, 4348, 
   8598, 3430, 4983, 9916, 5575, 2091, 5675, 8954, 0761, 3242, 
   7649, 3842, 6078, 1123, 8144, 1939, 4487, 6824, 5786, 4455, 
   9169, 2353, 7104, 0014, 3532, 6235, 3737, 3446, 8497, 1608, 
   5947, 9078, 0411, 9139, 2823, 3858, 7542, 2447,  629,  799, 
    932, 2034, 7641, 6301, 9415, 0024, 8822, 4243, 5918, 7770, 
   3517, 3742, 8472, 9127, 3351, 8108, 6206, 9826, 9462, 3508, 
     94, 8209, 5372, 9358, 0223, 7268, 9840, 8529,  771, 3572, 
   9937, 7143, 3051, 8448, 5031, 4636, 8590, 3294, 5210, 5741, 
   3634, 9242, 8400, 5990, 8113, 1154, 1555, 5658, 9085, 9179, 
   8736, 4712, 6754, 5967, 6848, 7139, 9501, 6505, 5333, 3315, 
   7737, 7527, 5977, 6657, 2070, 1140, 5534, 9133, 7690, 5258, 
   6915,  792, 9924, 9933, 9601, 5346, 9188, 2199, 1091, 7259, 
   4932,  242, 8314, 8326, 1129, 7811, 1933, 4677, 4867, 3075, 
   3132,  810, 9029,  727, 9055, 5940, 1442, 5141,  459,  627, 
   9792, 3026, 8012, 8760, 5954, 2642, 2583, 7230, 3431, 2174, 
   8984, 4221, 2782, 7529, 6415, 2073, 9761, 5659, 6208,  559, 
   3602, 6420, 5917,  489, 4267, 0675, 4343, 4515, 3388, 5903, 
   7493, 3408, 5463, 7913, 7004, 1043, 5956, 8239, 4803, 6724, 
   6532, 8070,  550, 7118, 2546, 4519, 7225, 7742, 9187, 6297, 
   8010,  691,   27, 2058, 4568, 5860, 2821, 9680, 5322, 3375, 
   7767, 2586, 8182, 0500, 2286, 9836, 4814, 5092,  969, 7444, 
   5085,  487, 8035, 3482, 4246, 0361, 7185, 3827, 6742, 6705, 
   4416, 2750,  989, 4263, 9161, 7310, 6412, 5782, 1174, 0307, 
   4382, 0464, 7345, 5385, 5629, 0465, 8815, 2334, 9408, 1466, 
   3045, 8856, 4975, 5449, 1861, 7048, 9815, 8885, 5492, 5345, 
   3349, 6925, 6863, 1659, 6273, 8183,  341, 3461,  952, 2726, 
   6124, 3483, 6073, 1571, 4614, 8278, 3868, 7124, 8762, 8298, 
   5478, 6643, 7519, 9364, 4932, 2554, 1261, 9594, 7183, 0345, 
   3712, 6647, 9640,  370, 8654, 4381, 7962, 4694, 2931, 5007, 
    685, 6414, 5349, 4396, 5994, 7944, 5011, 2190, 3240, 9377, 
   4256, 8256, 6413, 9956, 2922, 1004, 2709, 0215, 5639, 7081, 
   8260, 2812, 6636, 2429, 4114, 4715, 6381, 6933, 2137,  378,
]
 
 
#main program
n_comp, n_moves = quicksort(datos)
print "Comparaciones =", n_comp 
print "Movimientos =", n_moves
print "Tics =", n_comp + n_moves
print "Datos = [\n  ",
print "".join(["%04d" % datos[i] + ", " + "\n   "*((i+1)%10==0) for i in range(0, len(datos))]),
print "]"

Resultado:

Código: [Seleccionar]

Comparaciones = 5537
Movimientos = 3219
Tics = 8756
Datos = [
   0003, 0012, 0020, 0027, 0086, 0094, 0128, 0141, 0147, 0199, 
   0229, 0234, 0241, 0242, 0265, 0268, 0273, 0308, 0309, 0320, 
   0321, 0341, 0354, 0370, 0378, 0445, 0459, 0478, 0487, 0489, 
   0497, 0500, 0550, 0555, 0559, 0627, 0629, 0669, 0685, 0691, 
   0727, 0771, 0790, 0792, 0799, 0810, 0909, 0932, 0945, 0952, 
   0969, 0989, 1004, 1024, 1024, 1043, 1091, 1102, 1105, 1123, 
   1126, 1129, 1140, 1153, 1154, 1174, 1208, 1252, 1261, 1337, 
   1442, 1466, 1497, 1545, 1555, 1571, 1594, 1608, 1659, 1723, 
   1810, 1811, 1812, 1861, 1894, 1921, 1933, 1939, 1950, 1963, 
   1964, 2034, 2058, 2070, 2073, 2091, 2094, 2101, 2137, 2174, 
   2190, 2199, 2286, 2330, 2334, 2353, 2391, 2402, 2429, 2447, 
   2496, 2497, 2504, 2546, 2554, 2569, 2583, 2586, 2615, 2642, 
   2709, 2726, 2750, 2782, 2796, 2812, 2817, 2821, 2823, 2895, 
   2922, 2931, 2964, 2987, 2991, 3009, 3026, 3026, 3045, 3051, 
   3075, 3132, 3145, 3168, 3194, 3201, 3240, 3242, 3264, 3266, 
   3294, 3315, 3331, 3349, 3351, 3353, 3375, 3388, 3408, 3430, 
   3431, 3446, 3461, 3482, 3483, 3508, 3517, 3532, 3555, 3572, 
   3580, 3592, 3593, 3602, 3634, 3652, 3712, 3713, 3730, 3737, 
   3742, 3827, 3842, 3858, 3868, 3881, 3924, 3931, 4086, 4105, 
   4114, 4132, 4221, 4243, 4246, 4256, 4263, 4267, 4343, 4348, 
   4371, 4381, 4382, 4396, 4416, 4455, 4468, 4487, 4515, 4519, 
   4523, 4527, 4568, 4568, 4614, 4636, 4641, 4649, 4674, 4677, 
   4685, 4694, 4712, 4715, 4758, 4798, 4803, 4814, 4867, 4869, 
   4882, 4887, 4932, 4932, 4975, 4983, 5007, 5011, 5031, 5059, 
   5062, 5085, 5092, 5117, 5141, 5162, 5183, 5210, 5258, 5306, 
   5322, 5333, 5345, 5346, 5349, 5372, 5376, 5385, 5449, 5463, 
   5478, 5492, 5533, 5534, 5575, 5616, 5629, 5639, 5658, 5659, 
   5675, 5741, 5782, 5786, 5787, 5849, 5860, 5867, 5881, 5903, 
   5917, 5918, 5940, 5947, 5954, 5956, 5967, 5977, 5985, 5990, 
   5994, 5999, 6056, 6073, 6078, 6124, 6136, 6167, 6176, 6185, 
   6206, 6208, 6217, 6228, 6235, 6264, 6273, 6286, 6297, 6301, 
   6381, 6406, 6412, 6413, 6414, 6415, 6416, 6420, 6492, 6505, 
   6529, 6532, 6636, 6643, 6647, 6657, 6657, 6671, 6700, 6700, 
   6705, 6724, 6742, 6748, 6754, 6782, 6824, 6844, 6848, 6863, 
   6903, 6910, 6915, 6918, 6921, 6925, 6933, 6996, 7004, 7016, 
   7048, 7064, 7081, 7104, 7105, 7118, 7124, 7139, 7143, 7148, 
   7166, 7182, 7183, 7185, 7189, 7225, 7230, 7259, 7268, 7310, 
   7326, 7345, 7426, 7444, 7493, 7518, 7519, 7527, 7529, 7542, 
   7600, 7627, 7641, 7649, 7689, 7690, 7700, 7725, 7737, 7741, 
   7742, 7767, 7770, 7811, 7879, 7913, 7916, 7944, 7962, 7978, 
   8010, 8012, 8035, 8070, 8094, 8108, 8113, 8124, 8144, 8158, 
   8181, 8182, 8183, 8209, 8239, 8256, 8260, 8274, 8278, 8284, 
   8298, 8314, 8326, 8332, 8400, 8415, 8448, 8472, 8497, 8504, 
   8529, 8590, 8598, 8651, 8654, 8733, 8736, 8760, 8762, 8780, 
   8809, 8815, 8822, 8846, 8856, 8885, 8904, 8931, 8954, 8984, 
   9020, 9029, 9044, 9052, 9055, 9070, 9078, 9085, 9127, 9133, 
   9139, 9161, 9169, 9179, 9187, 9188, 9242, 9245, 9280, 9358, 
   9364, 9377, 9408, 9415, 9462, 9477, 9501, 9510, 9575, 9594, 
   9601, 9640, 9646, 9680, 9688, 9723, 9749, 9761, 9778, 9792, 
   9815, 9826, 9836, 9840, 9890, 9916, 9924, 9933, 9937, 9956, 
    ]

Saludos.

Título: Re:Problemas sencillos de programación para resolver
Publicado por: Berto en 17 de Junio de 2016, 14:47:35

Yo para ordenar de menor a mayor utilizo esta burbuja No lo e hecho todo solo utilizo array[33];
pero tiene una cosa BUENA deja al array[nº inferior] en array[0] A LA PRIMERA este donde este y parece rrapida
Eso si necesito operarla una y otra para dejar todo en orden pero del proyecto que difiere lo prioritario es allar al menor

INCONVENIENTE Si los numeros mayores estan al principio le cuesta muchos pasos dejarlos al final

Código: [Seleccionar]

//nu debe corresponder al tamaño del array
//se empieza por el final esto hace que el menor sea arrastrado a array[0] a la primera
void bur(){//Burbuja(0)
for(c1=nu-1;c1>0;c1--){//si nu=5---> 0 1 2 3 4 pasadas
c2=c1-1;///...........
//array[c1];//POSICION actual "superior array +1"
//array[c2];//posicion anterior
if(array[c2]>array[c1]){////si p.anterior es mayor a p.siguiente   invertir de menor a mayor
mayor=array[c2];
array[c2]=array[c1];//distancia menor debe pasar a "inferior array -1"
array[c1]=mayor;//array[+1]
}
}//for(c1)
}

Y Si lo importante es dejar al numero mayor al final del array[maximo] a la primera Empezar desde array[0] Y se consigue que el nº mayor pase a array[final] este donde este. Este es un ejemplo no adaptado a este proyecto

Código: [Seleccionar]

void bu2(){//Burbuja(1)
for(co=0;nu>=co;co++){//si nu=5---> 0 1 2 3 4 pasadas
ca=co+1;
if(ca>=nu){ return; }//se salio del array[nu]
p0=psz[co];//POSICION actual
p1=psz[ca];//posicion siguiente "superior array +1"
d0=dis[p0];
d1=dis[p1];//distancia siguiente "superior array +1" 
if(d0>d1){//si d0(actual) esta a + distancia k d1(sigiente) ...d1 tiene prioridad + cercano
psz[co]=p1;//prior //psicion-sigiente pasa aposicion-anterior//es necesario tanto intercanviar posicion y distancia
psz[ca]=p0;
}
}//for(co)
}

No las meti en redundancia while o for porque lo principal son los primeros resultados, pero si es inportante todo el orden si seria necesario algo a si

Saludos.

TODOPIC

Lenguajes de programación para PC => Visual Basic => Mensaje iniciado por: Picuino en 26 de Marzo de 2014, 11:55:24