Номер произведения n = (a ^ 2) * (a ^ 3) с использованием рекурсии только в haskell - PullRequest
Новая
       16

Номер произведения n = (a ^ 2) * (a ^ 3) с использованием рекурсии только в haskell

0 голосов
/ 17 марта 2019

В Хаскеле я хочу узнать, сколько пар a, b существует для данного числа n, данного n = (a^2) * (a^3).Я должен дать цифры, и он должен вернуть пары.Например: 

Main> count 24
0
Main> count 72
1
Main> count 256
2
Main> count 4096
3
Main> count 46656
4

До сих пор я сделал только программу, которая для числа n находит сумму всех возможных комбинаций для n = (a^2) * (a^3).Например, для n=2, (1^2+1^3)+(1^2+2^3)+(2^2+2^3)+(2^2+1^3).Какие-либо предложения?Мне необходимо реализовать эту программу без списков. 

sumF :: (Int->Int)->Int->Int
sumF f 0 = 0
sumF f n = sumF f (n-1) + f n



sumF1n1n :: (Int->Int->Int)->Int->Int
sumF1n1n f 0 = 0
sumF1n1n f n = sumF1n1n f (n-1)
    +sumF (\i -> f i n) (n-1)
    +sumF (\j -> f n j) (n-1)
    +f n n

func :: Int->Int->Int
func 0 0 = 0
func a b = res
    where
    res = (a^2*b^3)

call :: Int->Int
call n = sumF1n1n func n

1 Ответ

0 голосов
/ 22 марта 2019

Вы хотите сделать это, используя только рекурсию. Сначала вы должны найти способ перечислить все пары в диапазоне.Например, для диапазона (a, b) вы хотите [(0,0), (0,1), ..., (0,a), (1,0), ..., (1,b), ..., (a,b)].Первая идея - начать с (a, b), уменьшать a до достижения 0 и перезапускать с (a,b-1) и т. Д.

Мы можем попробовать что-то подобное: 

-- doesn't work
couples 0 0 = [(0,0)]
-- what to do when a reaches 0?   v
couples 0 b = [(0,b)] ++ couples *?* (b-1)
couples a b = [(a,b)] ++ couples (a-1) b

Когда a достигает 0, мы хотим перезапустить с начального значения a и уменьшить b на единицу.Следовательно, мы должны сохранить начальное значение a: 

couples' 0 0 _ = [(0,0)]
-- use max_a to set the restart
couples' 0 b max_a = [(0,b)] ++ couples' max_a (b-1) max_a
couples' a b max_a = [(a,b)] ++ couples' (a-1) b max_a

Это работает: 

couples a b = couples' a b a
main = print $ couples 3 2
-- [(3,2),(2,2),(1,2),(0,2),(3,1),(2,1),(1,1),(0,1),(3,0),(2,0),(1,0),(0,0)]

Теперь нам нужны не все пары, а только проверяющие a*a*b*b*b == n.(Примечание: я исключил пару (0,0), поскольку я предполагаю n /= 0. Если n==0, то у вас есть много решений!).

Это просто как: 

call' _ 0 0 _ = []
call' n 0 b max_a = call' n max_a (b-1) max_a
call' n a b max_a = (if n==a*a*b*b*b then [(a,b)] else []) ++ call' n (a-1) b max_a

Если я напишу: 

call n = call' n max max max
        where max = (ceiling.sqrt.fromIntegral) n

Я получу следующие результаты: 

call 24
-- []
call 72
-- [(3,2)]
call 256
-- [(2,4),(16,1)]
call 4096
-- [(1,16),(8,4),(64,1)]
call 46656
-- [(1,36),(8,9),(27,4),(216,1)]

Если вытолько для подсчета, используйте это: 

call' _ 0 0 _ = 0
call' n 0 b max_a = call' n max_a (b-1) max_a
call' n a b max_a = (if n==a*a*b*b*b then 1 else 0) + call' n (a-1) b max_a

Для записи вы можете сделать это со списком: 

Prelude> couples a b = [(i,j)| i<-[0..a], j<-[0..b]]
Prelude> couples 3 2
[(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0),(3,1),(3,2)]

И: 

Prelude> call n = [(a,b)| let max = (ceiling.sqrt.fromIntegral) n, a<-[0..max], b<-[0..max], n==a*a*b*b*b]
Prelude> call 24
[]
Prelude> call 72
[(3,2)]
Prelude> call 256
[(2,4),(16,1)]
Prelude> call 4096
[(1,16),(8,4),(64,1)]
Prelude> call 46656
[(1,36),(8,9),(27,4),(216,1)]
...