10只无差别的橘子放到3个不同的盘子里。允许有的盘子空着。请问一共有多少种不同的放法?A

本题正确答案为B。本题是一个乘法原理与组合综合运用的问题。首先，把球放入盒子需分三步走，这需用乘法原理。其次，放入盒中的球不计顺序，这是一个组合问题，因此，综合以上两点可知，共有C³₆×C²₃×C¹₁＝20×3×1＝60种放法

[答案]C。[解析]题中所述操作相当于：将10个不能区分的苹果放到三个盘子中(每个盘子至少一个苹果)，运用隔板法，

[答案]C。[解析]一个刚好能覆盖4个边长为6厘米的正方形的圆的直径是

厘米＞16厘米，故这个盘子不能放下4个边长为6厘米的正方体。估算知可以放下3个，呈“品”字形摆放。。

答案：结合二叉树的中序遍历，我们很容易就画出3阶汉诺塔的空间递归树：

中序遍历这个二叉树，遍历某个节点时，输出from和to，with无须输出，就可以得到3阶汉诺塔的移动顺序：

盘子:1A>>>>C

盘子:2A>>>>B

盘子:1C>>>>B

盘子:3A>>>>C

盘子:1B>>>>A

盘子:2B>>>>C

盘子:1A>>>>C

可以看到，汉诺塔算法所生成的二叉树是一个相当完美的“完全二叉树”，所以它的总节点数是2^3-1=7个。

二、先简化一下算法；通过层序遍历，构建双链表；顺序遍历双链表，输出！

1、再仔细观察一下递归树，例如第一层的节点：A--null--C,“分裂成”了第二层的两个节点：A--C--B和B--A--C，而第二层的第一个节点A--C--B,又“分裂成”了：A--null--C和C--null--B。简化一下:如果不考虑with柱，只考虑from和to柱，AC可以分裂成AB和BC，AB可以分裂成AC和CB......相信你已经看出规律了，所以可以进一步简化为下面的递归树：

2、通过队列来构造双链表：

为了实现算法，你需要写这样一个小函数：

private static final String str="ABC";

public String getWith(String from,String to){

String with;

//找出ABC中的某个和from、to都不相等的字符串，赋值给with

return with;

}

你还需要有一个节点类：

/**

 * 汉诺塔节点

 *

 */

public class HanNode {

/**

 * 盘子的编号

 */

private int num;

/**

 * from柱

 */

private String from;

/**to柱

 * 

 */

private String to;

/**

 * 双链表中的前驱结点

 */

private HanNode pre;

/**

 * 双链表中的后继结点

 */

private HanNode next;

public int getNum() {

return num;

}

public void setNum(int num) {

this.num = num;

}

public String getFrom() {

return from;

}

public void setFrom(String from) {

this.from = from;

}

public String getTo() {

return to;

}

public void setTo(String to) {

this.to = to;

}

public HanNode getPre() {

return pre;

}

public void setPre(HanNode pre) {

this.pre = pre;

}

public HanNode getNext() {

return next;

}

public void setNext(HanNode next) {

this.next = next;

}

public HanNode(int num, String from, String to) {

super();

this.num = num;

this.from = from;

this.to = to;

}

public HanNode() {

super();

}

@Override

public String toString() {

return " [盘子:" + num + ", 从:" + from + "到:" + to + "]";

}

}

还需要设置两个全局变量top和last作为双链表的头和尾，为了和其他的节点区分开来，设置它们的num为0；

 下面的任务就是通过队列来构造双链表，对于某一趟运算：

①取出一个节点currentNode出队列，把这个currentNode的from和to传入getWith()函数，然后生成两个新的节点leftNode{num=currentNode.getNum()-1，from=from，to=with}和rightNode{num=currentNode.getNum()-1,from=with,to=to},压入队列。

②把生成的leftNode和rightNode插入到双链表中的currentNode的两端（需要断裂原来的链并生成新的链）