Solução Informática – Nível Iniciante – Semana 28

Solução por Lúcio Figueiredo

Conhecimento prévio necessário:

• Loops

Perceba que não existem permutações bonitas para $n = 2$ e $n = 3$. Para $n = 1$, a permutação ${1}$ é uma resposta válida.

Para todo $n$ elementos. Para demonstrar isso, basta utilizar a seguinte construção:

1. Inicialmente, inisira o valor $2$ como primeiro elemento da permutação.
2. Em seguida, insira todos os números pares maiores que $2$ e menores ou iguais a $n$.
3. Por fim, insira em seguida os números ímpares menores ou iguais a $n$.

É fácil ver que a construção acima gera uma permutação bonita, já que não há nenhum par de elementos consecutivos com diferença igual a $1$.

Portanto, basta imprimir as três sequências indicadas acima utilizando um loop for. A complexidade final é $O(n)$. Confira o código abaixo para melhor entendimento: