欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【洛谷】【P1010题解】 [NOIP1998 普及组] 幂次方

程序员文章站 2022-05-08 22:53:02
...

题目描述

描述:输入一个整数n,1 <= n < 2 * 10^4

举例:

1315

答案:

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

分析:

因为1315=210+28+2^5+2+1,所以输出2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

题目思路:

  1. 首先,确定大的解题方向:观察1315及其答案,很容易发现1315需要被拆解成2的n次方之和,并且这个n也需要拆解,1需要拆成2(0),2不需要拆。所以,可以尝试用递归去解决这个问题。
    因为整个解题过程就把大的数拆成小的数,当这个数拆到1或2时,就可以直接返回。

  2. 如何拆数?因为是2的幂次方之和,所以需要log2函数来辅助拆数。
    即:int num = (int)log2(n)--------①
    这里的n是要求的数,得到的num是能分解出的最大2的幂次方数的幂。
    举个例子:如n=3=2^1+1时,num=1
    很明显log2(n)不一定是一个整数,比如上面的n,当处理完21后,还剩下一个1需要处理,观察答案,在21和1的中间需要插入一个+号。
    总结:输入数n,调用①,得到num,求解num,然后判断(key = (int)pow(2, num))==n?,如果相等,就不需要做任何处理。不相等,需要输出一个+号,然后继续求解n-key.

  3. 完善思路。按照第二步走,很明显可以一个很大的n化解成两部分,一个是n中能取的最大2的幂次方数,一个是剩余部分。然后递归调用,所以两部分各自都会继续再分,直到分到最小值时退出(也就是2和2(0))。
    但是考虑到题目所给的n的范围,思考:2049=210+210+1,如果只是按照上述实现会发现10会被重复求两次,当重复过多时会浪费大量不必要的时间,所以需要使用记忆化递归,用map来记录已求的n对应的字符串,递归的返回值也因此需要是string。

整理思路

  1. 声明函数DFS,输入int n,返回string
    编写递归函数体:
  2. 先判断当前n是否在map中存在,如果存在直接返回
  3. 使用①求出num,此时需要注意2的num次方也有可能重复计算,所以需要得到2的num次方的值(根据题意是不可能溢出的)并赋值给key,判断这个key是否在map中存在,如果存在,用临时变量string temp记录这个结果,如果不存在,则需要按照题意令temp=“2(” + DFS(num) + “)”;,直接求这个num的再进行拼接。
  4. 继续判断key是否等于n,如果相等就代表上一步已经分割完n,记录temp后,直接返回temp即可。不然,需要使用temp += “+” + DFS(n - key);,将剩下的部分连上+号,追加到temp的后面。
  5. 当前temp已经求解完毕,用n作为key,temp作为value,使用unordered_map<int,string>记录。最后返回这个temp
  6. 函数体编写完毕,剩下最轻松的部分:
    • (1)用变量n,完成键盘录入。
    • (2)声明map,初始化um[1] = “2(0)”;和um[2] = “2”;
    • (3)输出DFS(n)

代码实现(c++)

#include<iostream> // 基本输入输出
#include<cmath>	// log2和pow
#include<unordered_map> // map
using namespace std;


unordered_map<int, string> um;
string DFS(int n){
    if(um.find(n) != um.end()){ return um[n];}
    string temp;
    int num = (int)log2(n), key = (int)pow(2, num);
    if(um.find(key) != um.end()){ temp = um[key];}
    else{
        temp = "2(" + DFS(num) + ")";
    }
    if(key != n){
        temp += "+" + DFS(n - key);
    }

    um[n] = temp;
    return temp;
}

int n;
int main(){
    cin >> n;
    // 非常关键的初始化工作
    um[1] = "2(0)";
    um[2] = "2";
    // 直接打印结果
    cout << DFS(n);
    return 0;
}

时空复杂度就不分析了…水平有限,望轻喷


特么写了这么多,发现不能作为题解发出去…只好直接放CSDN上了