1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Ronch [10]
3 years ago
8

The fundamental source of the inefficiency is not the fact that recursive calls are being made, but that values are being recomp

uted. One way around this is to compute the values from the beginning of the sequence instead of from the end, saving them in an array as you go. Although this could be done recursively, it is more natural to do it iteratively. Proceed as follows: a. Add a method fib2 to your Fib class. Like fib1, fib2 should be static and should take an integer and return an integer. b. Inside fib2, create an array of integers the size of the value passed in. c. Initialize the first two elements of the array to 0 and 1, corresponding to the first two elements of the Fibonacci sequence. Then loop through the integers up to the value passed in, computing each element of the array as the sum of the two previous elements. When the array is full, its last element is the element requested. Return this value. d. Modify your TestFib class so that it calls fib2 (first) and prints the result, then calls fib1 and prints that result. You should get the same answers, but very different computation times.

Mathematics
2 answers:
Fudgin [204]3 years ago
8 0

Step-by-step explanation:

<em>(you can download the attached PDF for a better view)</em>

The Fibonacci sequence is a well-known mathematical sequence in which each term is the sum of the two previous terms.

More specifically, if fib(n) is the nth term of the sequence, then the sequence can be defined as follows:

fib(0) = 0

fib(1) = 1

fib(n) = fib(n-1) + fib(n-2) n>1

1. Because the Fibonacci sequence is defined recursively, it is natural to write a recursive method to determine the nth

number in the sequence. File Fib.java contains the skeleton for a class containing a method to compute Fibonacci

numbers. Save this file to your directory. Following the specification above, fill in the code for method fib1 so that it

recursively computes and returns the nth number in the sequence.

2. File TestFib.java contains a simple driver that asks the user for an integer and uses the fib1 method to compute that

element in the Fibonacci sequence. Save this file to your directory and use it to test your fib1 method. First try small

integers, then larger ones. You'll notice that the number doesn't have to get very big before the calculation takes a very

long time. The problem is that the fib1 method is making lots and lots of recursive calls. To see this, add a print

statement at the beginning of your fib1 method that indicates what call is being computed, e.g., "In fib1(3)" if the

parameter is 3. Now run TestFib again and enter 5—you should get a number of messages from your print statement.

Examine these messages and figure out the sequence of calls that generated them. (This is easiest if you first draw the

call tree on paper.) . Since fib(5) is fib(4) + fib(3),you should not be surprised to find calls to fib(4) and fib(3) in the

printout. But why are there two calls to fib(3)? Because both fib(4) and fib(5) need fib(3), so they both compute it—very

inefficient. Run the program again with a slightly larger number and again note the repetition in the calls.

3. The fundamental source of the inefficiency is not the fact that recursive calls are being made, but that values are being

recomputed. One way around this is to compute the values from the beginning of the sequence instead of from the end,

saving them in an array as you go. Although this could be done recursively, it is more natural to do it iteratively. Proceed

as follows:

a. Add a method fib2 to your Fib class. Like fib1, fib2 should be static and should take an integer and return an integer.

b. Inside fib2, create an array of integers the size of the value passed in.

c. Initialize the first two elements of the array to 0 and 1, corresponding to the first two elements of the Fibonacci

sequence. Then loop through the integers up to the value passed in, computing each element of the array as the sum

of the two previous elements. When the array is full, its last element is the element requested. Return this value.

d. Modify your TestFib class so that it calls fib2 (first) and prints the result, then calls fib1 and prints that result. You

should get the same answers, but very different computation times.

// ******************************************************************

// Fib.java

//

// A utility class that provide methods to compute elements of the

// Fibonacci sequence.

// ******************************************************************

public class Fib

{

//--------------------------------------------------------------

// Recursively computes fib(n)

//--------------------------------------------------------------

public static int fib1(int n)

{

//Fill in code -- this should look very much like the

//mathematical specification

}

// ******************************************************************

// TestFib.java

//

// A simple driver that uses the Fib class to compute the

// nth element of the Fibonacci sequence.

// ******************************************************************

import java.util.Scanner;

public class TestFib

{

public static void main(String[] args)

{

int n, fib;

Scanner scan = new Scanner(System.in);

System.out.print("Enter an integer: ");

n = scan.nextInt();

fib = Fib.fib1(n);

System.out.println("Fib(" + n + ") is " + fib);

}

}

Download pdf
sweet-ann [11.9K]3 years ago
7 0

Answer:

Refer below for the answer.

Step-by-step explanation:

Refer to the pictures attached for the code of all four parts.

You might be interested in
20.35 - 08.57 - 09.99 ​
rewona [7]
Your answer will be 1.49
7 0
2 years ago
Read 2 more answers
Jeremiah lives in New York City and takes a taxi almost everywhere he goes. In order to calculate the price of his taxi ride,
ohaa [14]

Answer: 2.50 is the fee he must pay before the taxi takes him anywhere

Step-by-step explanation: since it is an add on, and it is not multiplied by the variable, we know this is a one time expense, meaning it is the base charge.

The answer is A

4 0
3 years ago
A recent study at UGA (March 5, 2008) suggests that students with cell phones may take more risks than students that do not have
Ira Lisetskai [31]

Answer:

(a) -2.8

b) (1) Reject H0: p = 0.50 in favor of HA: p < 0.50; there is sufficient evidence to conclude that less than half of all UGA female students who, if they had a cell phone, would be willing to walk somewhere after dark that they would normally not go.

Step-by-step explanation:

The test statistic is:

z = \frac{X - \mu}{\frac{\sigma}{\sqrt{n}}}

In which X is the sample mean, \mu is the value tested at the null hypothesis, \sigma is the standard deviation and n is the size of the sample.

H0: p = 0.50

This means that:

\mu = 0.5, \sigma = \sqrt{0.5*0.5} = 0.5

In a random sample of 305 UGA female students, 128 responded that, if they had a cell phone, they would be willing to walk somewhere after dark that they would normally not go.

This means that n = 305, X = \frac{128}{305} = 0.4197

a) Value of the test statistic:

z = \frac{X - \mu}{\frac{\sigma}{\sqrt{n}}}

z = \frac{0.4197 - 0.5}{\frac{0.5}{\sqrt{305}}}

z = -2.8

Pvalue:

We are testing the hypothesis that the proportion is less than 0.5, which means that the pvalue of the test is the pvalue of z = -2.81.

Looking at the z-table, z = -2.8 has a pvalue of 0.0026

(b) What is the correct conclusion for this hypothesis test at the 0.05 level of significance?

0.0026 < 0.05, which means that we reject the null hypothesis, that the proportion is 0.5, and accept the alternate hypothesis, that the proportion is less than 0.5, option (1).

6 0
3 years ago
44.69 rounded to the nearest tenth
Romashka-Z-Leto [24]
The answer would be 44.7 not 44.5
3 0
3 years ago
It is what it is<br> ffmijcnrfchnejidxmjked uh rfj9iow,xoecnrubcyemxwkxm
Vesna [10]

Answer:

ok but this shii is fire ash

3 0
3 years ago
Read 2 more answers
Other questions:
  • If a country’s dept to gdp ratio is 142% the country is borrowing more than it is producing.
    10·2 answers
  • I need help again pleade
    11·1 answer
  • DeShawn won 85 super bouncy ball playing basketball at his school's game. Later, he gave three to each of his freinds. He only h
    15·1 answer
  • georgia knows that there is either an additive or multiplicative relationship between x and y.She only knows a single pair of da
    10·1 answer
  • Your great aunt sally loans you $5000 for three years and asks that you repay it with annually compounding interest at the rate
    11·1 answer
  • What is two thirds to the negative cubed power¿
    12·1 answer
  • Solve log base(x − 1) 16 = 4.
    12·2 answers
  • How many solutions does this linear equation system have y=2/3x+2
    8·1 answer
  • Write an equation in slope-intercept form for the line with slope -2/5 and y intercept 5.
    13·1 answer
  • Look at the Stem-and-Leaf charts shown below. What is the lowest value?
    5·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!