2006年06月13日
テクニカルエンジニア（エンベデッドシステム）試験に合格
情報処理技術者試験、２００６年春季の合格発表があり、受験した「テクニカルエンジニア（エンベデッドシステム）試験（ES）」に合格しました。
午前試験のスコアは，710 点です。
午後I試験のスコアは，725 点です。
午後II試験のスコアは，635 点です。←ギリギリ
前日に大同工大ロボットバトルに参加して、夜行バスで帰ってきてその足での受験と、無茶しましたが、ギリギリ合格していました。
投稿者 hiranoy : 23:28 | コメント (0)
2005年12月13日
アルゴリズム問題、解けるかな？
行きつけのblogで、アルゴリズムの問題が出されていた。
-------------------------------
【問題】 単方向リストがある。ノード数を n とするが、n の値は分からない。リスト中にループ（循環参照）が存在するか否かを O(n) で判定するアルゴリズムを示せ。ただし、単純にポインタが指したノード全てにマーキングをしておいて、新しいノードに移るたびにマーキングされているかを調べることで判定することは禁じ手とする。
-------------------------------
しかも、「エンジニアを自認している人は是非チャレンジしてみてください。」ときたもので、やらずにはいられません。
循環参照が存在すると、それをたどって何か処理しようとしても、無限ループになるだけなので、「禁じ手」と書いてあるマーキングが一番素直なやり方と思うが、禁じ手なので他を考える。
ベタな方法としては、リストのポインタを、配列にコレクションして行き、新しく追加する要素がすでにコレクションの中にあれば、循環参照となるが、これはコレクションの要素の参照回数が、１，２，３，４と増えていくので、n(n+1) = O(n^2)にはなってしまう。
あれこれ考えて、何とか回答らしき方法が見つかりました。
（私の回答を見たくない人は下の「続きを読む」をクリックしないでください。）
私の答え
「逆方向への単方向リストに変換したときに、変換前のHead が指し示す要素のNextの値がNULLではない場合、循環参照がある」
逆方向への変換に最大約２ｎ回の処理、リストを元に戻すために最大約２ｎ回の処理で、最大約４ｎ回がかかるが、O(n)の表記法だと、O(n)に分類される。
以下、説明。
-----------------
下記のような循環参照の単方向リストがある。
Head 「Next=2」
↓
2 「Next=4」
↓
4 「Next=3」
↓
3 「Next=1」
↓
1 「Next=4」→4へ （←循環参照）
このリストを、逆方向の単方向リストに変換する。まずは、循環していないところまで。
・Headが2を指しているので、2をリストの終端にするため、2の内容を変数に退避し、「Next=NULL」と変更する。退避した内容が、「Next=4」だったので、次に4の処理を行う。
・逆方向のリストだと、直前に処理した2がNext=となるべきなので、4の内容を変数に退避し、「Next=2」と変更する。退避した内容が、「Next=3」だったので、次に3の処理を行う。
・逆方向のリストだと、直前に処理した4がNext=となるべきなので、3の内容を変数に退避し、「Next=4」と変更する。退避した内容が、「Next=1」だったので、次に1の処理を行う。
・逆方向のリストだと、直前に処理した3がNext=となるべきなので、1の内容を変数に退避し、「Next=3」と変更する。退避した内容が、「Next=4」だったので、次に4の処理を行う。
ここまで処理すると以下のようになる。
2 「Next=NULL」
↑
4 「Next=2」
↑
3 「Next=4」
↑
1 「Next=3」 ←ここまで逆方向に変換、1には「Next=4」が入っていたことが分かっている。
さらに循環のところを処理していく。
・逆方向のリストだと、直前に処理した1がNext=となるべきなので、4の内容を変数に退避し、「Next=1」と変更する。退避した内容が、「Next=2」だったので、次に2の処理を行う。
・逆方向のリストだと、直前に処理した4がNext=となるべきなので、2の内容を変数に退避し、「Next=4」と変更する。退避した内容が、「Next=NULL」だったので、ReverseHeadという変数を用意して、そこに2を入れる。これで逆方向への変換は終了する。
すると、以下のようなリストを得る。
Head=2 ReverseHead=2
↓ ↓
2 「Next=4」
↓
4 「Next=1」→1へ
↑
3 「Next=4」
↑
1 「Next=3」
よって、答えは、
「逆方向への単方向リストに変換したときに、Head が指し示す要素のNextの値がNULLではない場合、循環参照がある」
ということになる。
リストを破壊した状態で終了するといけないので、再度ReverseHeadから辿って、逆方向への変換を行うと、リストは元通りになり、本当の意味で処理終了となる。
念のため、循環がない場合の例
Head 「Next=2」
↓
2 「Next=4」
↓
4 「Next=3」
↓
3 「Next=1」
↓
1 「Next=NULL」
逆方向へ変換すると
Head 「Next=2」
↓
2 「Next=NULL」
↑
4 「Next=2」
↑
3 「Next=4」
↑
1 「Next=3」
↑
ReverseHead 「Next=1」
となり、Headが指し示す要素の内容は、「Next=NULL」となる。
-----------------------------
投稿者 hiranoy : 03:44 | コメント (0)
2005年12月09日
SH2-7045F用書き込み制御プログラム
SH2の7045F用の、書き込み制御プログラムを作成しましたので、ソースコードを公開しておきます。（他でも動作すると思いますが、7045Fでのみ動作検証しましたということです）
SH2でいう「書き込み制御プログラム」とは、簡単に言うと、SH2のフラッシュへ書き込む時にSH2側で動作するソフトです。SH2-7045Fのハードウェアマニュアルの２２章「256kBフラッシュメモリ(F-ZTAT)」に詳しい説明があります。
全てアセンブラで記述しましたので、コンパクトで内臓RAMの空き領域が多く、機能を追加したい方にはうってつけです。（私も、今後、通信速度の高速化とSH2に繋がったシリアルEEPROMへの書き込み機能を追加する予定です。）
シリアル転送プロトコルは、h8write と同じにしてあります。
使い方：
みついわゆきお氏作 h8write.c の中の bin7045[] 配列の中身を、下記の bin7045.txt の内容をコピペして置き換えて使用します。が、通信速度は9600bpsのままで、そこがボトルネックなので、書き込み速度に関してオリジナルと性能の違いはありません。どちらかというと、ソースがあるので、改造してみたい人用です。
ソースコード bin7045.asm
h8write.c 組み込み用テキストファイル bin7045.txt