首页 > 分享 > 递归问题题目

递归问题题目

花匠小妙招
2024-12-07 20:19

－
　　递归部分内容算是彻底完成了，差强人意，不过还说得过去。题目都还是挺好的，对于思维训练方面也是挺全面的。其中印象最深的有四个题目：
一、三个圆做成的维恩图可以描述三个给定集合的8个子集。在这里插入图片描述

我尽量列了好多可能的集合，花了不少时间，也没搞明白所谓的这8个集合是哪八个（能够找出来的可不止八个）。但在找的过程中（因为问题是四个圆能够表示多少个子集个数）忽然转移了注意力，想找一下n个圆能够构成的可能集合数。列举后直观的去找规律。因为其实表示的集合其实就是“交”“并”“补”运算能够得到的集合数。初步的想法是组合数学寻求一般规律（对于数个数的题目很经常的会通过组合数学求解），但尝试了一下不好找。然后发现，当写出重叠后能够得到一些个相互相邻的区间，其实就可以抽象成一个无向图，继而求解图中能够得到的所有生成树。再然后，其实得到最多区间的方法就是使得新加的区间与先前的所有圆都相交以得到尽量多的小区间，这时其实可以去忽略“圆”形区间的形状了，而仅考虑n个集合相交的情况。当然，我没有细研究后两个想法（真要自己去查证应该是不小的工程，而且不见得一定能得到结果），但起码对于这类问题可以有不同的角度考虑，再找寻可行的解题思路。
二、双重河内塔问题
（1）河内塔上有2n个圆盘，第n个圆盘与第n+1个圆盘同样大，问要移动需要次数。
　　这个其实非常简单，只需要单纯的较普通河内塔问题加倍即可。即：aₙ=2ⁿ⁺¹-2，n>0。
（2）同（1），但要求移动后的相同的两个圆盘顺序先后顺序不变。
　　这里仍然可以采用河内塔问题的一般思路，即已知bₙ₋₁时，仅考虑第n组（两个）的移动情况，要保证第n组的优先顺序不变，很容易得到bₙ=2bₙ₋₁+bₙ₋₁+4，n>0(具体过程在书上)。如果没有题（1）,可能就这样结束了，错了也浑然不知。但重新看一下的话，对于前n-1组来说，会在起始位置和终点位置间来回移动了两次，最后第n组圆盘移动过去后再移动到终点位置。因此，在这里前两次的移动并不需要保证相同的圆盘优先顺序不变，且通过分析可以得到，通过题（1）的移动方式移动一次会反置优先顺序，但再进行一次反置就可以得到正确的优先顺序。如此，就可以得到bₙ=bₙ₋₁+2*aₙ₋₁+4,n>0，这一递推公式才是最优的(具体过程及封闭式在书上)。所以，回过头来看一下这个问题，直接给出(2)来不太容易思考全面得到正解，而先分析简单情况(改变了问题后的简单问题而不是原问题的简单可能情况)后再进一步研究原问题可能更易得到问题的解。当然这一问题对于这一方法的应用还不够直观，下一个题是对这一方法的典型的应用。
三、给定n条Z形线，每条Z形线由两条半直线和一条连接两条半直线的线段构成，问能够将平面切割成多少个区域。
　　暴力求解，单是简单情况就很复杂，处理不好可能就是处理错误数据最终顶多得到一个错误结论，所以不如将问题适当的修改。在这里可以将这一条直线中的连接线段无限延长，继而将两条半直线无限接近，这样，在两条折线相交时可以近似研究成两组由三条平行直线构成的组合进行相交以得到尽可能多的区域，这样就可以研究n条折线问题了。先前n-1条折线都已做到最优，在画第n条折线（第n组平行线）时，要使它与先前的已存在的所有折线都相交以得到尽可能多的新区域，这时计算新增的区域数。但得到的并不是原问题的解，所以还要考虑实际情况（原先存在的折角）对于区域数的影响，继而得到正解（具体过程及递推式、封闭式在书上）。这时再看一下这个题目，当发现题目较难解决时，可以考虑解决一个类似的较简单的问题，再最后返回原先的情况得到原问题的解，而在解决改变后的问题时，还是通过解决较小情况以得到一般规律的套路处理，如此形成了解决这一问题的一般思路。
四、约瑟夫问题求解倒数第二个人（最后一个死的人）位置。
　　我还是通过列举一部分数据（打表）以寻求一般规律，当然，递推公式写出来了，但无论如何写不出来一个封闭式，我用了两种方法，尝试了三个形式的封闭式也没能解出来，更无法从其二进制数中看到规律。所以去看了答案，发现答案的结果跟我的不同，而且求出来了封闭式（分段函数形式，我自己解时尝试过两种分段函数），而方法就是舍去n=2的情形去求解，看完后我很无语，我研究时想着要把n=2的情况包含到结果中去，所以使问题更加复杂，而答案中忽略后求解封闭式根本没当回事。这个题提一下主要目的是提醒自己，别老是傻了吧唧的一条路走到黑。
　　递归问题到这里就告一段落了，研究这一类问题对于ACM来说最重要的就是分析问题的角度，当问题规模较大时，可以考虑研究小情形以解决一般情形，而当问题结构复杂时，可以简化结构求解问题再推广到原先问题的解决。当然，明白了这些其实暂时来说对于做题（ACM的题目）来说作用并不是很大，但它的意义是对于解决此类问题的理解更加深刻，也就是对于递归问题和动态规划类问题问题分析角度和方法上更加清晰，但解决实际问题需要实战经验，所以看情况尽可能做题吧。