算法题

Question

有五个自然数，每个数都不相同，和是23。这五个数中某几个数的和，能表示1--23中任意的一个数。请列出这五个数的可能的组合。

Answer 1

我只知道结果1,2,4,8,16,不知用java怎么做

Answer 2

public class Test3 { /**
 * @param args
 */
public static void main(String[] args) {
System.out.println("非递归算法的实现：");
for(int i1=1; i1<23; i1++) {
for(int i2=i1+1; i2<23; i2++) {
for(int i3=i2+1; i3<23; i3++) {
for(int i4=i3+1; i4<23; i4++) {
for(int i5=i4+1; i5<23; i5++) {
if(i1 + i2 + i3 + i4 + i5 == 23) 
System.out.println(i1 +" "+ i2 +" "+i3+" "+i4+" "+i5);
}
}
}
}
}
System.out.println("递归算法的实现:");
int arr[] = new int[5]; //存储那5个数
getNum(arr, 0);
}

private static void getNum(int arr[], int pos) {
if(pos == arr.length) { //如果数组塞满了，则判断是否等于23
int result = 0;
for(int i=0; i<arr.length; i++) 
result += arr[i];
if(result == 23) { //如果是23，则循环打印出来
for(int i=0; i<arr.length; i++) 
System.out.print(arr[i] + " ");
System.out.println();
}
return;
}
for(int i=1; i<23; i++) {
if(pos > 0)  //拿到的后一个数必须大于前一个数
if(i < arr[pos-1]) continue;
if(isContain(i, arr)) continue;
arr[pos] = i;
getNum(arr, pos+1);
}
}

/**
 * 判断数组中arr是否包含了指定的数x
 * @param x
 * @param arr
 * @return
 */
private static boolean isContain(int x, int arr[]) {
for(int i=0; i<arr.length; i++) {
if(x == arr[i])
return true;
}
return false;
}
}

Answer 3

不好意思了，刚开始我理解错了题的意思，谢谢9楼的分析，昨天晚上想了一个晚上，终于将其修改完成，修改后的代码为，如果还有问题，希望大家给出意见：
public class Test3 { /**
 * 因为最开始的3个数1，2，3是必须要有的，所以只需判断最后的2个数能否合符条件即可
 * @param args
 */
public static void main(String[] args) {
int arr[] = new int[5]; //存储5个数，前3个数分别是1，2，3
arr[0] = 1; arr[1] = 2; arr[2] = 3;
for(int i=4; i<=8; i++) { //i代表的是第4个数，它的取值只能是4到8之间
boolean f = true; //记录当前的组合是否符合条件
arr[3] = i;
arr[4] = 23-6-i;
for(int j=2; j<4; j++) { //j值代表了当前取到的哪个数了
//只需判断前j个数的和与j后面那个数的差不能超过1就可以判断是否合符条件(至于为什么？仔细思考下就知道了)
if(getSum(arr, j)-arr[j+1] < -1) { 
f = false; //不合符就设为false
break;
}
}
if(f) { //如果符合就打印输出
for(int k=0; k<arr.length; k++) 
System.out.print(arr[k] + " ");
System.out.println();
}
}
}

private static int getSum(int arr[], int j) {
int sum = 0;
for(int i=0; i<=j; i++) {
sum += arr[i];
}
return sum;
}
}

Answer 4

good说的对，还得包括1，2，4的情况，下面是修改后的代码。
public class Test3 { /**
 * 因为最开始的2个数1，2是必须要有的，并且第3个数只能取3，4中间的值。
 * @param args
 */
public static void main(String[] args) {
int arr[] = new int[5]; //存储5个数，前2个数分别是1，2
arr[0] = 1; arr[1] = 2; 
for(int k=3; k<=4; k++) { //k代表了第3个数，只能取3，4中间的数
arr[2] = k;
for(int i=4; i<=8; i++) { //i代表的是第4个数，它的取值只能是4到8之间
if(i == k) continue;
boolean f = true; //记录当前的组合是否符合条件
arr[3] = i;
arr[4] = 23-3-k-i; //根据之前给定的4个数算出第5个数来
if(arr[4] == arr[3]) continue;
for(int j=2; j<4; j++) { //j值代表了当前取到的哪个数了
//只需判断前j个数的和与j后面那个数的差不能超过1就可以判断是否合符条件(至于为什么？仔细思考下就知道了)
if(getSum(arr, j)-arr[j+1] < -1) { 
f = false; //不合符就设为false
break;
}
}
if(f) { //如果符合就打印输出
for(int m=0; m<arr.length; m++) 
System.out.print(arr[m] + " ");
System.out.println();
}
}
}
}

private static int getSum(int arr[], int j) {
int sum = 0;
for(int i=0; i<=j; i++) {
sum += arr[i];
}
return sum;
}
}最后打印出来的结果是：
1 2 3 5 12 
1 2 3 6 11 
1 2 3 7 10 
1 2 4 5 11 
1 2 4 6 10 
1 2 4 7 9 

Answer 5

public class Math {
int [] a = new int[3];
public void run(int i){
a[0] = i;
for(int j=i+1;j<=sum(1)+1;j++){
a[1] = j;
int temp = 23-sum(2);
if(temp<=sum(2)+1){
a[2] = temp;
doPrint();
}else
continue;
  }
}
//求数组前n项加上1，2的和
public int sum(int num){
int sum = 1+2;
for(int i=0;i<num;i++){
sum += a[i];
}
return sum;
}
//打印
public void doPrint(){
System.out.print("1 "+"2 ");
for(int i:a){
System.out.print(i+" ");
}
System.out.println();
}
public static void main(String args[]){
Math math = new Math();
math.run(3);
math.run(4);
}
}
结果同上