递归与迭代解斐波那契数列及单调栈入栈问题

"2018年机试题目包含两道编程题，一道是关于计算斐波那契数列的问题，另一道是实现单调栈的功能。" 对于第一道题目，我们面临的是一个计算斐波那契数列的问题。斐波那契数列是一个经典的数列，其中每个数字是前两个数字的和，起始数字为0和1。给定一个整数n（0 < n < 100000），我们需要计算F(n)并返回结果对854562545取余的值。为了解决这个问题，避免递归方法导致的时间复杂度过高，我们可以使用循环迭代的方式来计算。在提供的源代码中，使用了两个变量f0和f1来存储斐波那契数列的前两个数，然后通过一个for循环来计算后续的数。每次迭代时，将f0和f1的和对854562545取余，然后更新f0和f1的值。当计算到n时，f就是所求的F(n)。 第二道题目要求实现一个单调栈。单调栈是一种特殊的栈，其特性是栈中的元素始终是单调递增或单调递减的。当一个新的元素n入栈时，如果栈顶元素大于n，那么就将栈顶元素出栈，直到栈顶元素不大于n。这样可以确保栈内元素始终保持单调性。题目中给出了输入和输出的例子，首先输入一个整数n表示待入栈的元素数量，接着输入n个数，最后输出入栈后的栈中元素。为了解决这个问题，可以使用一个动态分配的数组来模拟栈，并在读取每个输入数时，按照单调栈的规则调整栈的状态。源代码中，使用了一个while循环来处理输入，当新元素小于等于栈顶元素时，新元素入栈；否则，栈顶元素出栈，直到满足条件。最后，遍历栈并打印出栈中的元素。 这两道题目都是典型的算法题目，主要考察了递归与迭代的转换、栈数据结构的运用以及高效算法设计的能力。在实际编程中，理解这些基础知识对于解决复杂问题至关重要。