题库 信息学奥赛题库 题目列表 (魔法数字)小 H的魔法数字是 4。给定n,...
组合题

(魔法数字)小 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;    
 }
第1题 单选

①处应填(  

A.

 F[4] = 0

B.

F[1] = 4

C.

 F[1] = 2

D.

F[4] = 1

第2题 单选

②处应填(  

A.

!Vis[n]

B.

r < n

C.

F[M] == INT_MAX

D.

F[n] == INT_MAX

第3题 单选

③处应填(  

A.

F[i] == r

B.

!Vis[i] && F[i] == r

C.

F[i] < F[x] 

D.

!Vis[i] && F[i] < F[x]

第4题 单选

④处应填(  

A.

F[i] < F[x] 

B.

F[i] <= r

C.

Vis[i]

D.

i <= x

题目信息
完善程序 2021年 初赛
-
正确率
0
评论
217
点击