１から９０の整数から５つの整数を引いて小さい順に発表するとき、 連続した整数が現れない取り方は何通りある？ 詳細条件 １、３、５、７、９ はＯＫ １、４、５、７、９ は、４と５が連続しているため条件に該当しません。 |
答えを返すような関数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