当前位置:网站首页>Proof of the thinking of Hanoi Tower problem
Proof of the thinking of Hanoi Tower problem
2022-07-05 11:35:00 【Chinese descendants__】
Preface
Problem description : On a copper plate device , There are three rods ( Number A、B、C), stay A From the bottom up 、 Place in order from large to small 64 A gold plate ( Pictured 1). The goal of the game : hold A All the gold plates on the pole are moved to C On the pole , And still keep the original order . Operating rules : Only one plate can be moved at a time , And keep the big plate down all the time during the moving process , Small in , The plate can be placed during the operation A、B、C On any pole .
Problem analysis
In fact, the idea of the answer is very simple :
- set up A There are n Disc
- If n=1, Just put A->C ,Move( A, C);
- If it's something else
- Before A Upper n-1 A disk moves to B On ,Hanoi(n - 1, A, C, B)
- then A The last disc on the moves to C On ,Move(A, C)
- The final will be B Upper n-1 A disc moves C On ,Hanoi(n - 1, B, A, C)
But why is this feasible ? This comparison is puzzling . Here I offer you an idea : Using mathematical induction .
Prove :
hypothesis f(n) Operation representative handle n A disk from A The rod moves to C rod
Be careful , take n A disc, whether it's for A->C、B->C、A->B、C->B,B->A、C->A, These operations are completely equivalent
First ,f(1) The operation must be feasible
Now suppose f(n) Feasible operation , be f(n+1) The operation representative should put n+1 A disk from A The rod moves to C rod .
because f(n) Feasible operation , So you can put n A disk from A The rod moves to B rod , take A The last remaining disc of the rod is directly placed C rod .
Then it's because f(n) feasible , So you can put B Of the pole n A disk moves to C rod
Thus we can see that f(n+1) The operation of is feasible .
Obtain evidence : When n∈{1,2,3,…} when , f(n) Feasible operation
Here is C Complete case of language version ,P121_6 Representative question number , This code is written when I brush questions . The only real operation to start is P121_6 This function , Other functions are used to output relevant information , It's convenient for us to observe what happened .
typedef struct {
int *A;
int *B;
int *C;
int top[3];
}s_Hannoi,*p_hannoi;
// Hanoi Tower stack initialization
void P121_6_init(s_Hannoi& h, int n)
{
int i = n-1;
h.A = (int*)malloc(sizeof(int) * n);
h.B = (int*)malloc(sizeof(int) * n);
h.C = (int*)malloc(sizeof(int) * n);
h.top[0] = i;
h.top[1] = -1;
h.top[2] = -1;
for (;i >= 0;i--) {
h.A[i] = i;
}
}
void P121_6_Move(s_Hannoi& h,char out,char in)
{
int temp = -1,i,j;
printf("%c->%c:\n", out, in);
switch (out) {
case 'A':
temp = h.A[h.top[0]];
--h.top[0];
break;
case 'B':
temp = h.B[h.top[1]];
--h.top[1];
break;
case 'C':
temp = h.C[h.top[2]];
--h.top[2];
break;
}
switch (in) {
case 'A':
++h.top[0];
h.A[h.top[0]] = temp;
break;
case 'B':
++h.top[1];
h.B[h.top[1]] = temp;;
break;
case 'C':
++h.top[2];
h.C[h.top[2]] = temp;
break;
}
// Print the current structure
printf("\tA:");
for (i = 0;i < h.top[0]+1;i++) {
printf("%d,", h.A[i]);
}
printf("\n\tB:");
for (i = 0;i < h.top[1]+1;i++) {
printf("%d,", h.B[i]);
}
printf("\n\tC:");
for (i = 0;i < h.top[2]+1;i++) {
printf("%d,", h.C[i]);
}
printf("\n");
}
// The hanotta problem
void P121_6(s_Hannoi& h,int n,char A,char B,char C)
{
if (n == 1) {
P121_6_Move(h, A, C);
}
else {
P121_6(h, n - 1, A, C, B);
P121_6_Move(h, A, C);
P121_6(h, n - 1, B, A, C);
}
}
int main()
{
printf("***********************\n");
s_Hannoi h;
P121_6_init(h, 6);
P121_6(h, 6, 'A', 'B', 'C');
}
边栏推荐
猜你喜欢
12.(地图数据篇)cesium城市建筑物贴图
How can China Africa diamond accessory stones be inlaid to be safe and beautiful?
【云原生 | Kubernetes篇】Ingress案例实战(十三)
COMSOL -- 3D casual painting -- sweeping
Is it difficult to apply for a job after graduation? "Hundreds of days and tens of millions" online recruitment activities to solve your problems
AutoCAD -- mask command, how to use CAD to locally enlarge drawings
Cdga | six principles that data governance has to adhere to
分类TAB商品流多目标排序模型的演进
NFT 交易市场主要使用 ETH 本位进行交易的局面是如何形成的?
Summary of thread and thread synchronization under window
随机推荐
C # to obtain the filtered or sorted data of the GridView table in devaexpress
How can edge computing be combined with the Internet of things?
spark调优(一):从hql转向代码
1个插件搞定网页中的广告
2048游戏逻辑
解决readObjectStart: expect { or n, but found N, error found in #1 byte of ...||..., bigger context ..
Oneforall installation and use
How to protect user privacy without password authentication?
Advanced technology management - what is the physical, mental and mental strength of managers
Open3D 网格(曲面)赋色
Ffmpeg calls avformat_ open_ Error -22 returned during input (invalid argument)
FFmpeg调用avformat_open_input时返回错误 -22(Invalid argument)
MySQL statistical skills: on duplicate key update usage
871. Minimum Number of Refueling Stops
C operation XML file
Question and answer 45: application of performance probe monitoring principle node JS probe
Basics - rest style development
What does cross-border e-commerce mean? What do you mainly do? What are the business models?
Idea set the number of open file windows
爬虫(9) - Scrapy框架(1) | Scrapy 异步网络爬虫框架