15
3月, 2022

16進数の文字列の復元

実装しようとした時になんだっけ～ってすぐに思い出せなかったので記事にしておきます。

PHPなら１行。

echo hex2bin('746573745F6869726162756E');

Javaなら9行くらい？

import javax.xml.bind.DatatypeConverter;

public class Main {
    public static void main(String[] args) {
        String decText = new String(
                DatatypeConverter.parseHexBinary("746573745F6869726162756E"));
        System.out.println(decText);
    }
}

出力はどちらも

test_hirabun

11
3月, 2022

約数全列挙

約数を全列挙する方法について、２通り記載しておきます。

①　単純なアルゴリズム

割って０になることを１～Nまで順番に試していきます。

＜ソース＞

import java.util.ArrayList;
import java.util.List;

/**
 * 約数全列挙
 */
public class yakusu {

    public static void main(String[] args) {

       final int N = 1989;

       List<Integer> yakusu = new ArrayList<Integer>();

       for (int t = 1; t <= N; t++) {
           if (N % t == 0) {
               yakusu.add(t);
           }
       }
       System.out.println(yakusu);
    }
}

＜実行結果＞

[1, 3, 9, 13, 17, 39, 51, 117, 153, 221, 663, 1989]

②約数の性質を利用して

上記の場合　1989を3で割り切れることが分かれば、1989/3 = 663 と663でも割り切れます。そこで

＜ソース＞

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 約数全列挙
 */
public class yakusu {

    public static void main(String[] args) {

       final int N = 1989;

       List<Integer> yakusu = new ArrayList<Integer>();

       for (int t = 1; t * t <= N; t++) {
           if (N % t == 0) {
               yakusu.add(t);
               if (t * t != N) {
                   yakusu.add(N / t);
               }
           }
       }
       Collections.sort(yakusu);
       System.out.println(yakusu);
    }
}

こんな風にも書けます。

27
2月, 2022

n!の全列挙（順列）

Javaだと全列挙するメソッドがないらしい。

仕方ないので自作する機会が多いのでn!全列挙を作成しました。

件数が少ない時の最適解など全列挙して全部求めることもあるかな～って思います。

<ソース＞

public class Main {

    private static void buildPerm(int[] seed, int[] perm, boolean[] used, int index) {
        if (index == seed.length) {
            System.out.println(java.util.Arrays.toString(perm));
            return;
        }

        for (int i = 0; i < seed.length; ++i) {
            if (used[i]) continue;
            perm[index] = seed[i];
            used[i] = true;
            buildPerm(seed, perm, used, index + 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] seed = new int[]{1, 2, 3, 4};
        int[] perm = new int[seed.length];
        boolean[] used = new boolean[seed.length];
        buildPerm(seed, perm, used, 0);

    }
}

＜実行結果＞

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]
27
2月, 2022

bit全探索

ビット全探索とは、二進数とビットを用いて、ある集合の部分集合を全列挙（全探索）する便利なアルゴリズムです。

＜ソース＞

public class Main {

    // bit全探索
    public static void main(String[] args) {
        String[] 要素 = {"A","B","C", "D"};
        int 要素数 = 要素.length;
        StringBuffer sb = new StringBuffer();

        for (int i=0; i<(Math.pow(2,要素数)); i++) {
            sb.setLength(0);
            for (int j=0; j<要素数; j++) {
                int bit = 1&i>>j;
                System.out.print(bit);

                if (bit == 1) {
                    sb.append(要素[j]);
                }
            }
            System.out.print(" -> ");
            System.out.println(sb.toString());
        }
    }
}

＜実行結果＞

0000 -> 
1000 -> A
0100 -> B
1100 -> AB
0010 -> C
1010 -> AC
0110 -> BC
1110 -> ABC
0001 -> D
1001 -> AD
0101 -> BD
1101 -> ABD
0011 -> CD
1011 -> ACD
0111 -> BCD
1111 -> ABCD