前提・実現したいこと
Excelで以下の図1のようにセルに一つずつ0~9の整数を入れる作業をしていたところ、
作業で疲れたので少し休もうと近くあった高校の教科書「数学A」を手に取って読んでいました。
(「これマジで懐かしいなぁ・・・」と思いながら)
そこで場合の数のところの最短経路問題のページを見た瞬間、下の図に似ていることに
気づきました。
最短経路問題のように左上から右下まで移動したとき(図2のように)
セル上にある数字を足していきゴールに到達したところまでの合計値を求めることが
できます。今回実現したことはこの合計値の最小値を求めることです。
ただし、経路はすべてn×nの正方形です。
発生している問題・エラーメッセージ
実際、自分なりにアルゴリズムを考えてプログラミングを構築しましたが、あまりにも実行時間が
長すぎるため、もっと高速化したい。(そもそも考え方自体を変える必要があるかもしれない。)
該当のソースコード
(使用言語: Java8)
package sum; import java.util.*; import java.math.BigInteger; import static oracle.jrockit.jfr.events.Bits.intValue; public class Sum { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String line = sc.nextLine(); /*入力*/ String []data = new String[line.length() - 1]; int [][]number = new int[line.length()][line.length()]; int n = line.length(); int sum; for(int i = 0; i < line.length() - 1;i++){ data[i] = sc.nextLine(); /*ここまでが入力*/ } for(int i = 0; i < line.length(); i++){ number[0][i] = Integer.parseInt(line.substring(i,i+1)); } for(int i = 1; i < line.length(); i++){ for(int j = 0; j < line.length(); j++){ number[i][j] = Integer.parseInt(data[i - 1].substring(j,j+1)); } } BigInteger start = ruijou(n - 1).add(new BigInteger("-1")); BigInteger last = (start.add(new BigInteger("1"))).multiply(start); BigInteger i = start; String line2; int count; int count2; int x; int y; int min = 154781; while(i.compareTo(last) <= 0){ sum = number[0][0]; x = 0; y = 0; line2 = binary(i,n - 1); count = count_number(line2,0); count2 = count_number(line2,1); if(count == n - 1 && count2 == n - 1){ for(int j = 0; j < line2.length(); j++){ if(Integer.parseInt(line2.substring(j,j + 1)) == 0){ x++; sum += number[y][x]; } else if(Integer.parseInt(line2.substring(j,j + 1)) == 1){ y++; sum += number[y][x]; } } if(min > sum){ min = sum; } } i = i.add(new BigInteger("1")); } System.out.println(min); } public static BigInteger ruijou(int n) { BigInteger sum = BigInteger.ONE; for (int i = 1; i <= n; i++) { sum = sum.multiply(new BigInteger("2")); } return sum; } public static String binary(BigInteger n,int length) { BigInteger []binary = new BigInteger[length * 2]; int []binary2 = new int [length * 2]; for(int i = 0; i < length * 2; i++){ binary[i] = new BigInteger("0"); } int digits = 0; while(n.compareTo(new BigInteger("0")) > 0){ binary[digits] = n.remainder(new BigInteger("2")); n = n.divide(new BigInteger("2")); digits++; } for(int i = length * 2 - 1; i >= 0; i--){ binary2[i] = intValue(binary[i]); } char []buf = new char[length * 2]; for(int i = 0; i < length * 2; i++){ buf[i] = (char)('0' + binary2[length * 2 - 1 - i]); } String str = String.valueOf(buf); return str; } public static int count_number(String str,int n) /*nがいくつあるか数える関数*/ { int count = 0; for(int i = 0; i < str.length(); i++){ if(Integer.parseInt(str.substring(i,i+1)) == n){ count++; } } return count; }
試したこと
質問のところでは 8×8の正方形の図を使用しましたが、試したことを簡単に説明するために
3×3(図3)で説明したと思います。
まず、標準入力でint型の2次配列に0~9の数字を格納します。(これは自力で,できました。)
ここから自分が考えた最小合計値を求めるアルゴリズムを説明します。
まず、正方形の大きさが3×3なので右に2 下に2 移動することがわかります。
ここで2進数を使うことを思いつきました。
桁の数字が0の時 右、1の時 下に行くときは1と考えて、経路の通り方が右、右、下、下 の
場合は0011となります。(このように先頭が0の場合もある.)
3×3の場合,右と下 合計4回移動するので二進数の0と1の個数はそれぞれ2個ずつ
計4個ということになります。
つまり、最小値0011 最大値1100のfor文を作り、その中で演算を施せばいいと思いました。
詳しく述べますと、
1.最小値から1ずつ増やしていき0と1がそれぞれ2個ずつあるかチェックする。
(条件にあった場合だけ2に進む。)
2.桁の数が0の時は右、1の時は下に行き、その場所にある整数を足します。
3.あらかじめ、用意した最小値よりも小さい合計値が出た場合は最小値を更新します。
4.右、右、下、下の時は図4のようになり、合計値は
1+7+9+0+5=22になります。
これを一般化するとn×nのとき、0と1がそれぞれ(n - 1)個ある二進数の
最小値0000...1111と最大値1111....0000のfor文を使います。
しかし、これだとnの数が大きくなった時、処理に時間がかかります。
そもそも、二進数のところの最小値と最大値のところは、すべて10進数を2進数に
変える関数を使って(自分で作ったものですが)計算しています。
(n = 10の時は0と1がそれぞれ9個ずつなので最大値は10進数で約2^18と
大きな数字になり、for文のループする回数が多くなる。)
nが大きいとき条件に合わない2進数が多すぎて処理に時間がかかっているのです。
最小値と最大値はそれぞれ10進数で表すことができたので、
(ソースコードではそれぞれstart,lastにしてあります。)
これを解決するには
1.0と1がそれぞれ(n-1)個ある2進数のみ抽出できるようにする。
(これができると処理時間が短くて済む。具体的な数だと(2n-2)!/{(n - 1)!}{(n - 1)!})
2.そもそもこの考え方以外にもっと効率的な考え方がある
が考えられます。どなたがご教授お願い致します
補足情報(FW/ツールのバージョンなど)
NetBeans IDE 8.1 Java言語でプログラミングを構築しています。
回答4件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。