JAVA代码—算法基础：四平方定理问题

四平方定理问题

问题描述：给定一个正整数N，这个正整数N可以用不超过4个整数的平方和表示。
例如：12可以表示为 4+4+4，返回值 n=3，即 3个4之和。而4是2的平方。
给定整数13,13可以表示为 4+9， 返回值 n=2，即 2的平方和加上3的平方和。

问题分析：这个题目说的实际上的Lagrange四平方定理。这个定理在数学上已经被证明是正确的。我们不用证明，只需要使用这个定理来设计算法即可。

算法设计：

package com.bean.basic;import java.util.Arrays;public class PerfectSquaresDemo {/** 这个问题实际上是 Lagrange四平方定理，即 任何一个正整数都可以表示成不超过4个整数的平方之和。* dp[n] 代表表示给定整数n的平方数的数组* * 分析过程：* dp[0] = 0* dp[1] = dp[0]+1 = 1* dp[2] = dp[1]+1 = 2* dp[3] = dp[2]+1 =3* dp[4] = Min{ dp[4-1*1]+1, dp[4-2*2]+1} = Min {dp[3]+1,dp[1]+1} = 1* dp[5] = Min{ dp[5-1*1]+1, dp[5-2*2]+1} = Min {dp[4]+1,dp[1]+1} = 2* ....* * dp[13] = Min{ dp[13-1*1]+1, dp[13-2*2]+1, dp[13-3*3]+1} = Min {dp[12]+1,dp[9]+1,dp[4]+1} = 2* * 对于一般情况，推导出：* dp[n] = Min{dp[n-i*i]+1}, n-i*i>=0 && i>=1* */public static int numSquares(int n) {int[] dp = new int[n + 1];Arrays.fill(dp, Integer.MAX_VALUE);//初始化dp[0]为0dp[0] = 0;for(int i = 1; i <= n; ++i) {int min = Integer.MAX_VALUE;int j = 1;while(i - j*j >= 0) {min = Math.min(min, dp[i - j*j] + 1);++j;}dp[i] = min;}       return dp[n];}public static void main(String[] args) {// TODO Auto-generated method stubint target=(int)(Math.random()*2000)+1;int ANSWER=numSquares(target);System.out.println(numSquares(ANSWER));;}}

（完）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！