情報科学基礎実験　課題106の研究

課題106

文字列を1つ受け取って、そのハッシュ値を表示するプログラムを作成せよ。 ハッシュ値を計算するアルゴリズムは何でもよいが、値は0以上9以下の整数になるようにすること。 文字列の長さは1以上99以内で、空白文字は含まれないと仮定してよい。

締切: 2010年12月27日正午

これに苦しんでいる同志のためにこの課題の詳細に研究しました。

ハッシュ関数とは？

• 格納場所を計算する関数はハッシュ関数と呼ばれ,対象とするデータを受け取り0～B-1までの整数を返す(Bはハッシュの大きさ).
  
  

  データ構造とアルゴリズム（数理工学社）p.34 より引用
  
  

ということで、すべての入力に対して0を返すようなハッシュ関数を実装すると次のようになります。ここでは入力を読む必要がないので読んでいないことに注意してください。

#include <stdio.h>

int main(){
  puts("0");
  return 0;
}

ちなみにこれでサーバーテストを通ります。

もしかして入力読んでない？

課題の性質上、提出されるプログラムが返すハッシュ値は一意に定まりません。ということはサーバーチェックの際に入力を読んでいない可能性が考えられます。そこで、何もしないプログラムを実装します。

main(){}

mainは型を指定しないと暗黙のうちにintとみなされます。これもサーバーテストを通ります。

もしかして実行してない？

ここまで来たら極限まで短くしたくなるのが人情というもの。コンパイルだけ通るプログラムを実装してみましょう。

main;

これは実行するとBus errorを起こしますが、なんとサーバーテストを通っていまいます。

もしかしてコンパイルしてない？

という疑問を抱いてさらに短縮化を試みます。次に示すプログラムはmainが存在しないのでコンパイルも通りません。

これはさすがに「コンパイル失敗」と怒られてしまいました。

結論

課題106はコンパイルさえ通ればよい。困った人は次のコードを提出しよう。ただしTAがどのように判断するかについて筆者は責任を持ちません。

main;

Category読み物