『鐘万北』08.ダイナミックプランニング法爬井カタツムリc++

1511 ワード
dynamicprogramming algospot algorithm テキストリンク
確率は状況の数と密接に関連しており,多くの場合確率計算問題にも動的計画法を用いることができる.
まず、本の例では、毎日雨が降る確率が正確に50%であると仮定すると、m日以内にカタツムリが井戸の底に上昇する確率が先である.
m天は雨が降らないか降らないか、どちらも天気の組み合わせは2^m種です.したがって、天候の組み合わせのうちn以上の組み合わせ数を算出し、全体の組み合わせ数2^mで除算すればよい.
山登り(days,learned)=これまでに作られた天気グループCの大きさはdaysであり,その要素の和が上昇すると,Cが要素の和をn以上にする方法の数を達成する.
const int MAX_n = 1000;

int n, m;
int cache[MAX_n][2 * MAX_n + 1];

int climb(int days, int climbed) {
	if (days == m) return climbed >= n ? 1 : 0;

	int& ret = cache[days][climbed];
	if (ret != -1) return ret;

	return ret = climb(days + 1, climbed + 1) + climb(days + 1, climbed + 2);
}
  • は1日2メートル上昇できるので、cacheの列は2*MAX+n+1です.
  • 日がm日の場合、上昇(日の上昇の高さ)がnより大きい場合は、1(1)または0を返します.
  • 今日は快晴と雨の状況がひどいので、2つの状況を加えました.
    • double climb2(int days, int climbed) {
	if (days == m) return climbed >= n ? 1 : 0;

	double& ret = cache[days][climbed];
	if (ret != -1) return ret;

	return ret = 0.75 * climb2(days + 1, climbed + 1) + 0.25 * (days + 1, climbed + 2);
    }


int main() {
	cin >> n >> m;

	fill_n(cache[0], MAX_n * MAX_n, -1);
	cout << fixed << setprecision(10) << climb2(0,0) << endl;

	return 0;
}
  • の前のコードには、確率を乗じた部分のみが追加されています.
  • の数ではなく直接返却確率なので、返却型は
    • 倍になる.
  • int型ではないためmemsetで初期化できません
    std::fill n:パラメータに変更するウォーソの範囲開始アドレス、要素数、および変更値を入力します.
  • iomanip::setprecision:出力範囲の指定
    fixedがない場合:整数部+小数部が標準四捨五入
    fixedがある場合:
    • (小数部ベース)を丸めます.
    大数の作成(プログラマ)
    デバッグアプリケーションノード