作問の備忘録

テスト問題を作るときの、大した計算ではないけれども、やろうと思うとめんどくさいことどもを記録。

辞書式配列の問題の解法

地道に性質を調べて式を作っていくだけ。

 

n個の異なる文字 a_0,a_1,\dots,a_{n-1}を辞書式に並べたとき、与えられた文字列が何番目にあるかを求める。

① 文字の若い順に 0,1,2,…,n-1の数を当てはめる。

② その数より左にある数を見て、その数より小さい数が何個あるかを①の下にかく。

③ ①の数から②の数をそれぞれ引く。これを左から順に b_1,b_2,\dots,b_nとする。

④ \displaystyle 1+\sum_{m=1}^{n} b_m (n-m)! 番目

 

「どっちが若い文字か間違える」という数学とは関係ないミスを最小限にできるメリットがあり、導出も生徒の考える練習に良いと思うが、結果だけ覚えてテストで使う人間が出るので一長一短。