java - 非自明なJava数学の演習

Question

私はプログラミング能力をテストするためにこの質問を与えられました。プログラミングと同じくらい数学だと思いますが。私は正直に失敗しましたが、将来の参考のためにそれがどのように行われるのか知りたいです。

理想的な答えは、再帰とスレッドを使用することです。

あなたの姪は誕生日にブロックのセットを与えられ、彼女は3”×1”と4.5”×1”のブロックを使用してパネルを作ることにしました。構造の完全性のために、ブロック間のスペースは隣接する列に並んではいけません。 。たとえば、最初の2行のブロック間のスペースの一部が並んでいるため（点線​​で示されているように）、下の13.5インチ×3インチのパネルは受け入れられません。

7.5”×1”パネルを構築する2つの方法、7.5”×2”パネルを構築する2つの方法、12”×3”パネルを構築する4つの方法、および27”×5を構築する7958の方法があります。 」パネル。姪が48インチ×10インチのパネルを作成する方法はいくつありますか。答えは64ビット整数に収まります。答えを計算するプログラムを書いてください。

それが問題です。数学の観点からどこから始めればよいのかわかりません。最初の行で考えられるすべての組み合わせを計算する必要があることを理解しています。しかし、どうすればいいのかよくわかりません。次に、この時点で特定のスレッドで、次の行のすべての可能なコンボを計算できます。次に、最初の行の組み合わせごとに独自のスレッドを取得し、その設定を再帰的アルゴリズムに渡して、現在の行を最後の行と比較し、考えられる答えを見つけることができます。しかし、どの行でも可能な組み合わせを計算する方法がわからないため、実際にプログラムすることはできません。もしそうなら、それが合法的な行（2つのブロックが正確に重なっていない（千鳥））かどうかを確認して、次の行に進むことができるかもしれません。おそらく、各行は、コードの観点から次の行の周りにネストされたforループになります。しかし、再び私はしません

Answer 1

あなたは問題を最初によく理解していると思います。私があなたの考えを正しく理解しているなら、あなたは各行の配置ではなく、各ブロックの配置で繰り返しるべきです-垂直に向けられたブロックはすぐに通常の行を排除するからです。

私が採用するアプローチは次のとおりです。最終的にツリーを構築します（明示的にメモリ内または暗黙的に：ツリーは再帰関数で渡される引数にすることができます）。ツリーのノードはツリーの状態になります。したがって、ルートは「ブロックが配置されていません」です。最初のブロックを「どういうわけか」配置し（これについては説明します）、それは新しい状態を表します。

目標は、すべてが完全で（ボードが埋められている）、合法である（亀裂が並んでいない）リーフノードのセットを構築することです。では、どうやってそこにたどり着くのでしょうか。

ブロックの配置ごとに、4つの「代替現実」があります。水平に配置された3x1ブロック、垂直に配置された3x1（これを1x3と呼びます）、水平に配置された4.5x1、および1x4.5です。これらのオプションのそれぞれについて、行の次のポイントにブロックを「合法的に」配置しようとします。それが合法である場合（「ブロックはボードの端に重ならない、ブロックは垂直の端を共有しない」の線に沿って合法である）、そのボードを中間状態として受け入れ、その新しい状態で再帰することができます。それが合法でない場合、その状態は放棄されなければなりません。

このように考えると、最初の4つの子ノードは[3x1、1x3、4.5x1、1x4.5]のように左下隅のブロックになります。これらの4つの状態のそれぞれには、4つの構成のいずれかで「右側に」ブロックがあります。

行を移動するために、右端にぶつかると、「最も低い」空のスペースを見つけて、左から右に結ぶときに任意に埋めます。これは、エッジが不規則な場合に大きなセットを剪定するのに十分な熱心さですが、最初に始めたときのように、レベルがフラットな場合でもうまく機能します。

本質的に、ツリーには、中間状態ごとに（最大）4つのノードがあり、エッジは「配置の試行」を表します。その「試行された配置」にブロックを合法的に配置できない場合は、その可能性とツリーからのすべての子孫を剪定して、再帰しません。

このブルートフォース方式では、計算の複雑さが天文学的なものであっても、完成したボードが得られるはずです。スレッドとの並列化を検討する必要があるのは、いくつかの問題を正しく解決できる時点でのみです。再帰的な問題は、スレッドに適している傾向があります。これは、各再帰があまり苦痛を伴わずに並列化できることが多いためです。最初に正しく理解するようにしてください。

Answer 2

この投稿はほぼ5年前のものですが、私の答えは誰かに役立つかもしれません。以下の2つの解決策があります。1つは、マルチスレッドなしです。2つ目は、4つのスレッドを使用して問題を解決します。48x4パネルを計算します（48x10は非常に長く続きます）が、初期値を変更することで簡単に変更できます。

nbOfRows、nbOfCols、wallWidth、wall

マルチスレッドなしのソリューション：

import java.io.*;
import java.util.*;

class WallFlexOld
{
    static final float blocks[] = {3.0f, 4.5f};
    static final int nbOfRows = 4;
    static final int nbOfCols = 16;
    static final float wallWidth = 48.0f;
    static final float wall[][] = {
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
                            };

    static long nbOfCombinations = 0;

    public static void main(String args[])
    {
        long startTime = System.currentTimeMillis();
        addBlock(0, 0);
        long workingTime = System.currentTimeMillis() - startTime;

        System.out.println("Working time: " + workingTime + "ms");
        System.out.println("noc: " + nbOfCombinations);
    }

    static void addBlock(int row, int col)
    {
        for(float b: blocks)
        {
            wall[row][col] = b;
            if(blockFit(row, col))
            {
                if(rowWidth(row) <= wallWidth)
                {
                    if(rowWidth(row) == wallWidth)
                    {
                        if(row == (nbOfRows - 1))
                            nbOfCombinations++;
                        else
                            addBlock(row + 1, 0);
                    }
                    else //rowWidth < wallWidth
                        addBlock(row, col + 1);

                }
            }   
            wall[row][col] = 0; 
        }
    }

    static float rowWidth(int row)
    {
        float width = 0;
        for(float b: wall[row])
            width = width + b;
        return width;
    }

    static boolean blockFit(int row, int col)
    {
        if(row == 0)
            return true;

        boolean fit = true;
        float currentLenght = 0;
        for(int i = 0; i < col; i++)
            currentLenght = currentLenght + wall[row][i];

        float lowerRowCurLenght = 0;
        for(float b: wall[row - 1])
        {
            lowerRowCurLenght = lowerRowCurLenght + b;
            if((currentLenght == lowerRowCurLenght) & (currentLenght != wallWidth))
                fit = false;
        }

        return fit;
    }
}

マルチスレッドによる解決策：

import java.io.*;
import java.util.*;

class Wall implements Runnable
{
    private float blocks[];
    private int nbOfRows;
    private int nbOfCols;
    private float wallWidth;
    private float wall[][];
    private long nbOfCombinations = 0;
    private int row, col;

    public long getNbOfCombinations() { return this.nbOfCombinations; }

    Wall(float blocks[], int nbOfRows, int nbOfCols, float wallWidth, float wall[][], int row, int col)
    {
        this.blocks = blocks;
        this.nbOfRows = nbOfRows;
        this.nbOfCols = nbOfCols;
        this.wallWidth = wallWidth;
        this.wall = wall;
        this.row = row;
        this.col = col;
    }

    private boolean blockFit(int row, int col)
    {
        if(row == 0)
            return true;

        boolean fit = true;
        float currentLenght = 0;
        for(int i = 0; i < col; i++)
            currentLenght = currentLenght + wall[row][i];

        float lowerRowCurLenght = 0;
        for(float b: wall[row - 1])
        {
            lowerRowCurLenght = lowerRowCurLenght + b;
            if((currentLenght == lowerRowCurLenght) & (currentLenght != wallWidth))
                fit = false;
        }

        return fit;
    }

    private float rowWidth(int row)
    {
        float width = 0;
        for(float b: wall[row])
            width = width + b;
        return width;
    }

    private void addBlock(int row, int col)
    {
        for(float b: blocks)
        {
            wall[row][col] = b;
            if(blockFit(row, col))
            {
                if(rowWidth(row) <= wallWidth)
                {
                    if(rowWidth(row) == wallWidth)
                    {
                        if(row == (nbOfRows - 1))
                            nbOfCombinations++;
                        else
                            addBlock(row + 1, 0);
                    }
                    else //rowWidth < wallWidth
                    {
                        addBlock(row, col + 1);
                    }
                }
            }
            wall[row][col] = 0;
        }
    }


    @Override
    public void run()
    {
        addBlock(row, col);
    }
}

class WallMT
{
    static final float blocks[] = {3.0f, 4.5f};
    static final int nbOfRows = 4;
    static final int nbOfCols = 16;
    static final float wallWidth = 48.0f;
    static final float wall[][] = {
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
                            };

    public static void main(String args[])
    {
        wall[0][0] = blocks[0];
        wall[0][1] = blocks[0];
        Wall myWall1 = new Wall(blocks, nbOfRows, nbOfCols, wallWidth, getWallCopy(wall), 0, 2);
        Thread t1 = new Thread(myWall1);

        wall[0][0] = blocks[0];
        wall[0][1] = blocks[1];
        Wall myWall2 = new Wall(blocks, nbOfRows, nbOfCols, wallWidth, getWallCopy(wall), 0, 2);
        Thread t2 = new Thread(myWall2);

        wall[0][0] = blocks[1];
        wall[0][1] = blocks[0];
        Wall myWall3 = new Wall(blocks, nbOfRows, nbOfCols, wallWidth, getWallCopy(wall), 0, 2);
        Thread t3 = new Thread(myWall3);

        wall[0][0] = blocks[1];
        wall[0][1] = blocks[1];
        Wall myWall4 = new Wall(blocks, nbOfRows, nbOfCols, wallWidth, getWallCopy(wall), 0, 2);
        Thread t4 = new Thread(myWall4);

        long startTime = System.currentTimeMillis();
        t1.start();
        t2.start();
        t3.start();
        t4.start();
        try
        {
            t1.join();  
            t2.join();
            t3.join();  
            t4.join();  
        }
        catch(InterruptedException ie)
        {
            System.out.println("Thread " + t1 + " interrupted.");
        }

        long workingTime = System.currentTimeMillis() - startTime;

        System.out.println("Working time: " + workingTime + "ms");
        System.out.println("noc: " + (myWall1.getNbOfCombinations() + myWall2.getNbOfCombinations() + myWall3.getNbOfCombinations() + myWall4.getNbOfCombinations()));
    }

    static private float[][] getWallCopy(float wall[][])
    {
        float tmpWall[][] = new float[nbOfRows][nbOfCols];

        for(int i = 0; i < nbOfRows; i++)
            for(int j = 0; j < nbOfCols; j++)
                tmpWall[i][j] = wall[i][j];

        return tmpWall;
    }
}