在多道程序设计系统中,有三个作业 J1、J2、J3 到达时间依次为 8:00、8:30、9:00,它们需计算的时间分别 - 6 - 为 2 小时,1 小时和 0.5 小时。系统采用响应比高者优先调度算法在 10:00 开始选择作业,作业被选中的次序应该是____。 A J1、J2、J3 B J3、J2、J1 C J2、J1、J3 D J1、J3、J2

响应比高者优先调度算法是根据作业的等待时间和服务时间来计算响应比，响应比越高的作业优先被调度。假设当前时间为 10:00，计算每个作业的响应比：

J1 的等待时间为 2 小时，服务时间为 6 小时，响应比为 (2 + 6) / 6 = 1.33；
J2 的等待时间为 1.5 小时，服务时间为 2 小时，响应比为 (1.5 + 2) / 2 = 1.75；
J3 的等待时间为 1 小时，服务时间为 0.5 小时，响应比为 (1 + 0.5) / 0.5 = 3。

因此，应该选择响应比最高的作业 J3，然后是 J2，最后是 J1。所以答案是 B J3、J2、J1。

相关问题

以一个 m * n 的长方阵表示迷宫， 0和1分别表示迷宫的通路和障碍。 设计一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。 基本要求 ： （1） 实现一个以链表做存储的栈类型， 然后编写一个求解迷宫的非递归程序。 求的通路以三元组（i， j， d） 的形式输出， 其中：（i， j） 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 如： 对于下列数据的迷宫， 输出一条通路： （1， 1， 1），（1， 2， 2）， （2， 2， 2），（3， 2， 3），（3， 1， 2） ……。 （2） 编写递归形式的算法， 求得迷宫中所有可能的道路；

（1）非递归求解迷宫通路的程序：

首先，我们需要定义一个以链表为存储结构的栈类型。每个栈节点包含三个数据域：i，j和d，分别表示在迷宫中的坐标和前进的方向。

class MazeStackNode:
    def __init__(self, i, j, d):
        self.i = i
        self.j = j
        self.d = d
        self.next = None

class MazeStack:
    def __init__(self):
        self.top = None

    def isEmpty(self):
        return self.top is None

    def push(self, i, j, d):
        node = MazeStackNode(i, j, d)
        node.next = self.top
        self.top = node

    def pop(self):
        if self.isEmpty():
            return None
        node = self.top
        self.top = node.next
        return node

接下来，我们编写一个非递归算法来求解迷宫通路。该算法使用一个栈来保存当前的位置和前进方向，同时使用一个 visited 数组来记录已经访问过的位置。算法流程如下：

1. 将起点 (i0, j0) 和前进方向 d0 入栈，并将 visited[i0][j0] 设置为 True。
2. 从栈中弹出当前位置和前进方向，将其记为 (i, j, d)。
3. 如果当前位置是终点 (i1, j1)，则输出路径并结束。
4. 否则，按照前进方向 d 依次尝试前进，直到找到一个未访问过的位置 (i2, j2)。
5. 如果找到了未访问过的位置 (i2, j2)，则将其入栈，并将 visited[i2][j2] 设置为 True。
6. 如果没找到未访问过的位置，则将当前位置出栈。
7. 重复步骤 2 到步骤 6，直到栈为空，此时无法到达终点，输出无解信息。

下面是完整的 Python 代码实现：

def solve_maze(maze, i0, j0, i1, j1):
    m, n = len(maze), len(maze[0])
    visited = [[False] * n for _ in range(m)]
    stack = MazeStack()
    stack.push(i0, j0, 0)

    while not stack.isEmpty():
        i, j, d = stack.pop()
        visited[i][j] = True

        if i == i1 and j == j1:
            print_path(stack)
            return

        for nd in range(d+1, 5):
            if nd == 1 and i > 0 and not visited[i-1][j] and maze[i-1][j] == 0:
                stack.push(i-1, j, nd)
                break
            elif nd == 2 and j < n-1 and not visited[i][j+1] and maze[i][j+1] == 0:
                stack.push(i, j+1, nd)
                break
            elif nd == 3 and i < m-1 and not visited[i+1][j] and maze[i+1][j] == 0:
                stack.push(i+1, j, nd)
                break
            elif nd == 4 and j > 0 and not visited[i][j-1] and maze[i][j-1] == 0:
                stack.push(i, j-1, nd)
                break
        else:
            continue

    print("No solution.")

def print_path(stack):
    if stack.isEmpty():
        return
    node = stack.pop()
    print_path(stack)
    print("({}, {}, {})".format(node.i, node.j, node.d))

该算法的时间复杂度为 $O(mn)$，空间复杂度为 $O(mn)$。

（2）递归求解迷宫通路的程序：

首先，我们需要定义一个递归函数来求解迷宫通路。该函数需要接受当前位置和前进方向作为参数，并返回是否能够到达终点。为了记录路径，我们还需要定义一个栈类型，每个栈节点包含三个数据域：i，j和d，分别表示在迷宫中的坐标和前进的方向。

class MazeStackNode:
    def __init__(self, i, j, d):
        self.i = i
        self.j = j
        self.d = d
        self.next = None

class MazeStack:
    def __init__(self):
        self.top = None

    def isEmpty(self):
        return self.top is None

    def push(self, i, j, d):
        node = MazeStackNode(i, j, d)
        node.next = self.top
        self.top = node

    def pop(self):
        if self.isEmpty():
            return None
        node = self.top
        self.top = node.next
        return node

接下来，我们编写一个递归函数 solve_maze_recursive，该函数使用回溯的方法来求解迷宫通路。函数流程如下：

1. 如果当前位置是终点 (i1, j1)，则返回 True。
2. 按照前进方向 d 依次尝试前进，如果能够到达一个未访问过的位置 (i2, j2)，则将其入栈，并递归调用 solve_maze_recursive(i2, j2, nd)。
3. 如果递归调用返回 True，则说明已找到通路，将当前位置入栈并返回 True。
4. 如果前进方向已经尝试完毕，则将当前位置出栈并返回 False。

下面是完整的 Python 代码实现：

def solve_maze_recursive(maze, i, j, i1, j1, d, stack):
    if i == i1 and j == j1:
        return True

    for nd in range(d+1, 5):
        if nd == 1 and i > 0 and maze[i-1][j] == 0 and (i-1, j) not in stack:
            stack.push(i-1, j, nd)
            if solve_maze_recursive(maze, i-1, j, i1, j1, 0, stack):
                stack.push(i, j, nd)
                return True
            stack.pop()
        elif nd == 2 and j < len(maze[0])-1 and maze[i][j+1] == 0 and (i, j+1) not in stack:
            stack.push(i, j+1, nd)
            if solve_maze_recursive(maze, i, j+1, i1, j1, 0, stack):
                stack.push(i, j, nd)
                return True
            stack.pop()
        elif nd == 3 and i < len(maze)-1 and maze[i+1][j] == 0 and (i+1, j) not in stack:
            stack.push(i+1, j, nd)
            if solve_maze_recursive(maze, i+1, j, i1, j1, 0, stack):
                stack.push(i, j, nd)
                return True
            stack.pop()
        elif nd == 4 and j > 0 and maze[i][j-1] == 0 and (i, j-1) not in stack:
            stack.push(i, j-1, nd)
            if solve_maze_recursive(maze, i, j-1, i1, j1, 0, stack):
                stack.push(i, j, nd)
                return True
            stack.pop()

    return False

该算法的时间复杂度为指数级别，空间复杂度为 $O(mn)$，因此只适合求解小规模的迷宫。