java - 只是做了一些练习，遇到了一些问题，不知道是逻辑还是什么。我需要一些眼睛

问题描述

我总是回到这个问题，我从来没有解决它。我不知道为什么它给我带来了这么多问题。我通常可以很好地通过前四个测试用例，然后它会失败或运行太慢。自从我开始尝试它已经快一年了，所以我决定给它一个新的外观。我不在学校，这只是为了好玩，或者至少我认为会是这样。我采用了几何方法，并使用了递归方法。我想知道是否有人可以指出我的逻辑出错的地方，一个会使逻辑失败的测试用例。当我手动计算时，我自己提出的每个测试用例似乎都是正确的。除非我的数学是错的；我真的希望不是这样。

所以这就是问题所在：https ://open.kattis.com/problems/a1paper

我得到了 2 行输入，第一行告诉我最小的纸张尺寸，A2,3,4,5,.... 下一行给了我从尺寸 2、3 开始的纸张数量， 4，名词。

这个想法是确定将纸张粘在一起以获得A1纸所需的胶带数量。

这是我的解决方案：

import java.util.Scanner;

public class A1Paper
{   
    private static Scanner scan = new Scanner(System.in);
    private static final double ABSOLUTE_ERROR = Math.pow(10.0, -5.0);

    public static void main(String[] args)
    {
        final double SHORT_SIDE = Math.pow(2.0, -5.0/4.0);
        final double LONG_SIDE = Math.pow(2.0, -3.0/4.0);
        final double A1_AREA = 2 * SHORT_SIDE * LONG_SIDE;

        int remainingSizes = scan.nextInt() - 1;
        scan.nextLine();

        Result result = process(remainingSizes, SHORT_SIDE, LONG_SIDE, A1_AREA);

        if (result != null)
            System.out.println(result.getTape());
        else
            System.out.println("impossible");

        scan.close();
        return;
    }

    private static Result process(int remainingSizes, double shortSide, double longSide, double remainingArea)
    {   
        if (withinAbsoluteError(remainingArea))
        {
            return null;
        }

        if (remainingSizes == 0)
            return null;

        int remainingSheets = scan.nextInt();

        int sheetsUsed = 0;

        if (remainingSheets > 0)
        {
            double sheetArea = shortSide * longSide;

            while (remainingSheets > 0 && !withinAbsoluteError(remainingArea))
            {   
                remainingSheets--;
                sheetsUsed++;
                remainingArea -= sheetArea;
            }
        }

        Result prevResult = process(remainingSizes - 1, longSide/2.0, shortSide, remainingArea);
        Result thisResult = null;

        if (prevResult == null)
        {
            if (sheetsUsed%2 != 0 || sheetsUsed == 0)
                return null;

            thisResult = new Result(sheetsUsed/2, sheetsUsed/2 * longSide);
        }
        else
        {
            sheetsUsed += prevResult.getSheets();

            if (sheetsUsed%2 !=0)
                return null;

            thisResult = new Result(sheetsUsed/2, prevResult.getTape() + (sheetsUsed/2 * longSide));
        }

        return thisResult;
    }

    private static boolean withinAbsoluteError(double remainingArea)
    {   
        if (remainingArea <= ABSOLUTE_ERROR && remainingArea >= -ABSOLUTE_ERROR)
            return true;
        else
            return false;
    }

    private static class Result
    {
        private int sheets;
        private double tape;

        public Result(int sheets, double tape)
        {
            this.sheets = sheets;
            this.tape = tape;
        }

        public int getSheets()
        {
            return sheets;
        }

        public double getTape()
        {
            return tape;
        }
    }
}

显然存在一个不起作用的测试用例，Kattis 不想给我测试用例，所以我很好奇是否有人有任何想法。正如我所说，我提出的每一个例子似乎都通过了。

我将在这里解释我的功能：

private static Result process(int remainingSizes, double shortSide, double longSide, double remainingArea)

第一次调用函数：

remainingSizes ：从输入流接收到的第一个 int。因为它为您提供最小尺寸的纸张，例如。4 (A4) ，那么 3 将是剩余的尺寸（A2、A3、A4）。

给出了大小 A2 的 shortSide 和 longSide 并用于在其第一次迭代时调用该函数：

final double SHORT_SIDE = Math.pow(2.0, -5.0/4.0);
final double LONG_SIDE = Math.pow(2.0, -3.0/4.0);

剩余面积：最初传递第一个函数调用时，需要达到A1的面积，或者是A2面积的两倍。

结束递归的两种情况，要么区域在 absoluteError 内，要么我们用完了不同大小的纸张：

if (withinAbsoluteError(remainingArea))
            {
                return null;
            }

if (remainingSizes == 0)
                return null;

该函数的下一部分采用 A2 纸的数量（在第一次调用中）。如果我们有纸张，则计算 A2 的面积，并从剩余面积中减去，同时保持使用的纸张和剩余纸张的数量。然后是对该方法的递归调用，将纸张切成两半以获得下一个尺寸的纸张，例如 A3。

int remainingSheets = scan.nextInt();

        int sheetsUsed = 0;

        if (remainingSheets > 0)
        {
            double sheetArea = shortSide * longSide;

            while (remainingSheets > 0 && !withinAbsoluteError(remainingArea))
            {   
                remainingSheets--;
                sheetsUsed++;
                remainingArea -= sheetArea;
            }
        }

        Result prevResult = process(remainingSizes - 1, longSide/2.0, shortSide, remainingArea);

这个过程将一直持续到我遇到该区域或用完床单。

在该方法的下一部分中，我确定使用的磁带数量：

Result thisResult = null;

        if (prevResult == null)
        {
            if (sheetsUsed%2 != 0 || sheetsUsed == 0)
                return null;

            thisResult = new Result(sheetsUsed/2, sheetsUsed/2 * longSide);
        }
        else
        {
            sheetsUsed += prevResult.getSheets();

            if (sheetsUsed%2 !=0)
                return null;

            thisResult = new Result(sheetsUsed/2, prevResult.getTape() + (sheetsUsed/2 * longSide));
        }

        return thisResult;'

这里有两种可能，或者之前的调用返回null，并且没有页面，或者有页面。我看待它的方式是，如果我正在通过函数调用进行工作，那么当我将它们粘在一起并制作更大的页面时，必须有均匀数量的页面。

例如：

如果我有 1 - A2、1 - A3、2 - A4

然后将 2 - A4 沿其长边贴上，将制作一个 A3，将其添加到我拥有的 A3 中，这就是 2 - A3。将这些 2-A3 粘在一起形成 A2，将其添加到我拥有的那个上，即 2-A2。粗略地说，两个 A2 形成一个 A1。

我不知道这个解释是否完全清除了我的代码，对不起，如果我让它变得比它必须的更混乱。

标签： javatestcase

java - 只是做了一些练习，遇到了一些问题，不知道是逻辑还是什么。我需要一些眼睛

问题描述

解决方案

推荐阅读