Difference between revisions of "Problema do checksum"

From AdonaiMedrado.Pro.Br
Jump to: navigation, search
(New page: == Enunciado único == Os algoritmos de verificação tipo [http://pt.wikipedia.org/wiki/Soma_de_verifica%C3%A7%C3%A3o Checksum] trabalham executando operações sobre um conjunto de dados...)
 
Line 1: Line 1:
 
== Enunciado único ==
 
== Enunciado único ==
Os algoritmos de verificação tipo [http://pt.wikipedia.org/wiki/Soma_de_verifica%C3%A7%C3%A3o Checksum] trabalham executando operações sobre um conjunto de dados e são úteis para verificar se este conjunto de dados se permaneceu íntegro.
+
Os algoritmos de verificação tipo [http://pt.wikipedia.org/wiki/Soma_de_verifica%C3%A7%C3%A3o 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 onde cada par de bytes é chamado de P e elemento do par é chamado de B. Caso a entrada possua um número impar de bytes, para efeitos do algoritmo o último par é composto pelo último byte e o byte 0.
+
Este problema considera o seguinte algoritmo de checksum:
*Para cada par P
+
*Para cada byte B na posição P (sendo a primeira posição zero):
**Executa-se uma contagens dos bits 1 de cada elemento B chegando-se a um valor X.
+
**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.
**O valor X de cada byte B de P é operado bit-a-bit em operação de '''e''' chegando-se a um valor Y
+
**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 resto da divisão de Y por 11 deverá ser somado e acumulado em L.
+
*Ao final deve-se somar a L a quantidades de bytes B processados resultando em W.
+
  
O resultado checksum é W que deverá suportar o valor de até 100 dígitos.
+
O resultado deste algoritmo é W que deverá suportar um valor máximo de 32bits.
  
 
== Dificuldade 1 ==
 
== Dificuldade 1 ==
Line 25: Line 23:
 
  exemplo6.in
 
  exemplo6.in
 
  0
 
  0
 +
 +
Os arquivos acima podem ser baixados em [ftp://ftp.adonaimedrado.pro.br/web/wiki/documentos/professor/problema_checksum_entradas.zip].
  
 
==== Saída ====
 
==== Saída ====
 
  200
 
  200
  401
+
  202
  601
+
  357
  827
+
  15510
  38762
+
  52500
  51455
+
  13875
  
  
 
== Dificuldade 2 ==
 
== Dificuldade 2 ==
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).
+
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.
 
Para cada K deve ser gravado um aquivo K.checksum que deverá conter o número W representado em caracteres ASCII.

Revision as of 15:31, 19 June 2009

Enunciado único

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):
    • 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.

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

200
202
357
15510
52500
13875


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.