質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.49%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

1回答

2742閲覧

行列の計算回数を求めるアルゴリズムなんですがわからない部分を解説していただきたいです

gyro16

総合スコア89

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2017/04/23 02:04

編集2017/04/23 04:15

###前提・実現したいこと
連鎖的に行列の積を求める
n 個の
行列の連鎖が与えられた時スカラー乗算が最小になる計算順序の最小回数を求めるもののアルゴリズムなんですが、
matR 行配列、matC 列配列

for(int i = fr; i < to; i++){
int r = Mat(fr, i) + Mat(i+1, to) + (matR[fr] * matC[i] * matC[to]);

ここのところの解説が欲しいです。

入力
6
30 35
35 15
15 5
5 10
10 20
20 25

行列の積の計算をi番目で区切ったコストとそれ以降の計算コストということは分かるんですが、
(matR[fr] * matC[i] * matC[to])

この辺が分かりません。

###発生している問題・エラーメッセージ

エラーメッセージ

###該当のソースコード

java

1import java.util.*; 2 3public class Algo36{ 4 5 static int[][] multi; 6 static int[] matR; 7 static int[] matC; 8 9 public static void main(String[] args){ 10 11 Scanner scan = new Scanner(System.in); 12 13 int n = scan.nextInt(); 14 multi = new int[n][n]; 15 matR = new int[n]; 16 matC = new int[n]; 17 18 for(int i = 0; i < n; i++){ 19 matR[i] = scan.nextInt(); 20 matC[i] = scan.nextInt(); 21 } 22 23 System.out.println(Mat(0, n-1)); 24 25 scan.close(); 26 System.exit(0); 27 } 28 29 private static int Mat(int fr, int to){ 30 if(fr == to) 31 return 0; 32 if(multi[fr][to] == 0){ 33 int min = Integer.MAX_VALUE; 34 for(int i = fr; i < to; i++){ 35 int r = Mat(fr, i) + Mat(i+1, to) + (matR[fr] * matC[i] * matC[to]); 36 if(r < min) 37 min = r; 38 } 39 multi[fr][to] = min; 40 } 41 return multi[fr][to]; 42 } 43}

###試したこと
課題に対してアプローチしたことを記載してください

###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2017/04/23 02:16

問題が何のことかさっぱりわかりません。大元の問題を説明してください。
swordone

2017/04/23 03:25

すいません。まだ意味がわからないです。「行列の連鎖」?「スカラー乗算が最小になる計算順序の最小回数」?言葉の意味が分かりません。
guest

回答1

0

自己解決

Mat(fr,i) + Mat(i+1, to) + matR[fr] * matC[i] * matC[to];

は、行列の積をi番目で区切って、区切り前の計算コストMat(fr,i)と区切り後の計算コストMat(i+1,to)で、

matR[fr] * mat[i] * matC[to]は、区切りった者同士(2つ)の積の計算コスト
です。

投稿2017/04/23 05:46

gyro16

総合スコア89

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.49%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問