Жадный алгоритм на примере системы управления статусами студентов

2024-07-12

1.жадный алгоритмпредставлять

1. Идея алгоритма

Основная идея жадного алгоритма состоит в том, чтобы действовать шаг за шагом, начиная с начального решения проблемы. Согласно мере оптимизации, каждый шаг должен гарантировать возможность получения локального оптимального решения. На каждом шаге рассматривается только одна информация, и ее выбор должен соответствовать условиям локальной оптимизации. Если следующие данные и частичное оптимальное решение связаны вместе и оно больше не является допустимым решением, данные не будут добавлены к частичному решению до тех пор, пока все данные не будут перечислены или алгоритм больше не может быть добавлен и алгоритм не остановится.

Жадный алгоритм обычно работает следующим образом:

①Установитьматематическая модельчтобы описать проблему.

② Разделите проблему, которую необходимо решить, на несколько подзадач.

③ Решить каждую подзадачу и получить локально оптимальное решение подзадачи.

④ Объединить локальное оптимальное решение подзадачи с решением исходной задачи.

Жадный алгоритм — это более простой и быстрый метод проектирования определенных задач оптимального решения. Характерной чертой жадного алгоритма является то, что он действует шаг за шагом, часто делая оптимальный выбор на основе текущей ситуации и меры оптимизации, без рассмотрения всех возможных общих ситуаций, что устраняет необходимость исчерпать все возможности для поиска оптимального решения. Много времени потрачено.Жадный алгоритм используетсверху вниз , сделайте последовательный жадный выбор итеративным методом. Каждый раз, когда делается жадный выбор, желаемая проблема упрощается до меньшей подзадачи. На каждом этапе жадного выбора можно получить оптимальное решение проблемы. Хотя необходимо гарантировать, что локальное оптимальное решение может быть получено на каждом шаге, результирующее глобальное решение иногда не обязательно является оптимальным, поэтому жадные алгоритмы не возвращаются назад [2].

2. Введение в код


 
    /**
     * 为指定学生推荐最合适的课程。
     * @param scanner 用于接收用户输入的Scanner对象。
     * @param studentService 用于获取学生信息的服务。
     * @param courseService 用于获取课程列表的服务。
     */
    public static void recommendBestCourse(Scanner scanner, StudentService studentService, CourseService courseService) {
        // 提示用户输入学生ID并接收输入
        System.out.print("输入学生ID：");
        int studentID = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
 
        // 根据学生ID获取学生信息，如果学生不存在则返回
        Student student = studentService.getStudentById(studentID);
        if (student == null) {
            System.out.println("未找到该学生。");
            return;
        }
 
        // 获取所有课程的列表，如果没有课程信息则返回
        List<Course> courses = courseService.listAllCourses();
        if (courses.isEmpty()) {
            System.out.println("当前没有课程信息。");
            return;
        }
 
        // 使用贪心算法推荐最合适的课程
        Course bestCourse = findBestCourse(student, courses);
        if (bestCourse != null) {
            // 如果找到最佳课程，打印课程信息
            System.out.println("推荐的最合适课程是：" + bestCourse.getCourseName());
            System.out.println("课程ID: " + bestCourse.getCourseID());
            System.out.println("学分: " + bestCourse.getCreditHours());
        } else {
            System.out.println("没有找到合适的课程。");
        }
    }
 
    /**
     * 使用贪心算法找到最合适的课程。
     * @param student 需要推荐课程的学生。
     * @param courses 可供选择的所有课程列表。
     * @return 最佳课程对象。
     */
    private static Course findBestCourse(Student student, List<Course> courses) {
        Course bestCourse = null; // 用于存储当前找到的最佳课程
        int maxScore = Integer.MIN_VALUE; // 用于存储当前最高分数
 
        // 遍历所有课程
        for (Course course : courses) {
            // 计算每个课程的得分
            int score = calculateCourseScore(student, course);
            // 如果当前课程的得分高于已知最高分数，则更新最佳课程和最高分数
            if (score > maxScore) {
                maxScore = score;
                bestCourse = course;
            }
        }
 
        // 返回得分最高的课程作为最佳课程推荐
        return bestCourse;
    }
 
    /**
     * 计算单个课程的得分，用于评估课程的适宜性。
     * @param student 学生对象。
     * @param course 课程对象。
     * @return 计算得到的课程得分。
     */
    private static int calculateCourseScore(Student student, Course course) {
        int score = 0; // 初始化得分
 
        // 学分越高，得分越高，这里假设每1学分得10分
        score += course.getCreditHours() * 10;
 
        // 如果学生未修过该课程，额外加分，这里假设额外加50分
        List<Grade> grades = student.getGrades(new GradeService()); // 获取学生已修课程的列表
        boolean isTaken = grades.stream().anyMatch(grade -> grade.getCourseID() == course.getCourseID());
        if (!isTaken) {
            score += 50;
        }
 
        // 返回计算得到的得分
        return score;
    }

3. Используйте жадный алгоритм, чтобы рекомендовать наиболее подходящий курс конкретному студенту.

1. Определение метода:
— «recommendBestCourse» — статический метод, который получает объект «Сканер» для ввода данных пользователем, а также объекты сервисного уровня «StudentService» и «CourseService» для получения информации о студентах и курсах.

2. Обработка пользовательского ввода:
- Программа сначала предлагает пользователю ввести идентификатор студента, а затем использует объект «Сканер» для считывания этого входного значения.

3. Сбор информации о студентах:
- Используйте метод «studentService.getStudentById(studentID)» для получения информации о студенте на основе идентификатора студента. Если студент не существует, распечатайте подсказку и завершите выполнение метода.

4. Получите список курсов:
- Вызовите CourseService.listAllCourses(), чтобы получить список всех доступных курсов. Если информация о курсе отсутствует, также будет напечатана подсказка, и выполнение метода завершится.

5. Логика рекомендаций:
- Используйте жадный алгоритм, чтобы рекомендовать студентам наиболее подходящий курс, вызывая метод findBestCourse.

6. Реализация жадного алгоритма:
- Метод findBestCourse проходит по всем курсам и вычисляет балл для каждого курса с помощью метода CalculateCourseScore. Курс с наивысшим баллом выбирается как лучшая рекомендация.

7. Подсчет баллов:
- Метод CalculateCourseScore определяет логику расчета баллов за курс. В этом примере оценка зависит от двух факторов: количества кредитов за курс и того, прошел ли студент этот курс. Чем больше кредитов, тем выше балл, и дополнительные баллы начисляются, если студент не прошел курс.

8. Рекомендуемый результат:
- Если лучший курс найден, распечатайте название курса, идентификатор курса и информацию о кредитах. Если подходящего курса нет, распечатайте соответствующее сообщение-подсказку.

Обмен технологиями