Articles of algoritmo

Probabilidade de colisão ao usar um hash de 32 bits

Eu tenho um campo de chave de seqüência de caracteres de 10 caracteres em um database. Eu usei CRC32 para hash este campo, mas eu estou preocupado com duplicatas. Alguém poderia me mostrar a probabilidade de colisão nesta situação? ps meu campo de string é único no database. Se o número de campos de string […]

Como contar uma combinação possível para o problema da moeda

Eu estou tentando implementar um problema de moeda, especificação do problema é assim Crie uma function para contar todas as combinações possíveis de moedas que podem ser usadas para determinado valor. All possible combinations for given amount=15, coin types=1 6 7 1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 2) 1,1,1,1,1,1,1,1,1,6, 3) 1,1,1,1,1,1,1,1,7, 4) 1,1,1,6,6, 5) 1,1,6,7, 6) 1,7,7, protótipo de […]

Como calcular ou aproximar a mediana de uma lista sem armazenar a lista

Eu estou tentando calcular a mediana de um conjunto de valores, mas eu não quero armazenar todos os valores como isso poderia explodir os requisitos de memory. Existe uma maneira de calcular ou aproximar a mediana sem armazenar e classificar todos os valores individuais? Idealmente eu gostaria de escrever meu código um pouco como o […]

Qual é a complexidade temporal dos algoritmos Regex médios?

Eu não sou novo em usar expressões regulares, e eu entendo a teoria básica na qual elas são baseadas – máquinas de estados finitos. Não sou tão bom em análise algorítmica e não entendo como uma regex se compara a uma pesquisa linear básica. Estou perguntando porque na superfície parece uma pesquisa de matriz linear. […]

Algoritmo matemático eficiente para calcular interseções

Para um jogo que estou desenvolvendo, preciso de um algoritmo que possa calcular interseções. Resolvi o problema, mas a maneira como o fiz foi realmente desagradável e espero que alguém aqui tenha uma solução mais elegante. Um par de pontos representa os pontos finais de uma linha traçada entre eles. Dados dois pares de pontos, […]

enésimo número feio

Números cujos únicos fatores primos são 2, 3 ou 5 são chamados de números feios. Exemplo: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … 1 pode ser considerado como 2 ^ 0. Estou trabalhando para encontrar o número feio. Observe que esses números são distribuídos de maneira esparsa quando n fica […]

Estratégias para simplificar expressões matemáticas

Eu tenho uma tree bem formada que representa uma expressão matemática. Por exemplo, dada a string: “1+2-3*4/5” , isso é analisado em: subtract(add(1,2),divide(multiply(3,4),5)) Qual é expresso como esta tree: O que eu gostaria de poder fazer é pegar esta tree e reduzi-la o máximo possível. No caso acima, isso é bem simples, porque todos os […]

Hashing uma estrutura de tree

Acabei de encontrar um cenário no meu projeto onde preciso comparar diferentes objects de tree para igualdade com instâncias já conhecidas, e considerei que algum tipo de algoritmo de hashing que opera em uma tree arbitrária seria muito útil. Tomemos por exemplo a seguinte tree: O / \ / \ OO / | \ | […]

Geração de malha de pontos com coordenadas x, ye z

Problema: Geração de malha a partir de pontos 3D (com coordenadas x, yez). O que eu tenho são pontos no espaço 3D (com coordenadas x, yez) você pode ver na imagem 1. Qual seria a saída é a imagem 2 ou imagem 3 ou imagem 4. Em suma, seria malha. Material sobre ele pode ser […]

Complexidade temporal do algoritmo Sieve of Eratosthenes

Da Wikipedia: A complexidade do algoritmo é a operação de bits O(n(logn)(loglogn)) . Como você chega a isso? Que a complexidade inclui o termo loglogn me diz que existe um sqrt(n) algum lugar. Suponha que eu esteja executando a peneira nos primeiros 100 números ( n = 100 ), assumindo que marcar os números como […]