Рекурсивные функции

@Ivan_C · Регистрация: 11.01.2017

Author24 — интернет-сервис помощи студентам

Функция twopow n, которая вычисляет 2ⁿ, исходя из следующих соображений. Пусть необходимо возвести 2 в степень n.
Если n четно, т.е. n = 2k, то 2ⁿ= 2^2k = (2^k)². Если n нечетно, т.е. n = 2k + 1, то
2ⁿ = 2^2k+1= 2 · (2^2k). Функция twopow не должна использовать оператор ^ или любую функцию возведения в
степень из стандартной библиотеки. Количество рекурсивных вызовов функции должно быть пропорционально logn.

@Curry · 20.01.2018, 23:06

Haskell

twopow  :: Int -> Int
twopow  0 = 1
twopow  n = let (k,m) = n `divMod` 2 
                i     = twopow k
            in (m+1) * i * i

@Catstail · 21.01.2018, 10:04

А вот код, который возвращает кортеж (p,k), где p - степень двойки, а k - число умножений:

Haskell

pow2 :: Integer -> (Integer,Integer)
pow2 0 = (1,0)
pow2 1 = (2,0)
pow2 n | (m==0) = (p*p,k+1)
       | otherwise = (p*p*2,k+2)
         where m = n `mod` 2
               t = n `div` 2
               (p,k) = pow2 t 
 
*Main> pow2 2
(4,1)
*Main> pow2 9
(512,4)
*Main> pow2 40
(1099511627776,6)

@Ivan_C 0 / 0 / 0 Регистрация: 11.01.2017 Сообщений: 12
		1
	Рекурсивные функции 20.01.2018, 22:35. Показов 1482. Ответов 2 Метки нет (Все метки) Функция twopow n, которая вычисляет 2ⁿ, исходя из следующих соображений. Пусть необходимо возвести 2 в степень n. Если n четно, т.е. n = 2k, то 2ⁿ= 2^2k = (2^k)². Если n нечетно, т.е. n = 2k + 1, то 2ⁿ = 2^2k+1= 2 · (2^2k). Функция twopow не должна использовать оператор ^ или любую функцию возведения в степень из стандартной библиотеки. Количество рекурсивных вызовов функции должно быть пропорционально logn. 0

	21.01.2018, 10:04