洛谷P1010 [NOIP1998 普及组] 幂次方

骑猪看日落 2023-09-30 15:39 25阅读 0赞

#### 文章目录 ####

*  前言
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  样例 \#1
     *   *  样例输入 \#1
         *  样例输出 \#1
     *  【数据范围】
 *  代码
 *  解析
 *  结尾

--------------------

## 前言 ##

在做完洛谷P1010 \[NOIP1998 普及组\] 幂次方这道题之后，我对于现在的学习有了些许认识。

### 题目描述 ###

任何一个正整数都可以用  2 2 2 的幂次方表示。例如 $137=27+23+2^0 $。

同时约定方次用括号来表示，即  a b a^b ab 可表示为  a ( b ) a(b) a(b)。

由此可知， 137 137 137 可表示为  2 ( 7 ) + 2 ( 3 ) + 2 ( 0 ) 2(7)+2(3)+2(0) 2(7)\+2(3)\+2(0)

进一步：

7 = 2 2 + 2 + 2 0 7= 2^2+2+2^0 7=22\+2\+20 (  2 1 2^1 21 用  2 2 2 表示)，并且  3 = 2 + 2 0 3=2+2^0 3=2\+20。

所以最后  137 137 137 可表示为  2 ( 2 ( 2 ) + 2 + 2 ( 0 ) ) + 2 ( 2 + 2 ( 0 ) ) + 2 ( 0 ) 2(2(2)+2+2(0))+2(2+2(0))+2(0) 2(2(2)\+2\+2(0))\+2(2\+2(0))\+2(0)。

又如  1315 = 2 10 + 2 8 + 2 5 + 2 + 1 1315=2^\{10\} +2^8 +2^5 +2+1 1315=210\+28\+25\+2\+1，

所以  1315 1315 1315 最后可表示为  2 ( 2 ( 2 + 2 ( 0 ) ) + 2 ) + 2 ( 2 ( 2 + 2 ( 0 ) ) ) + 2 ( 2 ( 2 ) + 2 ( 0 ) ) + 2 + 2 ( 0 ) 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0) 2(2(2\+2(0))\+2)\+2(2(2\+2(0)))\+2(2(2)\+2(0))\+2\+2(0)。

题目来源：[洛谷P1010 \[NOIP1998 普及组\] 幂次方][P1010 _NOIP1998 _]

### 输入格式 ###

一行一个正整数  n n n。

### 输出格式 ###

符合约定的  n n n 的  0 , 2 0, 2 0,2 表示（在表示中不能有空格）。

### 样例 \#1 ###

#### 样例输入 \#1 ####

1315

#### 样例输出 \#1 ####

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

### 【数据范围】 ###

对于  100 % 100\\% 100% 的数据， 1 ≤ n ≤ 2 × 10 4 1 \\le n \\le 2 \\times \{10\}^4 1≤n≤2×104。

## 代码 ##

#include <bits/stdc++.h>
    using namespace std;
    
    int first = 1;
    
    void f(int num) {
        
    	int i = 0;
    	if (num == 0 ) {
        
    		cout << "0";
    		return ;
    	}// if ；特殊点0处理
    	if (num == 1) {
        
    		cout << "2(0)";
    		return ;
    	}// if 特殊点0处理
    	while (pow(2, i + 1) <= num)
    		i++;
    	cout << "2";
    	if (pow(2, i) != 2) {
        
    		cout << "(";
    		f(i);
    		cout << ")";
    	}// if ；生成共同点处理的同时，处理特殊点2
    	num -= pow(2, i);//将较大的数据拆分成一个个小部分的几个数据相加
    	if (num != 0) {
        
    		cout << "+";
    		f(num);
    	}// if
    }// f
    
    int main() {
        
    	int num;
    	cin >> num;
    	f(num);
    	return 0;
    }

--------------------

## 解析 ##

在结合了数据结构这门课之后，我对于处理算法问题有了新的感受。在**面对具体的问题的时候**，首先要突破现实物理的束缚，**将问题间的数学逻辑模型从整个问题中抽取出来**。

在面对递归问题中，首先要做的是**寻找普遍存在的共同点**和需要特别处理不符合共同点间处理逻辑的**特殊点**，将他们的处理方法各自编写出来。

在本题目中，特殊点是2、1、0。  
当输入数据或函数接收数据为**2**时，输出的仅是**2，不带括号**；  
当输入数据或函数接收数据为**1**时，输出的则是**2（0）**；  
当函数接收数据为**0**的时候，**结束**。

25 = 16 + 9 25=16+9 25=16\+9  
 = 16 + 8 + 1 =16+8+1 =16\+8\+1 \_\_\_\_\_(1)  
 = 2 4 + 2 3 + 2 0 =2^\{4\}+2^\{3\}+2^\{0\} =24\+23\+20\_\_\_\_(2)

2 4 2^\{4\} 24和 2 3 2^\{3\} 23还可以便是所说的普遍存在的共同点，可以继续使用代码中的函数f传入4和3继续进行递归。将4变为 2 2 2^\{2\} 22，接着2继续传入函数f，抵达特殊点情况；将3变为 2 + 1 2+1 2\+1，抵达特殊点情况。

--------------------

## 结尾 ##

如有错误遗漏，欢迎评论补充。

[P1010 _NOIP1998 _]: https://www.luogu.com.cn/problem/P1010