USACO - Your Ride Is Here

[JTGFerreira]

Boas pessoal,

no seguimento do que me foi sugerido decidi utilizar o USACO como ferramenta de aprendizagem. No entanto, logo no primeiro problema surgiu-me uma dúvida.

Submeti o meu código, foi aceite e passou em todos os testes mas ao ver a solução houve uma parte do código que não entendi:

#include <ctype.h>

int
hash(char *s)
{
int i, h;

h = 1;
for(i=0; s[i] && isalpha(s[i]); i++)
	h = ((s[i]-'A'+1)*h) % 47; //não percebo isto: (s[i]-'A'+1)
return h;
}

(Se isto for considerado spoiler avisem por favor que eu retiro).

Obrigado desde já.

[bubulindo]

'A' = 65. É isso que não percebes?

[pmg]

	h = ((s[i]-'A'+1)*h) % 47; //não percebo isto: (s[i]-'A'+1)

Eu não vi o problema, por isso não tenho o contexto completo.

O que a expressão s[ i ] - 'A' + 1] faz é, para cada i (para cada letra da string), assumindo que os caracteres 'A' até 'Z' são consecutivos (são-no em quase todos os computadores pessoais) é converter 'A' em 1, 'B' em 2, ..., 'Z' em 26.

Pelo código anterior, já sabemos que s[ i ] é uma letra (isalpha() devolveu "true"). Assumindo que as letras válidas são todas em maiusculas

s[i] - 'A' // 'A' - 'A' dá zero
s[i] - 'A' // 'B' - 'A' dá 1
...

[JoaoSantos95]

Eles usam o código ASCII de cada carácter para resolver o problema. O s[ i ] contêm o carácter em que nos situamos ao qual vai ser subtraído o código ASCII do carácter 'A' (e somar +1 visto que o 'A' é 1 e se não somassem ia dar a letra anterior aquela que nós queremos).

Exemplo:

Vamos supor que temos a palavra "ANA".

i = 1 -> s[1] = 'A' -> (('A' - 'A' + 1)) = 1 (como podemos ver obtivemos a posição da letra 'A' no alfabeto)

i = 2 -> s[2] = 'N' -> (('N' - 'A' + 1)) = 14 (como podemos ver obtivemos a posição da letra 'N' no alfabeto)

i = 3 -> s[3] = 'A' -> (('A' - 'A' + 1)) = 1 (como podemos ver obtivemos a posição da letra 'A' no alfabeto)

Aqui podes ver a tabela ASCII

[JTGFerreira]

Obrigado a todos, consegui entender  😛