「CodeIQ:Bits」の編集履歴(バックアップ)一覧はこちら
「CodeIQ:Bits」(2013/02/11 (月) 20:19:11) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
[[http://www.hyuki.com/codeiq/]]:問題1
:問題概要|
法則性を見つけて文字化けしたデータを復元する。
:データの先頭の一部|
?0??0?0???0?000100000?11??00?0100?0??1??000001?100?0010??000?1000?001100?0001101
:解法|
1)区切る
ビットの羅列から法則性を見つけるのは難しいので一定個数で区切ります。
個数はビット列ということでとりあえず8bit(1バイト)で区切ってみると
?0??0?0?
??0?0001
00000?11
??00?010
0?0??1??
000001?1
00?0010?
?000?100
0?001100
?0001101
とりあえず切りよく区切れたのでこのまま進めてみることに
2)法則を見る
見ると、下に行くほど上位のビットに1が出現することが多くなっているように思えるので、このことから0からの8bitの2進数という仮定を立てます。
そこで、実際の2進数と比較すると
?0??0?0?:00000000 ○
??0?0001:00000001 ○
00000?11:00000010 ×
??00?010:00000011 ×
0?0??1??:00000100 ○
000001?1:00000101 ○
00?0010?:00000110 ×
?000?100:00000111 ×
0?001100:00001000 ×
?0001101:00001001 ×
このように当てはまらないパターンがいくつか出現するため、仮定は間違いであるとわかります。
ただし、(わかっている範囲での)最上位bitの位置が左右で一致していることから仮定と答えが近いのではないかと考えられます。
そこでとりあえず最上位の1よりも上位にある?を0にしてみます。
00000000
00000001
00000011
00000010
000001??
000001?1
0000010?
00000100
00001100
00001101
だいぶそれっぽくなってきたんじゃないでしょうか?
残るは
000001??
000001?1
0000010?
この3つですね。
最初から4つのパターンは
00000000
00000001
00000011
00000010
であるため、00→01→11→10と変化すると考えられます。
6bit目と7bit目に適用すると
0000011?
00000111
0000010?
となります。
同じものが2度出現しないことから
00000111
00000111
00000101
と決定されるため、結果は
00000000
00000001
00000011
00000010
00000110
00000111
00000101
00000100
00001100
00001101
となります。
ここまでくればあとはすべてに同じ法則を適用するだけです。
基本的には
00000000
00000001
00000011
00000010
00000110
00000111
00000101
00000100
ここまでの法則を使って上位ビットまで拡大していけばOKです。
ちなみにこれはグレイコードという2進数表記法で隣接する値のハミング距離(異なる文字の数)が常に1になるようなものです。
私は元々知ってたので上述の手順の途中で気づいてからプログラムで書き出しました。
以下がそのコードです。
public class GrayCode {
public static void main(String args[]){
try {
PrintStream ps;
ps = new PrintStream("graycode.txt");
PrintStream oldps = System.out;
System.setOut(ps);
for(int i=0;i<256;i++){
String s = Integer.toBinaryString(i^i>>1);
s = String.format("%8s", s);
s = s.replaceAll(" ", "0");
System.out.println(s);
}
System.setOut(oldps);
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
このコードは縦に見たときのパターンからグレイコードを書き出していますので、縦のパターンから法則性に気づいた人もいるかもしれません。
ちなみに後から知ったんですが、ある2進数vからグレイコードへ変換するにはv ^ (v >> 1) をすればいいらしいです。
(^:排他的論理和、>>:ビットシフト)
[[http://www.hyuki.com/codeiq/]]:問題1
:問題概要|
法則性を見つけて文字化けしたデータを復元する。
:データの先頭の一部|
?0??0?0???0?000100000?11??00?0100?0??1??000001?100?0010??000?1000?001100?0001101
:解法|
1)区切る
ビットの羅列から法則性を見つけるのは難しいので一定個数で区切ります。
個数はビット列ということでとりあえず8bit(1バイト)で区切ってみると
?0??0?0?
??0?0001
00000?11
??00?010
0?0??1??
000001?1
00?0010?
?000?100
0?001100
?0001101
とりあえず切りよく区切れたのでこのまま進めてみることに
2)法則を見る
見ると、下に行くほど上位のビットに1が出現することが多くなっているように思えるので、このことから0からの8bitの2進数という仮定を立てます。
そこで、実際の2進数と比較すると
?0??0?0?:00000000 ○
??0?0001:00000001 ○
00000?11:00000010 ×
??00?010:00000011 ×
0?0??1??:00000100 ○
000001?1:00000101 ○
00?0010?:00000110 ×
?000?100:00000111 ×
0?001100:00001000 ×
?0001101:00001001 ×
このように当てはまらないパターンがいくつか出現するため、仮定は間違いであるとわかります。
ただし、(わかっている範囲での)最上位bitの位置が左右で一致していることから仮定と答えが近いのではないかと考えられます。
そこでとりあえず最上位の1よりも上位にある?を0にしてみます。
00000000
00000001
00000011
00000010
000001??
000001?1
0000010?
00000100
00001100
00001101
だいぶそれっぽくなってきたんじゃないでしょうか?
残るは
000001??
000001?1
0000010?
この3つですね。
最初から4つのパターンは
00000000
00000001
00000011
00000010
であるため、00→01→11→10と変化すると考えられます。
6bit目と7bit目に適用すると
0000011?
00000111
0000010?
となります。
同じものが2度出現しないことから
00000110
00000111
00000101
と決定されるため、結果は
00000000
00000001
00000011
00000010
00000110
00000111
00000101
00000100
00001100
00001101
となります。
ここまでくればあとはすべてに同じ法則を適用するだけです。
基本的には
00000000
00000001
00000011
00000010
00000110
00000111
00000101
00000100
ここまでの法則を使って上位ビットまで拡大していけばOKです。
ちなみにこれはグレイコードという2進数表記法で隣接する値のハミング距離(異なる文字の数)が常に1になるようなものです。
私は元々知ってたので上述の手順の途中で気づいてからプログラムで書き出しました。
以下がそのコードです。
public class GrayCode {
public static void main(String args[]){
try {
PrintStream ps;
ps = new PrintStream("graycode.txt");
PrintStream oldps = System.out;
System.setOut(ps);
for(int i=0;i<256;i++){
String s = Integer.toBinaryString(i^i>>1);
s = String.format("%8s", s);
s = s.replaceAll(" ", "0");
System.out.println(s);
}
System.setOut(oldps);
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
このコードは縦に見たときのパターンからグレイコードを書き出していますので、縦のパターンから法則性に気づいた人もいるかもしれません。
ちなみに後から知ったんですが、ある2進数vからグレイコードへ変換するにはv ^ (v >> 1) をすればいいらしいです。
(^:排他的論理和、>>:ビットシフト)
表示オプション
横に並べて表示:
変化行の前後のみ表示: