7
回答
递归
华为云实践训练营,热门技术免费实践!>>>   

能实现下面的递归方法

for (int i = 1; i <= 10; i++) {
            int sum1 = 0;
            sum1 += Math.pow(i, 2);
            if (sum1 == 100) {
                System.out.println(i);
            }
            for (int j = 1; j <= i; j++) {
                int sum2 = 0;
                sum2 += sum1 + Math.pow(j, 2);
                if (sum2 == 100) {
                    System.out.print(i + " ");
                    System.out.println(j);
                }
                for (int k = 1; k <= j; k++) {
                    int sum3 = 0;
                    sum3 += sum2 + Math.pow(k, 2);
                    if (sum3 == 100) {
                        System.out.print(i + " ");
                        System.out.print(j + " ");
                        System.out.println(k);
                    }

                    for (int l = 1; l <= k; l++) {
                        int sum4 = 0;
                        sum4 += sum3 + Math.pow(l, 2);
                        if (sum4 == 100) {
                            System.out.print(i + " ");
                            System.out.print(j + " ");
                            System.out.print(k + " ");
                            System.out.println(l);
                        }
                    }
                }
            }
        }

<无标签>
举报
lzhphantom
发帖于3个月前 7回/214阅

最后,整理以后的版本,应该是编程题的标准答案了。。。。。

import java.util.Stack;

public class 平方和为100的所有组合2 {

	static final int	SUM	= 100;

	public static void main(String[] args) {
		split(SUM, new Stack<Integer>());
	}

	private static void split(int sum, Stack<Integer> stack) {
		if (sum == 0) {
			System.out.println(stack);
		} else {
			// 限制,必须从大到小拆解,防止出现:9 3 3 1 和 9 1 3 3这种重复的组合
			int startValue = (int) (stack.isEmpty() ? Math.sqrt(sum) : stack.peek());
			for (int i = startValue; i >= 1; i--) {
				stack.push(i);
				int left = sum - i * i;
				if (left >= 0) {
					split(left, stack);
				}
				stack.pop();
			}
		}
	}

}

快来试试吧!

--- 共有 1 条评论 ---
lzhphantom哇,是真的厉害��,待我缓一缓 3个月前 回复
a、b、c有关系吗? 
r=1^2
r=1^2 + 2^2
r=1^2 + 2^2 + 3^2
r=1^2 + 2^2 + 3^2 + 4^2
r=1^2 + 2^2 + 3^2 + 4^2 + 5^2
r=1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2
.......................................... 
求加到几的时候,总和为100?

把完整的原题发出来吧,感觉在看你的程序猜题目

--- 共有 2 条评论 ---
依然菜刀 回复 @lzhphantom : 懂了,我帮你看下。。 3个月前 回复
lzhphantom举个例子 100=10^2 100=6^2+8^2 100=5^2+5^2+5^2+5^2 :100=7^2+5^2+5^2+1^2 等等,以此类推 3个月前 回复

不能用递归,自己实现了一种:

import java.util.ArrayList;
import java.util.List;

public class 平方和为100的所有组合 {

	private static int	SUM	= 100;

	public static void main(String[] args) {
		// 因子的最大值,如果和是101的话,最多也只能取到10,所以是下取整
		int maxItemValue = (int) Math.sqrt(SUM);
		
		// 可选的最大值~0的序列
		int[] items = new int[maxItemValue];
		for (int i = 0; i < maxItemValue; i++) {
			items[i] = maxItemValue - i;
		}
		
		// 每个因子可以选择的最多个数
		/*
		 * 当是10的时候
		 * 可选数字:             10  9  8  7  6  5  4  3   2   1
		 * 最多可选个数数     1   1  1  2  2  4  6  11  25  100
		 */
		int[] countLimit = new int[maxItemValue];
		
		for (int i = 1; i <= maxItemValue; i++) {
			countLimit[maxItemValue - i] = SUM / (int)Math.pow(i, 2);
		}
		
		int[] select = new int[maxItemValue];
		while (add(select, countLimit)) {
			checkAndOutput(items, select);
		}
	}
	
	/**
	 * 检查并输出可能的结果
	 * @param items 可选的最大值~0的序列(可以选择的因子)
	 * @param select 每个因子各选几个
	 */
	private static void checkAndOutput(int[] items, int[] select) {
		int sum = 0;
		List<Integer> selectItems = new ArrayList<Integer>();
		for (int i = 0; i < select.length; i++) {
			int selectItemCount = select[i];
			sum += items[i] * items[i] * selectItemCount;
			
			// 超结果了,无效组合,下一个
			if (sum > SUM) {
				return;
			}
			
			// 记录选择的项
			for (int j = 0; j < selectItemCount; j++) {
				selectItems.add(items[i]);
			}
		}
		if (sum == SUM) {
			System.out.println(selectItems);
			// 只有一个因子,肯定是最大了,结束
			if (selectItems.size() == 1) {
				System.exit(0);
			}
		}
	}

	/**
	 * 增加1
	 * @param select 当前的选择组合
	 * @param countLimit 每个选择最多可以选择多少个
	 * @return 是否加1成功,失败表示结束
	 */
	static boolean add(int[] select, int[] countLimit) {
		int length = select.length;
		// 末位加1
		select[length - 1]++;
		
		// 进位检测
		for (int i = length - 1; i >= 0; i--) {
			// 需要进位
			if (select[i] > countLimit[i]) {
				int higherPosition = i - 1;
				if (higherPosition < 0) {
					// 已经是最大值了,结束
					return false;
				}
				select[higherPosition]++;
				select[i] = 0; // 当前位回0
			} else {
				// 不需要进位
				break;
			}
		}
		return true;
	}

}

 

--- 共有 1 条评论 ---
lzhphantom谢谢,我看懂了 3个月前 回复

来个递归的版本,别客气!

import java.util.Collections;
import java.util.LinkedList;

public class 平方和为100的所有组合2 {

	static final int	SUM	= 1000;

	public static void main(String[] args) {
		split(SUM, new LinkedList<Integer>());
	}

	private static void split(int sum, LinkedList<Integer> valueStack) {
		if (sum == 0) {
			output(valueStack);
			return;
		} else if (sum == 1) {
			valueStack.push(1);
			output(valueStack);
			valueStack.pop();
		} else {
			// 限制,必须从大到小拆解,防止出现:9 3 3 1 和 9 1 3 3这种重复的组合
			int startValue = (int) (valueStack.isEmpty() ? Math.sqrt(sum) : valueStack.peek());
			for (int i = startValue; i >= 1; i--) {
				valueStack.push(i);
				int left = sum - i * i;
				if (left >= 0) {
					split(left, valueStack);
				}
				valueStack.pop();
			}
		}
	}

	private static void output(LinkedList<Integer> valueStack) {
		LinkedList<Integer> outputList = new LinkedList<Integer>(valueStack);
		Collections.reverse(outputList);
		System.out.println(outputList);
	}
}

 

顶部