O algoritmo do caixa é um algoritmo para fazer alterações no número mínimo de moedas que funciona muito bem para a maioria dos sistemas monetários. No entanto, como a maioria dos algoritmos gananciosos, não deixa de ter suas falhas. Se um sistema de moeda estiver configurado da maneira certa (ou errada), existem certos valores nos quais o algoritmo do caixa não conseguirá encontrar a mudança ideal.
Veja o seguinte exemplo:
Temos moedas de 4 ¢, 3 ¢ e 1 ¢. Queremos fazer 6 ¢.
O algoritmo do caixa selecionará primeiro a maior moeda (uma 4 ¢ para iniciar) e subtrairá e repetirá. Isso resultará em uma moeda de 4 ¢ e duas moedas de 1 ¢, num total de 3 moedas.
Infelizmente para o algoritmo, há uma maneira de ganhar 6 ¢ com apenas duas moedas (duas de 3 ¢).
Um sistema de mudança será considerado canônico se, para todos os valores inteiros, o Algoritmo do Caixa encontrar o número ideal de moedas.
Tarefa
Sua tarefa será usar um sistema como um contêiner não ordenado ou contêiner ordenado ordenado de números inteiros representando valores de moedas e gerar um valor verdadeiro se a entrada do sistema for canônica e, caso contrário, será falsificada.
Seu programa deve funcionar para todos os sistemas que podem criar qualquer valor. (ou seja, todos os sistemas terão uma moeda de 1 ¢)
Este é o código de golfe que menos bytes ganha.
Casos de teste
Esta lista não é exaustiva, seu programa deve funcionar para todas as entradas válidas
1, 3, 4 -> 0
1, 5, 10, 25 -> 1
1, 6, 10, 25 -> 0
1, 2, 3 -> 1
1, 8, 17, 30 -> 0
1, 3, 8, 12 -> 0
1, 2, 8, 13 -> 0
1, 2, 4, 6, 8 -> 1
fonte
25, 9, 4, 1
( desta publicação math.SE ) - mesmo que cada moeda seja maior que a soma das menores, as que não são gananciosas25, 4, 4, 4
ganham as que são gananciosas25, 9, 1, 1, 1
.9, 4, 1
->4, 4, 4
ser melhor do que9, 1, 1, 1
é um exemplo mais rigoroso.Respostas:
Haskell,
948782 bytesEssa solução funciona definindo uma função
j
que executa o algoritmo do caixa e informa quantas moedas o caixa usou. em seguida, verificamos o dobro do maior número da lista, supondo que o sistema tenha sido canônico para todos os números anteriores, que pegar a maior moeda possível é a escolha certa.Esta solução assume que a entrada está classificada.
basta verificar o comprovante até o dobro do maior número: suponha que o sistema não seja canônico para algum número
i
e deixek
o número maior da lista não maior quei
. assuma issoi >= 2k
e o sistema é canônico para todos os números menores quei
.use uma maneira ideal de criar
i
moedas e assuma que ela não contém a moedak
. se jogarmos fora uma das moedas, a nova soma de moedas deve ser maiork
e menor quei
- mas o algoritmo do caixa nesse número usaria ak
moeda - e, portanto, esse conjunto de moedas pode ser substituído por um conjunto igual de moedas contendo a moedak
e, portanto, há um conjunto de moedas contendo a moedak
para o númeroi
e, por indução, o algoritmo do caixa retorna a melhor opção.esse argumento realmente mostra que precisamos verificar apenas a soma dos dois maiores elementos - mas é mais demorado.
Edit: cinco bytes fora graças a Ørjan Johansen!
fonte
let
vez dewhere
. Você pode colocá-lo como um|let ...
protetor de padrão depoisf s
ou dentro da compreensão da lista.j i=last$0:[1+j(i-k)|k<-s,k<i]
.Pitão,
1815 bytesSuíte de teste
Um tipo diferente de força bruta. Isso começa formando todas as coleções de moedas com até k de cada uma, onde k é a maior moeda, que se supõe ser a última moeda. Eu acredito que isso sempre é suficiente para formar dois conjuntos de moedas com a mesma soma, uma gananciosa e outra mais curta, sempre que esse par existir.
Em seguida, localizo esse par da seguinte maneira:
Os subconjuntos são gerados em ordem crescente de tamanho e lexicograficamente por posição na entrada secundariamente. Agrupe as coleções de moedas por suas somas, de forma estável. Cada coleção de moedas é gerada em ordem decrescente, de modo que a solução gananciosa será o primeiro elemento do grupo, se e somente se a solução gananciosa for ótima, e será o último elemento do grupo lexicograficamente. Assim, encontramos a solução gananciosa e filtramos um índice diferente de zero no grupo. Se o conjunto de moedas for canônico, isso filtrará tudo, então simplesmente negamos logicamente o resultado e a saída.
Explicação:
fonte
/opt/tryitonline/bin/pyth: line 5: 28070 Killed ... Exit code: 137
no TIO? Apenas sem memória?PHP, 323 bytes
Da mesma forma que outras, conte as moedas até a soma dos dois últimos elementos da matriz
Minha melhor e mais longa resposta, acredito> 370 bytes
Dou apenas uma versão expandida porque é mais longa do que minha resposta antes
Explicação para esta resposta
Versão Online
Defina tudo na matriz como false == X
Defina todos os números na matriz que você controla como S
Foram encontradas diferenças entre o último S e o outro S ou 0
Comece por último S na matriz
Defina todo o número como D Where Last S + uma de todas as diferenças
Comece em todos os D
DEFINIR "T" para D valores na matriz
GOTO 5 Repita-o com todos os DI encontrados, não realmente no código
Se o próximo item na matriz tiver X, é um caso falso, caso contrário, True
Etapas adicionais A diferença está no caso no trecho 3 Entre 1 e 4 são 2 X Isso significa que você precisa do segundo D da Etapa 5. Após esse valor nesse caso 10 são todos os casos verdadeiros, eu pude ver até o momento que existe um relacionamento entre a diferença e a contagem na matriz que você controla para calcular quanto D (Etapa 5) você precisa obter o ponto antes de encontrar o último caso falso.
Você define vários valores do último item diretamente para true. Esses pontos podem fazer a diferença para decidir se a contagem gananciosa de moedas com o próximo valor é igual à do múltiplo do último na matriz. Por outro lado, você pode definir inimigos
Defina o primeiro inimigo como 1 + Último S
A partir deste ponto, adicione cada valor na matriz para definir os próximos inimigos.
Comece com o último inimigo Goto 2
Se agora você tem inimigos e casos verdadeiros, aumenta a probabilidade de que as contagens possam ser as mesmas. Com mais D, a probabilidade diminui.
mais? Bytes Obrigado @ JonathanAllan por me fornecer casos de teste errados
262 Bytes Quase, mas não o suficiente, 4 casos de teste incorretos no momento
casos de teste [1,16,256] antes devem ser verdadeiros após falso
Ordem crescente da matriz
Explicação
Parece que o que vi na tabela contém valores de [1,2,3,4,5,6] e altero apenas o último item até 9. para 2to3 e 4to5, criamos o valor do valor mais baixo no cálculo do módulo
fonte
", "
quando pode se separar","
; por que você se separa quando pode fazer uma lista; por que você classifica quando pode fazer uma lista classificada? (Eu também sou ainda não tem certeza se o método que você está usando é infalível, não é uma prova, porque a literatura Eu desnatado através parece sugerir que é mais difícil do que o que eu acho que o código está fazendo.)[1,2,5,11,17]
é canônico. Talvez dê uma olhada no artigo vinculado na minha resposta.JavaScript (ES6), 116
125 130Isso precisa da matriz de entrada classificada em ordem decrescente. Para cada valor de 2N até 2 (N é o valor máximo da moeda), ele encontra o número de moedas do algoritmo ganancioso e tenta encontrar um conjunto menor de moedas.
Menos golfe
Teste
fonte
Python,
21821115bytes-1 byte graças a @TuukkaX (um espaço pode ser excluído entre
<3
eor
)repl.it
Entrada em ordem decrescente.
Força horrivelmente bruta. Qualquer conjunto de uma moeda unitária e outra moeda é canônico. Para conjuntos maiores, o menor caso de falha, se existir, será maior ou igual à 3ª menor moeda (não tenho certeza de como poderia ser igual!) E menor que a soma das duas maiores moedas - veja este documento (que na verdade referencia outro, mas também fornece um método O (n ^ 3)).
g
conta as moedas usadas pelo método ganancioso, e a função sem nome percorre os possíveis candidatos (na verdade, de 0 a um a menos que o dobro da maior moeda para salvar bytes) e procura por qualquer coleção de menos moedas que também somam esse valor.g
trabalha executando o que um caixa faria, recursivamente pega a maior moeda menor ou igual ao valor ainda a ser recuperado[v for v in c if v<=x][0]
e conta e conta o número de moedas usadasn
,.A função sem nome retorna 1 se
len(c)
for menor que 3 e, caso contrário, testa que não é o caso,1-...
que quaisquer valores no intervalo de possibilidadesrange(c[0]*2)))
são possíveis com menos moedas,i in range(g(x,c))
criando uma coleção dessas muitas moedas,c*i
e examinando todas as combinações dei
moedas,,combinations(c*i,i)
para ver se alguma soma tem o mesmo valor.fonte
3or
Deveria trabalhar.not(...)
com #1-...
Gelatina ( garfo ),
1514 bytesEsta solução usa os limites para contra-exemplos deste documento . Lá, o autor usa um limite restrito para o contra-exemplo, mas, no interesse do golfe, é usado o intervalo da soma das denominações de moedas que é maior e contém esse limite.
Este programa calcula todos os casos de teste em menos de um segundo na minha máquina.
Infelizmente, isso depende de um ramo do Jelly, onde eu estava trabalhando na implementação de um átomo de solução Frobenius, para que você não possa experimentá-lo online.
Uso
O desempenho é bom e pode resolver todos os casos de teste de uma só vez em menos de um segundo.
Explicação
fonte
JavaScript (ES6),
144132124122110 110 bytesRequer que a matriz seja classificada em ordem decrescente. Usa a observação no artigo vinculado de que, se o sistema não for canônico, haverá pelo menos um valor menor que 2a [0], que exige menos moedas quando decomposto usando as moedas não utilizadas do algoritmo ganancioso inicial.
Edit: Salvo 12 bytes, percebendo que eu poderia verificar todas as moedas, mesmo que eu já tivesse atingido o valor alvo. Economizei 8 bytes alternando minha saída intermediária de
[l,b]
para[b,-l]
; isso me permitiu passar o primeiro resultado diretamente como o parâmetro da segunda chamada, além de uma pequena economia detectando se a segunda chamada foi bem-sucedida. Economizei 2 bytes movendo a definição deg
para osome
retorno de chamada, permitindo evitar passar desnecessariamente na variável de loop duas vezes. Economizei 12 bytes, alternando da minha função auxiliar recursiva para uma chamada parafilter
(possibilitada pela minha chave de saída intermediária).fonte
Perl, 69 bytes
Inclui +2 para
-pa
Dê moedas em ordem decrescente no STDIN. Opcionalmente, você pode deixar de fora a
1
moeda.coins.pl
:Constrói o número de moedas usadas pelo algoritmo dos caixas
@G
para montantes de 1 a duas vezes a maior moeda. Para cada quantia, verifique se, se essa quantia for reduzida em 1 valor de moeda, o algoritmo dos caixas precisará no máximo de 1 moeda a menos. Caso contrário, este é um contra-exemplo (ou houve um contra-exemplo anterior). Eu poderia parar no primeiro contra-exemplo, mas isso leva mais bytes. Portanto, a complexidade do tempo éO(max_coin * coins)
e a complexidade do espaço éO(max_coin)
fonte