人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

●質問者: kimu_507
●カテゴリ:ウェブ制作
✍キーワード:Java プログラム 作成 再帰 再帰呼び出し
○ 状態 :終了
└ 回答数 : 5/5件

▽最新の回答へ

1 ● kn1967
●20ポイント

はじめ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回目・・・と分けて考えていくと

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

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

◎質問者からの返答

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

勉強になりました。


2 ● pahoo
●20ポイント

再帰呼び出しの基本は 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);
}
◎質問者からの返答

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

今の結果は

2009年3月

日月火水木金土

1234567

891011121314

15161718192021

22232425262728

293031

2009年4月

日月火水木金土

1234

567891011

12131415161718

19202122232425

2627282930

下の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();

}

}

}


3 ● pahoo
●20ポイント

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

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


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

◎質問者からの返答

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

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


4 ● van-dine
●20ポイント

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

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

という公式があります。

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

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

↓ダミー

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

◎質問者からの返答

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

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


5 ● kn1967
●20ポイント

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/

◎質問者からの返答

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ