Geek Answers Handbook

Changed by Fibonacci: how to fix this algorithm?

I have this problem in front of me and I can’t figure out how to solve it. This is about the series 0,1,1,2,5,29,866...(Each number, except the first two, is the sum of the squares of the previous two numbers (2^2+5^2=29)). In the first part I had to write an algorithm (not a native speaker, so I really don’t know the terminology), which would get a place in the series and return its value ( 6 returned 29) Here is how I wrote it:

public static int mod(int n)
{
    if (n==1)
        return 0;
    if (n==2)
        return 1;
    else
        return (int)(Math.pow(mod(n-1), 2))+(int)(Math.pow(mod(n-2), 2));
}

However, now I need the algorithm to get the number and return the total amount before it in the series (6- 29+5+2+1+1+0=38) I do not know how to do this, I try, but so far I really can not understand the recursion, even if I wrote something correctly, How can I check this to be sure? And how to achieve the correct algorithm?

.

!

+6
5

:

mod(1) = 0
mod(2) = 0+1
mod(3) = 0+1+1
mod(4) = 0+1+1+2
mod(5) = 0+1+1+2+5
mod(6) = 0+1+1+2+5+29

, :

   2^2+5^2=29

, mod (7) x mod (6).

, mod:

 x = term(5)^2 + term(6)^2
 term(5) = mod(5) - mod(4)
 term(6) = mod(6) - mod(5)
 x = (mod(5)-mod(4))^2 + (mod(6)-mod(5))^2

, mod (7), mod (4), mod (5), mod (6) .

, , memoize !

Python:

def f(n):
    if n<=0:
        return 0
    if n==1:
        return 1
    a=f(n-1)
    b=f(n-2)
    c=f(n-3)
    return a+(a-b)**2+(b-c)**2

for n in range(10):
    print f(n)

:

0
1
2
4
9
38
904
751701
563697636866
317754178345850590849300
+4

, . : . - :

int f(int n) {
    if (n > 0)
        return f(-n) + f(n-1);
    else if (n > -2)
        return 0;
    else if (n == -2)
        return 1;
    else
        return f(n+1)*f(n+1)+f(n+2)*f(n+2);
}

8 ( ):

0
1
2
4
9
38
904
751701

, , .

+2

?:)

class Main {

  public static void main(String[] args) {
    final int N = 6; // Your number here.
    System.out.println(result(N));
  }

  private static long result(final int n) {
    if (n == 0) {
      return 0;
    } else {
      return element(n) + result(n - 1);
    }
  }

  private static long element(final int n) {
    if (n == 1) {
      return 0L;
    } else if (n == 2) {
      return 1L;
    } else {
      return sqr(element(n - 2)) + sqr(element(n - 1));
    }
  }

  private static long sqr(final long x) {
    return x * x;
  }
}

, (element) n- , result . , . .

+2

.

, :

f (n) = 0; n < 2

f (n) = 1; 2 >= n <= 3

f (n) = f (n-1) ^ 2 + f (n-2) ^ 2; > 3

:

f(0)= 0
f(1)= 0
f(2)= f(1) + f(0) = 1
f(3)= f(2) + f(1) = 1
f(4)= f(3) + f(2) = 2
f(5)= f(4) + f(3) = 5
and so on

:

= f (n); n = 0: k; k > 0

, , . , , :

class Dummy 
{

    public static void main (String[] args) throws InterruptedException {

        int n=10;

        for(int i=1; i<=n; i++)
        {
            System.out.println("--------------------------");
            System.out.println("Total for n:" + i +" = " + Dummy.f(i));
        }
    }

    private static int counter = 0;
    public static long f(int n)
    {   
        counter++;

        if(counter == 1)
        {
            long total = 0;
            while(n>=0)
            {    
                total +=  f(n);
                n--;
            }
            counter--;
            return total;
        }

        long result = 0;
        long n1=0,n2=0;

        if(n >= 2 && n <=3)
            result++; //Increase 1
        else if(n>3)
        {
            n1 = f(n-1);
            n2 = f(n-2);

            result = n1*n1 + n2*n2;
        }

        counter--;
        return result;
    }
}

:

--------------------------
Total for n:1 = 0
--------------------------
Total for n:2 = 1
--------------------------
Total for n:3 = 2
--------------------------
Total for n:4 = 4
--------------------------
Total for n:5 = 9
--------------------------
Total for n:6 = 38
--------------------------
Total for n:7 = 904
--------------------------
Total for n:8 = 751701
--------------------------
Total for n:9 = 563697636866
--------------------------
Total for n:10 = 9011676203564263700

, .

UPDATE: :

class Dummy 
{

    public static void main (String[] args) throws InterruptedException {

        Dummy app = new Dummy();
        int n=10;

        for(int i=1; i<=n; i++)
        {
            System.out.println("--------------------------");
            System.out.println("Total for n:" + i +" = " + app.mod(i));
        }
    }

    private static int counter = 0;
    public long mod(int n)
    {   
        Dummy.counter++;

        if(counter == 1)
        {
            long total = 0;
            while(n>=0)
            {    
                total +=  mod(n);
                n--;
            }
            Dummy.counter--;
            return total;
        }

        long result = 0;
        long n1=0,n2=0;

        if(n >= 2 && n <=3)
            result++; //Increase 1
        else if(n>3)
        {
            n1 = mod(n-1);
            n2 = mod(n-2);

            result = n1*n1 + n2*n2;
        }

        Dummy.counter--;
        return result;
    }
}
0

| Memoized , . memoization.

def FibonacciModified(n):
    fib = [0]*n
    fib[0],fib[1]=0,1
    for idx in range(2,n):
        fib[idx] = fib[idx-1]**2 + fib[idx-2]**2
    return fib

if __name__ == '__main__':
    fib = FibonacciModified(8)
    for x in fib:
        print x

Output:

0
1
1
2
5
29
866
750797

The above will calculate each number in a row once [no more]. In recursion, an element in a series will be calculated several times, regardless of the fact that the number was calculated earlier.

http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

0
source

More articles:


All Articles