Sorry, no corresponding articles.
--
--
--
no comments

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Related Posts

Next and Prev

Comments + Add Comment

Leave a comment

09
26
2011
0 comments

ACMプログラミングコンテストの過去問を解く2

さてシリーズその2。


今回の問題はコチラ↓
http://acm.timus.ru/problem.aspx?space=1&num=1054


Hanoi Tower

NEERC 2000 Central Subregional

要約

有名なパズル「ハノイの塔」を使った問題です。

3本の杭をそれぞれ1、2、3と表記し、
1・・・移動元
2・・・移動先
3・・・一時的な置き場
と、します。

インプットの最初の数字は移動させるディスクの数N、その後に続くN個の数字は、
小さい順にそれぞれのディスクが置かれている杭を表します。

インプットのディスクの状態がハノイの塔の何手目であるかを
アウトプットするプログラムを作ります。

ただしインプットでない場合は、
「-1」を出力させる必要があります。

考え方

定石通り再帰的呼出しを使います。

一番大きなN番目のディスクに注目すると、
1(移動元にいる)・・・手が進んでいない
2(移動先にいる)・・・2^(n-1)手進んだ状態
3(一時的な置き場にいる)・・・正着でない
となります。

次に大きいN-1番目のディスクは、N番目のディスクの位置によって、
「移動元」、「移動先」、「一時的な置き場」の関係が変わります。

<N = 1の場合>
1・・・移動元
2・・・一時的な置き場
3・・・移動先

<N = 2の場合>
1・・・一時的な置き場
2・・・移動先
3・・・移動元
と、なります。

N-1番目のディスクについてもN番目のディスクと同様に
何手進んだ状態であるか判定することが可能で、
NとN-1の関係は、N-1とN-2についても変わらないので、
再帰処理で全てのディスクから手数の合計が求められます。

プログラム

import java.util.Scanner;

public class HanoiTower {

static int[] p;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int i = 0;

p = new int[n];

for (int j = 0; j < n; j++) {
p[j] = sc.nextInt();
}

hanoi(n, i, 1, 2, 3);

}

static void hanoi(int n, int i, int from, int to, int temp) {

if(n == 0) {
System.out.println(i);
return;
}

if(p[n - 1] == from) {
hanoi(n - 1, i, from, temp, to);
} else if(p[n - 1] == to) {
i += Math.pow(2, n - 1);
hanoi(n - 1, i, temp, to, from);
} else {
System.out.println("-1");
}
}

}

Comments + Add Comment

Leave a comment

Urgench Time

Urgench Temp

Click for Urgench, Uzbekistan Forecast

Tweets

Counter (visitor)

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。