这个是输出编号 []里面放编号 import java.util.Scanner;public class Choose { public static void showTeams(int[] array, int i, int chooseNum, int[] ) { if (i >= array.length) { int cnt = 0; for (int j = 0; j < array.length; ++j) cnt += array[j]; if (cnt == chooseNum) { for (int j = 0; j < array.length; ++j) { if (array[j] == 1) System.out.print([j] + " "); } System.out.println(); } return; } array[i] = 1; ++i; showTeams(array, i, chooseNum, ); array[i - 1] = 0; showTeams(array, i, chooseNum, ); } public static void main(String[] args) { int total, chooseNum; Scanner sc = new Scanner(System.in); total = sc.nextInt(); chooseNum = sc.nextInt(); int[] array = new int[total]; int[] = new int[total]; for (int i = 0; i < array.length; ++i) { array[i] = 0; [i] = i + 1; } showTeams(array, 0, chooseNum, ); }}
int a = Convert.ToInt32(Console.ReadLine()); int c = Convert.ToInt32(Console.ReadLine()); int k=1; int m=1; for (int i = a; i >= a-c+1; i--) { k *= i; } for (int j = 1; j <= c; j++) { m *= j; } int l = k / m; Console.WriteLine(l); Console.ReadLine(); l为 有多少种 k是你输入的人数 m是你需要的组队人数
我也来凑个热闹, 贴个用泛型的 import java.util.ArrayList; import java.util.List; import java.util.Scanner;public class ChooseMInN2 { static int total; static int need; static List<Integer> selected = new ArrayList<Integer>();
public static void showTeams(int current ) { if (selected.size()==need){ //成功 System.out.println(selected); return; } if (current>total) return; //失败 showTeams(current+1); //不加当前元素,继续探索 selected.add(current); showTeams(current+1); //加当前元素,继续探索 selected.remove(new Integer(current)); //回溯 } public static void main(String[] args) { Scanner sc = new Scanner(System.in); total = sc.nextInt(); need = sc.nextInt(); showTeams(1); }}
不错,就是n选k,递归为n-1选k-1
又是排列组合的问题,凑个热闹吧,递归和非递归写法 import java.util.*; public class Test { public static void main(String[] args) throws Throwable { Scanner sc = new Scanner(System.in); System.out.printf("please input amount of group: "); int n = sc.nextInt(); System.out.printf("please input amount of team: "); int k = sc.nextInt(); sc.close();
System.out.println("------method 1------"); showTeam(0, n, k, new StringBuilder()); //递归 System.out.println("------method 2------"); showTeam2(n, k); //非递归 } public static void showTeam(int start, int n, int k, StringBuilder buf) {//递归 if (k<1 || n<k || n<=start) return; if (k==1) { //递归结束 for (int i=start; i<n; i++) { System.out.printf("%s%d\n", buf.toString(), i+1); } return; }
String s = buf.toString(); for (int i=start; i<n; i++) { buf.delete(0, buf.length()); buf.append(s).append(i+1); showTeam(i+1, n, k-1, buf); //递归调用 } } public static void showTeam2(int n, int k) { //非递归,模拟二进制进位, //二进制位是1表示选中,是0表示非选中 if (k<1 || n<k) return; int[] idx = new int[n]; //二进制位 idx[idx.length-1] = 1; //二进制最低位设置为1,表示选中 int cnt = 0; //选中的个数 StringBuilder buf = new StringBuilder(); while (idx[0] < 2) { cnt = 0; buf.delete(0, buf.length()); for (int i=0; i<idx.length; i++) { if (idx[i] == 1) { //如果二进制位是1 cnt++; //选中+1 buf.append(data[i]); //挑出对象 } } if (cnt == k) { //如果选中个数是k,则打印结果 System.out.println(buf); } idx[idx.length-1]++; //二进制进位 for (int i=idx.length-1; i>0; i--) { if (idx[i] == 2) { idx[i] = 0; idx[i-1]++; } else { break; } } } } }
感谢各位,在各位的指导下,我也写了一个方法,结帖前,把代码贴上。再次谢谢大家! import java.util.ArrayList; import java.util.List; import java.util.Scanner;public class TeamChoice6 { int [] a; int end; List<Integer> selected = new ArrayList<Integer>(); public TeamChoice6(int n, int k) {
a = new int[n]; for(int i=1;i<=n;i++) a[i-1] = i; end = a.length-1; } public void showTeams(int start, int need) { if(need == 0) System.out.println(selected); else{ for(int i=start;i<=end -need+1;i++){ selected.add(a[i]); showTeams(i+1,need-1); selected.remove(new Integer(a[i])); } }
} public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("please input amount of group: "); int n = sc.nextInt(); System.out.println("please input amount of team: "); int k = sc.nextInt(); sc.close(); TeamChoice6 tc = new TeamChoice6(n,k); tc.showTeams(0,k); }}
import java.util.Scanner;
/**
* 输出1的被选中。0的未被选中
* @author
*
*/public class Choose {
public static void showTeams(int[] array, int i, int chooseNum) {
if (i >= array.length) {
int cnt = 0;
for (int j = 0; j < array.length; ++j)
cnt += array[j];
if (cnt == chooseNum) {
for (int j = 0; j < array.length; ++j)
System.out.print(array[j] + " ");
System.out.println();
}
return;
}
array[i] = 1;
++i;
showTeams(array, i, chooseNum);
array[i - 1] = 0;
showTeams(array, i, chooseNum);
} public static void main(String[] args) {
int total, chooseNum;
Scanner sc = new Scanner(System.in);
total = sc.nextInt();
chooseNum = sc.nextInt();
int[] array = new int[total];
for (int i = 0; i < array.length; ++i)
array[i] = 0;
showTeams(array, 0, chooseNum);
}}
如(5,3)=(4,2)+(4,3),再依次分解(4,2),(4,3),这样的复杂度是O(nlogn)
但是在递归我过程中我不知道怎么把选定的人答应出来。你有没什么方法?
这个是输出编号
[]里面放编号
import java.util.Scanner;public class Choose {
public static void showTeams(int[] array, int i, int chooseNum, int[] ) {
if (i >= array.length) {
int cnt = 0;
for (int j = 0; j < array.length; ++j)
cnt += array[j];
if (cnt == chooseNum) {
for (int j = 0; j < array.length; ++j) {
if (array[j] == 1)
System.out.print([j] + " ");
}
System.out.println();
}
return;
}
array[i] = 1;
++i;
showTeams(array, i, chooseNum, );
array[i - 1] = 0;
showTeams(array, i, chooseNum, );
} public static void main(String[] args) {
int total, chooseNum;
Scanner sc = new Scanner(System.in);
total = sc.nextInt();
chooseNum = sc.nextInt();
int[] array = new int[total];
int[] = new int[total];
for (int i = 0; i < array.length; ++i) {
array[i] = 0;
[i] = i + 1;
}
showTeams(array, 0, chooseNum, );
}}
int c = Convert.ToInt32(Console.ReadLine());
int k=1;
int m=1;
for (int i = a; i >= a-c+1; i--)
{
k *= i;
}
for (int j = 1; j <= c; j++)
{
m *= j;
}
int l = k / m;
Console.WriteLine(l);
Console.ReadLine(); l为 有多少种 k是你输入的人数 m是你需要的组队人数
贴个用泛型的
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class ChooseMInN2 {
static int total;
static int need;
static List<Integer> selected = new ArrayList<Integer>();
public static void showTeams(int current ) {
if (selected.size()==need){ //成功
System.out.println(selected);
return;
}
if (current>total) return; //失败
showTeams(current+1); //不加当前元素,继续探索
selected.add(current);
showTeams(current+1); //加当前元素,继续探索
selected.remove(new Integer(current)); //回溯
} public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
total = sc.nextInt();
need = sc.nextInt();
showTeams(1);
}}
import java.util.*;
public class Test {
public static void main(String[] args) throws Throwable {
Scanner sc = new Scanner(System.in);
System.out.printf("please input amount of group: ");
int n = sc.nextInt();
System.out.printf("please input amount of team: ");
int k = sc.nextInt();
sc.close();
System.out.println("------method 1------");
showTeam(0, n, k, new StringBuilder()); //递归
System.out.println("------method 2------");
showTeam2(n, k); //非递归
} public static void showTeam(int start, int n, int k, StringBuilder buf) {//递归
if (k<1 || n<k || n<=start) return; if (k==1) { //递归结束
for (int i=start; i<n; i++) {
System.out.printf("%s%d\n", buf.toString(), i+1);
}
return;
}
String s = buf.toString();
for (int i=start; i<n; i++) {
buf.delete(0, buf.length());
buf.append(s).append(i+1);
showTeam(i+1, n, k-1, buf); //递归调用
}
} public static void showTeam2(int n, int k) { //非递归,模拟二进制进位,
//二进制位是1表示选中,是0表示非选中
if (k<1 || n<k) return; int[] idx = new int[n]; //二进制位
idx[idx.length-1] = 1; //二进制最低位设置为1,表示选中
int cnt = 0; //选中的个数
StringBuilder buf = new StringBuilder();
while (idx[0] < 2) {
cnt = 0;
buf.delete(0, buf.length());
for (int i=0; i<idx.length; i++) {
if (idx[i] == 1) { //如果二进制位是1
cnt++; //选中+1
buf.append(data[i]); //挑出对象
}
}
if (cnt == k) { //如果选中个数是k,则打印结果
System.out.println(buf);
} idx[idx.length-1]++; //二进制进位
for (int i=idx.length-1; i>0; i--) {
if (idx[i] == 2) {
idx[i] = 0;
idx[i-1]++;
} else {
break;
}
}
}
}
}
考虑两种情况:1,假设最后一个元素单独一个集合,那么只需考虑将剩下的四个分解成两个集合…4→2
2,假设最后一个元素不是单独一个集合。那么就考虑4→3。然后将最后一个分别加入即可。你的不适合你问的这个。记得有一楼是用二进制来做的。那个应该满足你问的。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class TeamChoice6 {
int [] a;
int end;
List<Integer> selected = new ArrayList<Integer>();
public TeamChoice6(int n, int k) {
a = new int[n];
for(int i=1;i<=n;i++)
a[i-1] = i;
end = a.length-1;
} public void showTeams(int start, int need) {
if(need == 0)
System.out.println(selected);
else{
for(int i=start;i<=end -need+1;i++){
selected.add(a[i]);
showTeams(i+1,need-1);
selected.remove(new Integer(a[i]));
}
}
} public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("please input amount of group: ");
int n = sc.nextInt();
System.out.println("please input amount of team: ");
int k = sc.nextInt();
sc.close();
TeamChoice6 tc = new TeamChoice6(n,k);
tc.showTeams(0,k);
}}