sumar numeros de una lista

[Breew]

Hola.

Como conseguiriais averiguar en un listado de numeros, que combinacion de numeros suman un valor determinado.

Por ejemplo, si tengo un listado con 30 numeros, que combinaciones de numeros suman un total de 986.

Gracias

[Joseg]

Hola.

Como conseguiriais averiguar en un listado de numeros, que combinacion de numeros suman un valor determinado.

Por ejemplo, si tengo un listado con 30 numeros, que combinaciones de numeros suman un total de 986.

Gracias

Analise este código:
https://craftofcoding.wordpress.com/2018/03/15/coding-cobol-a-program-with-loops-and-an-array/

Usar índices poderá ajudar:


01 myvar occurs 30 times INDEXED by myindex.
05 munumer pic 999.

[JCantero]

Hola.

Como conseguiriais averiguar en un listado de numeros, que combinacion de numeros suman un valor determinado.

Por ejemplo, si tengo un listado con 30 numeros, que combinaciones de numeros suman un total de 986.

Gracias

Bonito problema a resolver en cobol con un occurs (array o tabla en otros lenguajes). ( esto podría ser un buen algoritmo para seleccionar personas con conocimientos)

Esto se puede resolver de forma recursiva o interactiva.

De forma interactiva lo haría de la siguiente forma:

- Metería los números en un occurs o tabla.

- Buscar combinaciones de 1 elemento. Hasta recorrer la tabla o pasarse de la suma (condicion).
- Buscar 2 elementos alternando posiciones, hasta (condición).
*
*
*
- Buscar 29 elementos alternando posiciones, hasta condición.
- Buscar 30 elementos, hasta condición.

O quizas hacerlo justamente al revés.

Bonito reto.
A ver si tengo un rato y lo implemento.
:flipa:

[Josber]

@JCantero,

No existe ningún algoritmo que haga eso, (que yo sepa), el caso está en que si son la suma de 2 o 3 elementos en una combinación de, por ejemplo 30 elementos, el algoritmo es sencillo y rápido, el problema está en que sean la suma de cualquiera de los 30 elementos, (en el que necesites sólo 1 para que dé ese valor, o necesites los 30, para que lo dé), ahí el problema es que la cantidad de combinanciones, es exponencial al número de elemento, por lo que, en una tabla de 30 elementos, la cantidad de combinaciones sería de 2,6e+32, (30!), osea, 26 seguido 32 ceros, (2.600.000.000.000.000.000.000.000.000.000.000), lo cual, hace imposible el cálculo.

Un saludo.-

[JCantero]

@JCantero,

No existe ningún algoritmo que haga eso, (que yo sepa), el caso está en que si son la suma de 2 o 3 elementos en una combinación de, por ejemplo 30 elementos, el algoritmo es sencillo y rápido, el problema está en que sean la suma de cualquiera de los 30 elementos, (en el que necesites sólo 1 para que dé ese valor, o necesites los 30, para que lo dé), ahí el problema es que la cantidad de combinanciones, es exponencial al número de elemento, por lo que, en una tabla de 30 elementos, la cantidad de combinaciones sería de 2,6e+32, (30!), osea, 26 seguido 32 ceros, (2.600.000.000.000.000.000.000.000.000.000.000), lo cual, hace imposible el cálculo.

Un saludo.-


Creo que no es tanto.

Son (2^30)-1 == 1.073.741.823

Bonito reto

[Josber]

Creo que no es tanto.

Serían combinaciones, (30!), no permutaciones, ¿no?, perdón si estoy equivocado, hace tantos años de las matemáticas ... a ver si alguiien más puesto que yo, nos lo aclara :silba: :piensa:

[Joseg]

Serían combinaciones, (30!), no permutaciones, ¿no?, perdón si estoy equivocado, hace tantos años de las matemáticas ... a ver si alguiien más puesto que yo, nos lo aclara :silba: :piensa:


Em anexo projecto em Powercobol para calculo de um factorial e uma solução para o problema:

* IDENTIFICATION DIVISION.
* PROGRAM-ID. ACCSUM.
ENVIRONMENT DIVISION.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 ACCOUNTS.
05 ACC-X PIC S9(4)v99 COMP-3
OCCURS 12 TIMES.
01 B PIC 9(06) comp.
01 bx PIC 9(06) comp.
01 pos pic 9(06) comp.
01 sum1 pic s9(8)v99 comp-3.
01 sum2 pic s9(8)v99 comp-3.
01 r pic 9(06) comp.
01 res pic 9(06) comp.
01 comb pic x(15) value space.
PROCEDURE DIVISION.
0000-MAIN SECTION.
PERFORM 0100-init
perform 0200-process
EXIT PROGRAM.

0100-init section.
move 134 to ACC-X(1)
move 400 to ACC-X(2)
move 322 to ACC-X(3)
move 100 to ACC-X(4)
move 300 to ACC-X(5)
move 86 to ACC-X(6)
move 600 to ACC-X(7)
move 700 to ACC-X(8)
move 800 To ACC-X(9)
move 200 to ACC-X(10)
move 123 to ACC-X(11)
move 203 to ACC-X(12).
*> exit. *> GnuCobol
0200-process section.

perform varying b from 0 by 1
until b > 4095 *> 2^12 --> se for 30 numeros tem k ser 2^30 = 1.073.741.824
compute bx = b
compute pos = 0
move zero to sum1 sum2
perform until bx = zero
divide bx by 2 giving res remainder r

if ( r NOT = zero )
compute sum1 = sum1 + acc-x ( pos + 1 )
move '1' to comb(pos + 1 : 1)
else
compute sum2 = sum2 + acc-x ( pos + 1 )
move '0' to comb(pos + 1 : 1)
end-if

compute bx = bx / 2
add 1 to pos

end-perform

if (sum1 = 986 ) then
display "-->Combinação: " comb " -->Soma=" sum2
end-if
end-perform.
*> exit. *> GnuCobol

[JCantero]

@Joseg, reto conseguido y muy curiosa la solución.

---------- Post añadido : 14:35 ---------- Post anterior : 14:17 ----------

Va analizando cada combinación en binario. Es decir:

0
1
01
11
001
101
011
111
*
*
*
1111111111111 (hasta las posiciones que se configuren, en este caso 12)

Y va sumando en cada combinacion con los elementos de la lista dada y comprobando si da el resultado buscado.

¡ Muy Curioso ! pero eficiciente.

Ya lo he modificado para 30 elementos y lo he puesto en un windows y en un linux, a ver lo que tarda ¡¡¡

:pared:

---------- Post añadido : 20:18 ---------- Post anterior : 14:35 ----------

Para vuestra información y curiosidad. (buscando con 30 elementos) ( 2^30-1 combinaciones)

Compilado en RM/cobol y ejecutado en windows y linux.

Después de 7 horas esperando:
1) el proceso de windows 10 (64 bits) lleva un 30%
2) el proceso en linux (virtual) con 8 CPUs lleva un 45%

He realizado lo mismo en C. Lo he ejecutado en el linux. Ha tardado 2,5 minutos. Ya lo esperaba pero me ha sorprendido tan poco tiempo.

Me gustaria que hicierais lo mismo en otros COBOL para ver como son de rápidos en estas cosas.

Hacedlo para 30 elementos, modificando el programa de @joseg o os lo envio.

Por este motivo yo muchas veces implemento rutinas en C para obtener mejores resultados aunque no sean valorados. :cojo:

[Breew]

Brutal !!!!!!!!!

Menudos fieras

Gracias

[Kuk]

@JCantero, el problema de rendimiento debe venir del hecho que la rutina de @Joseg (a diferencia de tu rutina en C) no usa campos nativos.

Los COMP y COMP-3 deben reemplazarse por unos COMP-5 (de 2-4-8 bytes) para corresponder con la plataforma. Esto acelerará mucho el asunto.

[Joseg]

@Joseg, reto conseguido y muy curiosa la solución.

---------- Post añadido : 14:35 ---------- Post anterior : 14:17 ----------

Va analizando cada combinación en binario. Es decir:

0
1
01
11
001
101
011
111
*
*
*
1111111111111 (hasta las posiciones que se configuren, en este caso 12)

Y va sumando en cada combinacion con los elementos de la lista dada y comprobando si da el resultado buscado.

¡ Muy Curioso ! pero eficiciente.

Ya lo he modificado para 30 elementos y lo he puesto en un windows y en un linux, a ver lo que tarda ¡¡¡

:pared:

---------- Post añadido : 20:18 ---------- Post anterior : 14:35 ----------

Para vuestra información y curiosidad. (buscando con 30 elementos) ( 2^30-1 combinaciones)

Compilado en RM/cobol y ejecutado en windows y linux.

Después de 7 horas esperando:
1) el proceso de windows 10 (64 bits) lleva un 30%
2) el proceso en linux (virtual) con 8 CPUs lleva un 45%

He realizado lo mismo en C. Lo he ejecutado en el linux. Ha tardado 2,5 minutos. Ya lo esperaba pero me ha sorprendido tan poco tiempo.

Me gustaria que hicierais lo mismo en otros COBOL para ver como son de rápidos en estas cosas.

Hacedlo para 30 elementos, modificando el programa de @joseg o os lo envio.

Por este motivo yo muchas veces implemento rutinas en C para obtener mejores resultados aunque no sean valorados. :cojo:

Experimente o GnuCobol (traduz de cobol para C). É muito rápido.
Mas a rotina acima que mandei pode ser muito mais optimizada e não fazer tantos cálculos.
Substituir os CPMP-3 por COMP-5 (formato decimal é mais lento que o formato binário).
Se usar apenas números inteiros, deve de ajustar o PIC (aumenta a velocidade).

[JCantero]

@JCantero, el problema de rendimiento debe venir del hecho que la rutina de @Joseg (a diferencia de tu rutina en C) no usa campos nativos.

Los COMP y COMP-3 deben reemplazarse por unos COMP-5 (de 2-4-8 bytes) para corresponder con la plataforma. Esto acelerará mucho el asunto.

Si, eso fue lo primero que hice pero ese no es el problema.

El problema es que rmcobol es interpretado, pongas lo que pongas es lento. Luego probare con Acucobol que seguro que va mas rápido.

C es practicamente lenguaje maquina (como ensamblador) y no se puede comparar con ningún lenguaje excepto con ensamblador en cuestión de rapidez.

[Kuk]

@JCantero, todo depende del compilador. Si el compilador obtiene código máquina optimo, no importa el lenguaje.

Efectivamente se necesitaría un binario nativo, yo nunca he usado RM (aunque sabía que produce una especie de bytecode, como Java, y por ello los ejecutables son válidos en cualquier SO).