Algoritmos – Parte 01 – Loterias

Introdução

Nos primeiros posts no Blog sobre programação — vide Desmistificando a análise de sistemas e Desmistificando a programação — foi colocada de forma simples a ideia de programar alguma coisa, como sendo apenas uma sequência de instruções e decisões para se realizar uma tarefa. E, realmente é simples assim, o que precisamos fazer é usar corretamente a gramática da linguagem para realizar as tarefas em pequenas etapas, criando tarefas maiores e reaproveitando tarefas menores.

Algoritmos

Uma sequência de instruções para realizar uma tarefa específica pode ser chamada de “Algoritmo” — verifique a definição na Wikipedia – Algoritmo. Não é algo aplicado apenas a programação de computadores.

Consultando também a Wikipédia – Lista de Algoritmos, podemos ver vários exemplos de problemas específicos resolvidos com sequências de operação. Como o algoritmo em si trata apenas da sequência de operações para obter um resultado, ele pode ser implementado em várias linguagens de programação.

Alguns dos mais conhecidos e utilizados são algoritmos de ordenação e busca de dados, compressão, sorteio de números (números randômicos), criptográficos (segurança da informação), entre outros. Na internet podemos obter não apenas vários modelos de algoritmos, mas também várias implementações dos mesmos em várias linguagens de programação.

Algoritmos em AdvPL

Vamos pegar um problema qualquer, e criar um algoritmo para resolvê-lo, um por tópico. Um problema bem interessante de ser resolvido usando um programa de computador, é por exemplo lidar com análise combinatória. Podemos usar um algoritmo de geração de combinações (ou Combinação Simples) para, por exemplo, criar massas de dados explorando as combinações de vários parâmetros para testes de funções, combinar números para cartões de loteria — adoro esse algoritmo — entre outras finalidades. Vamos ver como realizar uma análise combinatória eficiente para loterias em AdvPL.

Combinação para Loterias

Em um determinado cartão de loteria, podemos preencher no mínimo N números diferentes, dentre um total de X números disponíveis, para concorrer a um prêmio caso uma quantidade mínima de números sorteados estejam presentes entre os N números do cartão.

Quando queremos por exemplo, determinar todas as possibilidades de combinação de Y números em cartões de X números, utilizamos um recurso de análise combinatória chamado “Combinação Simples”. Atualmente, para alguns tipos de loterias,o próprio bilhete de apostas já permitem você fazer uma aposta com mais números do que a aposta mínima. Neste caso, a sua aposta equivale a todas as possibilidades de combinação simples dos Y números em um cartão de X números.

MEGA-SENA

Vamos tomar como exemplo a MEGA-SENA, onde a aposta mínima é um bilhete com seis números preenchidos, a um valor de R$ 3,50 . Podemos preencher de 6 a 15 números em um cartão ou bilhete, porém o preço da aposta sobe proporcionalmente ao número de combinações simples da quantidade de números preenchidos em blocos de seis números. Veja a tabela abaixo, de apostas e preços, e a quantidade de apostas de 6 números equivalente.

NUMEROS NO  | VALOR DA     | EQUIVALE A <n> 
BILHETE     | APOSTA       | APOSTAS de 6 números
------------+--------------+------------------------          
6 números   | R$ 3,50      |    1 aposta 
7 números   | R$ 24,50     |    7 apostas 
8 números   | R$ 98,00     |   28 apostas 
9 números   | R$ 294,00    |   84 apostas 
10 números  | R$ 735,00    |  210 apostas 
11 números  | R$ 1617,00   |  462 apostas 
12 números  | R$ 3234,00   |  924 apostas 
13 números  | R$ 6006,00   | 1716 apostas 
14 números  | R$ 10510,50  | 3003 apostas 
15 números  | R$ 17517,50  | 5005 apostas

Quantidade de combinações possíveis

A fórmula para determinar uma combinação simples C, de n números em conjuntos de k elementos é:

C(n,k) = n! / k! * (n-k)!

Onde “!” significa o valor FATORIAL do elemento, “*” é o operador de multiplicação, “/” é o operador de divisão.

Na matemática, o fatorial (AO 1945: factorial) de um número natural n, representado por n!, é o produto de todos os inteiros positivos menores ou iguais a n. A notação n! foi introduzida por Christian Kramp em 1808.

Vamos pegar por exemplo uma combinação de 12 elementos em conjuntos de 6 elementos — equivalente ao cartão de 12 números da MEGA-SENA.

C(12,6) = 12! / 6! * (12-6)!
C(12,6) = 12! / 6! * 6!
C(12,6) = 479001600 / 720 * 720 
C(12,6) = 479001600 / 518400 
C(12,6) = 924

Logo, antes mesmo de começar a fazer a combinação, podemos determinar o número de resultados possíveis.

Combinando elementos

A lógica para realizar a combinação dos elementos é basicamente a mesma, não importa a quantidade de elementos a combinar ou o tamanho do conjunto resultante. Porém, dependendo da forma que ela for implementada, ela tende a ficar mais pesada quanto maior a quantidade de elementos a combinar. Vamos pegar por exemplo a combinação de 7 elementos numéricos, de 1 a 7, em conjuntos de 6 elementos.

C(7,6) = 7! / 6! * (7-6)!
C(7,6) = 7! / 6! * (1)!
C(7,6) = 5040 / 720 * 1
C(7,6) = 7

Logo de antemão, sabemos que esta combinação resultará em 7 resultados. Agora, vamos fazer a combinação. Partindo dos números já ordenados, a primeira combinação é:

1 2 3 4 5 6

Para determinar o próximo resultado, pegamos o próximo numero do conjunto da última posição e incrementamos uma unidade:

1 2 3 4 5 7

Ao tentar fazer a mesma operação para pegar o terceiro resultado, o número 7 é o último elemento do conjunto. Então, precisamos incrementar o número na posição anterior — quinta posição. Quando fazemos isso, o número da posição que atingiu o limite deve ser o próximo elemento relativo a posição anterior. Logo, o próximo resultado será:

1 2 3 4 6 7

Repetindo novamente esta operação, começando da direita para a esquerda, na sexta posição, o elemento 7 já é o último do conjunto. Então vamos para a quinta posição. O próximo elemento desta posição seria o 7, porém ele é o último elemento da combinação, e eu não estou na última posição do conjunto de resultado, isto significa que ele já está em uso em uma posição posterior. Logo, vamos a posição anterior — quarta posição — e incrementamos o número 4 para 5, obtendo o resultado:

1 2 3 5 6 7

Repetindo os passos anteriores, os números 5, 6 e 7 não podem ser incrementados pois já são os elementos finais da combinação. Logo, incrementamos na terceira posição o 3 para 4, depois na segunda posição de 2 para 3, depois na primeira, de 1 para 2, e depois acabou, pois não há como incrementar mais nada.

1 2 4 5 6 7 
1 3 4 5 6 7 
2 3 4 5 6 7

Com isso obtivemos os 7 resultados possíveis. Agora, vamos colocar essa regra em um código fonte. Para facilitar o uso deste recurso, vamos criá-lo como uma Classe em AdvPL. Após construir e otimizar o algoritmo, a primeira versão ficou assim (fonte ACOMB.PRW):

#include "protheus.ch"

CLASS ACOMB FROM LONGNAMECLASS

  DATA nCols
  DATA aElements
  DATA nSize
  DATA aControl
  DATA aMaxVal
  DATA nPos

  METHOD NEW()
  METHOD GETCOMB()
  METHOD NEXTCOMB()
  METHOD GETTOTAL() 

ENDCLASS

METHOD NEW( nCols , aElements ) CLASS ACOMB
Local nI , nMax
::nCols := nCols
::aElements := aElements
::nSize := len(aElements)
::nPos := nCols
::aControl := {}
::aMaxVal := {}
nMax := ::nSize - ::nCols + 1
For nI := 1 to ::nCols
  aadd(::aControl,nI)
  aadd(::aMaxVal, nMax )
  nMax++
Next
Return self

METHOD GETCOMB() CLASS ACOMB
Local nI , aRet := array(::nCols)
For nI := 1 to ::nCols
  aRet[nI] := ::aElements[ ::aControl[nI] ] 
Next 
Return aRet

METHOD NEXTCOMB() CLASS ACOMB
If ::aControl[::nPos] + 1 > ::aMaxVal[::nPos]
  ::nPos := ::nPos - 1 
  If ::nPos < 1 
    Return .F. 
  Endif
  If ::NEXTCOMB()
    ::nPos := ::nPos + 1
    ::aControl[::nPos] := ::aControl[::nPos-1]+1
  Else
    Return .F. 
  Endif
Else
  ::aControl[::nPos]++
Endif
Return .T.

METHOD GETTOTAL() CLASS ACOMB
Local nFat1 := Fatorial( ::nSize )
Local nFat2 := fatorial( ::nCols )
Local nFat3 := Fatorial( ::nSize - ::nCols )
Local nTot := nFat1 / ( nFat2 * nFat3 ) 
Return nTot

STATIC Function Fatorial(nNum)
Local nI := nNum - 1
While nI > 1 
  nNum *= nI 
  nI--
Enddo
Return nNum

A propriedade aControl controla os contadores de cada posição do conjunto de retorno, e a propriedade aMaxVal eu já determino qual é o valor máximo de um determinado contador para a coluna ou posição atual. O Método GetComb() retorna um array com os elementos combinados, e o método NextComb() determina qual a próxima combinação da sequência, atualizando o array aControl. Quando o método NextComb() retornar .F., não há mais combinações possíveis. E, usando o método GetTotal(), eu determino quantas combinações são possíveis.

Para testar a classe acima, vamos usar o seguinte fonte:

User Function ACombTst()
Local nI
Local nResult := 1
Local lEcho := .F. 
Local nTimer
Local nCols , aData := {}

// Monta 35 dezenas para combinar 
For nI := 1 to 35
  aadd(aData,strzero(nI,2))
Next
// Combinação em conjuntos de 6 dezenas 
nCols := 6
oLoto := ACOMB():New( nCols , aData )
nTotal := oLoto:GetTotal()
conout("Elementos ...... "+cValToChar(len(aData)) )
conout("Conjunto ....... "+cValToChar(nCols) )
conout("Combinacoes .... "+cValToChar(nTotal) )
If lEcho
  aRet := oLoto:GETCOMB()
  conout("("+strzero(nResult,6)+") "+aRet[1]+" "+aRet[2]+;
         " "+aRet[3] +" "+aRet[4]+" "+aRet[5]+" "+aRet[6] )
endif
nTimer := seconds()
While oLoto:NEXTCOMB()
  nResult++
  If lEcho
    aRet := oLoto:GETCOMB()
    conout("("+strzero(nResult,6)+") "+aRet[1]+" "+aRet[2]+;
           " "+aRet[3] +" "+aRet[4]+" "+aRet[5]+" "+aRet[6] )
  Endif
Enddo
nTimer := seconds() - nTimer
conout("Resultados ..... "+cValToChar(nResult) )
conout("Tempo .......... "+str(nTimer,12,3)+" s.")
Return

No meu notebook, determinar as 1623160 combinações possíveis de 35 números em blocos de 6 demorou aproximadamente 3,5 segundos. Vejamos o log de console:

Elementos ...... 35
Conjunto ....... 6
Combinacoes .... 1623160
Resultados ..... 1623160
Tempo .......... 3.531 s.

Sim, neste teste eu não peguei os resultados, e não imprimi os resultados, eu apenas chamei em loop o método NextComb() até ele calcular todas as combinações. Para a aplicação imprimir os resultados em console, basta colocar .T. na variável lEcho e recompilar o fonte. Não é necessário dizer que, haverá uma boa diferença de desempenho quando você passar a resgatar cada uma das combinações e mostrar/gravar cada uma no log de console.

Dividindo o número total de combinações pelo tempo que a aplicação demorou, a rotina gerou aproximadamente 459688 resultados por segundo. Eu diria que isso é um tempo fantasticamente rápido. O tempo necessário para gerar estas combinações é simplesmente irrelevante perto do tempo que você deve gastar para, por exemplo, registrar estas combinações em uma tabela ou Banco de Dados.

Outras Loterias

Vamos pegar agora a Lotofácil. Cada cartão tem 25 dezenas, a aposta mínima é um bilhete com 15 dezenas preenchidas, e o prêmio máximo é você acertar os 15 números. As chances de você ganhar jogando um bilhete com a aposta mínima é 1 em 3.268.760. Afinal, se você fizer todas as combinações de 25 dezenas em grupos de 15, é exatamente esse o número de combinações possível. Vamos ver isso rodando o programa ? Basta alterar o programa de teste para criar 25 dezenas, e atribuir 15 para nCols.

Elementos ...... 25
Conjunto ....... 15
Combinacoes .... 3268760
Resultados ..... 3268760
Tempo .......... 12.002 s.

Pode fazer a mesma coisa para a MEGA-SENA, são 60 elementos em conjunto de 6. Garanto que vai demorar bem mais que 12 segundos, afinal a MEGA-SENA são 50.063.860 possibilidades ou combinações, mais de 15 vezes do que a Loto Fácil. Vamos rodar, apenas pra ver quanto tempo demora.

Elementos ...... 60
Conjunto ....... 6
Combinacoes .... 50063860
Resultados ..... 50063860
Tempo .......... 94.201 s.

Conclusão

Mesmo sabendo de tudo isso, até agora eu não ganhei na loteria, pois matematicamente as chances de um número qualquer ser sorteado é uma para o conjunto de números. As chances de acertar todos os números de uma loteria com uma aposta é uma para o conjunto de possibilidades / combinações dos números que eu posso colocar no cartão. Matematicamente, as chances de qualquer aposta — qualquer uma, inclusive por exemplo as dezenas “01 02 03 04 05 06” , ou “05 10 15 20 25 30”, são as mesmas. A única forma de aumentar matematicamente a sua probabilidade ou chance de acerto é jogar mais cartões diferentes. E, no final das contas, você pode jogar um cartão com 16 números e não acertar nenhum.

Agradeço novamente a audiência, curtidas e compartilhamentos, e desejo a todos TERABYTES DE SUCESSO 😀

Referências

 

 

5 comentários sobre “Algoritmos – Parte 01 – Loterias

  1. Júlio, pra que serve o LONGNAMECLASS na criação da classe? Quando uso uma com herança eu coloco o nome da classe superior, mas não entendi esse LONGNAMECLASS.

    Obrigado!

    Curtido por 1 pessoa

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s