4

このプログラミングの問題についてどうすればよいかわかりません。

2 つの整数 n と m が与えられたとき、すべての数字が 0 から n-1 までのすべての数字を持ち、隣接する 2 つの数字の差がちょうど 1 で、数字の桁数が最大で「m」であるような数字がいくつ存在するか.

この問題を解決する最善の方法は何ですか? 直接的な数式はありますか?

編集: 数字は 0 から始めることはできません。

例: n = 3 および m = 6 の場合、18 個の数字 (210、2101、21012、210121 ... など) があります。

更新 (あいまいさに遭遇した人もいます): 0 から n-1 までのすべての数字が存在する必要があります。

4

4 に答える 4

1

1 つの方法として、再帰的にプログラムし、関数を呼び出して最後の桁を加算したり減算したりすることができます。

Haskell コード:

import Data.List (sort,nub)

f n m = concatMap (combs n) [n..m]

combs n m = concatMap (\x -> combs' 1 [x]) [1..n - 1] where
  combs' count result
    | count == m = if test then [concatMap show result] else []
    | otherwise  = combs' (count + 1) (result ++ [r + 1])
                ++ combs' (count + 1) (result ++ [r - 1])
   where r = last result
         test = (nub . sort $ result) == [0..n - 1]

出力：

*Main> f 3 6
["210","1210","1012","2101","12101","10121","21210","21012"
,"21010","121210","121012","121010","101212","101210","101012"
,"212101","210121","210101"]

Anirudh Rayabharam のコメントに応えて、次のコードがより「疑似コード」のようになることを願っています。桁数の合計が に達すると、解がすべての [0..n-1] をハッシュした場合m、関数は1 を出力し、そうでない場合は 0 を出力します。gこの関数は、開始桁数 [1..n-1] と合計桁数 [n..m]fの結果を累積します。g

Haskell コード:

import qualified Data.Set as S

g :: Int -> Int -> Int -> Int -> (S.Set Int, Int) -> Int
g n m digitCount lastDigit (hash,hashCount)
  | digitCount == m = if test then 1 else 0
  | otherwise       =
      if lastDigit == 0
         then g n m d' (lastDigit + 1) (hash'',hashCount')
         else if lastDigit == n - 1
                 then g n m d' (lastDigit - 1) (hash'',hashCount')
                 else g n m d' (lastDigit + 1) (hash'',hashCount') 
                    + g n m d' (lastDigit - 1) (hash'',hashCount') 
 where test = hashCount' == n
       d' = digitCount + 1
       hash'' = if test then S.empty else hash'
       (hash',hashCount')
         | hashCount == n          = (S.empty,hashCount)
         | S.member lastDigit hash = (hash,hashCount)
         | otherwise               = (S.insert lastDigit hash,hashCount + 1)

f n m = foldr forEachNumDigits 0 [n..m] where
  forEachNumDigits numDigits accumulator = 
    accumulator + foldr forEachStartingDigit 0 [1..n - 1] where 
      forEachStartingDigit startingDigit accumulator' =
        accumulator' + g n numDigits 1 startingDigit (S.empty,0)

出力：

*Main> f 3 6
18
(0.01 secs, 571980 bytes)

*Main> f 4 20
62784
(1.23 secs, 97795656 bytes)

*Main> f 4 25
762465
(11.73 secs, 1068373268 bytes)
于 2013-08-20T16:55:13.913 に答える