仅在haskell中使用递归的乘积数n =(a ^ 2)*(a ^ 3) [英] The number of the product n=(a^2) * (a^3) using recursion only in haskell

问题描述

在Haskell中，我想找到给定n = (a^2) * (a^3)的给定数字n的a，b对.我必须给出数字，并且它应该返回对.例如:

In Haskell, I want to find how many pairs a,b there are for a given number n, given n = (a^2) * (a^3). I must give the numbers and it should return the pairs. For example:

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).有什么建议?我必须实施没有列表的程序.

So far I have only done a program that for a number n, finds the sum of all possible combinations for n = (a^2) * (a^3). For example, for n=2, (1^2+1^3)+(1^2+2^3)+(2^2+2^3)+(2^2+1^3). Any suggestions? I am required to implement this program without lists.

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

推荐答案

您只想使用递归来实现您首先必须找到一种方法来枚举范围内的所有对.例如.对于您要[(0,0), (0,1), ..., (0,a), (1,0), ..., (1,b), ..., (a,b)]的范围(a, b).第一个想法是从(a, b)开始，减小a直到达到0，然后从(a,b-1)等重新启动.

You want to do it using recursion only You first have to find a way to enumerate all couples in a range. E.g. for the range (a, b) you want [(0,0), (0,1), ..., (0,a), (1,0), ..., (1,b), ..., (a,b)]. The first idea is to start with (a, b), decrease a until it reaches 0 and restart with (a,b-1) etc.

我们可以尝试这样的事情:

We could try something like that:

-- 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的初始值:

When a reaches 0, we want to restart from the initial value of a and decrease b by one. Hence we have to store the initial value of 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的夫妇. (注意:由于我假定n /= 0，所以排除了(0,0)对.如果是n==0，那么您有很多解决方案！).

Now, we don't want all the couples, but only those verifying a*a*b*b*b == n. (Note: I excluded the (0,0) couple since I assume n /= 0. If n==0, then you have a lot of solutions!).

这很简单:

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)]

如果您只想计数，请使用以下方法:

If you only want the count, use this:

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

为便于记录，您可以使用列表推导来完成此操作:

For the record, you can do this with list comprehensions:

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)]

这篇关于仅在haskell中使用递归的乘积数n =(a ^ 2)*(a ^ 3)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！