P1010 幂次方

calendar May 6, 2026 · 4 分钟阅读 · 递归  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1010
难度 橙题（普及-）
知识点 递归、分治、二进制
来源 NOIP 1998 普及组

题目描述

任何一个正整数都可以用 2 的幂次方表示。

例如 137 = 2^7 + 2^3 + 2^0。

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

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

进一步：7 = 2^2 + 2^1 + 2^0，所以 137 最终可表示为：2(2(2)+2(1)+2(0))+2(2+1)+2(0)

请你编程序输入一个正整数 n，输出其 2 的幂次方的表示形式。

输入格式

一个正整数 n（n ≤ 20000）

输出格式

符合约定的 n 的 2 的幂次方表示

解题思路

核心思想

这道题考察的是递归分治思想，将大问题分解为小问题来解决。

  1. 分解：将正整数 n 转换为二进制，每一位代表 2^k 的系数
  2. 递归处理：对于每个指数 k，如果 k > 1，需要递归地将 k 也分解为 2 的幂次方
  3. 组合输出：按从高位到低位的顺序输出，用 + 连接各项

算法步骤

  1. 将 n 转换为二进制数组
  2. 从高位到低位遍历，如果该位为 1：
    • 输出 2
    • 如果指数为 1，直接输出 2(1)（代码中省略 1）
    • 如果指数大于 1，递归输出 2(递归处理指数)
  3. 用 + 连接各项

完整代码

C++

#include <bits/stdc++.h>
using namespace std;

long long n;

/**
 * 将正整数 x 表示为 2 的幂次方的递归函数
 * @param x 要处理的正整数
 */
void f(long long x) {
    bool a[50];
    if (x == 0) {
        cout << 0;
        return;
    }
    memset(a, 0, sizeof(a));
    int len = 0;
    
    // 将 x 转换为二进制，存储到数组 a 中
    while (x != 0) {
        a[len++] = x % 2;
        x = x / 2;
    }
    
    // 从高位到低位遍历，输出 2 的幂次方表示
    for (int i = len - 1; i >= 0; i--) {
        if (a[i] == 0) {
            continue;  // 该位为 0，跳过
        }
        if (i != len - 1) {
            cout << "+";  // 非第一项，前面加 +
        }
        cout << "2";
        if (i != 1) {
            cout << "(";
            f(i);  // 递归处理指数
            cout << ")";
        }
    }
}

int main() {
    cin >> n;
    f(n);
    return 0;
}

关键代码讲解

二进制转换

while (x != 0) {
    a[len++] = x % 2;  // 取出最低位
    x = x / 2;         // 右移一位
}

这段代码将十进制数 x 转换为二进制数组。例如 137 的二进制是 10001001。

递归输出

for (int i = len - 1; i >= 0; i--) {
    if (a[i] == 0) continue;
    if (i != len - 1) cout << "+";
    cout << "2";
    if (i != 1) {
        cout << "(";
        f(i);  // 递归处理指数 i
        cout << ")";
    }
}
  • 从高位到低位遍历二进制数组
  • 如果该位为 1，则输出 2
  • 如果指数 i > 1，递归处理 i（因为 2^1 直接写成 2）
  • 如果指数 i = 1，直接输出 2（不输出括号）

示例解析

以 n = 137 为例：

步骤 二进制 处理
137 10001001 输出 2(7)+2(3)+2(0)
7 111 输出 2(2+1+0)
2 10 输出 2

最终输出：2(2(2)+2(1)+2(0))+2(2+1)+2(0)

复杂度分析

方法 时间复杂度 空间复杂度
递归分治 O(log n × log n) O(log n)

易错点

  1. 递归终止条件：n = 0 时需要特殊处理，输出 0
  2. 指数为 1 的情况：2^1 = 2，直接输出 2，不需要括号
  3. 加号位置：第一项前面不加 +，其余各项前面加 +
  4. 数据范围：n ≤ 20000，使用 long long 足够存储

其他语言解法

Python

def f(x: int) -> str:
    """将正整数 x 表示为 2 的幂次方的递归函数"""
    if x == 0:
        return "0"
    
    # 转换为二进制数组
    bits = []
    while x != 0:
        bits.append(x % 2)
        x //= 2
    
    result = []
    for i in range(len(bits) - 1, -1, -1):
        if bits[i] == 0:
            continue
        
        if i == 0:
            result.append("2(0)")
        elif i == 1:
            result.append("2")
        else:
            result.append(f"2({f(i)})")
    
    return "+".join(result)


def main():
    n = int(input())
    print(f(n))


if __name__ == '__main__':
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    
    private static void f(long x, StringBuilder sb, boolean isFirst) {
        if (x == 0) {
            sb.append("0");
            return;
        }
        
        // 转换为二进制数组
        int[] a = new int[50];
        int len = 0;
        while (x != 0) {
            a[len++] = (int) (x % 2);
            x /= 2;
        }
        
        // 从高位到低位遍历
        for (int i = len - 1; i >= 0; i--) {
            if (a[i] == 0) continue;
            if (!isFirst) sb.append("+");
            sb.append("2");
            if (i != 1) {
                sb.append("(");
                f(i, sb, true);
                sb.append(")");
            }
            isFirst = false;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        f(n, sb, true);
        System.out.print(sb.toString());
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

func f(x int64, sb *string, isFirst *bool) {
    if x == 0 {
        *sb += "0"
        return
    }
    
    // 转换为二进制数组
    a := make([]int, 50)
    length := 0
    for x != 0 {
        a[length] = int(x % 2)
        x /= 2
        length++
    }
    
    // 从高位到低位遍历
    for i := length - 1; i >= 0; i-- {
        if a[i] == 0 {
            continue
        }
        if !*isFirst {
            *sb += "+"
        }
        *sb += "2"
        if i != 1 {
            *sb += "("
            // 递归调用时传递 true，确保子表达式内部正确添加 +
            isFirstSub := true
            f(int64(i), sb, &isFirstSub)
            *sb += ")"
        }
        *isFirst = false
    }
}

func main() {
    in := bufio.NewReader(os.Stdin)
    
    var n int64
    fmt.Fscan(in, &n)
    
    var sb string
    isFirst := true
    f(n, &sb, &isFirst)
    fmt.Print(sb)
}

JavaScript

'use strict';

/**
 * 将正整数 x 表示为 2 的幂次方的递归函数
 * @param {number} x
 * @returns {string}
 */
function f(x) {
    if (x === 0) {
        return '0';
    }
    
    // 转换为二进制数组
    const bits = [];
    while (x !== 0) {
        bits.push(x % 2);
        x = Math.floor(x / 2);
    }
    
    const parts = [];
    for (let i = bits.length - 1; i >= 0; i--) {
        if (bits[i] === 0) continue;
        
        if (i === 0) {
            parts.push('2(0)');
        } else if (i === 1) {
            parts.push('2');
        } else {
            parts.push(`2(${f(i)})`);
        }
    }
    
    return parts.join('+');
}

const fs = require('fs');
const n = parseInt(fs.readFileSync('/dev/stdin', 'utf8').trim());
console.log(f(n));