Re: [理工] [離散] 遞迴
※ 引述《mqazz1 (無法顯示)》之銘言：
: in how many ways can n symbols from {0,1,...,9} 聯集 {+,*}
: from an arithmetic expression, e.g. 2+13*5 ?
: (a leading + is not allowed)
我假設001這種數字是算合法的(因為題目也沒說..)
設 A[n]是長度為n的方法數
則 A[1] = 10 , A[2] = 100
(0~9) (00~99)
而當長度為n時,依倒數第二個是數字還是運算元來分
可知
A[n] = 10*A[n-1] + 2*10*A[n-2] , n>2
因為前n-1位如果是合法的表示,則第n-1位一定是數字,
如此一來最後一位也只能擺(0~9)所以有10*A[n-1]種排法
若n-1位是運算元,則前n-2位一定要是合法表示,
如此一來有A[n-2]*2*10種放法
有遞迴式以後就剩解遞迴了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.82
推
04/14 18:03, , 1F
04/14 18:03, 1F
討論串 (同標題文章)