その挑戦受けて立つ(2)!!

アバター
tk-xleader
記事: 158
登録日時: 14年前
連絡を取る:
tk-xleader に連絡する

その挑戦受けて立つ(2)!!

投稿記事 by tk-xleader » 13年前

ってなわけで、次はコッホ曲線のほうについてやってみようかと（マージソートのやつは擬似コードがいまひとつピンと来ない。）…

問題
整数nを入力し、深さnの再帰呼び出しによって作成されるコッホ曲線の頂点の座標を出力するプログラムを作成せよ。
プログラムはC, C++, JAVA, C++11, C#, Dいずれかの言語で作成すること。

コッホ曲線はフラクタルの一種として知られている。フラクタルとは再帰的な構造を持つ図形のことであり、多くの場合再帰的な関数の呼び出しを用いて描画することができる。
コッホ曲線を描く手順は以下の通りである：

線分を引く。（図左上）
線分を3等分し、中央の線分を1辺とする正三角形を描き、下の辺を消す。（図右上）
得られた4つの線分に対して同じ操作を繰り返す。（図左下）
得られた16の線分に対して同じ操作を繰り返す。（図右下）

この操作を無限に繰り返すとコッホ曲線になる。

画像

なお、初期状態は(0, 0), (100, 0)を端点に持つ線分とする。

入力
　1つの整数nが与えられる。
出力
　コッホ曲線の各頂点の座標(x, y)を出力せよ。１行に１点出力せよ。端点の１つ(0, 0)から開始し、一方の端点(100, 0)で終えるひと続きの線分の列となる順番に出力せよ。出力は小終点４桁以下の誤差を含んでいてもよい。

制約

0 ≤ n ≤ 6
ところで、この問題は不完全です。nの使い方についての説明がありません。たぶん、nは再帰の深さなんでしょう。

ってわけで、これもD言語で解答することにしましょう。

解答

CODE: 

import std.stdio;
import std.conv;
import std.string;
import std.math;

struct Point{
	double x,y;
}

/**
 *コッホ曲線を表すクラス。
 */
class KochCurve{
	private Point[] vertexes;
	///両端の座標と、再帰の深さを引数に取るコンストラクタ
	///Params:
	/// begin = 始点
	/// end   = 終点
	/// n     = 再帰の深さ
	public this(Point begin,Point end,int n){
		setCurve(begin,end,n); //実際の処理はSetCurveメンバ関数に委譲する。
	}
	
	///コッホ曲線を生成してthisにセットする。
	///Params:
	/// begin = 始点
	/// end   = 終点
	/// n     = 再帰の深さ
	public void setCurve(Point begin,Point end,int n){
		Vertexes = makeCurve([begin,end],n);
	}
	
	///コッホ曲線の頂点座標を得る。
	@property public Point[] Vertexes(){
		return vertexes;
	}
	@property private void Vertexes(Point[] vertexes){
		this.vertexes = vertexes;
	}
	
	static private Point[] makeCurve(Point[] current,int nest){
		if(nest == 0)return current;
		
		Point[] result;
		for(int i = 0; i < current.length - 1; i++){
			result ~= current[i];
			
			//t1,t2は、線分を3等分する点の座標で、t1がcurrent[i]に近い方になる。
			Point t1 = Point((2 * current[i].x + current[i+1].x)/3,(2 * current[i].y + current[i+1].y)/3);
			Point t2 = Point((current[i].x + 2 * current[i+1].x)/3,(current[i].y + 2 * current[i+1].y)/3);
			
			result ~= t1;
			
			result ~= Point(t1.x + (cos(PI/3) * (t2.x - t1.x) - sin(PI/3) * (t2.y - t1.y)),
				t1.y + (sin(PI/3) * (t2.x - t1.x) + cos(PI/3) * (t2.y - t1.y)));
			
			result ~= t2;
		}
		result ~= current[$-1];
		
		return makeCurve(result,nest-1);
	}
}

void main(){
	//nは再帰の深さ
	int n = to!int(stdin.readln().strip());
	
	auto curve = new KochCurve(Point(0.0,0.0),Point(100.0,0.0),n);
	
	foreach(Point p; curve.Vertexes){
		writefln("%f,%f",p.x,p.y);
	}
}
ページトップ
コメントはまだありません。