ゆっちのBlog

Java

NetBeans 8 開発版で JDK 8 EA を使ってみた

Java NetBeans

まだまだ遠いけど、手が届きそうなところまで近づいてきた JDK 8 を試してみます。

統合開発環境を使って動かせるようにも成りつつあるようです。

IntelliJ12でJDK8のlambda

Eclipse で Java8！

そこで我らがヒーロー NetBeans はどういった状況なのか？　さっそく試してみました。

次期リリース予定の開発版をダウンロードしてインストールしてみました。

JDK 8 は Java™ Platform, Standard Edition 8 Early Access with Lambda Support と

JDK™ 8 Early Access Releases があります。

後者は前者の成果物を一部マージしたものとなっているようです。（たぶん・・・）

現在は Build b79 となっています。

Java™ Platform, Standard Edition 8 Early Access with Lambda Support を使って NetBeans をインストールしたのですが、

ちょっと問題が発生したので JDK™ 8 Early Access Releases に切り替えました。

JDK の変更は設定ファイルをちょこっと書き換えるだけで簡単にできるので気にしなくていいですね。

それでは The Java Tutorials を試してみましょう。

jp\yucchi\Member.java

package jp.yucchi;

import java.util.Date;
import java.util.Calendar;
import java.util.GregorianCalendar;

public class Member {

    public enum Sex {

        MALE, FEMALE
    }
    String name;
    Calendar birthday;
    Sex gender;
    String emailAddress;

    Member(String nameArg, Calendar birthdayArg,
            Sex genderArg, String emailArg) {
        name = nameArg;
        birthday = birthdayArg;
        gender = genderArg;
        emailAddress = emailArg;
    }

    public int getAge() {
        Calendar today = GregorianCalendar.getInstance();
        int age = today.get(Calendar.YEAR) - birthday.get(Calendar.YEAR);
        if ((birthday.get(Calendar.MONTH) > today.get(Calendar.MONTH))
                || (birthday.get(Calendar.MONTH) == today.get(Calendar.MONTH)
                && birthday.get(Calendar.DAY_OF_MONTH)
                > today.get(Calendar.DAY_OF_MONTH))) {
            age--;
        }
        return age;
    }

    public void printMember() {
        System.out.println(name + ", " + this.getAge());
    }

    public Sex getGender() {
        return gender;
    }

    public String getName() {
        return name;
    }

    public String getEmailAddress() {
        return emailAddress;
    }
}

package jp.yucchi;

import java.util.Date;

import java.util.Calendar;

import java.util.GregorianCalendar;

public class Member {

public enum Sex {

MALE, FEMALE

}

String name;

Calendar birthday;

Sex gender;

String emailAddress;

Member(String nameArg, Calendar birthdayArg,

Sex genderArg, String emailArg) {

name = nameArg;

birthday = birthdayArg;

gender = genderArg;

emailAddress = emailArg;

}

public int getAge() {

Calendar today = GregorianCalendar.getInstance();

int age = today.get(Calendar.YEAR) - birthday.get(Calendar.YEAR);

if ((birthday.get(Calendar.MONTH) > today.get(Calendar.MONTH))

|| (birthday.get(Calendar.MONTH) == today.get(Calendar.MONTH)

&& birthday.get(Calendar.DAY_OF_MONTH)

> today.get(Calendar.DAY_OF_MONTH))) {

age--;

}

return age;

}

public void printMember() {

System.out.println(name + ", " + this.getAge());

}

public Sex getGender() {

return gender;

}

public String getName() {

return name;

}

public String getEmailAddress() {

return emailAddress;

}

jp\yucchi\RosterTest.java

package jp.yucchi;

import java.util.ArrayList;
import java.util.GregorianCalendar;
import java.util.List;
import java.util.function.Block;

import java.util.function.Predicate;

public class RosterTest {

    interface CheckMember {

        boolean test(Member p);
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String... args) {
        List<Member> roster = new ArrayList<>();
        roster.add(
                new Member(
                "Fred",
                new GregorianCalendar(1980, 6, 20),
                Member.Sex.MALE,
                "fred@example.com"));
        roster.add(
                new Member(
                "Jane",
                new GregorianCalendar(1990, 7, 15),
                Member.Sex.FEMALE, "jane@example.com"));
        roster.add(
                new Member(
                "George",
                new GregorianCalendar(1991, 8, 13),
                Member.Sex.MALE, "george@example.com"));
        roster.add(
                new Member(
                "Bob",
                new GregorianCalendar(2000, 9, 12),
                Member.Sex.MALE, "bob@example.com"));

        for (Member p : roster) {
            p.printMember();
        }

        System.out.println("\n２０歳以上のメンバー:");
        printMembersOlderThan(roster, 20);
        System.out.println();

        System.out.println("１４歳以上、３０歳未満:");
        printMembersWithinAgeRange(roster, 14, 30);
        System.out.println();

        System.out.println("Members who are eligible for Selective Service:");

        class CheckMemberEligibleForSelectiveService implements CheckMember {

            public boolean test(Member p) {
                return p.getGender() == Member.Sex.MALE
                        && p.getAge() >= 18
                        && p.getAge() <= 25;
            }
        }

        printMembers(
                roster, new CheckMemberEligibleForSelectiveService());

        System.out.println();

        System.out.println("Members who are eligible for Selective Service "
                + "(anonymous class):");

        printMembers(
                roster,
                new CheckMember() {
            public boolean test(Member p) {
                return p.getGender() == Member.Sex.MALE
                        && p.getAge() >= 18
                        && p.getAge() <= 25;
            }
        });

        System.out.println();

        System.out.println("Members who are eligible for Selective Service "
                + "(lambda expression):");

        printMembers(
                roster, (Member p)  -> p.getGender() == Member.Sex.MALE
                && p.getAge() >= 18
                && p.getAge() <= 25);

        System.out.println();

        System.out.println("Members who are eligible for Selective Service "
                + "(with Predicate parameter):");

        printMembersWithPredicate(
                roster, p  -> p.getGender() == Member.Sex.MALE
                && p.getAge() >= 18
                && p.getAge() <= 25);

        System.out.println();

        System.out.println("Members who are eligible for Selective Service "
                + "(with Predicate and Block parameters):");

        processMembers(
                roster,
                p  -> p.getGender() == Member.Sex.MALE
                && p.getAge() >= 18
                && p.getAge() <= 25,
                p  -> p.printMember());

        System.out.println();

        System.out.println("Members who are eligible for Selective Service "
                + "(with Predicate, Block, and Mapper parameters):");

//        processMembersWithMapper(
//            roster,
//            p -> p.getGender() == Member.Sex.MALE
//                && p.getAge() >= 18
//                && p.getAge() <= 25,
//            p -> p.getEmailAddress(),
//            email -> System.out.println(email)
//        );



    }

    private static void printMembersOlderThan(List<Member> roster, int age) {
        for (Member p : roster) {
            if (p.getAge() >= age) {
                p.printMember();
            }
        }

    }

    private static void printMembersWithinAgeRange(List<Member> roster, int low, int high) {
        for (Member p : roster) {
            if (low <= p.getAge() && p.getAge() < high) {
                p.printMember();
            }
        }

    }

    public static void printMembers(
            List<Member> roster, CheckMember tester) {
        for (Member p : roster) {
            if (tester.test(p)) {
                p.printMember();
            }
        }
    }

    public static void printMembersWithPredicate(
            List<Member> roster, Predicate<Member> tester) {
        for (Member p : roster) {
            if (tester.test(p)) {
                p.printMember();
            } else {
            }
        }
    }

    public static void processMembers(
            List<Member> roster,
            Predicate<Member> tester,
            Block<Member> block) {
        for (Member p : roster) {
            if (tester.test(p)) {
//                block.apply(p);
                block.accept(p);
            }
        }
    }
//     public static void processMembersWithMapper(
//        List<Member> roster,
//        Predicate<Member> tester,
//        Mapper<String, Member> mapper,
//        Block<String> block) {
//        for (Member p : roster) {
//            if (tester.test(p)) {
//                String data = mapper.map(p);
//                block.accept(data);
//            }
//        }
//    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

package jp.yucchi;

import java.util.ArrayList;

import java.util.GregorianCalendar;

import java.util.List;

import java.util.function.Block;

import java.util.function.Predicate;

public class RosterTest {

interface CheckMember {

boolean test(Member p);

}

/**

* @param args the command line arguments

public static void main(String... args) {

List<Member> roster = new ArrayList<>();

roster.add(

new Member(

"Fred",

new GregorianCalendar(1980, 6, 20),

Member.Sex.MALE,

"fred@example.com"));

roster.add(

new Member(

"Jane",

new GregorianCalendar(1990, 7, 15),

Member.Sex.FEMALE, "jane@example.com"));

roster.add(

new Member(

"George",

new GregorianCalendar(1991, 8, 13),

Member.Sex.MALE, "george@example.com"));

roster.add(

new Member(

"Bob",

new GregorianCalendar(2000, 9, 12),

Member.Sex.MALE, "bob@example.com"));

for (Member p : roster) {

p.printMember();

}

System.out.println("\n２０歳以上のメンバー:");

printMembersOlderThan(roster, 20);

System.out.println();

System.out.println("１４歳以上、３０歳未満:");

printMembersWithinAgeRange(roster, 14, 30);

System.out.println();

System.out.println("Members who are eligible for Selective Service:");

class CheckMemberEligibleForSelectiveService implements CheckMember {

public boolean test(Member p) {

return p.getGender() == Member.Sex.MALE

&& p.getAge() >= 18

&& p.getAge() <= 25;

}

printMembers(

roster, new CheckMemberEligibleForSelectiveService());

System.out.println();

System.out.println("Members who are eligible for Selective Service "

+ "(anonymous class):");

printMembers(

roster,

new CheckMember() {

public boolean test(Member p) {

return p.getGender() == Member.Sex.MALE

&& p.getAge() >= 18

&& p.getAge() <= 25;

}

});

System.out.println();

System.out.println("Members who are eligible for Selective Service "

+ "(lambda expression):");

printMembers(

roster, (Member p) -> p.getGender() == Member.Sex.MALE

&& p.getAge() >= 18

&& p.getAge() <= 25);

System.out.println();

System.out.println("Members who are eligible for Selective Service "

+ "(with Predicate parameter):");

printMembersWithPredicate(

roster, p -> p.getGender() == Member.Sex.MALE

&& p.getAge() >= 18

&& p.getAge() <= 25);

System.out.println();

System.out.println("Members who are eligible for Selective Service "

+ "(with Predicate and Block parameters):");

processMembers(

roster,

p -> p.getGender() == Member.Sex.MALE

&& p.getAge() >= 18

&& p.getAge() <= 25,

p -> p.printMember());

System.out.println();

System.out.println("Members who are eligible for Selective Service "

+ "(with Predicate, Block, and Mapper parameters):");

// processMembersWithMapper(

// roster,

// p -> p.getGender() == Member.Sex.MALE

// && p.getAge() >= 18

// && p.getAge() <= 25,

// p -> p.getEmailAddress(),

// email -> System.out.println(email)

// );

}

private static void printMembersOlderThan(List<Member> roster, int age) {

for (Member p : roster) {

if (p.getAge() >= age) {

p.printMember();

}

private static void printMembersWithinAgeRange(List<Member> roster, int low, int high) {

for (Member p : roster) {

if (low <= p.getAge() && p.getAge() < high) {

p.printMember();

}

public static void printMembers(

List<Member> roster, CheckMember tester) {

for (Member p : roster) {

if (tester.test(p)) {

p.printMember();

}

public static void printMembersWithPredicate(

List<Member> roster, Predicate<Member> tester) {

for (Member p : roster) {

if (tester.test(p)) {

p.printMember();

} else {

}

public static void processMembers(

List<Member> roster,

Predicate<Member> tester,

Block<Member> block) {

for (Member p : roster) {

if (tester.test(p)) {

// block.apply(p);

block.accept(p);

}

// public static void processMembersWithMapper(

// List<Member> roster,

// Predicate<Member> tester,

// Mapper<String, Member> mapper,

// Block<String> block) {

// for (Member p : roster) {

// if (tester.test(p)) {

// String data = mapper.map(p);

// block.accept(data);

// }

}

コメントアウトしてあるところがあるのですが Mapper インターフェースが無いよって言われます。

JDK を変更しても一緒だったので何か変更されたのか、変更中なのかもしれません。

とりあえずここまではチュートリアル通りに動くようです。

一部コードは変更してあります。

さぁ、それでは、NetBeans の Lambda Expression 対応状況をみてみましょう。

このような匿名クラスを使ってるのをみつけると

このように Lambda Expression に変更できますよって親切に教えてくれます。

Lambda 使っちゃいますよってポチッってすると

これからの Java に変更されます。

チュートリアルで Lambda Expression を使う場合のコードと同じですね。（＾－＾）

おまけとして、Java™ Platform, Standard Edition 8 Early Access with Lambda Support を使った場合は

このように Functional Operation をお勧めしてくれます。

なんて親切なんだろう。

で、お勧めに従って Use Functional Operation をポチッとクリックすると

素敵ですね。拡張 for 文から見慣れない forEach 文を使った構文に変更されてます。

filter() を使えばいろいろ便利に使えそうな予感がします。

チュートリアルの充実と JDK 8 及び NetBeans の熟成が楽しみです。(*^O^*)

Hatena タグ: Java,NetBeans

TAGS: Java,NetBeans | 2013年3月8日3:51 PM | Comment : 0

実行可能JARファイルが Java 7 u11 で動くようになっていた

Java

実行可能JARファイルが Java 7 になってから動かなくなってがっかりしていたが Windows 8 Pro , Java 7 u11 で動くことを確認！

いつから動くようになったのかは不明です。

また、Windows 7 での確認はまだしていません。

これで過去に作った自分専用の Java アプリが使えます。（＾＾）

そう言えばこの件をネットで調べていたとき同じように Java 7 で動かなくなって弱ってる人を発見しました。

早速教えてあげようと思ったがどこのサイトだったか記憶にない（＾＾；

Hatena タグ: Java

TAGS: Java | 2013年1月30日5:10 PM | Comment : 0

Nクイーン問題 nQueens Problem

Java

Java で Nクイーン問題　nQueens Problem をプログラミングしてみました。

まず Nクイーン問題とは何か？

ネットでググってみると８クイーン問題ってのがよくとりあげられてます。

Nクイーン問題とはそれを一般化したようです。

では８クイーン問題から調べていきましょう。

８クイーン問題では、王妃（クイーン）８個が用意されています。

チェス盤のサイズは王妃（クイーン）と同じ数とします。

８クイーンでは縦、横８マスです。

そのチェス盤に全ての王妃（クイーン）を配置します。

ただし、それぞれの王妃（クイーン）の利き筋には配置できません。（縦、横、斜めの４ライン）

以上の条件を全て満たす王妃（クイーン）の配置パターン及び総数を求めるものです。

それではどうやって解を導き出したらいいのか考えてみることにします。

８個の王妃（クイーン）を全ての組み合わせに配置して上記の条件をクリアするかを確認すればいいだけのことですね。

しかし、その方法だと 8 X 8 = 64 マスあるから

64 X 63 X 62 X 61 X 60 X 59 X 58 X 57 = 178,462,987,637,760 通りもあることになります。

ちょっと多いですね。

王妃（クイーン）の数が大きくなった時のことを考えたら厳しいです。

しかし、全ての組み合わせを調べる必要はなさそうです。

何故なら、同じ列、行に王妃は配置できないからです。

縦、横の利き筋の条件を考慮した結果、各列、行には王妃（クイーン）は 1 個だけしか配置できない！

よって、 8! = 40,320 通りまで激減させることができる。

あと斜めの利き筋２つを利用すれば計算処理はもっと少なくなるだろう。

以上のことを考慮した上で次のようなプログラムを作ればいいかもしれない。

private static void trySet(int i) {

for (王妃の数だけループ) {

if (利き筋から外れていれば) {

王妃 i 列 j 行に配置

if (i == (王妃８個配置できたら) {

トータルパターン数をカウントアップ

盤面を表示

}else {

王妃の利き筋（行、斜め）をセット

次の列を配置（再帰 trySet(i + 1)）

王妃の利き筋（行、斜め）を解除

                    }
             }
     }
}

ってことで作ってみました。

ただ、デバッガでプログラムの流れを追うために王妃（クイーン）の数は 4 としました。

もちろん、王妃（クイーン）の数は一般化できるようにしてあります。

nqueensproblem.NQueensProblem.java

package nqueensproblem;

/**
 *
 * @author Yucchi
 */
public class NQueensProblem {

    // 王妃数
    private static final int QUEENS = 4;
    // 王妃の配置位置 
    private static final int [] VERTICAL = new int [QUEENS];
    // 行に王妃が配置されてるかチェック用  
    private static final boolean [] HORIZONTAL = new boolean [QUEENS]; 
    // 右４５度斜めラインに王妃が配置されているかチェック用
    private static final boolean [] DIP_POSITIVE = new boolean [QUEENS * 2 -1]; 
    // 左４５度斜めラインに王妃が配置されているかチェック用
    private static final boolean [] DIP_NEGATIVE = new boolean [QUEENS * 2 - 1];
    // 安全 
    private static final boolean SAFE = false;
    // 危険 
    private static final boolean OUT = true;
    // トータルパターン数 
    private static int counter; 

    public static void main(String[] args) {
        trySet(0);
        if(counter < 1){
            System.out.println("配置不可能でした。");
        }else{
            System.out.println(counter + " パターン配置可能でした。");
        }
    }
    
    // 全ての可能な王妃の配置位置を取得、そしてトータルパターン数も取得する。
    private static void trySet(int i) {
        for (int j = 0; j < QUEENS; j++) {
            // 行 ( j )、／右４５度斜めライン ( i + j )、＼左４５度斜めライン (i - j + ( QUEENS -1 )) 配置チェック
         if (HORIZONTAL [j] == SAFE && DIP_POSITIVE [i + j] == SAFE && DIP_NEGATIVE [i - j + ( QUEENS -1)] == SAFE) { 
            VERTICAL [i] = j; // 王妃 i 列 j 行に配置
            if (i == ( QUEENS -1)) { // 王妃の配置完了
                 counter++; // トータルパターン数カウンター
                 printBoard(); // 盤面を表示
             }else {
                // 王妃の利き筋（行、斜め）をセット
               HORIZONTAL [j] = DIP_POSITIVE [i + j] = DIP_NEGATIVE [i - j + ( QUEENS -1)] = OUT;
               // 次の列を配置
               trySet(i + 1);
               // 王妃の利き筋（行、斜め）を解除
               HORIZONTAL [j] = DIP_POSITIVE [i + j] = DIP_NEGATIVE [i - j + ( QUEENS -1)] = SAFE;
            }
         }
      }
    }

    // 全ての可能な王位配置位置を出力　●が王妃が置かれた場所である。
    private static void printBoard() {
        System.out.println("第 " + counter + " パターン"); 
        for (int i = 0; i < QUEENS; i++) {
         for (int j = 0; j < QUEENS; j++) {
                System.out.printf("%s", j == VERTICAL [i] ? "● " : "□ ");
            }
         System.out.println();
      }
      System.out.println();

    }
}

package nqueensproblem;

/**

* @author Yucchi

public class NQueensProblem {

// 王妃数

private static final int QUEENS = 4;

// 王妃の配置位置

private static final int [] VERTICAL = new int [QUEENS];

// 行に王妃が配置されてるかチェック用

private static final boolean [] HORIZONTAL = new boolean [QUEENS];

// 右４５度斜めラインに王妃が配置されているかチェック用

private static final boolean [] DIP_POSITIVE = new boolean [QUEENS * 2 -1];

// 左４５度斜めラインに王妃が配置されているかチェック用

private static final boolean [] DIP_NEGATIVE = new boolean [QUEENS * 2 - 1];

// 安全

private static final boolean SAFE = false;

// 危険

private static final boolean OUT = true;

// トータルパターン数

private static int counter;

public static void main(String[] args) {

trySet(0);

if(counter < 1){

System.out.println("配置不可能でした。");

}else{

System.out.println(counter + " パターン配置可能でした。");

}

// 全ての可能な王妃の配置位置を取得、そしてトータルパターン数も取得する。

private static void trySet(int i) {

for (int j = 0; j < QUEENS; j++) {

// 行 ( j )、／右４５度斜めライン ( i + j )、＼左４５度斜めライン (i - j + ( QUEENS -1 )) 配置チェック

if (HORIZONTAL [j] == SAFE && DIP_POSITIVE [i + j] == SAFE && DIP_NEGATIVE [i - j + ( QUEENS -1)] == SAFE) {

VERTICAL [i] = j; // 王妃 i 列 j 行に配置

if (i == ( QUEENS -1)) { // 王妃の配置完了

counter++; // トータルパターン数カウンター

printBoard(); // 盤面を表示

}else {

// 王妃の利き筋（行、斜め）をセット

HORIZONTAL [j] = DIP_POSITIVE [i + j] = DIP_NEGATIVE [i - j + ( QUEENS -1)] = OUT;

// 次の列を配置

trySet(i + 1);

// 王妃の利き筋（行、斜め）を解除

HORIZONTAL [j] = DIP_POSITIVE [i + j] = DIP_NEGATIVE [i - j + ( QUEENS -1)] = SAFE;

}

// 全ての可能な王位配置位置を出力　●が王妃が置かれた場所である。

private static void printBoard() {

System.out.println("第 " + counter + " パターン");

for (int i = 0; i < QUEENS; i++) {

for (int j = 0; j < QUEENS; j++) {

System.out.printf("%s", j == VERTICAL [i] ? "● " : "□ ");

}

System.out.println();

}

System.out.println();

}

さて、理屈やコードだけでは解りにくいかもしれないのでこのプログラムの流れをデバッグ実行して確認してみます。

デバッグウィンドウやウォッチポイントの変数の値を確認しながらごらんくださいませ。

プログラムの流れを見ていると人間の思考原理に非常に良く似ていますね。

とりあえず順番に試してみる。

条件を考慮して無駄なことはせず作業量を減らす。

途中で駄目だと判断できたら戻って次のパターンからやり直す。

それの繰り返しで処理を完了する。

こういったアルゴリズムはバックトラック法って言われているようです。

深さ優先探索アルゴリズムですね。

試行錯誤的に解を探し出すタイプの問題に有効です。

つまり、基本的に全ての選択肢を試してみるしか無い場合なんかには有効のようです。

いつ頃、誰が、どのような理由でこういったアルゴリズムを考えたのか？

考えた人を心から尊敬します。

ちなみに８王妃問題としてプログラムを実行したい場合は上記プログラムの 9 行目の

private static final int QUEENS = 4; // 王妃数

王妃数を 8 に変更してください。

任意の王妃数をこれによって設定できますがあまり王妃数を大きくすると計算量が指数関数的に増加するでしょうからほどほどに(^_^;

再帰アルゴリズムについてはこちらで簡単な覚え書きを残してあります。

再帰アルゴリズム　その１

再帰アルゴリズム　その２

ユークリッドの互除法 Euclidean Algorithm

ハノイの塔 Tower of Hanoi

Hatena タグ: Java

TAGS: Java | 2013年1月5日6:58 AM | Comment : 0

ハノイの塔 Tower of Hanoi

Java

Java でハノイの塔をプログラミングしてみました。

再帰アルゴリズムでググるとほとんどの言語でサンプルがあります。

しかし、再帰アルゴリズムは理屈では理解できても実際に使おうとすると難しいものです。

そこで NetBeans を使って再帰アルゴリズムの仕組みをみていこうと思います。

まず、ハノイの塔についておさらいしておきましょう。

Wikipedia によると、ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発売したゲーム『ハノイの塔』がルーツである。

その内容は下記のようになっている。

インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。

そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。

そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。

これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し替えのルールの説明は省略）。

そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。

n 枚の円盤すべてを移動させるには最低 2^n-1 回(2のｎ乗 – 1 回)の手数がかかります。

なんか恐ろしいですね。

それにハノイの塔じゃなくてブラフマーの塔になってます。（なんでだろう？ )

さて。肝心の移し替えのルールをザックリと確認しましょう。

移し替えの際、円盤は一回に一枚しか移し替えできない。

小さな円盤の上に大きな円盤を重ね置くことはできない。

実にシンプルなルールですね。

しかし、シンプルだからといって侮れません。

考え方としては円盤の枚数を n 枚とします。

そして円盤が重ね置いてあるダイヤの針は左( LEFT )とします。

移し替え先のダイヤの針は右( RIGHT )、そして移し替え作業用のダイヤの針を中央( CENTER )とします。

まず、n -1 枚の円盤を中央のダイヤの針に移し替えます。

そして、右のダイヤの針に左のダイヤの針に残っている一番大きな円盤( n 枚目の円盤 )を移し替えます。

次に中央のダイヤの針に移し替えられた n-1 枚の円盤を左のダイヤの針に移し替えます。

言葉よりプログラムの流れで確認したほうが理解し易いかもしれませんね。

上記の考え方を再帰アルゴリズムを利用して組んだコードがこれです。

素人が作ったプログラムなので読みにくいとは思いますがじっくりプログラムの流れを確認してください。

yucchi.jp.hanoi.Hanoi.java

package yucchi.jp.hanoi;

/**
 *
 * @author Yucchi
 */
public class Hanoi {

    private static int count;
    private static int TARGET_NUMBER = 3;

    // ハノイの塔
    // n : 移動させる円盤の枚数
    // from : 移動元の塔
    // work : 作業用の塔 ---> 一番下の円盤以外の一時的な置き場所
    // dest : 移動先の塔
    private static void hanoi(int n, String from, String work, String dest) {
        if (n > 0) {
            // n - 1 番目の輪を LEFT から CENTER に移動させる。
            hanoi(n - 1, from, dest, work);
            // 上の hanoi(n - 1, from, dest, work)を実行完了後に
            // n 番目の円盤を移動させる。
            System.out.println(++count + " ： " + n + "番目の円盤を" + from + "から" + dest + "へ移動させる。");
            // 上の hanoi(n - 1, from, dest, work) メソッドで
            // 一番下以外の棒がfromからworkに移っているので、
            // 今度は work を from にして、空いた from を work にして移動させる。
            // n - 1 番目の輪を CENTER から LEFT に移動させる。
            hanoi(n - 1, work, from, dest);
        }
    }

    public static void main(String[] args) {
        System.out.println(TARGET_NUMBER + "枚のハノイの塔　開始");
        // ダイアでできた LEFT 塔にある TARGET_NUMBER 枚の純金の円盤をダイアでできた RIGHT 塔に移動させる。
        hanoi(TARGET_NUMBER, "LEFT", "CENTER", "RIGHT");
        System.out.println(TARGET_NUMBER + "枚のハノイの塔　終了");
    }
}

package yucchi.jp.hanoi;

/**

* @author Yucchi

public class Hanoi {

private static int count;

private static int TARGET_NUMBER = 3;

// ハノイの塔

// n : 移動させる円盤の枚数

// from : 移動元の塔

// work : 作業用の塔 ---> 一番下の円盤以外の一時的な置き場所

// dest : 移動先の塔

private static void hanoi(int n, String from, String work, String dest) {

if (n > 0) {

// n - 1 番目の輪を LEFT から CENTER に移動させる。

hanoi(n - 1, from, dest, work);

// 上の hanoi(n - 1, from, dest, work)を実行完了後に

// n 番目の円盤を移動させる。

System.out.println(++count + " ： " + n + "番目の円盤を" + from + "から" + dest + "へ移動させる。");

// 上の hanoi(n - 1, from, dest, work) メソッドで

// 一番下以外の棒がfromからworkに移っているので、

// 今度は work を from にして、空いた from を work にして移動させる。

// n - 1 番目の輪を CENTER から LEFT に移動させる。

hanoi(n - 1, work, from, dest);

}

public static void main(String[] args) {

System.out.println(TARGET_NUMBER + "枚のハノイの塔　開始");

// ダイアでできた LEFT 塔にある TARGET_NUMBER 枚の純金の円盤をダイアでできた RIGHT 塔に移動させる。

hanoi(TARGET_NUMBER, "LEFT", "CENTER", "RIGHT");

System.out.println(TARGET_NUMBER + "枚のハノイの塔　終了");

}

どうでしょうか？

理解できましたでしょうか？

考え方は非常にシンプルだけどけっこう流れは追っていくと複雑に感じますね。

いちおう参考までにこれも貼っておきます。

hanoi メソッドが再帰的に実行されているのが確認できます。

これで再帰アルゴリズムで複雑な繰り返し処理を記述できるようになったとはとても思えないけど

ちょっとは再帰アルゴリズムの使いどころを理解したつもりになりました。

たぶん、すぐに忘れてしまうだろうけどまた挑戦してみたらいいだけのことだし。

気楽に楽しんでいこう！ (*^o^*)

再帰アルゴリズムについてはこちらで簡単な覚え書きを残してあります。

再帰アルゴリズム　その１

再帰アルゴリズム　その２

ユークリッドの互除法 Euclidean Algorithm

Hatena タグ: Java

TAGS: Java | 2013年1月4日5:03 AM | Comment : 1

ユークリッドの互除法 Euclidean Algorithm

Java

Java でユークリッドの互除法　Euclidean Algorithm をプログラミングしてみました。

再帰アルゴリズムを使ってます。

再帰アルゴリズムについてはこちらで簡単な覚え書きを残してあります。

再帰アルゴリズム　その１

再帰アルゴリズム　その２

ユークリッドの互除法とはいったいどんな仕組みなのか調べてみました。

ある二つの自然数の最大公約数を求めるのに非常に優れた方法らしいです。

名前に互除法とあるとおり互いに割り算を行って解を導き出す方法です。

簡単に説明すると自然数 r1 と r 2 ( r1 >= r2 ) の最大公約数を求めるとき ( 注意 : r の後の数字と n は小さい数字だと思ってください。)

r1 / r2 の余り r3 を求める。

次に r2 / r3 の余り r4 を・・・

これを rn が 0 になるまで繰り返す。

この時、 r(n-1) が最大公約数となる。

実にシンプルです。

数学的証明はここでは割愛させていただきます。

これを Java プログラムにするには再帰アルゴリズムを使えば簡単にできそうですね。

さっそく作ってみましょう。

euclidean_algorithm.Euclidean_Algorithm.java

package euclidean_algorithm;

/**
 *
 * @author Yucchi
 */
public class Euclidean_Algorithm {

    public static void main(String[] args) {
        if (args.length != 2) {
            System.err.println("えらー (゜´Д｀゜) 自然数を二つ入力してね。");
            System.exit(0);
        }

        int x = java.lang.Integer.parseInt(args[0]);
        int y = java.lang.Integer.parseInt(args[1]);

        if (x < 0 || y < 0) {
            System.err.println("えらー (゜´Д｀゜) 自然数を二つ入力してね。");
            System.exit(0);
        }
        
        if (x < y) {
            y ^= x;
            x ^= y;
            y ^= x;
        }
        
        System.out.println(args[0] + " と " + args[1] + " の最大公約数は " + gcd(x, y) + " だよね。");
        
    }

    private static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
}

package euclidean_algorithm;

/**

* @author Yucchi

public class Euclidean_Algorithm {

public static void main(String[] args) {

if (args.length != 2) {

System.err.println("えらー (゜´Д｀゜) 自然数を二つ入力してね。");

System.exit(0);

}

int x = java.lang.Integer.parseInt(args[0]);

int y = java.lang.Integer.parseInt(args[1]);

if (x < 0 || y < 0) {

System.err.println("えらー (゜´Д｀゜) 自然数を二つ入力してね。");

System.exit(0);

}

if (x < y) {

y ^= x;

x ^= y;

y ^= x;

}

System.out.println(args[0] + " と " + args[1] + " の最大公約数は " + gcd(x, y) + " だよね。");

}

private static int gcd(int x, int y) {

return y == 0 ? x : gcd(y, x % y);

}

非常にシンプルで解りやすいですね。

せっかくだからデバッグ実行させてプルグラムの流れを確認してみよう。

変数 x , y の値に注目です。

main() メソッドの引数二つを整数とし、大きさを比較し計算処理のため必要に応じて値を入れ替え、

再帰メソッドで答えが出るまで(再帰のループから抜ける条件になるまで）ひたすらぐるぐる回るってかんじ。

ユークリッドの互除法ってシンプルだけど良く考えられた素晴らしいものですね。

最後にすでにお気付きの方もいると思うのですが上記プログラムはちょっと手抜きの部分があります。

目的がユークリッドの互除法を試してみるということなのでご容赦のほどを(^_^;

ちなみに java.lang.NumberFormatException が・・・・・・です。（本当は忘れていたことは内緒です）

Hatena タグ: Java

TAGS: Java | 2013年1月3日4:58 AM | Comments : 2

« 古い記事新しい記事 »

ゆっちのBlog

NetBeans 8 開発版で JDK 8 EA を使ってみた

実行可能JARファイルが Java 7 u11 で動くようになっていた

Nクイーン問題 nQueens Problem

ハノイの塔 Tower of Hanoi

ユークリッドの互除法 Euclidean Algorithm

Recent Comments

Java

NetBeans

カテゴリー

アーカイブ

RSS FEED

ねこび～ん

メタ情報

ゆっちのカレンダー

2024年11月
月	火	水	木	金	土	日
« 1月
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

ゆっちのBlog

NetBeans 8 開発版で JDK 8 EA を使ってみた

実行可能JARファイルが Java 7 u11 で動くようになっていた

Nクイーン問題 nQueens Problem

ハノイの塔 Tower of Hanoi

ユークリッドの互除法 Euclidean Algorithm

Popular post ranking

Recent Comments

Java

NetBeans

カテゴリー

アーカイブ

RSS FEED

ねこび～ん

メタ情報

ゆっちのカレンダー