使用递归的 C# 求解任务

本文关键字:任务 递归 | 更新日期: 2023-09-27 18:35:32

这是数据(模块代码,主题,您必须参加多少科目才能参加此模块,该模块代码)

N01 Math 0
N02 Physics 1 N01
N03 Chemistry 2 N01 N02
N04 Sports 0
N05 Logic 1 N04
N06 Music 1 N05
N07 Theatre 2 N03 N06
N08 Law 1 N03
N09 OS 2 N07 N08

最终结果

N01 Math
N04 Sports
N02 Physics
N03 Chemistry
N08 Law
N05 Logic
N06 Music
N07 Theatre
N09 OS

任务:找到所有符合要求的模块,例如(数学和体育没有任何要求,所以它们是第一和第二,为了选修物理,你必须选数学,这没有任何要求,所以物理是第三等等。

必须用递归来解决这个问题,但我不知道从哪里开始,什么是堆栈,我只知道如何使用递归解决简单的问题,比如找阶乘。有什么提示或指南如何解决这个问题吗?

使用递归的 C# 求解任务

我不会给你任何代码,因为那是你的工作。但是要让您知道该怎么做:

您需要一个具有

  • 身份证 ( string
  • 姓名 ( string
  • 依赖关系 ( List<string>

您将数据放入这些列表中。

然后你可以编写一个函数,我们称之为CalcDependencyLevel函数,它计算每个数据结构与结构列表相比的依赖级别:

此方法检查依赖项。如果没有依赖项,则为 0。如果它有一个依赖项,则它是 1 + 该依赖项的CalcDependencyLevel结果(这是递归)。

如果某些内容具有多个依赖项,则需要计算所有结果,然后使用最大值。

将此分数附加到每个数据结构,然后按该分数排序。

如果要优化算法,请在计算分数后立即将其附加到结构中,并在递归中使用预先计算的分数(如果可用),这样您就不必一遍又一遍地为同一实例重新计算它。

<小时 />

我上面所说的粗略实现(可能比你的类现在更高级,你绝对应该用你知道的方法实现你的解决方案,而不仅仅是复制这个并上交):

using System;
namespace ConsoleApp14
{
    using System.Collections.Generic;
    using System.Linq;
    internal class Course
    {
        public string Id { get; set; }
        public string Name { get; set; }
        public List<string> Dependencies { get; set; }
        public int? DependencyDepth { get; set; }
        public override string ToString()
        {
            return Name;
        }
    }
    internal class Program
    {
        private static string data = "N01 Math 0'n" 
                                   + "N02 Physics 1 N01'n"
                                   + "N03 Chemistry 2 N01 N02'n"
                                   + "N04 Sports 0'n"
                                   + "N05 Logic 1 N04'n"
                                   + "N06 Music 1 N05'n"
                                   + "N07 Theatre 2 N03 N06'n"
                                   + "N08 Law 1 N03'n"
                                   + "N09 OS 2 N07 N08'n";
        private static int DependencyDepth(Course course, List<Course> courses)
        {
            if (!course.DependencyDepth.HasValue)
            {
                if (!course.Dependencies.Any())
                {
                    course.DependencyDepth = 0;
                }
                else
                {
                    course.DependencyDepth = 1 + course.Dependencies.Max(dep => DependencyDepth(courses.First(c => c.Id == dep), courses));
                }
            }
            return course.DependencyDepth.Value;
        }
        static void Main()
        {
            var courses = data.Split("'n", StringSplitOptions.RemoveEmptyEntries)
                              .Select(line => line.Split(" "))
                              .Select(parts => new Course { Id = parts[0], Name = parts[1], Dependencies = parts.Skip(3).ToList() })
                              .ToList();
            courses.ForEach(course => DependencyDepth(course, courses));
            courses.OrderBy(course => course.DependencyDepth).ToList().ForEach(Console.WriteLine);
            
            Console.ReadLine();
        }
    }
}
<小时 />

结果是

数学

体育

物理

逻辑

化学

音乐

剧院

法律

操作系统

逻辑只需要运动。我不知道为什么你的目标是在逻辑之前对化学进行排序,因为它依赖于另外两个级别的课程。你可能想问问你的预期结果是如何产生的。它们不加起来。