首页 > 代码库 > [ALGO-12] 幂方分解

[ALGO-12] 幂方分解

2024-07-06 14:33:12   221人阅读

算法训练 幂方分解  
时间限制：1.0s   内存限制：256.0MB
问题描述
　　任何一个正整数都可以用2的幂次方表示。例如：
　　137=27+23+20 
　　同时约定方次用括号来表示，即ab 可表示为a（b）。
　　由此可知，137可表示为：
　　2（7）+2（3）+2（0）
　　进一步：7= 22+2+20 （21用2表示）
　　3=2+20 
　　所以最后137可表示为：
　　2（2（2）+2+2（0））+2（2+2（0））+2（0）
　　又如：
　　1315=210 +28 +25 +2+1
　　所以1315最后可表示为：
　　2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
输入格式
　　输入包含一个正整数N（N<=20000），为要求分解的整数。
输出格式
　　程序输出包含一行字符串，为符合约定的n的0，2表示（在表示中不能有空格）
分析：递归求解

import java.util.Scanner;

public class Main {

	static int[] nums = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,
			4096, 8192, 16384 };

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		while (scanner.hasNext()) {
			int n = scanner.nextInt();

			showResult(n, 14);
			System.out.println();
		}
	}

	/**
	 * 
	 * @param n
	 *            数值
	 * @param index
	 *            nums数组的下标
	 */
	private static void showResult(int n, int index) {
		if (index == 0) {
			System.out.print("0");
			return;
		}
		if (index == 1) {
			System.out.print("2(0)");
			return;
		}

		while (index >= 0) {
			if (n - nums[index] >= 0) {
				if (index != 1) {
					System.out.print("2(");
					showResult(index, index);
					System.out.print(")");
				} else {
					System.out.print("2");
				}

				n -= nums[index];
				if (n != 0) {
					System.out.print("+");
					showResult(n, index);
					return;
				}
			}
			index--;
		}
	}
}


联系
我们