- 637 名前：デフォルトの名無しさん [2008/01/26(土) 15:31:15 ]
- [1] 授業単元：離散数学
[2] 問題文(含コード&リンク)：
格子点上に置かれた任意の4点を結ぶ最小の直線スタイナーツリーを見つけるプログラムを作成せよ。
候補が複数ある場合は、それらを全て表示させるようにさせよ。
[3.1] OS：XP
[3.2] コンパイラ名とバージョン：bcc
[3.3] 言語：C
[4] 期限：2/7
[5] その他の制限：
直線スタイナー木とは、碁盤上の縦横の線の交点に点を置き、
置いた全ての点を、碁盤の直線に沿って作る線分によって結ぶネットワークの事です。
例 www.dotup.org/uploda/www.dotup.org2826.jpg.html
閉路（ある点を出て、またその点に帰ってくる道がある状態）を作ってはいけません。
その直線スタイナー木の中で、最も距離の短いものを探せというものです。
もちろん、答えは複数候補ある場合が圧倒的に多いです。
とりあえず、自分で4点の座標を適当に置いてやれ、という事です。
どんなに泥臭い方法でも構わないので、ご協力お願いします。
|
 |
