テンプレートには自分で試したことという項目があります.すなわち回答者がまるまる答えを教えてくれるわけではないので,丸投げのような形で質問するのはやめましょう.
あと明らかに出力例と問題文の条件に齟齬があるので,質問の投稿前にプレビューして確認してください.
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通りでした。
テンプレートには自分で試したことという項目があります.すなわち回答者がまるまる答えを教えてくれるわけではないので,丸投げのような形で質問するのはやめましょう.
あと明らかに出力例と問題文の条件に齟齬があるので,質問の投稿前にプレビューして確認してください.
これはJAVAの問題ではなく、アルゴリズムの問題ですね。
アルゴリズムを考える力はプログラマーの大事な基礎力です。
どうか諦めずに挑戦してみてください。
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()
}
}()
上の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();
});
}
}
実行してみると、左右反転の除外が効いていないです。なぜ?
自己レスです。
実行してみると、左右反転の除外が効いていないです。なぜ?
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);
};
}
}