完整题目描述

题目：码小课课程安排

码小课网站计划在一个学期内为学生们安排一系列编程课程。每门课程有不同的持续时间（以周为单位），并且部分课程之间存在先修关系，即学生必须先完成某些课程，才能开始其他课程的学习。请设计一个算法，以确定是否存在一种安排方式，使得所有课程都能在给定的学期内（假设学期足够长，足以容纳所有课程）被完成，同时满足所有课程的先修关系。

输入：

1. 课程列表，每门课程包含课程ID、课程名称和持续时间（周数）。
2. 先修关系列表，表示哪些课程是其他课程的先修课程。

输出：

• 如果存在满足条件的课程安排，输出一个可能的课程安排顺序（不需要是唯一的）。
• 如果不存在满足条件的课程安排，输出"无法安排所有课程"。

示例

输入：

{
  "courses": [
    {"id": 1, "name": "编程基础", "duration": 6},
    {"id": 2, "name": "数据结构与算法", "duration": 8, "prerequisites": [1]},
    {"id": 3, "name": "Web开发基础", "duration": 4},
    {"id": 4, "name": "高级Web开发", "duration": 10, "prerequisites": [3]},
    {"id": 5, "name": "数据库原理", "duration": 7, "prerequisites": [1]}
  ]
}

输出：

1: 编程基础
3: Web开发基础
5: 数据库原理
2: 数据结构与算法
4: 高级Web开发

PHP 示例代码

<?php

function topologicalSort($courses) {
    $graph = [];
    $inDegree = [];
    $result = [];

    // 构建图及入度数组
    foreach ($courses as $course) {
        $graph[$course['id']] = isset($course['prerequisites']) ? $course['prerequisites'] : [];
        $inDegree[$course['id']] = 0;
    }

    foreach ($courses as $course) {
        if (isset($course['prerequisites'])) {
            foreach ($course['prerequisites'] as $prerequisite) {
                $graph[$prerequisite][] = $course['id'];
                $inDegree[$course['id']]++;
            }
        }
    }

    // 找到所有入度为0的节点
    $queue = [];
    foreach ($inDegree as $id => $degree) {
        if ($degree == 0) {
            $queue[] = $id;
        }
    }

    // 拓扑排序
    while (!empty($queue)) {
        $current = array_shift($queue);
        $result[] = $current;

        if (isset($graph[$current])) {
            foreach ($graph[$current] as $neighbor) {
                $inDegree[$neighbor]--;
                if ($inDegree[$neighbor] == 0) {
                    $queue[] = $neighbor;
                }
            }
        }
    }

    // 检查是否所有课程都被排序
    if (count($result) != count($courses)) {
        return "无法安排所有课程";
    }

    // 转换为课程名称
    $sortedCourses = [];
    foreach ($result as $id) {
        foreach ($courses as $course) {
            if ($course['id'] == $id) {
                $sortedCourses[] = $course['name'];
                break;
            }
        }
    }

    return implode("\n", array_map(function($name, $index) use ($sortedCourses) {
        return "$index+1: $name";
    }, $sortedCourses, array_keys($sortedCourses)));
}

// 示例输入
$courses = [
    ["id" => 1, "name" => "编程基础", "duration" => 6],
    ["id" => 2, "name" => "数据结构与算法", "duration" => 8, "prerequisites" => [1]],
    ["id" => 3, "name" => "Web开发基础", "duration" => 4],
    ["id" => 4, "name" => "高级Web开发", "duration" => 10, "prerequisites" => [3]],
    ["id" => 5, "name" => "数据库原理", "duration" => 7, "prerequisites" => [1]]
];

echo topologicalSort($courses);
?>

注意：此PHP代码仅处理了课程安排的逻辑部分，没有涉及学期时间长度是否足够的具体检查，因为题目已假设学期足够长。