★★Java質問・相談スレッド161★★

1名無しさん@Next2ch:2013/05/16(木) 13:54:28.65 ID:MGNiMjNi

プログラミング言語Javaに関する質問スレです。
JavaScript, Ajaxの質問は、ここでは受け付けていません。
Web製作管理    http://pc11.2ch.net/hp/
Webプログラミング http://pc11.2ch.net/php/
をご利用下さい。

よくある質問
・「コマンドまたはファイル名が違います」
 「'javac' は、内部コマンドまたは外部コマンド、
 操作可能なプログラムまたはバッチ ファイルとして認識されていません。」
 「Exception in thread "main" java.lang.NoClassDefFoundError: 」
 (p)ttp://www.wikiroom.com/java/?path,classpath
・String に == は使うな。equals() を使え。
・「\12288 は不正な文字です。」
文字リテラル以外で全角スペースは使えません。半角スペースに。
・その他の質問→「APIのjavadoc見ろ」

前スレッド
★★Java質問・相談スレッド160★★
http://toro.2ch.net/test/read.cgi/tech/1361516065/

2名無しさん@Next2ch:2013/05/16(木) 15:45:04.03 ID:OGZjNzVk

< `∀´>ニダー

3名無しさん@Next2ch:2015/03/14(土) 04:02:25.83 ID:3cGNbzwN

「Java SE 7は2011年7月に一般公開された。OracleではJavaのサポートについて、
一般公開から3年間もしくは後継バージョンの一般公開から1年間としており、
Java SE 7は一般公開から約3年9カ月でサポートが終了する。5月以降はアップデートが行われない」

Java SE 7のサポート切れ間近、バージョンアップを検討して! - ITmedia エンタープライズ
http://www.itmedia.co.jp/enterprise/articles/1503/11/news079.html
2015年03月11日 12時49分

4名無しさん@Next2ch:2016/02/26(金) 20:31:23.26 ID:KW9IB0mr

次のようなプログラムを作っています
一つ、または二つ以上の升がある
それぞれの升には、すでに水が入っている
これらの升を使って、目的の水の量を測る

例1
升1(容量3l)、実際に入っている水の量は2l
升2(容量1l)、実際に入っている水の量は0l
目的の水の量は1l
⇒升1の水を升2に移すと、
升1: 2l ⇒1l
升2: 0l ⇒1l
完成

例2
升1(容量3l)、実際に入っている水の量は0l
升2(容量3l)、実際に入っている水の量は0l
升3(容量3l)、実際に入っている水の量は0l
目的の水の量は5l
⇒解なし

例3
升1(容量0l)、実際に入っている水の量は0l
目的の水の量は0l
⇒既に解けている


実際のプログラムはこんな感じ
public class Masu {
private int[] masu;
private int[] state;

public Wein(int[] masu, int[] state) {
this.masu = masu; //升1(容量3l),升2(容量0l)→masu[0] = 3; masu[1] = 0;
this.state = state; //升1,実際の水1l→state[0] = 1;
}

public boolean solved(int purpose, int[] result){
for(int i=0; i<masu.length; i++)
if(result[i]==purpose)
return true;
return false;
}

//To Do
public void solveHelper(int purpose, int from, int to, int[] result){//バックトラック法
if(solved(purpose, from, to, result))
return;

//移さない
result[from] = state[from];
result[to] = state[to];
solveHelper(from,to+1,result);
solveHelper(from+1,to,result);

//移す
if(state[from]>masu[to]-state[to]){
int d = state[from]-(masu[to]-state[to]);
result[from] = d;
result[to] = masu[to];
}
else{
result[from] = 0;
result[to] = state[to] + state[from]
}
solveHelper(from,to+1,result[][]);
solveHelper(from+1,to,result[][]);
return;
}

//To Do
public int[] solve(int purpose){//purpose=目的の水の量
int[] result = new int[masu.length];
//result[1] = 問題を解いた後に升2に入っている水の量
solveHelper(purpose, result);
return result;
}
}

水を移すか移さないかで再帰をすれば、バックトラック法を作れると思ったのですが、バックトラック法だと、同じ作業を繰り返さないのでダメな気がしてきました…

例えば、升1から升2に移して升2から升3に移したあとに、また升1から升2に移す作業を、バックトラック法では試してくれないですよね?そうすると、すべてのパターンを試すことができないのでは…

そもそもバックトラック法を使ってプログラムしようとしてるのが間違ってるのかも…

5名無しさん@Next2ch:2016/03/16(水) 20:59:54.83 ID:svp6oYtA

漸近的計算時間をO 記法で表す方法はわかりますが、計算量や必要な領域もO記法を使って表現しているのを見ました。

例えば、
https://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88
の、「ソートアルゴリズムの一覧」では、メモリ使用量(必要な領域)をO記法で表現していて、
https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88
では、最悪空間計算量がО(n) total, O(1) auxiliary
となっています

1、計算量とはなにを示しているのですか?
2、計算量や必要な領域をO記法で表すためにはどのような計算をすればいいのですか?

6名無しさん@Next2ch:2016/03/20(日) 16:27:41.87 ID:nAadkoiM

O はランダウの記号
「問題が無限に大きいときの値が」「定数倍の違いを除いてだいたいこんなもの」という意味(厳密な定義はググれ)
無限にという言葉が嫌なら n = 10^100000000000000 くらいを仮定すればいい

例えば 10n^2 + 4n + 2 という式があるとき n = 10^100000000000000 を代入すると
4n+2 は 10n^2 より 100000000000000 桁も小さいゴミなので無視できる
10n^2 の 10 も n = 10^100000000000000 と比べれば些細な違いなので無視する

だから 10n^2 + 4n + 2 = O(n^2)

1. 空間計算量はメモリ使用量だと思えばいい
バイト数でもビット数でもGBで数えてもなんでも構わない
なぜなら何を単位として数えても定数倍変わるだけだから
(ビット単位とGB単位ならたった80億倍しかかわらない n = 10^100000000000000 と比べれば微々たる違い)

2. 計算量を考えるときはまず「問題の大きさ」を定義する。一次元配列なら要素数 n を「大きさ」にすればいい
 二次元配列についての問題なら幅wと高さhの二つを「大きさ」としてもいいし
 全要素数 n = w*h を「大きさ」としてもいい。考えやすいように何かを自分勝手に採用すればいい

 次に空間計算量を求める場合「何が一番メモリを食うか」を考える
 ソートなら仮に要素数 n に対して 100^(1000n) 行のプログラムが必要ならば
 プログラム自体を格納するためのメモリのほうがワーキング領域よりたぶん大きい
 でも普通そんなことはないのでプログラムの大きさは無視し「テンポラリに確保する要素数」を採用する
 もちろん「テンポラリに確保するバイト数」でもいい。定数倍違うだけ

 あとはゴリゴリ文章題を解く
 「要素数 n の配列をこの方法でソートするとき、テンポラリに確保する要素数はいくつになりますか?」
 答えが 1000000 log(30n + 2) とかになったならこれを O(logn) と答えればよい


レスを書き込む

関連スレッド

スレッドタイトルレス
VB.NET質問スレ(Part40)1
Androidプログラミング質問スレ Part323
スレ立てるまでもない質問はここで 126匹目2
もの凄い勢いで誰かが質問に答えるスレ@理系板15
【エスパー】超初心者の質問に答えるスレ【マジレス】12
ソフトウェア総合質問スレ5
Windows総合質問スレ8
どんな質問にもマジレスするスレッド25
Linux総合質問スレ6