[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Algoritmo Errata



Minha outra resposta desse e-mail tem uns erros,
reescrevo aqui, espero que esteja certo agora.

 --- João_Gilberto_Ponciano_Pereira
<jopereira@vesper.com.br> escreveu: > Pessoal
> 
> Alguém saberia um algoritmo otimizado para resolver
> as seguintes questões?
> 
> 1- Seja A o conjunto de naturais de 6 dígitos como
> combinação dos algarismos
> 1...6 (sem repetição), ordenados de forma crescente,
> tal que A1 = 123456, A2
> = 123465, A3 = 123546 .... A6! = 654321
> Dado X, encontrar o valor de Ax

Crie a sequencia B(1, 2, 3, 4, 5, 6)
Faça o seguinte de n = 1 até n = 6

Pegue o quociente inteiro Qn = (X % 5! % 4! % ... %
(7-n)!) / (6-n)!, incremente em 1. *Retire* o Qn-ésimo
elemento de B (B passa a ter um elemento a menos) e
coloque ele na n-ésima casa mais significativa de AX.
Onde a % b é igual ao resto da divisão de a por b.

n=1
Pegue o quociente inteiro q1 = X/5!, incremente q em
1.
*Retire* o q1-ésimo elemento da sequência B e coloque
ele na casa mais significativa de AX.

n=2
Agora pegue o quociente inteiro q2 = (X % 5!)/4!.
incremente q2 em 1, retire o q2-ésimo elemento de B e
coloque ele na segunda casa mais significativa de AX.
..
..


quando n = 6 você repete aquilo tudo e você tem seu AX
prontinho.

(não testei esse algorítimo, mas acho que funciona)

> 2- Seja A o conjunto de naturais de 6 dígitos como
> combinação dos algarismos
> 1...8 (sem repetição), ordenados de forma crescente,
> tal que A1 = 123456, A2
> = 123457, A3 = 123458 .... A(8!/2!) = 876543
> Dado X, encontrar o valor de Ax

análogo ao primeiro, com a diferença que sempre vai
sobrar 2 números em B

[]'s,
Helder Toshiro Suzuki


_______________________________________________________________________
Yahoo! Mail
O melhor e-mail gratuito da internet: 6MB de espaço, antivírus, acesso POP3, filtro contra spam. 
http://br.mail.yahoo.com/
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================