|
投稿者：山中和義
投稿日：2014年 9月14日(日)07時00分11秒
|
|
|
|
問題
正の整数が書かれたカードが何枚かあり、全てのカードの和は15であるとする。
1以上15以下の任意の整数kに対し、書かれた数の和がkになるように何枚かを選び出すことができという。
またその選び方は、同じ数の書かれたカードを区別しないものとするとただ1通りである。
このようなカードの組合せはどのようなものが可能か、全ての組合せを探して下さい。
例
5の場合、
1,1,1,1,1
1,1,1,2
1,1,3
1,2,2
の4通り
考察
1が少なくとも1つある分割数を考えればよい。
自明なもの
1,1,1,…,1
└ n個 ┘
1,1,1,…,1, k ただし、1≦k≦[(n+1)/2]
└ n-k個 ┘
n=2^k-1
1,2,4,8,…,2^(k-1)
n=Σk
1,2,3,4,…,k
（終り）
LET N=15 !枚数の最大
DIM A(N) !数字の並び
LET A(1)=1 !番兵
PUBLIC NUMERIC C !場合の数
LET C=0
CALL try(2,N-1,A,N)
PRINT C; "通り"
PRINT T(N,N); "通り"
END
EXTERNAL SUB try(P,M,A(),N) !バックトラック法で検索する
FOR i=A(P-1) TO M !nを昇順の並びで分割する
LET A(P)=i
IF M-i=0 THEN !分割が終わったなら
DIM B(N) !1からnまでの数 ※フラグ
MAT B=ZER
LET B(A(1))=1 !組み合わせ（動的計画法） 1つ目
LET T=A(1) !※最大値
FOR J=2 TO P !1つずつ選ぶ（2つ目以降）
LET W=A(J)
FOR K=T TO 1 STEP -1 !その数との和
IF B(K)=1 THEN LET B(K+W)=1
NEXT K
LET B(W)=1 !その数のみ
LET T=T+W
NEXT J
FOR K=1 TO N !1からnまでの数字がつくれたか
IF B(K)=0 THEN EXIT FOR
NEXT K
IF K>N THEN !可能なら
LET C=C+1 !結果を表示する
FOR J=1 TO P
PRINT A(J);
NEXT J
PRINT
END IF
ELSE
CALL try(P+1,M-i,A,N) !次へ
END IF
NEXT i
END SUB
EXTERNAL FUNCTION T(n,k) !漸化式
IF k<=1 THEN
LET T=1
ELSE
IF n<2*k-1 THEN
LET T=T(n,INT((n+1)/2))
ELSE
LET T=T(n,k-1)+T(n-k,k)
END IF
END IF
END FUNCTION
|
|
|
|
投稿者：GAI
投稿日：2014年 9月14日(日)10時33分44秒
|
|
|
|
> No.3498[元記事へ]
山中和義さんへのお返事です。
> 問題
> 正の整数が書かれたカードが何枚かあり、全てのカードの和は15であるとする。
> 1以上15以下の任意の整数kに対し、書かれた数の和がkになるように何枚かを選び出すことができという。
> またその選び方は、同じ数の書かれたカードを区別しないものとするとただ1通りである。
> このようなカードの組合せはどのようなものが可能か、全ての組合せを探して下さい。
> 例
> 5の場合、
> 1,1,1,1,1
> 1,1,1,2
> 1,1,3
> 1,2,2
> の4通り
>
これだと、その選び方は、同じ数の書かれたカードを区別しないものとするとただ1通りである。
の条件に反し
1,1,1,2
で２を構成する方法が 1+1,2
の２通り存在することになる。
よって答えは 3通りになります。
|
|
|
|
投稿者：山中和義
投稿日：2014年 9月14日(日)15時14分30秒
|
|
|
|
> No.3498[元記事へ]
発展問題
正の整数が書かれたカードが何枚かあり、全てのカードの和は15であるとする。
1以上15以下の任意の整数kに対し、書かれた数の和がkになるように何枚かを選び出すことができるという。
またその選び方は、同じ数の書かれたカードを区別しないものとするとただ1通りである。
このようなカードの組合せはどのようなものが可能か、全ての組合せを探して下さい。
例
5の場合、
1,1,1,1,1
1,1,3
1,2,2
の3通り
2,1+1や1+1+1,1+2なので、1,1,1,2を除く。
考察
!1種類の数の場合
!1,1,1,…,1
!└ a個 ┘
!題意より、a=n
LET N=15
PRINT "1が";STR$(N);"個"
PRINT
!2種類の数の場合
!1がa個あるので、1からaまでの数はこれで表せるので、2番目の数はa+1である。
!1,1,…,1, a+1,a+1,…,a+1
!└ a個 ┘ └ b個 ┘
!題意より、a+(a+1)b=n ∴(a+1)(b+1)=n+1
!不定方程式を解く。
LET M=N+1
FOR A=2 TO M-1
IF MOD(M,A)=0 THEN !n+1の約数なら（1とn+1は除く）
LET B=M/A
PRINT "1が";STR$(A-1);"個、"; STR$(A);"が";STR$(B-1);"個"
END IF
NEXT A
PRINT
!3種類の数の場合
!1,1,…,1, a+1,a+1,…,a+1, (a+1)(b+1),(a+1)(b+1),…,(a+1)(b+1)=a+(a+1)b+1
!└ a個 ┘ └ b個 ┘ └ c個 ┘
!題意より、a+(a+1)b+(a+1)(b+1)c=n ∴(a+1)(b+1)(c+1)=n+1
!不定方程式を解く。
LET M=N+1
FOR A=2 TO M-1
IF MOD(M,A)=0 THEN !n+1の約数なら
FOR B=2 TO M/A-1
IF MOD(M/A,B)=0 THEN !(n+1)/aの約数なら
LET C=(M/A)/B
PRINT "1が";STR$(A-1);"個、";
PRINT STR$(A);"が";STR$(B-1);"個、";
PRINT STR$(A*B);"が";STR$(C-1);"個"
END IF
NEXT B
END IF
NEXT A
PRINT
!4種類の数の場合
!1,…,1, a+1,…,a+1, (a+1)(b+1),…,(a+1)(b+1), (a+b)(b+1)(c+1),…,(a+b)(b+1)(c+1)=a+(a+1)b+{a+(a+1)b+1}c+1
!└a個┘ └ b個 ┘ └ c個 ┘ └ d個 ┘
!題意より、a +(a+1)b +(a+1)(b+1)c +(a+1)(b+1)(c+1)d = n ∴(a+1)(b+1)(c+1)(d+1)=n+1
!不定方程式を解く。
LET M=N+1
FOR A=2 TO M-1
IF MOD(M,A)=0 THEN !n+1の約数なら
LET M1=M/A
FOR B=2 TO M1-1
IF MOD(M1,B)=0 THEN !(n+1)/aの約数なら
LET M2=M1/B
FOR C=2 TO M2-1
IF MOD(M2,C)=0 THEN !(n+1)/(ab)の約数なら
LET D=M2/C
PRINT "1が";STR$(A-1);"個、";
PRINT STR$(A);"が";STR$(B-1);"個、";
PRINT STR$(A*B);"が";STR$(C-1);"個、";
PRINT STR$(A*B*C);"が";STR$(D-1);"個"
END IF
NEXT C
END IF
NEXT B
END IF
NEXT A
PRINT
!5種類の数の場合
! ：
! ：
END
実行結果
1が15個
1が1個、2が7個
1が3個、4が3個
1が7個、8が1個
1が1個、2が1個、4が3個
1が1個、2が3個、8が1個
1が3個、4が1個、8が1個
1が1個、2が1個、4が1個、8が1個
|
|
|
|
投稿者：山中和義
投稿日：2014年 9月15日(月)10時57分49秒
|
|
|
|
> No.3500[元記事へ]
> 発展問題
> 正の整数が書かれたカードが何枚かあり、全てのカードの和は15であるとする。
> 1以上15以下の任意の整数kに対し、書かれた数の和がkになるように何枚かを選び出すことができるという。
> またその選び方は、同じ数の書かれたカードを区別しないものとするとただ1通りである。
> このようなカードの組合せはどのようなものが可能か、全ての組合せを探して下さい。
> 例
> 5の場合、
> 1,1,1,1,1
> 1,1,3
> 1,2,2
> の3通り
>
> 2,1+1や1+1+1,1+2なので、1,1,1,2を除く。
考察
1,…,1, a+1,…,a+1, (a+1)(b+1),…,(a+1)(b+1), (a+1)(b+1)(c+1),…,(a+1)(b+1)(c+1), …
└a個┘ └ b個 ┘ └ c個 ┘ └ d個 ┘
題意より、a +(a+1)b +(a+1)(b+1)c +(a+1)(b+1)(c+1)d + … = n ∴(a+1)(b+1)(c+1)(d+1) … = n+1
不定方程式を解く。
したがって、数の並びには、n+1の約数が現れる。
構造が見えてきたので、再帰呼出しでプログラムをまとめてみる。
LET N=15
DIM X(N) !個数
PUBLIC NUMERIC C !場合の数
CALL try(1,N+1,X)
PRINT C; "通り"
END
EXTERNAL SUB try(P,M,X()) !バックトラック法で検索する
LET X(P)=M !p種類揃ったなら
LET C=C+1 !結果を表示する
LET T=1
FOR i=1 TO P
PRINT STR$(T);"が";STR$(X(i)-1);"個、";
LET T=T*X(i)
NEXT i
PRINT
FOR A=2 TO M-1
IF MOD(M,A)=0 THEN !約数なら
LET X(P)=A
CALL try(P+1,M/A,X) !次へ
END IF
NEXT A
END SUB
実行結果
1が15個、
1が1個、2が7個、
1が1個、2が1個、4が3個、
1が1個、2が1個、4が1個、8が1個、
1が1個、2が3個、8が1個、
1が3個、4が3個、
1が3個、4が1個、8が1個、
1が7個、8が1個、
8 通り
n=2014のとき、n+1=2015=5×13×31
1が2014個、
1が4個、5が402個、
1が4個、5が12個、65が30個、
1が4個、5が30個、155が12個、
1が12個、13が154個、
1が12個、13が4個、65が30個、
1が12個、13が30個、403が4個、
1が30個、31が64個、
1が30個、31が4個、155が12個、
1が30個、31が12個、403が4個、
1が64個、65が30個、
1が154個、155が12個、
1が402個、403が4個、
13 通り
|
|
|
|
投稿者：GAI
投稿日：2014年 9月16日(火)12時21分16秒
|
|
|
|
> No.3501[元記事へ]
山中和義さんへのお返事です。
すっきりしたプログラムで記述できるんですね。
> n=2014のとき、n+1=2015=5×13×31
>
> 1が2014個、
> 1が4個、5が402個、
> 1が4個、5が12個、65が30個、
> 1が4個、5が30個、155が12個、
> 1が12個、13が154個、
> 1が12個、13が4個、65が30個、
> 1が12個、13が30個、403が4個、
> 1が30個、31が64個、
> 1が30個、31が4個、155が12個、
> 1が30個、31が12個、403が4個、
> 1が64個、65が30個、
> 1が154個、155が12個、
> 1が402個、403が4個、
> 13 通り
これを真似て
n=8639
で実行したら大変なことになりました。
（とても人間業では不可能です。）
なんと76864 通りでした。
（断トツの多さです。第２位 n=9215 の 45568 通り）
|
|
|
戻る