编写函数，给定一个整数 N，返回以某种方式排列的整数数组 1..N，所以每 2 个连续数字的和是一个平方。
当且仅当满足以下两个条件时，解才有效:
范围 1..N 中的每个数字都使用一次且仅使用一次。
每 2 个连续数的和是一个完全平方数(平方根)。
结果是根据上述规则按特定顺序排列的 1-n 个数字的列表!!!
例子
对于 N=15，解决方案可能如下所示:
[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]
查看-
16 16 16 16 16 16 16
/+\ /+\ /+\ /+\ /+\ /+\ /+\
[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]
\+/ \+/ \+/ \+/ \+/ \+/ \+/
9 25 9 25 9 25 9
9 = 3*3
16 = 4*4
25 = 5*5
length of the returned list is n=15 and uses numbers from 1-n(15)
例如，如果 N=5，则数字 1,2,3,4,5 不能放入平方和行:1+3=4, 4+5=9，但是 2 没有对并且不能链接 [1,3 ] 和 [4,5]。
解决方案列表返回必须使用最多为 n 的数字且长度必须等于 n
我的解决方案是使用递归方法，这是我的尝试:
import java.util.*;
public class SquareSums {
public static List<Integer> gg= new ArrayList<Integer>() ;
public static List<Integer> buildUpTo(int n) {
int checkCurrent=1,firstInList=1;
while(checkCurrent<=n+1){
boolean[] flag= new boolean[n+1];
List<Integer> l= new ArrayList<Integer>();
l=checker(n,checkCurrent,l,1,flag,firstInList, true);//n, prev, list, current, flag
checkCurrent++;
if(l.size()==n) {System.out.println("true "+ n);return l;}
}
return null;
}
public static List<Integer> checker(int num, int current,List<Integer> l,int prev, boolean[] flag,int k, boolean one){
if(l.size()==num) {return l;}
else if(prev>num+1 || current>num) {return l;}
if(one) {
flag[current]=true;
l.add(current);print(l);
l=checker(num,1,l,current,flag,1,false);
}
flag[prev]=true;
System.out.println("check if square root: "+" num1: "+prev+ " num2: "+current+" sum is: "+(prev+current)+" sqrt: "+Math.sqrt(prev+current)+ " sqrt int: "+Math.floor(Math.sqrt(prev+current)));
if(current<flag.length &&!flag[current] && Math.sqrt(prev+current)==Math.floor(Math.sqrt(prev+current))) {
l.add(current);print(l);
l=checker(num,1,l,current,flag,1,false);
}
else {
print(l);
l=checker(num,k++,l,prev,flag,k,false);
}
return l;
}
public static void main(String[] args) {
List<Integer> l= buildUpTo(15);
print(l);
}
static void print(List<Integer> l) {
System.out.println(" -------------------- ");
for(int i=0;i<l.size();i++) {
System.out.println(l.get(i));
}
System.out.println(" --------------------- ");
System.out.println(" ");
System.out.println(" ");
}
}
我如何解决/修复代码以使其正常工作(使用递归方法和无流？)？
这是测试代码:
import org.junit.Test;
import org.junit.runners.JUnit4;
import java.util.List;
public class Tests {
@Test
public void sampleTests() {
List.of(5,15,16,23,37).forEach(Check::isGood);
}
}
然后在下面发布的代码解决方案的帮助下，我对代码进行了一些修改，但它仍然无法正常工作。
public class SquareSums {
public static List<Integer> gg= new ArrayList<Integer>() ;
public static List<Integer> buildUpTo(int n) {
int checkCurrent=1;
while(checkCurrent<=n+1){
List<Integer> l=checker(n,checkCurrent,new ArrayList<Integer>(),1,new boolean[n+1],1);//n, prev, list, current, flag
checkCurrent++;
if(l.size()==n) {System.out.println("true "+ n);return l;}
}
return gg;
}
static boolean checkPerfectSquare(double x)
{
double sq = Math.sqrt(x);
return ((sq - Math.floor(sq)) == 0);
}
public static List<Integer> checker(int num, int current,List<Integer> l,int prev, boolean[] flag,int k){
if(l.size()==num) {return l;}
else if(prev>num+1 || current>num) {return l;}
if(l.size()==0) {
flag[current]=true;
l.add(current);System.out.println(l);
l=checker(num,1,l,current,flag,1);
}
flag[prev]=true;
if(current<flag.length &&!flag[current] && checkPerfectSquare(prev+current)) {
l.add(current);System.out.println(l);
l=checker(num,1,l,current,flag,1);
l.remove(l.size()-1);
flag[l.size()-1]=false;
}
else {
System.out.println(l);
l=checker(num,k++,l,prev,flag,k);
}
return l;
}
public static void main(String[] args) {
List<Integer> l= buildUpTo(15);
System.out.println("\n"+"Answer is: ");
System.out.println(" -------------------- ");
System.out.println(l);
System.out.println(" -------------------- ");
}
}
[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, **1, 8**]预期的实际结果是:(不是我的代码，n=15时的真正解决方案)[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, **6, 10, 15, 1, 8**]如果我们仔细观察，我们可以看到我的代码出错的地方。似乎我需要在递归中添加一些东西，它可以返回尝试每个选项。我该怎么做？
最佳答案
我已经实现了可以为您提供特定给定范围内的连续平方和序列的代码。
所以你可以根据你的要求修改它。
public static void main(String[] args) {
//n -> 0 will be starting point
// size-> 15 size of sequence
//range-> range for which you want to find. Example value should include between 1 to 30
//check-> so that now value should be repeated so
//if you want to repeat value just remove boolean flag it will work and put all if else into one code
getvalue(0,15, new ArrayList<>(),20,new boolean[20]);
}
static void getvalue(int n, int size, ArrayList<Integer> ar, int range, boolean check[]) {
if(n==size)
{
System.out.println(ar);
return;
}
for (int i = 1; i < range; i++) {
if (ar.size() == 0) {
ar.add(i);
check[i] = true;
getvalue(n+1,size, ar,range, check);
check[i] = false;
}
else if(check[i]==false)
{
int val=ar.get(ar.size()-1);
if(checkPerfectSquare(val+i))
{
check[i]=true;
ar.add(i);
getvalue(n+1,size, ar,range, check);
ar.remove(ar.size()-1);
check[i]=false;
}
}
}
}
static boolean checkPerfectSquare(double x)
{
double sq = Math.sqrt(x);
return ((sq - Math.floor(sq)) == 0);
}
关于java - 递归查找给定长度的平方和的顺序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/65737605/