(魔法数字)小 H的魔法数字是 4。给定n,他希望用若干个 4进行若干次加法、减法和整除运算得到 。但由于小 H计算能力有限,计算过程中只能出现不超过 M= 10000的正整数。求至少可能用到多少个 4。
例如,当 =2时,有 2=(4 + 4)/4,用到了 3个 4,是最优方案。
试补全程序。
#include <iostream> #include <cstdlib> #include <climits> using namespace std; const int M = 10000; bool Vis[M + 1]; int F[M + 1]; void update(int &x, int y) { if (y < x) x = y; } int main() { int n; cin >> n; for (int i = 0; i <= M; i++) F[i] = INT_MAX; ① int r = 0; while (②) { r++; int x = 0; for (int i = 1; i <= M; i++) if (③) x = i; Vis[x] = 1; for (int i = 1; i <= M; i++) if (④) { int t = F[i] + F[x]; if (i + x <= M) update(F[i + x], t); if (i != x) update(F[abs(i - x)], t); if (i % x == 0) update(F[i / x], t); if (x % i == 0) update(F[x / i], t); } } cout << F[n] << endl; return 0; }
①处应填( )
F[4] = 0
F[1] = 4
F[1] = 2
F[4] = 1
②处应填( )
!Vis[n]
r < n
F[M] == INT_MAX
F[n] == INT_MAX
③处应填( )
F[i] == r
!Vis[i] && F[i] == r
F[i] < F[x]
!Vis[i] && F[i] < F[x]
④处应填( )
F[i] < F[x]
F[i] <= r
Vis[i]
i <= x