javaで組み合わせの計算 npn、nCnを求めるプログラムを再帰呼び出を使って作成しようとします。再帰呼び出しに対して詳しくないのでお願いします。

回答の条件
  • URL必須
  • 1人5回まで
  • 登録:2009/06/16 00:52:48
  • 終了:2009/06/23 00:55:02

回答(5件)

id:kn1967 No.1

kn1967回答回数2915ベストアンサー獲得回数3012009/06/16 02:26:07

ポイント20pt

はじめMath! Javaでコンピュータ数学:第48回 確率の数学 順列と組合せ [前編]|gihyo.jp … 技術評論社

はじめMath! Javaでコンピュータ数学:第49回 確率の数学 順列と組合せ [中編]|gihyo.jp … 技術評論社

はじめMath! Javaでコンピュータ数学:第50回 確率の数学 順列と組合せ [後編]|gihyo.jp … 技術評論社

組み合わせ計算に関しては上記が参考になるかと思います。


再起呼び出しが苦手との事なので、

上記サイトにて再起呼び出しを使っている部分の動作を追ってみることにしましょう。

はじめMath! Javaでコンピュータ数学:第50回 確率の数学 順列と組合せ [後編]|gihyo.jp … 技術評論社 2ページ目

//階乗計算

private long factorial(int n) {

if ( n == 0 ) {// n が0 になったら1 を返して脱出 

return 1;

} else {

return n*factorial(n-1);// 再帰呼び出し

}

}


仮に n = 3 で呼び出したとすれば

(1)呼び出し。この時点で n = 3
  private long factorial(int n) {
    if ( n == 0 ) {
      return 1;// n = 3 なので、ここは通らない
    } else {
      return n*factorial(n-1);// (2)から値を得て結果 3 * 2 で 6 を呼び出し元に返す。
    }
  }
(2)再起呼び出し1回目 1 引かれてるので、この時点で n = 2
  private long factorial(int n) {
    if ( n == 0 ) {
      return 1;// n = 2 なので、ここは通らない。
    } else {
      return n*factorial(n-1);// (3)から値を得て結果 2 * 1 で 2 を(1)へ返す
    }
  }
(3)再起呼び出し2回目 さらに 1 引かれてるので n = 1
  private long factorial(int n) {
    if ( n == 0 ) {
      return 1;// n = 1 なので、ここは通らない。
    } else {
      return n*factorial(n-1);// (4)から値を得て結果 1 * 1 で 1 を(2)へ返す。
    }
  }
(4)再起呼び出し3回目 さらに 1 引かれてるので n = 0
  private long factorial(int n) {
    if ( n == 0 ) {
      return 1;// n = 0 なので、以下に進まず、この時点で 1 を(3)に返す。
    } else {
      return n*factorial(n-1);
    }
  }

再起呼び出しという言葉は難しく聞こえますが

やっていることは1つのサブルーチンを何度も呼んでいるだけなので

上のように1回目、2回目・・・と分けて考えていくと

意外とあっさり理解できるかと思います。

(同じ内容のサブルーチンがいくつもあると考えても良いでしょう)

id:kimu_507

詳しく説明して頂き有難うございます。

勉強になりました。

2009/06/16 08:22:31
id:pahoo No.2

pahoo回答回数5960ベストアンサー獲得回数6332009/06/16 10:20:37

ポイント20pt

再帰呼び出しの基本は kn1967 さんが回答された通りです。


今回は学習ということですが、実際のプログラムでは、数値計算で再帰呼び出しを使うことは滅多にありません。for, while といったループ制御に比べ、メモリやCPUパワーを使うためです。

再帰処理と参照渡し(モドキ)のメリット・デメリット 」はC言語における注意を記した記事ですが、Javaでも当てはまります。


また、これはループ制御の場合にも言えることですが、終了条件には注意しなければなりません。とくに再帰呼び出しだと、与えられた n が巨大だったり、定義域外だったりすると、メモリエラー(スタック不足)を引き起こし、OSによってはシステムが丸ごとダウンしてしまいます。

そこで、再帰呼び出しの前に n の大きさを制限するとか、定義域のチェックをするといった工夫が必要です。

たとえば階乗関数で再帰呼び出し回数を99回以下にするなら、下記のようにします。

static long factorial(long n) {
    if (n < 1 || n > 99)  return 0;   //即リターン
    if (n == 1) return 1;
    else        return n * fact(n - 1);
}
id:kimu_507

すみません カレンダー横並びをようやって設定すればいいか教えてください。

今の結果は

2009年3月

日 月 火 水 木 金 土

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 31

2009年4月

日 月 火 水 木 金 土

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

下の4月の分を3月分の隣に出力したいです。


import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.FileWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.PrintWriter;

import java.util.Calendar;

public class Test {

// 年と月を入力

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

// キーボードから入力された文字列を変数に格納する

System.out.println("年を入力してください。");

String Year = br.readLine();

System.out.println("月を入力してください。");

String Month = br.readLine();

System.out.println("横を入力してください。");

String Width = br.readLine();

System.out.println("縦を入力してください。");

String Height = br.readLine();

// int mt[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

String day[] = { "日", "月", "火", "水", "木", "金", "土" };

// 入力チェック

if (Year.equals("") || Month.equals("") || Width.equals("")

|| Height.equals("")) {

System.out.println("入力してください");

} else {

// 文字列をINT変数に格納する

int year = Integer.parseInt(Year);

int month = Integer.parseInt(Month);

int width = Integer.parseInt(Width);

int height = Integer.parseInt(Height);

// テキストに出力する

PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(

"calendar.txt", true)));

{ //縦値数まで出力する

for (int h = 1; h <= height; h++) {

//月が13になったら年に1を足す、月は1に戻る

if (month==13) {

year++;

month = 1;

}

pw.println(year + "年" + month + "月");

//曜日出力

for (int i = 0; i < day.length; i++) {

pw.print(day[i] + "\t");

}

pw.println("\n");

// javaカレンダークラス

Calendar cal = Calendar.getInstance();

// 年、月をセットする

cal.set(year, month - 1, 1);

// 毎月最後の日付を取得

int allday = cal.getActualMaximum(Calendar.DAY_OF_MONTH);

// 月初めの曜日を取得

int week = cal.get(Calendar.DAY_OF_WEEK);

// その月の日数分まで繰り返す

for (int i = 1; i <= allday; i++) {

// 1日の曜日位置まで移動する

if (i == 1) {

for (int j = 0; j < week - 1; j++) {

pw.print("\t");

}

} else {//

cal.add(Calendar.DAY_OF_MONTH, 1);

}

// 日付出力 日付と日付間をtabで空ける

pw.print(i + "\t");

// 土曜日になったら改行する

if (cal.get(Calendar.DAY_OF_WEEK) == 7) {

pw.println("\n");

}

}

//月数を増やす

month++;

pw.println("\n");

}

}

pw.close();

}

}

}

2009/06/17 16:13:43
id:pahoo No.3

pahoo回答回数5960ベストアンサー獲得回数6332009/06/17 18:24:27

ポイント20pt

kimu_507 : すみません カレンダー横並びをようやって設定すればいいか教えてください。

申し訳ありません。本質問と関係ない内容ですし、前回質問で解決していると思うのですが‥‥。


※設定された回答回数の上限になりました。さらにフォローが必要でしたら、コメント欄を開けていただくか、回答回数を増やしてください。

id:kimu_507

なんかすみません 今色んな事をやっているので。。。

カレンダー横並だけできなくて伺いました。

2009/06/19 11:31:16
id:van-dine No.4

van-dine回答回数108ベストアンサー獲得回数112009/06/18 22:45:23

ポイント20pt

mPn = (m-n+1)*mP(n-1)

mCn = (m-1)C(n-1) + (m-1)Cn

という公式があります。

後は再帰の基本だけで書けるので、そう難しくはありません。

公式を単に書けば動くことが多いので、数学書を一通り読まれてはどうでしょうか?

↓ダミー

http://q.hatena.ne.jp/

id:kimu_507

有難うございます。 今やってる途中です。

また なんかあったら お願いします。

2009/06/19 01:51:46
id:kn1967 No.5

kn1967回答回数2915ベストアンサー獲得回数3012009/06/19 00:30:36

ポイント20pt

pahoo氏のおっしゃる通り、まったく別の話なので答えるべきではないのですが

「再起呼び出し」への関連質問だと拡大解釈して

「再起呼び出し」に関連する部分だけ回答させていただこうと思います。


エレガントなコードではありませんが、提示なさったコードと比較してみてください。

(年月を毎回聞かれるのは面倒なので、引数として渡すようにしてますが適宜改造してください)

import java.lang.*;
import java.io.*;
import java.util.*;

class cal2 {

    public static void main(String[] args) throws IOException {
        int year = Integer.parseInt(args[0]); // 引数を数値に変換
        int month = Integer.parseInt(args[1]);
        int height = Integer.parseInt(args[2]);
        Calendar cal = Calendar.getInstance(); // カレンダークラス準備
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("calendar.txt", true))); // ファイル出力開始
        for (int h = 0; h < height; h++) { // 縦方向ループ
            cal.set(year, month - 1, 1); // 年、月をセットする
            int start = 2 - cal.get(Calendar.DAY_OF_WEEK); // 月初めの曜日からスタート日を取得
            int end = cal.getActualMaximum(Calendar.DAY_OF_MONTH); // 月最後の日付を取得
            pw.println (
                String.format("%4d年%2d月           \r\n日 月 火 水 木 金 土 ", year, month) +
                mcal(start, end) + 
                "\r\n"
            );
            if (month == 12) { //月を増やす(12月ならば年に1を足して月は1に戻す)
                year++;
                month = 1;
            } else {
                month++;
            }
        }
        pw.close(); // ファイル出力終了
    }

    private static String mcal(int start, int end) {
        if (start > end) { // 終了判定
            return "";
        } else {
            String Calendar = "";
            for (int i = start; i <= start + 6; i++) {
                if ((i > 0) && (i <= end)) { // 通常処理
                    Calendar += String.format("%2d ", i);
                } else { // 月初・月末の処理
                    Calendar += "   ";
                }
            }
            return "\r\n" + Calendar + mcal(start + 7, end);
        }
    }

}

http://jp.sun.com/java/

id:kimu_507

すみません、大変助かります。 早速 参考させて頂きます。

これからもなんかあったらお願いします。

2009/06/19 01:58:53

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません