As disputas que surgem periodicamente em fóruns temáticos sobre se um programador precisa de matemática há muito se tornam um local e área comum de guerras santas. Estando do nosso lado (direito) da fronteira, separando o bem do mal, quero compartilhar um exemplo que demonstra claramente o quanto é necessário e até (não teremos medo dessa palavra) é necessário.
Considere um problema de programação interessante, que possui um caráter um tanto de olimpíada.
Pnp: A partir deste momento, os defensores da ideia de que a programação hoje consiste em páginas da web muito bem projetadas podem parar de ler, você está absolutamente certo, não precisa de matemática ...
Bem, você não precisa insistir nisso, não é pior do que nós, e seu trabalho é realmente importante, porque eu já concordei que temos idéias diferentes sobre programação ...
Sim, você está absolutamente certo de que esses olimpíadas não conseguirão, com a ajuda da última estrutura, desenhar sete linhas perpendiculares vermelhas em uma linha de código ...
Não obstante, considero correta a minha ideia (esta é uma propriedade fatal de matéria altamente organizada na forma de corpos protéicos); portanto, apresentarei os argumentos que a sustentam.Formulo o problema - quantos números diferentes de comprimento K que terminam em um determinado botão p podem ser digitados no teclado do telefone (teclado) se precisarmos mover os botões com um cavaleiro de xadrez. Entende-se que você viu o teclado (eu ainda tenho um telefone celular normal, não um smartphone, então eu o vejo todos os dias, um leitor mais avançado deve entrar em contato com a Internet para obter ajuda) e você sabe como anda um cavalo de xadrez (fácil para o google). a matemática não tem nada a ver com isso até agora, se você não tem em mente a capacidade de calcular opções.
A primeira solução é bastante óbvia - pegamos todos os 10 botões um após o outro (denotamos seu número por n por generalidade), consideramos todos os números possíveis de K longo e contamos aqueles que terminam no botão desejado. Os números resultantes são resumidos e a resposta está pronta. O número total de opções visualizadas é expresso aproximadamente como n * B (K), onde B (K) é o número de movimentos possíveis de comprimento K. Na verdade, é necessário considerar a soma de n posições, pois B (p, K) obviamente depende do número do botão mas, como primeira estimativa, desça.
Antes de prosseguir na pesquisa B, é possível reduzir significativamente o número de opções aplicando (não, ainda não a matemática) o senso comum. Como o movimento dos botões depende do fundo, podemos reverter a tarefa e procurar todos os números de comprimento K começando no botão desejado p. Então, o número total de opções será B (p, K), que é n vezes menos. Uau, acabamos de encontrar uma maneira de acelerar a busca de uma solução 10 vezes - legal, vamos ver quanto resta.
Precisamos avaliar B (p, K), para o qual determinamos que a cada movimento temos de 2 a 3 opções para o desenvolvimento de eventos. Segue-se (em geral, isso é combinatório, mas intuitivamente claro) que o número total de opções será de 2 ** K a 3 ** K (daqui em diante eu uso K-1 como K). Podemos até melhorar essa estimativa passando para um modelo probabilístico. Considerando que a presença de um dedo em cada botão no momento é igualmente provável (uma declaração forte, provavelmente incorreta, mas aceitável com estimativas aproximadas), podemos calcular o número médio de opções de movimento 7 * 2 + 2 (botões 4 e 6) * 3 = 20/9 ~ 2,22 . Então a estimativa será 2,22 ** K, e sabemos com certeza que temos um mínimo de 2 ** K. Então, para K = 100, obtemos um limite inferior 2 ** 100 = (2 ** 10) ** 10> (10 ** 3) ** 10 = 10 ** 30.
Se considerarmos uma opção em um nanossegundo (e isso não é fácil, mesmo em um PC desktop poderoso), precisamos de 10 ** 30/10 ** 9 = 10 ** 21 segundos. Em seguida, lembramos que os maravilhosos mnonônicos "π segundos são iguais a um século" e o tempo necessário será de 10 ** 21 / 3,14 * 10 ** 9 ~ 3 * 10 ** 11 séculos. Parece-me que poucos leitores viverão para ver o final dos cálculos usando a metodologia proposta. O expositor é terrível, apenas o fatorial é pior que ela.
Melhoraremos a solução com base no fato de estarmos interessados no número de opções, mas não nas próprias opções. Você pode oferecer a fórmula óbvia B (p, K) = a soma de B (p ', K-1) para todos os p' nos quais obtemos 1 movimento de p. Começamos a partir do botão final e atribuímos a ele um peso de 1, depois executamos o procedimento de somar os pesos atuais para o próximo, repita na profundidade desejada.
Ilustramos o que foi dito com um exemplo, começando com o número 1 {1234567890}:
peso inicial {1000000000},
após a primeira transferência {0000010100} (2 opções),
após a segunda transferência {2010001001} (5 opções),
após o terceiro {0102040300} (10 opções) e assim por diante.
O algoritmo é simples, pode ser implementado mesmo com as mãos. A estimativa geral do tempo de execução é de K iterações, em cada uma das quais para n pesos não modificamos mais que n pesos relacionados, total
n ** 2 * K. Para o caso considerado anteriormente, 10 * 10 * 100 = 10 ** 4 - um pouco.
Resta apenas avaliar a duração de cada operação - essa é a adição (questão do lixo), mas não a adição simples (deste local em mais detalhes). Já definimos o limite inferior da resposta para 2 ** K, ou seja, precisamos definitivamente de pelo menos K bits para representar o resultado. O limite superior é 3 ** K, para o nosso caso 3 ** 100 = (3 ** 5) ** 20 <(2 ** 8) * 20 = 2 ** 160, ou seja, garantimos o encaixe em 160 bits. Podemos supor que 128 bits são suficientes para nós, já que 2,2 ** 100 <2 ** 128, mas aceitar tal declaração de fé é assustador; portanto, precisamos de um número com pelo menos 160 bits ou 49 dígitos decimais, dependendo da sua biblioteca de números alta precisão.
PNP: Não ofereça um ponto flutuante, precisamos de um resultado completamente preciso.Nas premissas aceitas, a operação de adição ocupará 160/8 = 20 bytes / 4 = 5 adições de números inteiros de 32 bits, o que não afeta a ordem do tempo (permanece linear em K), mas pode aumentar significativamente o tempo real de cálculo (várias vezes).
De qualquer forma, o resultado é simplesmente magnífico - transformamos a tarefa de fundamentalmente insolúvel em um tempo razoável para completamente solucionável: se uma operação de adição elementar for realizada em um microssegundo (e isso é fácil de garantir, mesmo na placa Arduino), o tempo total não excederá 10 ** 4 * 20 / 10 ** 6, menos de um segundo) e ficamos sem matemática.
No entanto, e se precisarmos de K maior - é claro, a ordem linear dos cálculos - isso é maravilhoso, mas pode (e vai) levar a perdas de tempo significativas para valores grandes. Acontece que você pode melhorar significativamente o tempo esperado, observe suas mãos.
O que fazemos em cada etapa do cálculo (pseudo-código):
= 0;
1
2
* ( 1 2)
* 1 2.
=
2 ( 1 * )
0 1, . '=* =(...((*)*)...). , =***. , . **3,
***3 — , ? , …
— , **3 , , , ( ) ( ), . , 100 99 8. , 2*log2(), ( =100 1000/10=100 ) ,
2*log2()***3. , , , . , , log2(K), , , 100.
- ( , ), , , .