[Sintaxis] 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/...-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.

[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

[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

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 ¡¡¡



---------- 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.

[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.