Difference between revisions of "Problema do checksum"

Revision as of 15:40, 19 June 2009

Enunciado únificado

Os algoritmos de verificação tipo Checksum trabalham executando operações sobre um conjunto de dados e são úteis para verificar se este conjunto de dados permanece íntegro.

Este problema considera o seguinte algoritmo de checksum:

• Para cada byte B na posição P (sendo a primeira posição zero, a segunda 1, etc.):
  • Para cada B que estiver em uma posição P impar, deve-se contar a quantidade de bits 0 em B e acumular esta quantidade em um inteiro W.
  • Para cada B que estiver em uma posição P par, deve-se contar a quantidade de bits 1 em B e acumular esta quantidade em um inteiro W.

O resultado deste algoritmo é W que deverá suportar um valor máximo de 32bits.

Atenção: este algoritmo é apenas um exemplo para fins didáticos e não deve ser utilizado em aplicações reais.

Dificuldade 1

Faça um programa que receberá um número N e N cadeias de caracteres K (máximo de 200 caracteres). Cada K representará o caminho de um arquivo para o qual deve ser calculado o checksum segundo algoritmo descrito acima. A entrada termina quando for encontrada a cadeia "0" (sem as aspas).

A saída deverá ser dada na saída padrão e deverá ser o número W descrito no algoritmo acima.

Exemplo 1

Entrada

exemplo1.in
exemplo2.in
exemplo3.in
exemplo4.in
exemplo5.in
exemplo6.in
0

Os arquivos acima podem ser baixados em [1].

Saída

400
402
207
42146
96072
36937

Dificuldade 2

Faça um programa que receberá um número N e N cadeias de caracteres K. Cada K representará o caminho de um arquivo para o qual deve ser calculado o checksum segundo algoritmo descrito acima. A entrada termina quando for encontrada a cadeia "0" (sem as aspas).

Para cada K deve ser gravado um aquivo K.checksum que deverá conter o número W representado em caracteres ASCII.