構造体で木構造を作り出すには？ (ID:72210)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文

ありがとうございます。
自分で調べて解決しました。

同じく木構造を解く次の問題で悩んでいたりします。
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1056&lang=jp
できるだけ高い精度で問題を解こうとしてるのですが、分類がごちゃごちゃしていて、ちょっと解けそうで解けない微妙な段階です。

#include <stdio.h>
#include <math.h>
void calc(int n);

int main(void){
	int n;
	scanf("%d",&n);
	calc(n);
	return 0;
}

void calc(int n){
	long double sum=0.0;
	long double k=1.0;
	long double nextK=0;
	int deep=0;
	//分類Aの弁当個数期待値の計算
	for(int i=0;i<n;i++){
		sum+=k;
		nextK=k*(k*0.5);
		if(nextK-k<=0.000000000000001){
			//ここより深い階層は計算に対して影響を与えないので打ち切り
			deep=i;
			k=nextK;
			break;
		}
		k=nextK;
	}
	
	printf("%0.19Lf %0.19Lf",sum,k);
	long double m1=1.0;//分類Cの最初の独立な期待値
	long double m2=1.5;//分類Cの2つ目の独立な期待値
	long double t1,t2;
	long double two=2.0;
	long double k2=k;
	//分類 Bは0なので飛ばして分類Cの最初の確率計算
	//桁あふれを防止するためfor文で確率を求める。
	//Mi でiがdeepからのデータのみを扱うことになる
	for(int i=0;i<n-deep;i++){
		if(i%2==1){
			m2=m1*0.5+m2*0.5+1.0;
		}else{
			m1=m1*0.5+m2*0.5+1.0:
		}
	}
//この辺の計算、ｎ-deep-2やｎ-deepの値の設定が適切か悩んでます
	k2=1.0-1.0/powl(two,(long double)(n-depp-2));
	for(int i=deep;i<n-2;i++){
		k=k*powl(two,(long double)(n-i+1));
		k2*=2.0;
		if(i%2==1){
			m2=m1*0.5+m2*0.5+1.0;
			sum+=m2*k2*k;
		}else{
			m1=m1*0.5+m2*0.5+1.0;
			sum+=m1*k2*k;
		}
	}
}

←解決時は質問者本人がここをチェックしてください。

戻る