商业网站设计欣赏,家装装饰设计,电脑网页制作培训,html前端网站开发PPT深度优先遍历-解决排列组合问题
问题1#xff1a; 假设袋子里有编号为1,2,…,m这m个球。现在每次从袋子中取一个球记下编号#xff0c;放回袋中再取#xff0c;取n次作为一组#xff0c;枚举所有可能的情况。 分析#xff1a; 每一次取都有m种可能的情况#xff0c;因此…深度优先遍历-解决排列组合问题
问题1 假设袋子里有编号为1,2,…,m这m个球。现在每次从袋子中取一个球记下编号放回袋中再取取n次作为一组枚举所有可能的情况。 分析 每一次取都有m种可能的情况因此一共有 m n m^n mn种情况。 这里我们取m 3, n 4则有 3 4 3^4 34种不同的情况。
代码
import java.util.Stack;public class Test {static int cnt 0;static StackInteger s new StackInteger();/*** 递归方法当实际选取的小球数目与要求选取的小球数目相同时跳出递归* param minv - 小球编号的最小值* param maxv - 小球编号的最大值* param curnum - 当前已经确定的小球的个数* param maxnum - 要选取的小球的数目*/public static void kase1(int minv,int maxv,int curnum, int maxnum){if(curnum maxnum){cnt;System.out.println(s);return;}for(int i minv; i maxv; i){s.push(i);kase1(minv, maxv, curnum1, maxnum);s.pop();}}public static void main(String[] args){kase1(1, 3, 0, 4);System.out.println(cnt);}
}输出
[1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 1, 3]
[1, 1, 2, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]
[1, 1, 3, 1]
[1, 1, 3, 2]
[1, 1, 3, 3]
[1, 2, 1, 1]
[1, 2, 1, 2]
[1, 2, 1, 3]
[1, 2, 2, 1]
[1, 2, 2, 2]
[1, 2, 2, 3]
[1, 2, 3, 1]
[1, 2, 3, 2]
[1, 2, 3, 3]
[1, 3, 1, 1]
[1, 3, 1, 2]
[1, 3, 1, 3]
[1, 3, 2, 1]
[1, 3, 2, 2]
[1, 3, 2, 3]
[1, 3, 3, 1]
[1, 3, 3, 2]
[1, 3, 3, 3]
[2, 1, 1, 1]
[2, 1, 1, 2]
[2, 1, 1, 3]
[2, 1, 2, 1]
[2, 1, 2, 2]
[2, 1, 2, 3]
[2, 1, 3, 1]
[2, 1, 3, 2]
[2, 1, 3, 3]
[2, 2, 1, 1]
[2, 2, 1, 2]
[2, 2, 1, 3]
[2, 2, 2, 1]
[2, 2, 2, 2]
[2, 2, 2, 3]
[2, 2, 3, 1]
[2, 2, 3, 2]
[2, 2, 3, 3]
[2, 3, 1, 1]
[2, 3, 1, 2]
[2, 3, 1, 3]
[2, 3, 2, 1]
[2, 3, 2, 2]
[2, 3, 2, 3]
[2, 3, 3, 1]
[2, 3, 3, 2]
[2, 3, 3, 3]
[3, 1, 1, 1]
[3, 1, 1, 2]
[3, 1, 1, 3]
[3, 1, 2, 1]
[3, 1, 2, 2]
[3, 1, 2, 3]
[3, 1, 3, 1]
[3, 1, 3, 2]
[3, 1, 3, 3]
[3, 2, 1, 1]
[3, 2, 1, 2]
[3, 2, 1, 3]
[3, 2, 2, 1]
[3, 2, 2, 2]
[3, 2, 2, 3]
[3, 2, 3, 1]
[3, 2, 3, 2]
[3, 2, 3, 3]
[3, 3, 1, 1]
[3, 3, 1, 2]
[3, 3, 1, 3]
[3, 3, 2, 1]
[3, 3, 2, 2]
[3, 3, 2, 3]
[3, 3, 3, 1]
[3, 3, 3, 2]
[3, 3, 3, 3]
81问题2 假设袋子里有编号为1,2,…,m这m个球。先后从袋子中取出n个球依次记录编号枚举所有可能的情况。 分析 这是排列问题如果取出的球顺序不同也是算不同的情况。因此应该有 m ∗ ( m − 1 ) ∗ ( m − 2 ) ∗ . . . ∗ ( m − n 1 ) m*(m-1)*(m-2)*...*(m-n1) m∗(m−1)∗(m−2)∗...∗(m−n1)种情况即 A m n m ! ( m − n ) ! A_m^n\frac{m!}{(m-n)!} Amn(m−n)!m!种 这里取m 5, n 3。则有5*4*3种。 和问题1相比唯一的区别是排列中不可以有重复。因此开了used数组用以标记是否已经访问。
代码
import java.util.Stack;public class Test {static int cnt 0;static StackInteger s new StackInteger();static boolean[] used new boolean[10000];/*** 递归方法当实际选取的小球数目与要求选取的小球数目相同时跳出递归* param minv - 小球编号的最小值* param maxv - 小球编号的最大值* param curnum - 当前已经确定的小球的个数* param maxnum - 要选取的小球的数目*/public static void kase2(int minv,int maxv,int curnum, int maxnum){if(curnum maxnum){cnt;System.out.println(s);return;}for(int i minv; i maxv; i){if(!used[i]){ //判断是否已经取过s.push(i);used[i] true;kase2(minv, maxv, curnum1, maxnum);s.pop();used[i] false;}}}public static void main(String[] args){kase2(1, 5, 0, 3);System.out.println(cnt);}
}输出
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 2]
[1, 3, 4]
[1, 3, 5]
[1, 4, 2]
[1, 4, 3]
[1, 4, 5]
[1, 5, 2]
[1, 5, 3]
[1, 5, 4]
[2, 1, 3]
[2, 1, 4]
[2, 1, 5]
[2, 3, 1]
[2, 3, 4]
[2, 3, 5]
[2, 4, 1]
[2, 4, 3]
[2, 4, 5]
[2, 5, 1]
[2, 5, 3]
[2, 5, 4]
[3, 1, 2]
[3, 1, 4]
[3, 1, 5]
[3, 2, 1]
[3, 2, 4]
[3, 2, 5]
[3, 4, 1]
[3, 4, 2]
[3, 4, 5]
[3, 5, 1]
[3, 5, 2]
[3, 5, 4]
[4, 1, 2]
[4, 1, 3]
[4, 1, 5]
[4, 2, 1]
[4, 2, 3]
[4, 2, 5]
[4, 3, 1]
[4, 3, 2]
[4, 3, 5]
[4, 5, 1]
[4, 5, 2]
[4, 5, 3]
[5, 1, 2]
[5, 1, 3]
[5, 1, 4]
[5, 2, 1]
[5, 2, 3]
[5, 2, 4]
[5, 3, 1]
[5, 3, 2]
[5, 3, 4]
[5, 4, 1]
[5, 4, 2]
[5, 4, 3]
60问题3 从m个球里编号为1,2,3…,m一次取n个球其中mn记录取出球的编号枚举所有的可能性。 分析 这是组合问题。应该有 ( m n ) m ! n ! ( m − n ) ! \binom{m}{n}\frac{m!}{n!(m-n)!} (nm)n!(m−n)!m!种可能性。 这里如果取m 8, n 4. 则有 ( 8 4 ) 8 ! 4 ! ( 8 − 4 ) ! 8 × 7 × 6 × 5 4 × 3 × 2 × 1 70 \binom{8}{4}\frac{8!}{4!(8-4)!}\frac{8\times7\times6\times5}{4\times3\times2\times1}70 (48)4!(8−4)!8!4×3×2×18×7×6×570种可能。
代码
import java.util.Stack;public class Test {static int cnt 0;static StackInteger s new StackInteger();/*** 递归方法当前已抽取的小球个数与要求抽取小球个数相同时退出递归* param curnum - 当前已经抓取的小球数目* param curmaxv - 当前已经抓取小球中最大的编号* param maxnum - 需要抓取小球的数目* param maxv - 待抓取小球中最大的编号*/public static void kase3(int curnum, int curmaxv, int maxnum, int maxv){if(curnum maxnum){cnt;System.out.println(s);return;}for(int i curmaxv 1; i maxv; i){ // i maxv - maxnum curnum 1s.push(i);kase3(curnum 1, i, maxnum, maxv);s.pop();}}public static void main(String[] args){kase3(0, 0, 4, 8);System.out.println(cnt);}
}输出
[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 3, 6]
[1, 2, 3, 7]
[1, 2, 3, 8]
[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 4, 7]
[1, 2, 4, 8]
[1, 2, 5, 6]
[1, 2, 5, 7]
[1, 2, 5, 8]
[1, 2, 6, 7]
[1, 2, 6, 8]
[1, 2, 7, 8]
[1, 3, 4, 5]
[1, 3, 4, 6]
[1, 3, 4, 7]
[1, 3, 4, 8]
[1, 3, 5, 6]
[1, 3, 5, 7]
[1, 3, 5, 8]
[1, 3, 6, 7]
[1, 3, 6, 8]
[1, 3, 7, 8]
[1, 4, 5, 6]
[1, 4, 5, 7]
[1, 4, 5, 8]
[1, 4, 6, 7]
[1, 4, 6, 8]
[1, 4, 7, 8]
[1, 5, 6, 7]
[1, 5, 6, 8]
[1, 5, 7, 8]
[1, 6, 7, 8]
[2, 3, 4, 5]
[2, 3, 4, 6]
[2, 3, 4, 7]
[2, 3, 4, 8]
[2, 3, 5, 6]
[2, 3, 5, 7]
[2, 3, 5, 8]
[2, 3, 6, 7]
[2, 3, 6, 8]
[2, 3, 7, 8]
[2, 4, 5, 6]
[2, 4, 5, 7]
[2, 4, 5, 8]
[2, 4, 6, 7]
[2, 4, 6, 8]
[2, 4, 7, 8]
[2, 5, 6, 7]
[2, 5, 6, 8]
[2, 5, 7, 8]
[2, 6, 7, 8]
[3, 4, 5, 6]
[3, 4, 5, 7]
[3, 4, 5, 8]
[3, 4, 6, 7]
[3, 4, 6, 8]
[3, 4, 7, 8]
[3, 5, 6, 7]
[3, 5, 6, 8]
[3, 5, 7, 8]
[3, 6, 7, 8]
[4, 5, 6, 7]
[4, 5, 6, 8]
[4, 5, 7, 8]
[4, 6, 7, 8]
[5, 6, 7, 8]
70
