2006年06月13日

テクニカルエンジニア(エンベデッドシステム)試験に合格

情報処理技術者試験、2006年春季の合格発表があり、受験した「テクニカルエンジニア(エンベデッドシステム)試験(ES)」に合格しました。

 午前試験のスコアは,710 点です。
 午後I試験のスコアは,725 点です。
 午後II試験のスコアは,635 点です。←ギリギリ

前日に大同工大ロボットバトルに参加して、夜行バスで帰ってきてその足での受験と、無茶しましたが、ギリギリ合格していました。

投稿者 hiranoy : 23:28 | コメント (0)

2005年12月13日

アルゴリズム問題、解けるかな?

行きつけのblogで、アルゴリズムの問題が出されていた。

-------------------------------
【問題】 単方向リストがある。ノード数を n とするが、n の値は分からない。リスト中にループ(循環参照)が存在するか否かを O(n) で判定するアルゴリズムを示せ。ただし、単純にポインタが指したノード全てにマーキングをしておいて、新しいノードに移るたびにマーキングされているかを調べることで判定することは禁じ手とする。
-------------------------------

しかも、「エンジニアを自認している人は是非チャレンジしてみてください。」ときたもので、やらずにはいられません。

循環参照が存在すると、それをたどって何か処理しようとしても、無限ループになるだけなので、「禁じ手」と書いてあるマーキングが一番素直なやり方と思うが、禁じ手なので他を考える。
ベタな方法としては、リストのポインタを、配列にコレクションして行き、新しく追加する要素がすでにコレクションの中にあれば、循環参照となるが、これはコレクションの要素の参照回数が、1,2,3,4と増えていくので、n(n+1) = O(n^2)にはなってしまう。

あれこれ考えて、何とか回答らしき方法が見つかりました。
(私の回答を見たくない人は下の「続きを読む」をクリックしないでください。)

私の答え
「逆方向への単方向リストに変換したときに、変換前のHead が指し示す要素のNextの値がNULLではない場合、循環参照がある」

逆方向への変換に最大約2n回の処理、リストを元に戻すために最大約2n回の処理で、最大約4n回がかかるが、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のハードウェアマニュアルの22章「256kBフラッシュメモリ(F-ZTAT)」に詳しい説明があります。

全てアセンブラで記述しましたので、コンパクトで内臓RAMの空き領域が多く、機能を追加したい方にはうってつけです。(私も、今後、通信速度の高速化とSH2に繋がったシリアルEEPROMへの書き込み機能を追加する予定です。)

シリアル転送プロトコルは、h8write と同じにしてあります。

使い方:
みついわゆきお氏作 h8write.c の中の bin7045[] 配列の中身を、下記の bin7045.txt の内容をコピペして置き換えて使用します。が、通信速度は9600bpsのままで、そこがボトルネックなので、書き込み速度に関してオリジナルと性能の違いはありません。どちらかというと、ソースがあるので、改造してみたい人用です。

ソースコード bin7045.asm
h8write.c 組み込み用テキストファイル bin7045.txt

投稿者 hiranoy : 03:01 | コメント (0)