MC102: Algoritmos e Programação de Computadores - Turmas K e L

Zanoni Dias (PED)

 

Terceiro Exercício de Laboratório

 

 

Bijeção

 

Seja Sn = {i | 1 £ i £ n} e uma função f: Sn ® Sn. Uma função f dessa forma é uma bijeção se e somente se puder ser escrita como uma permutação dos elementos de Sn. Por exemplo:

S5 = {1,2,3,4,5}

f:              1 ® 3

                2 ® 4

                3 ® 1

                4 ® 5

                5 ® 2

Podemos representar f pela permutação: (3 4 1 5 2), que significa que a bijeção f mapeia 1 em 3, 2 em 4, 3 em 1, e assim por diante.

 

Uma propriedade importante das bijeções é que toda bijeção f possui inversa f--1 (ou seja, f--1(x) = y, tal que f(y) = x). Para nosso exemplo anterior temos que f--1 pode ser representada pela permutação: (3 5 1 2 4). Para entender melhor: olhando a definição de f do exemplo acima percorra as setas (®) no sentindo contrário. Ou seja, 1 será mapeado em 3, 2 em 5, 3 em 1, e assim por diante.

 

Obs.:      Uma função é bijetora se ela for um mapeamento de um para um.

 

O programa

 

O objetivo deste laboratório é escrever um programa que lê um valor n (1 £ n £ 20) e em seguida n inteiros (seu programa deve ser capaz de ler todos os valores entrados numa só linha - use read ao invés de readln). Seu programa deve verificar se os valores lidos correspondem a uma bijeção válida para o conjunto Sn, ou seja, se os valores lidos formam uma permutação válida para este mesmo conjunto. Caso seja uma bijeção válida calcule e imprima f--1 (a inversa de f) na representação de permutação, caso contrário imprima a mensagem:

'Os valores lidos nao formam uma bijecao valida.'

 

Exemplo 1: Se você fornecer o valor 3, e em seguida 2, 3, 1, seu programa deverá imprimir:

 

(3 1 2)

 

Exemplo 2: Ao fornecer para o seu programa o valor 4 e em seguida 4, 1, 4, 2 ele deverá imprimir a mensagem:

 

Os valores lidos nao formam uma bijecao valida.

 

Exemplo 3: Para o valor 5, mais os números 4, 5, 1, 3, 2, seu programa deverá imprimir:

 

(3 5 4 1 2)

 

Entrega

 

O programa é estritamente individual e deverá ser entregue até dia 12 de novembro através da Web Page do curso (www.dcc.unicamp.br/~zanoni/mc102). Maiores detalhes serão discutidos em sala de aula e no laboratório.