アルゴリズムの問題いろいろ
- 合計金額になるすべてのお金の組み合わせを計算する。
例:10ドル、5ドル、1ドルを組み合わせて123ドルになるのは何通り?
use strict; sub f{ my( $amount, @curs ) = @_; my $cur = shift @curs; my $total; return 0 unless $cur; if( @curs == 0 ) { return 1 unless $amount % $cur; return 0 if $amount % $cur; } for( my $i=0; $i<=$amount/$cur; $i++ ){ $total += f( $amount - ($cur*$i), @curs ); } return $total; } print f( @ARGV );
perl amount.pl 123 10 5 1 169
- C++で書く場合
#include <stdio.h> #include <stdlib.h> int subTotal(int total, int cur[], int start, int end){ if(total==0) return 1; int pat=0; if((end-start)>0){ for(int i=0; i*cur[start]<=total; i++){ pat += subTotal( total-i*cur[start], cur, start+1, end ); } } else { if( total % cur[start] == 0 ) pat++; } return pat; } int main(int args, char* argv[]){ int *cur = new int[args-1]; for(int i=0; i<args-2; i++) cur[i] = atoi( argv[i+2] ); int result = subTotal( atoi(argv[1]), cur, 0, args-3 ); printf("%d", result); delete cur; return 0; }
# a.out 1234 100 50 20 10 5 1 6764940