Qbic's questions

有n个高度相同的梯形。浪费区域 - 当一个梯形连接到另一个梯形或连接到胶带的开头/结尾时，三角形的区域被切断。

任务是开发一种算法，用于在将梯形放置在胶带上时最大限度地减少浪费的面积。当您需要找到浪费区域为 0 的放置时，我会考虑使用简化版本。

梯形 (ABCD) 由三个数字给出：

• Bx - B点的x坐标
• Cx - C点的x坐标
• Dx - D点的x坐标

A 点总是 (0, 0)

输入文件示例：

n
b1x c1x d1x
...
bnx cnx dnx

Example:
10
-100 0 500
-900 -100 500
-1400 -400 500
-500 -400 500
-900 -400 500
-1300 500 500
0 400 500
-800 -800 500
-900 -900 500
-600 -300 500

我写了一个递归算法，但它在处理大量梯形时运行缓慢。1000个梯形，他数了很久。

程序.cs

using Minimization;

const int h = 10;

decimal StartArea(int bx) => Math.Abs(bx) * h / 2;

decimal EndArea(int cx, int dx) => Math.Abs(cx - dx) * h / 2;

decimal Area(int cx, int dx, int bx) => (cx < dx && bx < 0) || (cx > dx && bx > 0) ?
        (Math.Abs(cx - dx) - Math.Abs(bx)) * h / 2 :
        (Math.Abs(cx - dx) + Math.Abs(bx)) * h / 2;

var path = @"c:\tests\9.txt";

var trapezoids = FileUtilities.GetTrapezoids(path);

HashSet<(int bx, int cx, int dx, int index)> startCandidates = new();

for (var i = 0; i < trapezoids.Length; i++)
{
    if (StartArea(trapezoids[i].bx) == 0)
        startCandidates.Add((trapezoids[i].bx, trapezoids[i].cx, trapezoids[i].dx, i));
}

var candidates = new Dictionary<int, HashSet<int>>();

for (var i = 0; i < trapezoids.Length; i++)
{
    candidates[i] = new HashSet<int>();
    for (var j = 0; j < trapezoids.Length; j++)
    {
        if (i == j) continue;
        if (Area(trapezoids[i].cx, trapezoids[i].dx, trapezoids[j].bx) == 0)
            candidates[i].Add(j);
    }
}


int[] res = null;

foreach (var (bx, cx, dx, index) in startCandidates)
{
    res = new int[trapezoids.Length];
    var currentPlace = 0;

    var currentIndex = index;
    res[currentPlace] = currentIndex;
    currentPlace++;

    res = PossibleList(currentPlace, res.AsSpan(), trapezoids);

    if (res != null)
        break;
}

int[]? PossibleList(int currentPlace, Span<int> span, Span<(int bx, int cx, int dx)> trapezoids)
{
    var currentIndex = res[currentPlace - 1];

    var nextCandidates = Except(candidates[currentIndex], span, currentPlace);

    if (nextCandidates.Count == 0)
        if (currentPlace == trapezoids.Length && EndArea(trapezoids[currentIndex].cx, trapezoids[currentIndex].dx) == 0)
            return span.ToArray();
        else
            return null;

    foreach (var candidate in nextCandidates)
    {
        span[currentPlace] = candidate;

        var possible = PossibleList(currentPlace + 1, span, trapezoids);

        if (possible != null)
            return possible;
    }

    return null;
}

HashSet<int> Except(HashSet<int> candidates, Span<int> span, int currentPlace)
{
    var res = new HashSet<int>();

    foreach (var candidate in candidates)
        if (!span[..currentPlace].Contains(candidate))
            res.Add(candidate);

    return res;
}

文件实用程序.cs

namespace Minimization
{
    /// <summary>
    /// Утилиты для работы с файлами
    /// </summary>
    public static class FileUtilities
    {
        public static Span<(int bx, int cx, int dx)> GetTrapezoids(string path)
        {
            using var sr = new StreamReader(path);

            var n = int.Parse(sr.ReadLine()!);

            var res = new (int bx, int cx, int dx)[n];

            for (var i = 0; i < n; i++)
            {
                var str = sr.ReadLine();
                var splitted = str!.Split();
                res[i] = (int.Parse(splitted[0]), int.Parse(splitted[1]), int.Parse(splitted[2]));
            }

            return res.AsSpan();
        }
    }
}

如何优化算法？我正在考虑尝试使用堆栈，但我真的不知道没有递归该怎么做。

任务：通过分隔符“;”将字符串分成几部分 该函数的形式为 Sum(expr) 或 Sum(expr; condition)。嵌套理论上是无限的

输入：Sum(a;b) 输出 expr = a 条件 = b

输入：Sum(a) 输出 expr = a 条件 = null

输入数据：Sum(Sum(a;c);b) 输出数据 expr = Sum(a;c) 条件 = b

输入数据：Sum(Sum(a);Sum(b;d)) 输出数据 expr = Sum(a) 条件 = Sum(b;d)

请告知如何最好地处理这些情况。我尝试使用搜索 IndexOf(";")，它在嵌套的情况下无法正常工作