Números de saída até 2 ^ n-1, "classificados"
Tome um número inteiro positivo n como entrada e dê saída (alguns dos) números decimais que podem ser criados usando n bits, ordenados da seguinte maneira:
Primeiro, liste todos os números que podem ser criados com apenas um 1e o restante 0na representação binária (classificada), depois todos os números que podem ser criados com dois consecutivos 1 , o restante 0, depois três consecutivos 1 e assim por diante.
Vamos ver como é isso para n = 4 :
Portanto, a saída para n = 4 é: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (formato de saída opcional).
Isso é código-golfe , então o código mais curto em cada idioma vence!
Boas explicações são altamente encorajadas , também para soluções em "idiomas regulares"!
Um dup de codegolf.stackexchange.com/q/98322/61904 ?
@ zeppelin Eu também pensava assim no começo, mas este é muito diferente.
Relacionado. (Ligeiramente).
Bônus imaginário se alguém fizer isso sem nenhuma forma de conversão básica (usando simples matemática antiga).
Escrevi isso, que é uma mistura entre os dois, eu acho. Experimente online!
Python , 53 bytes
A função recursiva gera a lista classificada como uma pré-ordem percorrida nesta árvore (exemplo com n=4):
As ramificações esquerdas dobram o valor, e as ramificações direitas i->i*2+1existem e existem apenas para ímpares i. Portanto, a caminhada de pré-encomenda para não-folhas é T(i)=[i]+T(i*2)+i%2*T(i*2+1).
A árvore termina em profundidade n, onde nestá a entrada. Isso é obtido decrementando na cada passo e parando quando é 0.
Uma estratégia alternativa seria terminar com valores que iexcedam 2**n, em vez de rastrear a profundidade. Eu achei que esse fosse um byte a mais:
Uau. Não é apenas um truque muito legal / inteligente, mas é extremamente eficaz. +1, resposta muito boa!
O [f]toque é divertido, não posso dizer que já vi isso antes.
Isso se qualifica para o bônus imaginário .
Ẇé um componente ideal para esse desafio e é implementado para que os resultados estejam na ordem certa para esse desafio. Bem feito :-)
Não são esses 12 bytes (pelo menos em UTF-8)?
@Gareth Sim, mas o Jelly também suporta um conjunto de caracteres de byte único , que contém os únicos 256 símbolos que entende.
Cada número na lista desejada é a diferença de duas potências de 2; portanto, simplesmente as geramos em ordem, usando Tablee achatando a lista. Eu acho que isso ganha o bônus imaginário de Stewie Griffin :)
Uma porta do algoritmo Jelly de Dennis . Eu não sabia Subsequencesantes disso! (Também não vi que as milhas haviam postado essa resposta exata ... vá com uma votação!)
Nota: Esta solução é idêntica ao código Mathematica de @mile , publicado 5 horas antes da edição de @GregMartin. No entanto, por meta consenso , essa resposta ainda é válida.
Ugh, eu não vi isso - obrigado por apontar.
Um programa completo que recebe informações por meio de um prompt e alerta cada número em sucessão. Isso também se qualifica para o bônus imaginário .
(Nota: usa em console.logvez de alert)
Sugestão (depois de verificar "não mostrar mais pop-ups"): Altere para console.log para o trecho de teste.
@TejasKale Boa ideia, obrigado!
Retorna uma lista separada por espaços de números inteiros.
Bônus imaginário amigável.
Python 2 , 64 61 bytes
-3 bytes graças a Dennis
Python 2 , 65 63 58 bytes
Passei uma hora inventando essa fórmula (2<<i)-1<<j... e você já descobriu. Bom trabalho! Além disso, bom trabalho em se livrar das faixas duplas
Exemplo de uso: f 4-> [1,2,4,8,3,6,12,7,14,15]. Experimente online! .
Como funciona: para cada número bem [1..n], comece com 2^b-1e repetidamente dobrar o valor e tomar n-b+1elementos desta lista.
Usa o truque de soma de sub-listas, como mostrado na resposta de Dennis 'Jelly
A conversão binária é tão burra no groovy.
-1 graças a Gurupad Mamadapur
Clichê de conversão binária de 28 bytes, tão doloroso.
{(1..<2**it)...salva um byte.
Usa o algoritmo de Dennis.
Utilitários Bash + Unix, 51 bytes
A entrada n é passada em um argumento.
Use seq para imprimir todos os números com n ou menos dígitos. (Estes são os números da base 10, portanto, existem muitos números extras aqui. É um desperdício e consome tempo, mas isso é código de golfe!)
A chamada para grep mantém apenas os números que consistem precisamente em 1s seguidos por 0s.
Em seguida, use sort -r para classificá-los em ordem lexicográfica reversa.
Por fim, dc está definido como entrada de base 2 - empurra os números classificados em uma pilha e depois imprime a pilha de cima para baixo. (Isso imprime o último item enviado primeiro, etc., e é por isso que estou usando sort -r em vez de apenas sort.)
Corrigido um erro: eu havia omitido a opção -f% .f para seq, necessária para contagens de números inteiros a partir de 1000000 em diante. (Agradecemos a @TobySpeight por apontar que havia um problema.)
" Desperdício e demorado " ... e inteligente ! Obrigado por isso - é um bom lembrete de ignorar deliberadamente a eficiência computacional ao jogar golfe. Isso é realmente difícil quando você passar o resto de seus dias escrevendo rápido e código claro ...
Alguns valores estão faltando: dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -relata apenas 12 valores. Eu acho que você quer, em grep ^1[01]*$vez disso.
@ TobySpeight Obrigado - houve um erro que eu corrigi. O problema não estava na regex; a questão era que seq exigia uma opção. (Não sei por que você estava obtendo apenas 12 valores de saída - mesmo a versão incorreta produziu 21 valores em vez dos 28 corretos. .) Eu testei isso no Linux e no OS X agora.
Na verdade, eu não entendi bem a pergunta - a palavra importante "consecutiva" de alguma forma passou direto por mim!
Perl 6 , 38 bytes
Ou seja, constrói os números assim:
Essa foi a minha primeira abordagem antes de pensar na solução de mudança de bits (na verdade mais simples) acima.
Eu comecei com f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]
da resposta de nimi acima ganhou o insight que sum.map(2^)$[0..x]pode ser condensado até2^x-1
[1..n] - lista com o número de bits consecutivos que queremos percorrer`
>> = - traduzido aproximadamente para cada elemento da lista à esquerda, passe-o para a função à direita e concatene todos os resultados
\ x -> - declaração da função lambda com um argumento
map xy - aplica a função x a todos os membros da lista y
No nosso caso x = (\ y-> 2 ^ y * (2 ^ x-1)) - outra função lambda 2 ^ y * (2 ^ x-1)). Essa fórmula surge da multiplicação por duas adicionando um zero à direita em binário (exemplo 0001 a 0010). 2 ^ x - 1 é o número de bits com os quais estamos trabalhando. portanto, para 11, temos 2 ^ 0 * 3 (isto é, não mude nada) == 0011, então 2 ^ 1 * 3 = 0110 e, em seguida, 2 ^ 2 * 3-1100.
[0..nx] Cria a lista de quantas vezes podemos mudar os bits. Se estivermos trabalhando com um único 1, olhando para 0001, queremos mudar 3 vezes (4-1). Se estamos trabalhando com dois 11, queremos 4-2 e assim por diante.
Nota: isso foi feito independentemente das soluções de ovs e de Dennis , embora seja muito semelhante a ambas.
Dicas (codificação e dinheiro) são sempre bem-vindas!
Japonês , 11 bytes
Isso praticamente usa a abordagem de @ Dennis:
Python , 61 59 bytes
Você pode usar $argnmuito boa ideia. Depois de ler a pergunta que eu tenho na minha cabeça uma solução com mais de 200 Bytes
@ JörgHülsermann Obrigado por me lembrar de STDIN. Eu simplesmente amo mesclar loops.
J , 19 bytes
Isso usa o mesmo método na solução @Dennis ' .
Programa completo, com saída separada por vírgula + espaço, conforme especificado.
A notação em estrela descompacta as listas. Então print(*[1,2,3])é o mesmo que print(1,2,3). Passe ao int()construtor uma sequência de '1's consecutivos.
-~bavalia como b+1, mas você não precisa cercá-lo entre colchetes ao multiplicar uma sequência.
Bitshift o número inteiro produzido um número crescente de vezes. print()possui o argumento sep opcional, especificando a sequência a ser inserida entre cada item em uma lista descompactada.
Você pode apenas imprimir a lista. O formato de saída não é tão rigoroso.
Dobra o valor inicial desde que o resultado seja menor que 2^n. Posteriormente, atualiza o valor inicial a ser (initial_value * 2) + 1e inicia novamente a partir daí até que finalmente chegue (2^n)-1.
por exemplo, para n=4:
Tentei algumas abordagens "inteligentes", mas essa parece ser a mais curta (literalmente, siga as instruções)
Cada iteração começa com 2 ^ n-1 e multiplica por 2 até que o limite superior seja atingido. Nada extravagante, apenas matemática básica.
QBIC , 37 bytes - bônus imaginário = ainda 37 bytes ...
Pena que ainda não while-wendintegrei o QBIC ... Explicação:
EDIT: QBIC agora tem suporte para WHILE:
Isso é apenas 26 bytes! Aqui está o WHILE:
1 byte salvo graças a @Luis
@LuisMendo muito esperto! Obrigado
R , 69 48 46 bytes
Cada número decimal correspondente aos do i in 1..nsistema binário é multiplicado por 2^(0..n-i), ou seja, primeiras n-i+1potências de dois (1, 2, 4, ...).