8-1. 1として作成

1391 ワード
DP ps テキストリンク
動的プログラミング)1
1.質問
整数Xが与えられた場合、整数Xに使用できる演算は4つあります.
  • Xを5で割って5で割った.
  • Xを3で割って3で割った.
  • Xを2で割って2で割った.
  • Xから1を減算します.
    • 整数Xが与えられると、4つの演算を適宜用いて1が作成される.使用演算回数の最大値を出力してください.
    たとえば、整数26の場合、計算される3回の演算の最大値は次のとおりです.
  • 26-1=25(Xマイナス1)
  • 25/5=5(5分割)
  • 5/5=1(5分割)
    • 2.入力
  • 第1行は整数Xを与える.(1<=X<=30,000)
    • 3.出力
  • の1行目の演算回数の最大値を出力します.
    • 4.解答
  • は似たような問題をたくさん作って、すぐにできました.
  • 個の整数ごとに、演算の最大値を配列に格納するように実現され、重複文の昇格方式が使用される.
  • は、min関数を使用しようとしたが、配列のデフォルト値は0であることを一時的に考慮した.
  • はすべての数字で1を減算する演算が可能であるため、配列中の値がX−1の値に+1の値を加えた値を最小演算回数とし、残りの演算を実行しながら最高値を更新する方式で実現される.
    • 5.最初のコードと異なる点
    딱히 없음
    6.コード
    #include <iostream>
#include <algorithm>

using namespace std;

int d[30001];

int main() {
	int x;
	cin >> x;

	for (int i = 2; i <= x; i++) {
		d[i] = d[i - 1] + 1;
		if (i % 5 == 0) d[i] = min(d[i], d[i / 5] + 1);
		if (i % 3 == 0) d[i] = min(d[i], d[i / 3] + 1);
		if (i % 2 == 0) d[i] = min(d[i], d[i / 2] + 1);
	}
	cout << d[x] << endl;
}
    EventBusの最適化-KeventBus
    Fedora 17下LNMP構成