1. Centroide

Uma das tarefas mais recorrentes na análise de dados é o cálculo do centroide de um conjunto de pontos do espaço euclideano $d$-dimensional. O centroide é a média do conjunto, isso é, cada uma de suas coordenadas é dada pela média das coordenadas correspondentes do conjunto de pontos. Tipicamente, o centroide é um ponto representativo das características de algum conjunto de dados.

No entanto, o cálculo de centroide é sensível à escala, então é necessário realizar uma etapa de preparação dos dados chamada de normalização (uma discussão sobre isso está disponível nesse link).

Há várias formas de preparar dados e, entre as mais comuns, listamos:

1. Não normalizar, i.e., utilizar os dados de entrada diretamente.

2. Normalizar coordenadas por intervalo, também chamada de normalização min-max. Nesse caso, cada coordenada é modificada linearmente de forma que os valores mínimos e máximos sejam $-1$ e $1$. Se todos os valores forem iguais, então cada coordenada é mapeada para $0$.

3. Tratar cada ponto como um vetor independentemente e dividir cada um deles por seu comprimento, de forma que o vetor passe a ter norma euclidiana unitária.

Escreva um programa centroide que leia um conjunto variável de pontos $d$-dimensionais e calcule o centroide utilizando cada uma das estratégias acima.

Uma consideração importante ao lidar com números com o computador é que muitas vezes eles não são representados de maneira exata. Que complicações isso pode ter e que tipos de cuidados você poderia ter para mitigar essas complicações?

Entrada

A primeira linha contém dois números inteiros $d$ e $n$ que indicam a dimensão e o número de pontos que serão lidos. Cada uma das próximas $n$ linhas contém $d$ números reais, correspondendo às coordenadas de um dos pontos.

3 2
1.600 -0.700 -0.600
-1.100 0.800 -2.400

Saída

A saída contém uma linha com o centroide encontrado para cada uma das estratégias acima, em ordem.

nenhum: 0.250 0.050 -1.500
janela: 0.000 0.000 0.000
normal: 0.234 -0.045 -0.597

2. Quase palíndromo

Uma string é um $k$-quase palíndromo se, ao compará-la com o seu inverso, tiver no máximo $k$ caracteres diferentes. Por exemplo, arara é um $0$-quase palíndromo e araro é um $2$-quase palíndromo.

Crie um programa quase_palindromo que verifique se uma palavra é um $k$-quase palíndromo.

Entrada

A primeira linha contém um número $k$ e a segunda linha contém uma string.

2
araro

Nesse exercício, você pode supor que a maior palavra tem 400 caracteres, então você não precisa se preocupar com entradas maiores do que isso. Na prática, isso quase nunca é verdade, então ler uma string cegamente, com scanf por exemplo, é pedir para ter problemas sérios de segurança. Quais são esses problemas e o que fazer para evitá-los mesmo sem conhecer a entrada?

Saída

Uma linha contendo sim ou nao, dependendo se a string é um $k$-quase palíndromo.

sim

3. Desafio e recompensa

João tem um dado com seis faces.
Maria está a $x$ passos de João.
Se João joga o dado e tira $p$,
Maria dá $p$ passos até o João.

Se $p$ é igual a $x$ nesse momento,
Maria recompensa João agora.
Mas se for maior que $x$, João, lamento,
Maria dá as costas e vai-se embora.

Crie um programa recompensa que calcule a probabilidade de João receber a recompensa se ele puder jogar o dado até $n$ vezes e cada vez Maria se aproximar mais um pouquinho. Você deve supor que todas as faces do dado ocorrem com probabilidades iguais.

Entrada

Número inteiros $n$ e $x$.

2 2

Saída

Um número entre 0 e 1 com três casas decimais após a vírgula representando a probabilidade de João conseguir a recompensa.

0.194

Dicas

Observe que no exemplo da entrada há apenas duas possibilidades para João ganhar o jogo: jogar o dado uma vez e obter a face 2; ou jogar o dado duas vezes obtendo a face 1 em cada uma delas. Em qualquer cenário diferente desses, Maria passará direto por João. A probabilidade de João obter a face 2 na primeira jogada é $1/6$. Se João obtém a face 1, ainda tem direito a mais uma jogada. Portanto, a probabilidade de João obter a face 1 duas vezes é $(1/6{)}^2=1/36$. A probabilidade de João ganhar a recompensa é $1/6+1/36=7/36\approx 0.194$. A imagem abaixo ilustra essas possibilidades.

Critérios

Você deve utilizar alocação dinâmica para armazenar e manipular os dados de entrada do primeiro item. Nos demais exercícios, não é necessária alocação dinâmica, mas você deve resolver os problemas utilizando algoritmos recursivos, mesmo que conheça algoritmos iterativos para eles.

← Anterior Voltar Próximo →