写一下非递归算法的伪代码

非递归算法可以使用循环来实现，以下是一个求斐波那契数列第n项的非递归算法的伪代码：

function fibonacci(n)
    if n <= 1
        return n
    else
        prev_prev := 0
        prev := 1
        current := 1
        for i from 2 to n
            current := prev + prev_prev
            prev_prev := prev
            prev := current
        return current

该算法使用循环将前两项的值初始化为0和1，然后计算每一项的值并将其存储在变量current中，最后返回current的值。

相关问题

背包问题非递归算法伪代码

以下是背包问题的非递归算法伪代码：

knapsack(W, wt, val, n):
    // W: 背包容量，wt: 物品重量数组，val: 物品价值数组，n: 物品数量
    dp = 二维数组，大小为 (n+1) x (W+1)
    
    // 初始化 dp 数组
    for i = 0 to n:
        for w = 0 to W:
            if i == 0 or w == 0:
                dp[i][w] = 0
            else if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

其中，`dp[i][w]` 表示在前 `i` 个物品中，背包容量为 `w` 的情况下所能获得的最大价值。`wt[i-1]` 和 `val[i-1]` 分别表示第 `i` 个物品的重量和价值，因为数组下标是从 0 开始的，所以需要减去 1。最终返回 `dp[n][W]`，表示在前 `n` 个物品中，背包容量为 `W` 的情况下所能获得的最大价值。

写出非递归快速选择算法的伪代码

非递归的快速选择算法通常会利用分治策略，通过一趟遍历找出枢轴，然后根据枢轴将数组划分成三部分：小于枢轴的元素、等于枢轴的元素以及大于枢轴的元素。下面是一个简单的非递归快速选择算法的伪代码示例：

function quickSelectNonRecursive(arr, k):
    if arr is empty or k < 0 or k >= length(arr):
        return None  // 处理边界条件

    pivotIndex = partition(arr)  // 分区函数，返回枢轴元素的索引
    if pivotIndex == k:
        return arr[pivotIndex]
    else if pivotIndex < k:
        // 如果k在分区后的右侧，递归在右侧数组中查找
        return quickSelectNonRecursive(arr[pivotIndex + 1:], k - pivotIndex - 1)
    else:
        // 否则在左侧数组中查找
        return quickSelectNonRecursive(arr[:pivotIndex], k)

function partition(arr):
    pivotValue = arr[length(arr) / 2]  // 取数组中心元素作为枢轴
    i = lowIndex = 0
    j = highIndex = length(arr) - 1
    while i <= j:
        while arr[i] < pivotValue and i <= j:
            i += 1
        while arr[j] > pivotValue and i <= j:
            j -= 1
        if i < j:
            swap arr[i] with arr[j]
        else:
            swap arr[i] with arr[length(arr) - 1]  // 将枢轴放到正确的位置
    return i

在这个伪代码中，`quickSelectNonRecursive`函数负责主循环，每次根据当前枢轴找到正确区域，然后继续在子数组中进行下一次迭代直到找到目标位置。`partition`函数负责对数组进行分区操作。