java汉诺塔不可逆向问题!,将A中碟子在A,B,C三个柱子无限来回放的时候,比如某个碟子刚从A放入B,再把这个碟子从B

如何能够用最短的次数呗呗

int hanio(int a,int b,int c,int n,int *result) //a,b,c 分别代表3根针,n是金片数
//result是个长度为n的数组,第一位表示最小的金片,第二位表示次小的金片,...最后一位表示最大的数组.
//数组每个位上的值为a或b或c,表示该金片在哪个针上.显然,对于确定的result只有一种合法状态
{
if(n==1)
{
if(result[n-1]==c) return 0;
else return 1;
} //如果只有一个金片,平凡情况
else if(result[n-1]==c) return hanio(a,b,c,n-1,result);
//如果最大的金片在C针即第三根针上,该金片不动,问题转化为将n-1个金片移到C针上
else if(result[n-1]==a) return hanio(a,c,b,n-1,result)+(1r[j];//这里要防止r溢出
cout

你把1,2盘看成一个特殊的盘.所以现在n=2,当n=2时,需先把1盘移动到B塔中,把1-3步一起看,作用即把特殊盘移动至B.
然后把3盘移动至C塔,即第4步.
最后,把特殊盘移动到C塔上,同样把5-7步一起看,达到的效果即把特殊盘移动至C盘,完成!
等于4的时候 ,其实就是把123盘看成特殊盘!同样的道理,因为汉诺塔是递归实现的,明白之后很简单.

n个盘子的汉诺塔,无论旧规则新规则,都要分三步：
0、把(n-1)个盘子移到1号柱
1、把最后一个盘子移到2号柱
2、把(n-1)个盘子移到2号柱
为啥新规则也要遵守这三步呢.首先,前(n-1)个盘子必须都移到别的地方,才能移动最后一个盘子.这(n-1)个盘子的目标显然都不能是0号柱.
能不能是2号柱呢?也不可能,否则无法把最后一个盘子移到2号柱,因为违反“最底部盘子必须最大”的规则.
所以,第0步必须是把(n-1)个盘子移动到1号柱.
在1号柱上,最大的那个盘子必须在底部,但上面的(n-2)个盘子没有限制,这是唯一和旧规则不同的地方.
于是,旧规则里完全递归的问题在这里有点变化.n个盘子的第0步并不是完全对同一问题的递归,而是产生了新的子问题.
定义以下3种汉诺塔问题.这些问题的移动规则都是新规则.
传统汉诺塔：把n个有序的盘子移到另一柱,移动后仍然有序.
汉诺塔变体1：把n个有序的盘子移到另一柱,移动后最大的盘子必须在最低,但其余盘子随意.
汉诺塔变体2：把n个无序（最大的盘子必须在最低,但其余盘子随意）的盘子移到另一柱,移动后变成有序.
于是,在旧规则下,一个传统汉诺塔问题会产生2个少一个盘子的传统汉诺塔问题；而新规则下,一个传统汉诺塔问题会产生1个少一个盘子的汉诺塔变体1（第0步）,以及少一个盘子的汉诺塔变体2（第2步）.
接下来考虑m个盘子的汉诺塔变体1.要从0号柱移动到2号柱.要完成这个问题,仍然分3步：
0、把(m-1)个盘子移到1号柱
1、把最大的盘子移到2号柱
2、把(m-1)个盘子移到2号柱
为啥仍然分3步,是因为要求最大的盘子必须在2号柱底部.
但是这里的第2步非常简单,只要把每一个盘子依次移动到2号柱就可以了,不用来回倒腾,因为2号柱的底部已经有一个最大的盘子了.于是需要(m-1)次移动,不可能更少了.
那么第0步呢?这又是一个汉诺塔变体1.也就是熟悉的递归.
先等等,第0步的时候有没有可能在1号柱的底部,由于父问题的移动而已经有一个更大的盘子了?如果是这样,那就不用递归了,直接一个个移到1号柱就行了.
回答是没有,汉诺塔变体1如果有父问题,就一定是父问题的第0步,而第0步之前是没有任何移动的,也就不可能在0号柱以外的地方有更大的盘子.
所以不影响结论,汉诺塔变体1的第0步是递归.
汉诺塔变体1解决之后,2号柱上除了最大的盘子以外,其余盘子的顺序跟少一个盘子的子问题的顺序相反.想象一下第2步的具体过程就能明白了.直觉告诉我这个顺序可能很重要,因为汉诺塔变体2的解法可能跟初始顺序有关.
现在终于可以计算汉诺塔变体1的最优解移动次数了.记m个盘子的汉诺塔变体1的最优解移动次数为H1(m),则H1(m) = H1(m-1) + 1 + (m-1).显然H1(1) = 1,于是H1(m) = 1+2+3+...+m = m(m+1)/2.
接下来考虑m个盘子的汉诺塔变体1按照最优解解决后,2号柱是什么样子?
把所有盘子编号0,1,2,...,m-1.0号最小.
对于1个盘子的汉诺塔变体1,显然最终顺序是0.
对于2个盘子,会把0反序后下面放个1,于是最终顺序是（从顶到底）0,1.
对于3个盘子,会把0,1反序后下面放个2,于是1,0,2.
对于4个盘子,2,0,1,3.
5个盘子,3,1,0,2,4.
6个盘子,4,2,0,1,3,5.
能看出规律了我就不往下写了.最小的盘子竟然是夹在中间……好像不太好搞……
接下来考虑m个盘子的汉诺塔变体2,还是从0号柱移到2号柱.由于在传统汉诺塔中,这个问题是在汉诺塔变体1之后,所以m个盘子的初始排序就是上述的规律.
汉诺塔变体2仍然分3步：
0、把(m-1)个盘子移到1号柱
1、把最大的盘子移到2号柱
2、把(m-1)个盘子移到2号柱
这次,第0步非常简单,因为0号柱上最顶部的盘子恰好就是第二大的,把它移到1号柱之后它就是1号柱的最大盘子.然后把剩下(m-2)个盘子依次移到1号柱顶上就行了,一共是(m-1)次移动.而且移动完后,1号柱上恰好就是(m-1)个盘子的汉诺塔变体1的最终结果.
而第2步移动完后所有盘子需要有序,这也产生了完全一样只是少一个盘子的子问题,形成递归.这个递归比较显然,因为子问题和当前的汉诺塔变体2完全一样.
这样看来汉诺塔变体2和汉诺塔变体1是完全对称的,于是m个盘子的汉诺塔变体2的最优解的移动次数也是H2(m) = m(m+1)/2.
最后回到n个盘子的传统汉诺塔.
第0步是(n-1)个盘子的汉诺塔变体1,需要n(n-1)/2次移动.
第1步是1次移动.
第2步是(n-1)个盘子的汉诺塔变体2,需要n(n-1)/2次移动.
最后的最后,传统汉诺塔的最优解的移动次数是：
H(n) = n(n-1)/2 + 1 + n(n-1)/2 = n^2 - n + 1.
可比旧规则的指数级次数要好多了,这帮和尚的想法还真不错.
以上完全是我个人的现场推理的结论,尽可能进行了严密的推导但难免有遗漏之处,结论是错的也有可能,仅供参考.

（1）将上面（n-1）个从左边移到中间,
（2）将第n个从左边移到右边
(3)将上面（n-1）个从中间移到右边
这样就把移动N个的任务,转化成移动两次（n-1）个和移动一次第N个的任务,而移动（n-1）个需要移动两次（n-20个和移动一次第（n-1）个,移动（n-2）个需要移动两次（n-3）个和移动一次第（n-2）个——如此继续,直到转化为移动一个的情形,根据这个过程,可得递推公式
a1=1
an=2an-1+1(n>1)[(n-1)是下标,（n）也是下标]

hanoi函数的目的是解决汉诺塔的移动序列,它有4个参数：
1.n表示要移动的盘子的个数
2.一开始盘子在哪个柱子上,这个变量叫a,所以可以说,一开始在a柱子上
4.最后盘子要移动到哪个柱子上,这个变量叫c,所以可以说,最后要移动到c柱子上
3.中间用来过渡的柱子.汉诺塔一共3个柱子,用两个是不能完成的,所以还要有一个柱子进行过渡.
首先,如果n等于1,说明就只有一个盘子要从a柱子移动到c柱子,那么直接打印a->c
如果盘子的数量大于1,那就要分开解决.
（1）首先把顶上的n-1个盘子从一开始的a柱子移动到b柱子
递归调用：
第一个参数是要移动的盘子数量,现在需要移动n-1个盘子
第二个参数是从哪里开始移动,现在盘子都在a柱子上,所以是a
第四个参数是移到哪里去,现在要移到b柱子上,所以是b
第三个参数是剩下的那个柱子,也就是c
（2）n-1个盘子移掉以后,a柱子只剩下最后的大盘子,直接移到c柱子,也就是打印a->c
（3）把（1）之后移到b柱子上的n-1个盘子从b移动到c
所以递归调用：
第一个参数是盘子个数,现在只有n-1个了
第二个参数是从哪里开始移,现在盘子都在b柱子上,所以是b
第四个参数是移到哪里去,我们要移到c柱子上,所以是c
第三个参数就是另外的一个柱子,所以是a

把1，2移到C杆违反了规则：大的碟子2不能叠在小的碟子1上面把1移到A，2移到C，1移到C，3移到A，1移到B，2移到A，1再移到A

#include
#include
#define MaxSize 4
typedef int ElemType;
typedef struct
{
x05ElemType data[MaxSize];
x05int top;char name;
}SqStack;
void InitStack(SqStack * &s,char b) //初始化栈
{
x05s=(SqStack *)malloc(sizeof(SqStack));
x05s->top=-1;s->name=b;
}
void ClearStack(SqStack * &s) //销毁栈
{
x05free(s);
}
void CreateStack(SqStack * &s) //创建栈
{
x05int A[MaxSize],i;
x05for(i=0;itop++;
x05x05s->data[s->top]=A[i];
x05}
}
int Pop(SqStack * &s,ElemType &e) //出栈
{
x05if(s->top==-1)
x05x05return 0;
e=s->data[s->top];x05
x05s->top--;
x05return 1;
}
int Push(SqStack * &s,ElemType e) //进栈
{
x05if(s->top==MaxSize-1)
x05return 0;
x05s->top++;
s->data[s->top]=e;
x05return 1;
}
void DispStack(SqStack *s) //显示栈中元素
{
x05for(int i=s->top;i>=0;i--)
x05x05printf("%d ",s->data[i]);
x05printf("n");
}
void Move(SqStack * &A,SqStack * &B) //将栈A的栈顶元素移动到栈B
{
x05ElemType e;
Pop(A,e);
x05Push(B,e);
}
void Hanoi(int n,SqStack *A,SqStack *B,SqStack * &C) //汉诺塔算法
{char e;
x05if(n==1) {Move(A,C);
x05printf("将第%d个碟子从%c移到%c上n",A->data[A->top+1],A->name,C->name);
x05}
x05else{
x05x05Hanoi(n-1,A,C,B);
x05x05Move(A,C);
x05x05printf("将第%d个碟子从%c移到%c上n",A->data[A->top+1],A->name,C->name);
x05x05Hanoi(n-1,B,A,C);
x05}
}
void main()
{
x05SqStack *A,*B,*C;
x05InitStack(A,'A') ;
x05InitStack(B,'B') ;
x05InitStack(C,'C') ;
x05CreateStack(A);
x05printf("A栈中元素从栈顶到栈底依次为：");
x05DispStack(A);
x05Hanoi(MaxSize,A,B,C);
x05printf("C栈中元素从栈顶到栈底依次为：");
x05DispStack(C);
x05ClearStack(A);
x05ClearStack(B);
ClearStack(C);
}

毫无差别啊，只不过一个动作做两次而已，比如原来是move from A to B,现在变成连着两次move from A to B,move from A to B。

一个单位有10个部门,每个部门都有一部电话,但是整个单位只有一根外线,当有电话打过来的时候,由转接员转到内线电话,已知各部门使用外线电话的频率为（次/天）
5 20 10 12 8 4 3 5 6 9
问应该如何设计个内线电话号码,使得接线员拨号次数尽可能少?
这是哈夫曼树的应用