1から90の整数から5つの整数を引いて小さい順に発表するとき、 連続した整数が現れない取り方は何通りある? 詳細条件 1、3、5、7、9 はOK 1、4、5、7、9 は、4と5が連続しているため条件に該当しません。 |
答えを返すような関数T を定義してみよう. 6個から2個を選ぶ場合の数を知りたければ T(6,2) とすれば答が得られるようなTである. 一般解はすぐにはわからないので,実際に 6個から2個を選ぶ過程を考えてみる. <----numSet=6---> #1 #2 #3 #4 #5 #6 X ^ | a)まず, #1 を選ぶとする.その場合の数は, 次の問題に帰着する: <---4----> 4つから1つを選ぶ,つまり T(4,1) #3 #4 #5 #6 .... それは4とおり. 以下,最初の1個を左から何番目にとるか, すべて列挙してみよう. b)2個めのときは,次は <--3--> 3つから1つを選ぶ,つまりT(3,1) #4 #5 #6 .... それは3とおり. c) 3個めのときは. <-2> 2つから1つを選ぶ,つまりT(2,1) #5 #6 .... それは2とおり. d) 4個めのときは <1> 1つから1つを選ぶ,つまりT(1,1) #6 .... それは1とおり. つまり T(6,2) = T(4,1) + T(3,1) + T(2,1) + T(1,1). という展開が成り立つ. どんなT(s,c)も,この展開を繰り返せば,自明なT(n,1)=n の和に帰着する.ところで,「はて?」と思われるかたも多いと思います.T()の,よく知られている再帰的定義は,下記のほうだと思います.
T(a,n) = T(a-1, n-2) + T(a, n-1)こちらを利用するのがスマート,ではありますよね...まあ,気にしないことにします!w (こちらは,再帰の深さが瞬間的に見通せないですし...私のほうは,一回再帰するたびに,選ぶ個数の残りが減っていくので,再帰の深さが自明という利点があります.(屁理屈))
これで,一応実装はできます. ご存知のように,この手の再帰的定義では,求まった計算結果を保存しておいて,より大きな数に対する計算の際に参照してやると,無駄な再計算を省くことが出来て,大変効率的です. ですが,ここでは,単純化のため,基本的に実装しないことにします(たまに,実装したものもありますがw).
以上の方針で,いくつかの言語でコードを書いてみました.
% perl solve.pl とします. -------- # Sep. 11, 2008 zhuo sub CalcCombInternal { my ( $nSet, $nChoice ) = @_; if ( $nChoice == 1 ) { return $nSet; } my $total = 0; for ( my $nSubSet = $nSet - 2; $nSubSet >= ($nChoice-1); --$nSubSet ) { $total += CalcComb( $nSubSet, $nChoice - 1 ); } return $total; } # caching sub CalcComb { my ( $nSet, $nChoice ) = @_; if ( $isCached{$nSet,$nChoice} == 0 ) { $value{$nSet,$nChoice} = CalcCombInternal( $nSet, $nChoice ); $isCached{$nSet,$nChoice} = 1; } return $value{$nSet,$nChoice}; } $val = CalcComb( 90, 5 ); print "$val\n"; # 34826302最初の関数だけでも解けるけど再帰ものの定石で結果を保存しておくのに2つめの関数を使用。
% perl solve.pl とします. ---- # Sep. 11, 2008 zhuo sub CalcComb { my ( $nSet, $nChoice ) = @_; if ( $nChoice == 1 ) { return $nSet; } my $total = 0; for ( my $nSubSet = $nSet - 2; $nSubSet >= ($nChoice-1); --$nSubSet ) { $total += CalcComb( $nSubSet, $nChoice - 1 ); } return $total; } $val = CalcComb( 90, 5 ); print "$val\n"; # 34826302
---- ; by zhuo (defun CalcComb (nSet nChoice) ; (print (format "c(%d %d)" nSet nChoice) (get-buffer "*scratch*")) (if (eq nChoice 1) nSet (let ((total 0) (nSubChoice (- nChoice 1)) (nSubSet (- nSet 2))) (while (>= nSubSet nSubChoice) (setq total (+ total (CalcComb nSubSet nSubChoice))) (setq nSubSet (- nSubSet 1))) total))) (print (CalcComb 90 5) t) ; 34826302
% tclsh solve.tcl ---- # by zhuo proc CalcComb { nSet nChoice} { if { $nChoice == 1 } { return $nSet } set total 0 set nSubSet [expr $nSet - 2] set nSubChoice [expr $nChoice - 1] while { $nSubSet >= $nSubChoice } { incr total [CalcComb $nSubSet $nSubChoice] incr nSubSet -1 } return $total } set val [CalcComb 90 5] puts $val # 34826302
% sh solve.sh. 唯一、遅すぎて(90,5)の結果が出ないので、10,3で。
---- #by zhuo total=0 function CalcComb { echo "c($1 $2)" if [ "$2" -eq "1" ] ; then total=`expr $total + $1` else typeset -i nSubChoice=`expr $2 - 1` typeset -i nSubSet=`expr $1 - 2` while [ $nSubSet -ge $nSubChoice ]; do CalcComb $nSubSet $nSubChoice nSubSet=`expr $nSubSet - 1` done fi } CalcComb 10 3 echo "c(10 3)=$total"
% awk -f solve.awk ---- # by zhuo function CalcComb ( nSet, nChoice, _total, _nSubSet, _nSubChoice ) { if ( nChoice == 1 ) return nSet; _total = 0; _nSubSet = nSet - 2; _nSubChoice = nChoice - 1; while ( _nSubSet >= _nSubChoice ) { _total += CalcComb( _nSubSet, _nSubChoice ); --_nSubSet; } return _total; } BEGIN { print CalcComb( 90, 5 ); } # 34826302
---- <html> <head> <script type="text/javascript"> <!-- // by zhuo function CalcComb ( nSet, nChoice, _total, _nSubSet, _nSubChoice ) { if ( nChoice == 1 ) return nSet; _total = 0; _nSubSet = nSet - 2; _nSubChoice = nChoice - 1; while ( _nSubSet >= _nSubChoice ) { _total += CalcComb( _nSubSet, _nSubChoice ); --_nSubSet; } return _total; } document.write( CalcComb( 90, 5 ) ); // 34826302 </script> </head> <body> </body> </html>
---- % by zhuo % nSet nChoice -> CalcComb -> result /CalcComb { dup 1 eq { pop } { 1 sub exch 2 sub 0 exch -1 3 index { 2 index CalcComb add } for exch pop } ifelse } def % to render the result on the graphic pane %! /Times-Roman findfont 128 scalefont setfont 32 640 moveto 90 5 CalcComb =string cvs show % 34826302
コード: 10 rem Oct. 17, 2008 zhuo, in Z80 (MSX) 100 c lear 200,&HD000:a=&HD006:def usr=a 110 read b$:if b$="" goto 130 120 for i=1to len(b$)step2:poke a,val("&H"+MID$(b$,i,2)):a=a+1:next:goto 110 130 poke &HD000,90:poke &Hd001,5:a=usr(0) 140 for a=&HD005 to &HD002 step -1:print right$(("0"+hex$(peek(a))),2);:next 500 data "F5E5D5C5ED4B00D0210000545DCD23D0ED6302D0ED5304D0C1D1E1F1C9100409" 510 data "D013C90D0D79B8D8C5CD23D0C118F5" 520 data "" 結果: 0213683E この16進数を, perlの使える環境で perl -e 'printf("%d\n", 0x0213683e);' とやって10進数に換算してみると34826302であり、合っている。 余談: native speed mode(3.58MHz)で約75秒で解が求まった。sh版に勝ったw