Go to Qiita Advent Calendar 2024 Top
LoginSignup
mmhsivgnhmf
@mmhsivgnhmf (aaa)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

java 教えてください

Q&A

Closed

Java

javaの問題をしていますが全然わかりません

1～7の2枚ずつのカード14枚を使って以下の条件になるように、隙間なく並べられるすべてのパターンを調べるプログラムを作成してください。 なお、左右反転しただけのパターンは除外する。

条件
1と1のカードの間には1枚のカードが入る。
2と2のカードの間には2枚のカードが入る。
3と3のカードの間には2枚のカードが入る。
4と4のカードの間には2枚のカードが入る。
5と5のカードの間には2枚のカードが入る。
6と6のカードの間には2枚のカードが入る。
7と7のカードの間には7枚のカードが入る。

実行結果

①⑦①②⑤⑥②③④⑦⑤③⑥④
①⑦①②⑥④②⑤③⑦④⑥③⑤
①⑥①⑦②④⑤②⑥③④⑦⑤③
①⑤①⑥⑦②④⑤②③⑥④⑦③
①④①⑤⑥⑦④②③⑤②⑥③⑦
①④①⑥⑦③④⑤②③⑥②⑦⑤
①⑥①③⑤⑦④③⑥②⑤④②⑦
①⑤①⑦③④⑥⑤③②④⑦②⑥
①⑤①⑥③⑦④⑤③②⑥④②⑦
①⑤①④⑥⑦③⑤④②③⑥②⑦
⑤①⑦①⑥②⑤④②③⑦⑥④③
④①⑦①⑥④②⑤③②⑦⑥③⑤
④①⑥①⑦④③⑤②⑥③②⑦⑤
⑦①③①⑥④③⑤⑦②④⑥②⑤
⑦①④①⑥③⑤④⑦③②⑥⑤②
⑥①⑤①⑦③④⑥⑤③②④⑦②
④⑥①⑦①④⑤②⑥③②⑦⑤③
⑦③①⑥①③④⑤⑦②⑥④②⑤
④⑥①⑦①④③⑤⑥②③⑦②⑤
⑤⑥①⑦①③⑤④⑥③②⑦④②
⑦④①⑤①⑥④③⑦⑤②③⑥②
⑤⑦①④①⑥⑤③④⑦②③⑥②
③⑥⑦①③①④⑤⑥②⑦④②⑤
⑤⑦④①⑥①⑤④③⑦②⑥③②
②⑥⑦②①⑤①④⑥③⑦⑤④③
④⑤⑥⑦①④①⑤③⑥②⑦③②
全部で26通りでした。

0

3Answer

Verclene
@Verclene

テンプレートには自分で試したことという項目があります.すなわち回答者がまるまる答えを教えてくれるわけではないので,丸投げのような形で質問するのはやめましょう.

あと明らかに出力例と問題文の条件に齟齬があるので,質問の投稿前にプレビューして確認してください.

2Like
iiokazuya
@iiokazuya

これはJAVAの問題ではなく、アルゴリズムの問題ですね。
アルゴリズムを考える力はプログラマーの大事な基礎力です。
どうか諦めずに挑戦してみてください。

1Like
nak435
@nak435

Javaというより、アルゴリズムの問題ですね。

解き方はいくつもあると思いますが、深さ優先探索で解いてみました。
言語はSwiftです。Javaコードは後ほどアップします。

import Foundation

let main: () = {
    let K = [
        [1, 0, 1],
        [2, 0, 0, 2],
        [3, 0, 0, 0, 3],
        [4, 0, 0, 0, 0, 4],
        [5, 0, 0, 0, 0, 0, 5],
        [6, 0, 0, 0, 0, 0, 0, 6],
        [7, 0, 0, 0, 0, 0, 0, 0, 7],
    ]
    func isPlaceable(_ n: Int, _ p: Int, _ g: inout [Int]) -> Bool {
        let k = K[n]
        if p + k.count > g.count { return false }
        for m in 0 ..< k.count {
            if k[m] != 0 {
                if g[p + m] != 0 { return false }
                g[p + m] = k[m]
            }
        }
        return true
    }
    var ans = Set<[Int]>()
    func dfs(_ n: Int, _ g: [Int]) {
        if n == 7 {
            if !ans.contains(g.reversed()) {
                ans.insert(g)
            }
            return
        }
        for p in 0 ..< g.count {
            var g = g
            if !isPlaceable(n, p, &g) { continue }
            dfs(n + 1, g)
        }
    }
    dfs(0, [Int](repeating: 0, count: 14))
    ans.sorted{ $0.lexicographicallyPrecedes($1) }.forEach {
        $0.forEach { print($0, terminator: " ") }
        print()
    }
}()

0Like

Comments

  1. @nak435

    上のSwiftコードをChatGPTにJavaに変換してもらったコードです。

    import java.util.HashSet;
import java.util.Set;

public class Main {
    static int[][] K = {
            {1, 0, 1},
            {2, 0, 0, 2},
            {3, 0, 0, 0, 3},
            {4, 0, 0, 0, 0, 4},
            {5, 0, 0, 0, 0, 0, 5},
            {6, 0, 0, 0, 0, 0, 0, 6},
            {7, 0, 0, 0, 0, 0, 0, 0, 7}
    };

    static boolean isPlaceable(int n, int p, int[] g) {
        int[] k = K[n];
        if (p + k.length > g.length) return false;
        for (int m = 0; m < k.length; m++) {
            if (k[m] != 0) {
                if (g[p + m] != 0) return false;
                g[p + m] = k[m];
            }
        }
        return true;
    }

    static Set<int[]> ans = new HashSet<>();

    static void dfs(int n, int[] g) {
        if (n == 7) {
            if (!ans.contains(reverse(g))) {
                ans.add(g);
            }
            return;
        }
        for (int p = 0; p < g.length; p++) {
            int[] clonedG = g.clone();
            if (!isPlaceable(n, p, clonedG)) continue;
            dfs(n + 1, clonedG);
        }
    }

    static int[] reverse(int[] array) {
        int[] reversedArray = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            reversedArray[i] = array[array.length - 1 - i];
        }
        return reversedArray;
    }

    public static void main(String[] args) {
        dfs(0, new int[14]);
        ans.stream().sorted((a, b) -> {
            for (int i = 0; i < a.length; i++) {
                if (a[i] != b[i]) return a[i] - b[i];
            }
            return 0;
        }).forEach(g -> {
            for (int i : g) {
                System.out.print(i + " ");
            }
            System.out.println();
        });
    }
}

    実行してみると、左右反転の除外が効いていないです。なぜ？

  2. @nak435

    自己レスです。

    実行してみると、左右反転の除外が効いていないです。なぜ？

    if (!ans.contains(reverse(g))) {
    ↑この場合、containsメソッドを使うなら、hashCodeメソッドとequalsメソッドを実装する必要があるようです。
    そこで、int[]やめてStringで実装しました。

    import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    static String[] K = {
            "101",
            "2002",
            "30003",
            "400004",
            "5000005",
            "60000006",
            "700000007"
    };

    static boolean isPlaceable(int n, int p, String g) {
        String k = K[n];
        if (p + k.length() > g.length()) return false;
        for (int m = 0; m < k.length(); m++) {
            if (k.charAt(m) != '0') {
                if (g.charAt(p + m) != '0') return false;
            }
        }
        return true;
    }

    static String place(int n, int p, String g) {
        String k = K[n];
        if (p + k.length() > g.length()) return g;
        for (int m = 0; m < k.length(); m++) {
            if (k.charAt(m) != '0') {
                if (g.charAt(p + m) != '0') return g;
            }
        }
        String s = "";
        for (int m = 0; m < g.length(); m++) {
            if (p <= m && m < p + k.length()) {
                if (k.charAt(m - p) != '0') {
                    s += k.charAt(m - p);
                } else {
                    s += g.charAt(m);
                }
            } else {
                s += g.charAt(m);
            }
        }
        return s;
    }

    static String reverse(String aString) {
        if (aString == null) return aString;
		String reverseString = "";
		for (int i = aString.length() - 1; i >= 0; i--) {
			reverseString = reverseString + aString.charAt(i);
		}
		return reverseString;
    }

    static Set<String> ans = new HashSet<>();

    static void dfs(int n, String g) {
        if (n == 7) {
            if (!ans.contains(reverse(g))) {
                ans.add(g);
            }
            return;
        }
        for (int p = 0; p < g.length(); p++) {
            if (!isPlaceable(n, p, g)) continue;
            String nextG = place(n, p, g);
            dfs(n + 1, nextG);
        }
    }

    public static void main(String[] args) {
        dfs(0, "00000000000000");
        String array[] = ans.toArray(String[]::new);
        Arrays.sort(array);
        for (String s : array) {
            System.out.println(s);
        };
    }
}

Your answer might help someone💌

LoginSign Up