数据结构的问题， 用java实现， 求好心人帮忙
有四个数 1，2，3，5，任意相加(可以重复)等于一个固定值N(<15)，列出所有可能组合，用java实现！ --------------------编程问答----------------------------------------编程问答-------------------- 本来想用递归解决的，后来感觉麻烦。
//有四个数 1，2，3，5，任意相加(可以重复)等于一个固定值N(<15)，列出所有可能组合，用java实现！
public class Test {
public static void main(String[] args) {
int n=10;
for(int a=0;a<=15;a++){
for(int b=0;b<8;b++){
for(int c=0;c<=5;c++){
for(int d=0;d<=3;d++){
if((a+2*b+3*c+5*d)==n){
System.out.println("1的数量:"+a+"，2的数量:"+b+"，3的数量:"+c+"，5的数量:"+d);
}
}
}
}
}
}
}
晚上回去想想用递归解决。。
感觉递归更有挑战性。 --------------------编程问答-------------------- 运行报错了
java.lang.NoClassDefFoundError: BankTest
Caused by: java.lang.ClassNotFoundException: BankTest
at java.net.URLClassLoader$1.run(URLClassLoader.java:202)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(URLClassLoader.java:190)
at java.lang.ClassLoader.loadClass(ClassLoader.java:306)
at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:301)
at java.lang.ClassLoader.loadClass(ClassLoader.java:247)
Exception in thread "main" --------------------编程问答-------------------- 可以了 刚才搞错了 --------------------编程问答-------------------- 这个应该是有公式的。递归求解。
这里用个蠢的死的方法，穷举了呀兄弟，应该能拿分。小二上代码。
package test;
public class Test15 {
public void printOne(int[] a,int vLen,boolean isNextLine,String t){
int cnt=a.length/vLen;
for(int j=1;j<=cnt;j++){
String temp="";
int k=j;
while(k>0){
temp+=vLen+" ";
k--;
}
for(int i=0;i<a.length;i++){
if(i>j*vLen-1){
temp+=a[i]+" ";
}
}
//打印附加参数
if(t.length()>0){
temp+=t;
}
//打印结果
System.out.print(temp);
//打印换行
if(isNextLine){
System.out.println(" ");
}
}
}
public void printTwo(int[] a,int vLen1,int vLen2,String t){
int cnt=a.length/(vLen1+vLen2);
for(int j=1;j<=cnt;j++){
String temp="";
int k=j;
while(k>0){
temp+=vLen1+" "+vLen2+" ";
k--;
}
for(int i=0;i<a.length;i++){
if(i>j*(vLen1+vLen2)-1){
temp+=a[i]+" ";
}else{
if(i==j*(vLen1+vLen2)-1){
int[] b=new int[a.length-i-1];
System.arraycopy(a,i,b,0,a.length-i-1);
//在剩余的1中打印只含vLen1的情况
if(b.length>vLen1-1){
printOne(b,vLen1,true,temp);
}
//在剩余的1中打印只含vLen2的情况
if(b.length>vLen2-1){
printOne(b,vLen2,true,temp);
}
}
}
}
if(t.length()>0){
temp+=t;
}
//打印结果
System.out.print(temp);
System.out.println(" ");
}
}
public void printThree(int[] a,int vLen1,int vLen2,int vLen3){
int cnt=a.length/(vLen1+vLen2+vLen3);
for(int j=1;j<=cnt;j++){
String temp="";
int k=j;
while(k>0){
temp+=vLen1+" "+vLen2+" "+vLen3+" ";
k--;
}
for(int i=0;i<a.length;i++){
if(i>j*(vLen1+vLen2+vLen3)-1){
temp+=a[i]+" ";
}else{
if(i==j*(vLen1+vLen2+vLen3)-1){
int[] b=new int[a.length-i-1];
System.arraycopy(a,i,b,0,a.length-i-1);
//在剩余的1中打印只含vLen1的情况
if(b.length>vLen1-1){
printOne(b,vLen1,true,temp);
}
//在剩余的1中打印只含vLen2的情况
if(b.length>vLen2-1){
printOne(b,vLen2,true,temp);
}
//在剩余的1中打印只含vLen3的情况
if(b.length>vLen3-1){
printOne(b,vLen3,true,temp);
}
//在剩余的1中打印只含 vLen1，vLen2情况
if(b.length>vLen1+vLen2-1){
printTwo(b,vLen1,vLen2,temp);
}
//在剩余的1中打印只含 vLen1，vLen3情况
if(b.length>vLen1+vLen3-1){
printTwo(b,vLen1,vLen3,temp);
}
//在剩余的1中打印只含 vLen3，vLen2情况
if(b.length>vLen3+vLen2-1){
printTwo(b,vLen3,vLen2,temp);
}
}
}
}
//打印结果
System.out.print(temp);
System.out.println(" ");
}
}
public static void main(String[] args){
int n1=1,n2=2,n3=3,n5=5;
//等于15的情况
//int f=15;
int[] a=new int[15];
//等于6的情况
//int f=6;
//int[] a=new int[6];
System.out.println("The First Form:");
for(int i=0;i<a.length;i++){
a[i]=1;
System.out.print(a[i]+" ");
}
System.out.println(" ");
Test15 test=new Test15();
System.out.println("The Other Form:");
System.out.println("只含5:");
test.printOne(a,n5,true,"");
System.out.println("只含3:");
test.printOne(a,n3,true,"");
System.out.println("只含2:");
test.printOne(a,n2,true,"");
System.out.println("只含2-5:");
test.printTwo(a,n2,n5,"");
System.out.println("只含3-5:");
test.printTwo(a,n5,n3,"");
System.out.println("只含3-2:");
test.printTwo(a,n2,n3,"");
System.out.println("只含3-2-5:");
test.printThree(a,n2,n3,n5);
}
}
--------------------编程问答--------------------
你好LZ,此楼正解。
本人理解可能有所偏差，但打印的数据也是正确的,拙略的方法，见笑了。打印如下：
The First Form:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
The Other Form:
只含5:
5 1 1 1 1 1 1 1 1 1 1
5 5 1 1 1 1 1
5 5 5
只含3:
3 1 1 1 1 1 1 1 1 1 1 1 1
3 3 1 1 1 1 1 1 1 1 1
3 3 3 1 1 1 1 1 1
3 3 3 3 1 1 1
3 3 3 3 3
只含2:
2 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 1 1 1 1 1 1 1 1 1 1 1
2 2 2 1 1 1 1 1 1 1 1 1
2 2 2 2 1 1 1 1 1 1 1
2 2 2 2 2 1 1 1 1 1
2 2 2 2 2 2 1 1 1
2 2 2 2 2 2 2 1
只含2-5:
2 1 1 1 1 1 1 2 5
2 2 1 1 1 1 2 5
2 2 2 1 1 2 5
2 2 2 2 2 5
5 1 1 1 2 5
2 5 1 1 1 1 1 1 1 1
2 5 2 5 1
只含3-5:
5 1 1 5 3
3 1 1 1 1 5 3
3 3 1 5 3
5 3 1 1 1 1 1 1 1
只含3-2:
2 1 1 1 1 1 1 1 1 2 3
2 2 1 1 1 1 1 1 2 3
2 2 2 1 1 1 1 2 3
2 2 2 2 1 1 2 3
2 2 2 2 2 2 3
3 1 1 1 1 1 1 1 2 3
3 3 1 1 1 1 2 3
3 3 3 1 2 3
2 3 1 1 1 1 1 1 1 1 1 1
2 1 1 1 2 3 2 3
2 2 1 2 3 2 3
3 1 1 2 3 2 3
2 3 2 3 1 1 1 1 1
2 3 2 3 2 3
只含3-2-5:
2 1 1 1 2 3 5
2 2 1 2 3 5
3 1 1 2 3 5
5 2 3 5
2 3 2 3 5
2 3 5 1 1 1 1 1
--------------------编程问答-------------------- 老题目了，最笨的方法是回溯(O(N!)的复杂度，但可以求出所有排列)，好一点的方法是幂集(O(pow(2,N))的复杂度)，再好一点的是利用C(N,K)=C(N-1,K-1)+C(N-1,K)进行分治(有重复计算，但比幂集要好)，最好的方法是动态规划（依然利用利用C(N,K)=C(N-1,K-1)+C(N-1,K)，自底向上依次填写矩阵,N*N的复杂度）。 --------------------编程问答-------------------- 来个递归版的
import java.util.Stack;
public class digui {
static Stack<Integer> s = new Stack<Integer>();
public static Stack<Integer> recur(int start, Stack<Integer> s, int total) {
if (total == 0) {
System.out.println(s);
return s;
} else if (start <= 5 && start <= total) {
if (start == 4)
return recur(5, s, total);
else {
s.push(start);
recur(start, s, total - start);
s.pop();
return recur(start + 1, s, total);
}
} else {
return null;
}
}
public static void main(String[] args) {
System.out.println(recur(1, s, 15));
}
}
补充：Java , Java相关
