情報基礎A 「Cプログラミング」総合演習

このページには、線形計画法を使って空間を「最大限に」埋める円を描くプログラムの開発を、演習課題としてまとめました。

準備

以下に取り組む前に、まず、以下のページの内容を確認しておくこと。

作業を始める前に、同じディレクトリにturtle.hが保存されていることを確認すること。

なお、課題3と4については、加えて、simplex.hも必要である。

課題１ 円の描画

亀で描く基本的な図形 多角形の描画関数を参考に、中心座標 x,y 半径 r の円を描く関数 circle(x,y,r) を定義し、 それを使って、図1に示すように、左端が互いに接し、半径の異なる10個の円を描画するプログラム: ten-circles.cを作成せよ。

円を多角形で近似的に（「折れ線近似」で）描く際、小さな円では線分（多角形の辺）の長さをあまり短くしても、見栄えはほとんど違わない。 そこで、circle()関数では、半径に応じて辺の長さを適切に調整することで、小さな円ほど素早く描ける（亀場での描画時間が短くなる）ように工夫せよ。

課題では、最も大きな円の中心座標を(0.0, 0.0)、半径を200.0とし、円の半径が 200.0, 180.0, 160.0, ... 20.0 と規則的に変化するようプログラムすること。 その際、「規則的な変化」を反復処理（for文）によって実現すること。

スクリーンショットの画像ファイル名は ten-circles.pngとせよ。

図１

tfield-capture-kadai1-3

課題２　円による「縄張り」の定式化

この課題に取り組む前に、線形計画法による最適化 の内容を把握し、例題プログラムを実行してみること。線形計画法については、教科書3.7節『焙煎コーヒー売ってます』が参考になる。

上記を踏まえ、平面上の異なる４点(点0, 1, 2, 3とする）を中心に、半径がそれぞれ $r_0, r_1, r_2, r_3$ の4つの円を描いた際、 円が互いに重なり合わず（円が別の円の中に含まれてもいけない）、かつ、半径の和($r_0+r_1+r_2+r_3$)を最大とするような半径の組み合わせを、線形計画問題として解きたい。

円iとjの中心間距離を$d_{ij}$のように表記する（例えば、1と2の距離は$d_{12}$）とき、この問題の制約条件と目的関数を表す表式を、 以下の例（これは3点の場合）にならってテキストファイルで文書化せよ。数式はC言語の書式に沿って記述すること。 ファイル名は opt-circle-4.txt とせよ。 

課題2
氏名 東北太郎

点0, 1, 2の座標をそれぞれ (x[i], y[i]) (ここでi=0,1,2)とし、それらを中心とする円の半径を r0, r1, r2 とする。

目的関数:
1*r0 + 1*r1 + 1*r2

制約条件:
1*r0 + 1*r1 + 0*r2 <= d01
0*r0 + 1*r1 + 1*r2 <= d12
1*r0 + 0*r1 + 1*r2 <= d02
r0>=0
r1>=0
r2>=0

ここで、点間の距離はそれぞれ
d01 = sqrt((x[0]-x[1])*(x[0]-x[1]) + (y[0]-y[1])*(y[0]-y[1]))
d12 = sqrt((x[1]-x[2])*(x[1]-x[2]) + (y[1]-y[2])*(y[1]-y[2]))
d02 = sqrt((x[0]-x[2])*(x[0]-x[2]) + (y[0]-y[2])*(y[0]-y[2]))
で与えられる。

課題３　円による「縄張り」の描画

課題2を踏まえ、以下に示すの4つの円の配置について最適解を計算し、図4の例のように、亀場に最適な大きさの円を描くプログラムを作成せよ。

計算に用いる4つの円の中心座標 (x,y)

0, 0
100, 120
30, -70
-90, 10

最適解の計算とグラフィック表示は、ひとつのプログラム中で行なうようにすること（２本の別々のプログラムを作成するのではない）。 円の描画には、課題1で作成したcircle()関数を用いること。 また、グラフィック表示だけでなく、円の半径$r_i$と目的関数$z$の最大値を、printf()関数を使って、コンソール画面に出力するようにすること。

プログラムファイル名はopt-circle-4.c、スクリーン画像のファイル名はopt-circle-4.pngとせよ。

図2

tfield-capture-kadai2-1

opt-circle-4.cのひな形

亀場用ヘッダーファイル
turtle.h
に加えて、線形計画法用の
simplex.h
をプログラムと同じディレクトリーに保存しておくこと。 

/* 情報基礎A 課題3 氏名：東北太郎 */
#include <stdio.h>
#include <math.h>
#include "turtle.h"

#define N ???
#define M ???

#include "simplex.h"

void circle( ??? )
{
 ...
 
}

main() {
  /* 必要な変数を宣言・設定する */
  float a[M][N] = { ??? } ;
  float b[M] = { ??? } ;
  float c[N] = { ??? } ;
  int res ;
  ...

  /* 線形計画法を解く */
  INIT_COEF(a, b, c) ;
  res = SIMPLEX() ;
  ...

  /* 計算結果をグラフィック表示する */
  CON("localhost") ;
  CLR() ;
  RST() ;
  ...

}

課題４ 線形計画法による計算の自動化

課題3で作成したプログラムをさらに発展させ、 キーボードから8つの点のx,y座標を入力すると、線形計画法の条件式（配列要素の値）を計算によって自動生成し、 円の配置をグラフィック表示するCプログラムを作成せよ。 加えて、円の半径$r_i$と目的関数$z$の値を、コンソール画面に出力するようにすること。 プログラムファイル名は opt-circle-8.c とし、スクリーン画像はopt-circle-8.pngとせよ。

なお、スクリーン画像を提出する際には、以下の座標値について計算した結果を示すこと：

円の中心座標（x,y)
0, 0
-50,-180
-100,0
-100,120
70,180
90,10
180,50
-170,-60

描画の際、図3のように、円だけでなく中心点の座標も分かるよう表示すること。

図3

tfield-capture-kadai2-2

【ヒント】$n$個の点が与えられたとき、互いの中心間の距離は、$ {n \choose 2}$　通りの組み合わせがある。 すなわち、２つの円の半径の関係についての制約条件の数は$\frac{n(n-1)}{2}$である。