求n的n次幂和: 1^1+2^2+3^3+……+n^n

时间:2021-06-06 15:12:07
 编程实现计算Σi^i,其中n为用户输入的任意整数。(提示:要考虑结果可能超出长整数long的表示范围的情况)

package org.lina.com;

import java.io.IOException;
import java.util.Scanner;

//content:求n的n次幂和--> 1^1+2^2+3^3+……+n^n
/*防止越界的方法:把大数存在整形数组中;最终的结果放在sum数组,k^k的值存放在 result数组中。
 注意:大数在数组中存放的规则是:大数的低位存放在下标较小的数组元素中,读取的时候采用倒着读,
 即先读最较高位的,最后读下标为零的元素
 */
public class n1_new {

	static int number = 10000; // 定义能够存放的最大位数,可以根据需要改变

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		// Java从控制台读入一个整数n
		int n;
		char ch = 'y';
		while ('y' == ch) {
			System.out.print("请输入一个正整数:");
			Scanner s = new Scanner(System.in);
			n = s.nextInt();
			if (n > 10000 || n < 0) {
				System.out.print("输入了不合法的数字!");
			} else {
				System.out.println("输入整数n为:" + n);
				n_nAnd(n);
				System.out.print("continue? (y/n):");
				ch = (char) System.in.read();
			}

		}

	}

	// 大数相加的函数
	static void BigAdd(int sum[], int height_sum, int result[], int height_res) {
		int i;
		// 存放两位数相加,还有后位的进位
		int tempSum = 0;
		// 存放进位--两个数组对应的每一位想加都可能存在进位
		int carry = 0;

		for (i = 0; i < height_res; i++) {
			tempSum = sum[i] + result[i] + carry;
			sum[i] = tempSum % 10;
			carry = tempSum / 10;
		}
	}

	// 求n的n次幂和的函数--其中涉及求k^k次
	static void n_nAnd(int n) {
		int sum[] = new int[number];// 最终的结果
		sum[0] = 1; // 使得最低位为1
		int height_sum = 1; // 和的位数
		int height_res;

		// 求和
		for (int k = 1; k <= n; k++) {
			int result[] = new int[number]; // 存放k次幂的结果
			// 初始化数组
			result[0] = 1;
			height_res = 1; // k^k的位数
			// 计算k^k
			for (int i = 1; i <= k; i++) {
				int res = 0;
				for (int j = 0; j < height_res; j++) {
						int buf = result[j] * k + res;
						result[j] = buf % 10;
						res = buf / 10;
					if (res != 0) {
						//需进位时,只需要数组的实际长度加1,不需要同时把res(进位值)付给后一位数
						height_res++;
					} 
					/*这段代码有问题:后一位应该先*k,再+res(),而不是先被赋值再*k,不然会导致进位数多乘一个k~~改进如上
					while (res != 0) {
						result[height_res++] = res % 10;
						res /= 10;
					}*/
				}

			}// 计算k^k结束

			if (k > 1 && k <= n) {
				BigAdd(sum, height_sum, result, height_res);
			}

		}// 求和结束

		// 输出结果--先输出高位
		for (int i = number - 1; i >= 0; i--) {
			if (sum[i] != 0) {
				for (int j = i; j >= 0; j--) {
					System.out.print(sum[j]);
				}
				System.out.println();
				System.out.println("结果总长度是:" + (i + 1));
				break;
			}
		}
	}
}