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

Zanoni Dias (PED)

 

Quarto Exercício de Laboratório

 

 

Composição

 

Seja Sn = {i | 1 £ i £ n} e uma função f: Sn ® Sn. Uma função f dessa forma (não necessariamente uma bijeção) pode ser representada resumidamente por uma seqüência de valores em Sn. Por exemplo, seja S5 = {1,2,3,4,5} e a função f como definida abaixo:

f:              1 ® 3

                2 ® 4

                3 ® 1

                4 ® 2

                5 ® 4

Podemos representar f pela seqüência (3 4 1 2 4), que significa que a função f mapeia 1 em 3, 2 em 4, 3 em 1, e assim por diante.

 

Podemos definir a composição de funções como o produto f1f2...fn. Note que a composição "age pela direita", ou seja a composição g = f1f2...fn, pode ser escrita como g(x) = f1(f2(...fn(x))). Por exemplo:

 

f1

f2

f3

g = f1f2f3

1 ® 3

1 ® 2

1 ® 4

1 ® 2

2 ® 5

2 ® 3

2 ® 1

2 ® 5

3 ® 4

3 ® 4

3 ® 3

3 ® 1

4 ® 1

4 ® 5

4 ® 2

4 ® 4

5 ® 2

5 ® 1

5 ® 3

5 ® 1

 

Temos, por exemplo, que g mapeia 1 em 2, pois f3 mapeia 1 em 4, f2 mapeia 4 em 5 e finalmente f1 mapeia 5 em 2; da mesma forma, g mapeia 2 em 5, pois f3 mapeia 2 em 1, f2 mapeia 1 em 2 e finalmente f1 mapeia 2 em 5, e assim por diante.

 

O programa

 

O objetivo deste laboratório é escrever um programa que lê um inteiro n (que representa o tamanho do conjunto Sn), um inteiro m (o número de funções a serem lidas) e em seguida n*m inteiros (que representam os n valores de cada uma das m funções). Seu programa pode supor que: 1 £ n,m £ 20 e que os valores lidos que formam as m funções são todos dentro do intervalo [1..n]. Seu programa deve ser capaz de ler todos os valores numa só linha - use read ao invés de readln. Seu programa deve calcular g = f1f2...fn  e imprimir o resultado como uma seqüência de inteiros.

 

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

 

(1 3 2)

 

Exemplo 2: Ao fornecer para o seu programa o valores 4 e 3 em seguida 2, 1, 4, 3, 3, 4, 1, 2, 3, 1, 3, 4 ele deverá imprimir o resultado:

 

(2 4 2 1)

 

Entrega

 

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