Este é um quebra-cabeça comum que muitos de vocês resolveram manualmente. Agora é a hora de escrever um algoritmo para resolver o mesmo.
Existem palitos de igual número alinhados em dois lados diferentes, um de frente para o outro. Há um único espaço vazio entre eles. Diga algo como a figura a seguir (se o número total de palitos de fósforo for 4).
Cada bastão pode deslizar um passo na direção para a frente (se o espaço frontal imediato estiver livre) ou pode ser saltado sobre um bastão na frente e aterrissar no espaço livre (se esse espaço estiver livre). O movimento na direção inversa não é possível (até o espaço é livre). Nenhum salto reverso também é permitido. Apenas um movimento é permitido em uma etapa.
Agora, você deve escrever um algoritmo para encontrar as etapas mínimas necessárias, usando as palitos de fósforo do lado esquerdo para o lado direito e os palitos de fósforo do lado direito para o lado esquerdo.
Por exemplo: se houver um total de 2 palitos de fósforo (1 em cada lado), as etapas serão:
Nota: Na figura acima, o lado esquerdo foi movido primeiro. Existe outra solução quando o manípulo do lado direito se move primeiro. Mas para esse problema, você deve fornecer apenas uma solução e isso também pressupondo que o manípulo do lado esquerdo se mova primeiro.
A figura a seguir descreve os movimentos com 4 palitos de fósforo (2 de cada lado):
Nota: Na figura acima, o lado esquerdo foi movido primeiro. Existe outra solução quando o manípulo do lado direito se move primeiro. Mas para esse problema, você deve fornecer apenas uma solução e isso também pressupondo que o manípulo do lado esquerdo se mova primeiro.
[Suposição: A entrada pode ser qualquer número par entre 02 e 14 (ou seja, 1 a 7 palitos de fósforo em cada lado). Para entradas fora desse intervalo, você não precisa fazer nenhuma validação nem fornecer nenhuma mensagem de erro. Nota: Na saída, cada etapa é separada por um '|' caractere (pipe). Os programadores COBOL sempre devem assumir o PIC 9 (2) como tamanho de entrada e também podem assumir que a saída tenha comprimento máximo fixo de 450 caracteres, preenchido com espaços à direita.]
Entrada de amostra:
02
Saída de amostra:
01To02|03To01|02To03|
Entrada de amostra:
04
Saída de amostra:
02To03|04To02|05To04|03To05|01To03|02To01|04To02|03To04|
Entrada de amostra:
06
Saída de amostra:
03To04|05To03|06To05|04To06|02To04|01To02|03To01|05To03|07To05|06To07|04To06|02To04|03To02|05To03|04To05|
fonte
Respostas:
APL 129
O código abaixo leva a entrada e a saída da tela para a tela no formato especificado:
Um bom terço do código é utilizado para formatar a saída. A lógica é completa pela ocorrência do símbolo in no código.
Abaixo está o resultado para uma entrada 08 como uma verificação:
fonte
Javascript
178 174161prompts paranentãoalerts resposta. (Sem0preenchimento)Mais recentes:
2:
1:
Isso usa o conceito de que o padrão é espelhado:
Então, onde
n=2, o padrão de movimento é:O que equivale a
Esse padrão se repete assim (
n=8)Podemos notar alguns padrões aqui:
n/2, que se repete 3 vezes e depois volta para 1.1e o número de saltos sequenciais aumentando de 1 paran/2depois diminuindo de volta para 1.n=14:Saída de amostra:
f(2):f(8):f(40):Aqui estão alguns pseudo-códigos para demonstrar o método:
fonte
l/L/r/Rem/j. Eu gosto da idéia de separar a distância movida da direçãoC -
216213Minha solução é baseada em dois fatos:
O campo "para" é o campo "de" da movimentação anterior (já que você sempre cria um espaço vazio no espaço do qual se move e sempre move para um espaço vazio)
Existe um padrão muito regular para as distâncias e direções que são movidas. Para os três primeiros casos de teste, eles são:
1 -2 11 -2 -1 2 2 -1 -2 11 -2 -1 2 2 1 -2 -2 -2 1 2 2 -1 -2 1Com isso em mente, basicamente escrevi um programa para produzir e continuar esse padrão. Tenho certeza de que deve haver uma maneira recursiva muito bonita e muito mais elegante de escrever isso, mas ainda não descobri:
E jogava golfe (mesmo que esse fosse um desafio de código, não golfe):
fonte
scanf. Estou atualizando minha resposta com uma versão melhor.N(2)=rLr,N(4)=rLlRRlLr,N(6)=rLlRRrLLLrRRlLr, etc.Mathematica
Essa abordagem cria uma
Nestsequência ed do tamanho e da direção dos movimentos, formatada como{fromPosition,toPosition}, começando pela posiçãon, em quense refere ao número de pares de correspondência. Em seguida,Foldé a sequência para uma função que começa com o movimento{n, n+1}.Visualizando os Swaps
r,,beosão imagens ou uma correspondência vermelha, uma correspondência azul e nenhuma correspondência, respectivamente.A seguir, formata a saída de
zpara exibir os swaps com correspondências.swapsproduz uma lista de estados usando os pares ordenados dezcomo comandos para permutar a lista inicial e as listas subseqüentes.swapMatchesexibe os estados em uma grade.fonte
Javascript 191
Caracteres contados usando
grep =|tr -d \ |wc -cfonte
02, os valores estão corretos, mas está faltando o final|. Nos outros dois casos, os valores estão muito diferentes e a formatação de10também está incorreta. Também não tem certeza sobre o seu método de contagem de caracteres. Por que você está contando apenas o corpo da função menos o retorno?tr -d \ |wc -cleva novas linhas em conta