3

試験の学習中に、演習で次のタスクを見つけました。

乗算と加算のみを使用しながら、2を底とする整数の対数（切り上げ）を与える関数を記述します。

すぐに試してみましたが、解決できませんでした。それは簡単な作業だと思いましたが、整数除算を使用した場合にのみ解決策を見つけることができました（たとえばHaskellで）：

log2 :: Int -> Int
log2 1 = 0
log2 2 = 1
log2 x = 1 + log2 (x `div` 2)

このタスクは、乗算だけで可能ですか？左側（パターン）で乗算を使用すると、常にコンパイラエラーが発生します。そして、右側でそれを使用して、どうすればソリューションをより低い数値にまでさかのぼることができますか？

4

3 に答える 3

5

そして、右側でそれを使用して、どうすればソリューションをより低い数値にまでさかのぼることができますか？

再帰。フロアの計算が簡単なので、次の事実を使用します。

ceiling (log_2 n) == floor (log_2 (2*n-1))

簡単にわかるように。次に、底辺の対数を見つけるために、底辺bの対数を計算してb²調整します。

log2 :: Int -> Int
log2 1 = 0
log2 2 = 1
log2 n
    | n < 1     = error "Argument of logarithm must be positive"
    | otherwise = fst $ doLog 2 1
      where
        m = 2*n-1
        doLog base acc
            | base*acc > m = (0, acc)
            | otherwise = case doLog (base*base) acc of
                            (e, a) | base*a > m -> (2*e, a)
                                   | otherwise  -> (2*e+1,a*base)

より多くのステップを必要とするより単純なアルゴリズムは、引数の値に達するか超えるまで、単純に反復し、各ステップで2を乗算し、カウントすることです。

log2 :: Int -> Int
log2 n
    | n < 1     = error "agument of logarithm must be positive"
    | otherwise = go 0 1
      where
        go exponent prod
            | prod < n  = go (exponent + 1) (2*prod)
            | otherwise = exponent
于 2013-01-10T22:11:27.770 に答える
3

どうですか：

log2 n = length (takeWhile (<n) (iterate (*2) 1))

？

プレリュードの関数（、、および比較演算子など）を使用できると思いerrorますfst。それが試験で許可されていない場合は、理論的にはの定義を使用して、lengthダニエルtakeWhileのiterate答えに比較的近いものになってしまう可能性があります（精神的には、おそらく手紙にはありません！）。

于 2013-01-16T13:50:00.270 に答える
0

たぶん、級数展開を使用して対数関数を近似することができます。特にテイラーのもの。

于 2013-01-10T22:39:12.980 に答える