C++数据结构学习:递归(2.2)

2016-02-19 20:23 5 1 收藏

今天给大家分享的是由图老师小编精心为您推荐的C++数据结构学习:递归(2.2)，喜欢的朋友可以分享一下，也算是给小编一份支持，大家都不容易啊!

【 tulaoshi.com - 编程语言】

3号盘子的目标柱是C，但是已经有了1号盘子，我们最直觉的反映就是——将碍事的盘子搬到另一根柱子上面去。于是，我们要做的是（规律2）：保存当前柱的信息（柱子号、应该搬动的最下面一块盘子的号，和它的目标柱），以备当障碍清除后回到现在的柱子继续搬，将当前柱转换为碍事的盘子所在的柱子。假设这样若干步后，我们将7号盘子从A搬到了C，此时，保存当前柱号的栈一定是空了，我们该怎么办呢？

　　　　显而易见的，转换当前柱为B，把6号盘子搬到C。由此可得出（规律3）：假设当前的问题规模为n，搬动第n个盘子到C后，问题规模减1，当前柱转换到另一个柱子，最下面的盘子的目标柱为C。
　　

更多内容请看C/C++技术专题数据结构数据结构教程专题，或　　综上，我们已经把这个问题解决了，可以看出，要害是如何确定当前柱需要移动多少盘子，这个问题请大家自己考虑，给出如下例程，因为没有经过任何优化，本人的编码水平又比较低，所以这个函数很慢——比递归的还慢10倍。
　　
　　
　　　　#include
　　
　　 !-- frame contents -- !-- /frame contents -- 　　#include
　　
　　　　using namespace std;
　　
　　　　class Needle
　　
　　　　{
　　　　
　　　　public:
　　　　
　　　　Needle() { a.push_back(100); }//每一个柱子都有一个底座
　　　　
　　　　void push(int n) { a.push_back(n); }
　　　　
　　　　int top() { return a.back(); }
　　
　　　　int pop() { int n = a.back(); a.pop_back(); return n; }
　　
　　　　int movenum(int n) { int i = 1;while (a[i] n) i++; return a.size() - i; }
　　
　　　　int size() { return a.size(); }
　　
　　　　int operator [] (int n) { return a[n]; }
　　
　　　　private:
　　
　　　　vector a;
　　
　　　　};
　　
　　　　void Hanoi(int n)
　　
　　　　{
　　
　　　　Needle needle[3], ns;//3个柱子，ns是转换柱子时的保存栈，借用了Needle的栈结构
　　
　　　　int source = 0, target, target_m = 2, disk, m = n;
　　
　　　　for (int i = n; i 0; i--) needle[0].push(i);//在A柱上放n个盘子
　　
　　　　while (n)//问题规模为n，开始搬动
　　
　　　　{
　　

更多内容请看C/C++技术专题数据结构数据结构教程专题，或　　if (!m) { source = ns.pop(); target_m = ns.pop();
　　
　　　　m = needle[source].movenum(ns.pop()); }//障碍盘子搬走后，回到原来的当前柱
　　
　　　　if (m % 2) target = target_m; else target = 3 - source - target_m;//规律1的实现
　　
　　 !-- frame contents -- !-- /frame contents -- 　　if (needle[source].top() needle[target].top())//当前柱顶端盘子可以搬动时，移动盘子
　　
　　
　　　　{
　　
　　　　disk = needle[source].top();m--;
　　
　　　　cout < disk < " move " < (char)(source + 0x41) < " to "< (char)(target + 0x41) < endl;//显示搬动过程
　　
　　　　needle[target].push(needle[source].pop());//在目标柱上面放盘子
　　
　　　　if (disk == n) { source = 1 - source; target_m = 2; m = --n; }规律3的实现
　　
　　　　}
　　
　　　　else//规律2的实现
　　
　　　　{
　　
　　　　ns.push(needle[source][needle[source].size() - m]);
　　
　　　　ns.push(target_m); ns.push(source);
　　
　　　　m = needle[target].movenum(needle[source].top());
　　
　　　　target_m = 3 - source - target; source = target;
　　
　　　　}
　　
　　　　}
　　　　}
　　

更多内容请看C/C++技术专题数据结构数据结构教程专题，或　　这个算法实现比递归算法复杂了很多（递归算法在网上、书上随便都可以找到），而且还慢很多，似乎是多余的，然而，这是有现实意义的。 !-- frame contents -- !-- /frame contents -- 我不知道现在还在搬64个盘子的僧人是怎么搬的，不过我猜想一定不是先递归到1个盘子，然后再搬——等递归出来，估计胡子一打把了（能不能在人世还两说）。我们一定是马上决定下一步怎么搬，就如我上面写的那样，这才是人的正常思维，而用递归来思考，想出来怎么搬的时候，黄瓜菜都凉了。
　　
　　　　正像我们做事的方法，虽然我今生今世完不成这项事业，但我一定要为后人完成我能完成的，而不是在那空想后人应该怎么完成——假如达不到最终的结果，那也一定保证向正确的方向前进，而不是呆在原地空想。
　　
　　　　由此看出，计算机编程实际上和正常的做事步骤的差距还是很大的——我们的做事步骤假如直接用计算机来实现的话，其实并不能最优，原因就是，实际中的相关性在计算机中可能并不存在——比如人脑的逆推深度是有限的，而计算机要比人脑深很多，论记忆的准确性，计算机要比人脑强很多。这也导致了一个普通的程序员和一个资深的程序员写的算法的速度经常有天壤之别。因为，后者知道计算机喜欢怎么思考。
　　

更多内容请看C/C++技术专题数据结构数据结构教程专题，或

来源:http://www.tulaoshi.com/n/20160219/1623541.html

上一篇： Windows RT 支持的语言版本汇总
下一篇：关于Java数据对象JDO 2.0查询语言的特点

看过《C++数据结构学习:递归(2.2)》的人还看了以下文章更多>>

C++数据结构学习:二叉树(4)

标签：编程语言网络编程

才刚开了个头，就要说再见了——在树这里，除了二叉树，别的都还没有讲。为什么可以总结了呢？因为前面已经涉及到了树的两个基本用途，而假如再讲B＋、B－，就不能不提到搜索，假如是胜者树就不能不提到排序。为此，把这部分放到后面。 !-- frame contents -- !-- /frame contents -- 我前面所做的努力，只是让你有个基本概念，什么...

C++数据结构学习:二叉树(2)

标签：编程语言网络编程

线索化二叉树这是数据结构课程里第一个碰到的难点，不知道你是不是这样看，反正我当初是费了不少脑细胞——当然，恼人的矩阵压缩和相关的加法乘法运算不在考虑之列。 !-- frame contents -- !-- /frame contents -- 我费了不少脑细胞是因为思考：他们干什么呢？很欣喜的看到在这本黄皮书上，这章被打了*号，虽然我不...

C++数据结构学习:二叉树(3)

标签：编程语言网络编程

递归遍历与非递归遍历前面写过一些关于递归的文章，因为那时还没有写到树，因此也举不出更有说服力的例子，只是阐述了“递归是一种思想”，正像网友评价的，“一篇入门的文章”。但只要能能让你建立“递归是一种思想”这个观念，我的努力就没有白费。 !-- frame contents -- !-- /frame contents -- 现在，讲完了二叉...

C++数据结构学习:二叉树(1)

标签：编程语言网络编程

这些天参与了CSDN论坛的讨论，改变了我以前的一些看法。回头看我以前的东西，我虽对这本书很不满，但我还是按照它的安排在一点点的写；这样就导致了，我过多的在意书中的偏漏，我写的更多是说“这本书怎样”，而偏离了我写这些的初衷——给正在学习数据结构的人一些帮助。 !-- frame contents -- !-- /frame contents -- 正像我在前...

C++数据结构学习:在链表中链入对象

标签：编程语言网络编程

似乎你也注重到了，不管怎么定义，似乎一个链表中的对象都是同一类型的。而实际上，这也是必须的，否则，返回节点中的数据这样的函数的返回值的类型是什么呢？但是，人的要求是无止境的……（省略本人感慨若干百字）。 !-- frame contents -- !-- /frame contents -- 把不同的对象链在一个链表中的目的是为了方便使用，现在一定记住...

查看更多精彩>>