代写R, matlab程序、代做代写R经济统计语言、代做Newton’s Method

日期：2018-07-12 03:24

E. Fink

3300 Problems, Section 5: Newton’s Method, Numerical Integration; Functions; Searching and Sorting

Dictionaries

1. Use two iterations of Newton’s method starting with the value 1 to estimate a solution to the equation x

2 ? 6 = 0.

2. Estimate R 8

4

√

1 + x

4dx using Simpson’s rule, with N = 4. Do not simplify your answer.

3. Consider the following program:

def f(a):

print(a)

a = a + 1

return a + 2

def main():

x = 2

y = f(x)

print(x, y)

main()

What will print out?

4. Determine what the following code displays.

def fn(x, y):

x = x + 1

y = y + 2

return x + y

def main():

a = 10

y = 20

c = fn(y,a)

d = fn(c,a)

print(a,y,c,d)

main()

5. Determine what the following code displays.

def add1_to_first(x):

x[0] += 1

return x

def main():

y = [4,5,6]

z = add1_to_first(y)

print(y, z)

main()

6. What will be displayed by the following?

glob1 = 5

glob2 = 6

def fn(x):

x += glob1

glob2 = x

return [x, glob2]

def main():

print(fn(3), glob1, glob2)

main()

7. What will be displayed by the following function?

def recu(x):

if x <= 2:

return 8

return x + recu(x-2)

def main():

print(recu(5))

main()

8. What will be displayed by the following function?

def recu(x):

if x <= 2:

return 8

return [x, recu(x-2)]

def main():

print(recu(5))

main()

9. I have an attempt at a recursive version of the factorial function. It doesn’t work. Explain what happens when I call,

say, fact3. How can I fix it?

def fact(x):

return x * fact(x-1)

10. I have the following function which computes the nth Fibonacci number. When I run fib(100), the program appears

to freeze up. Explain why.

def fib(n):

if n <= 2:

return 1

else:

return fib(n-1) + fib(n-2)

11. Write a function called my sum, which takes a list of numbers as input, and returns the sum of those numbers, using NO

LOOPS: use recursion (and slicing) instead!

12. Write a recursive function called dog, which takes as input a positive float, and returns the number of times you can

divide that number by 2 before you get an answer ≤ 1. For instance, dog(9) should return 4, because if you divide 9 by

2 you get 4.5; when you 4.5 by 2 you get 2.25; when you divide 2.25 by 2 you get 1.125; and finally, when you divide

1.125 by 2 you get 0.5625 which is ≤ 1. You should use NO LOOPS, and NO MATH functions other than +,-,*,/ and

comparisons (<, >, <=, >=).

13. What will print when the following code is run?

def fn(my_num, my_list):

my_num += 1

my_list[0] += 1

a_number = 10

a_list = [4,8,2,3]

x = fn(a_number, a_list)

2

print(a_number)

print(a_list)

print(x)

14. Write a function called update, which takes one list parameter as input, adds 1 to each entry, and returns nothing. For

example, when the following code is run, the list [5, 7, 9, 10] should print out:

x = [4, 6, 8, 9]

update(x)

print(x)

15. Recall the formula e

x ≈ 1 +

x

1! +

x

2

2! +

x

3

3! + . . . +

x

n

n!

, where n can be any integer greater than 1. The higher the value

of n, the more accurate your estimate is.

Write a program that asks the user to input a value of x, and a power n, that outputs an approximation to e

x using the

terms up to power n. For example, if the user enter 0.1 for x and 3 for n, the program should output 1.10517, because

1 +

0.1

1! +

0.1

2

2! +

0.1

3

3! = 1.10517 (when rounded).

For full credit, accomplish this using two functions. One should be called myExp that computes the approximation:

this function should have two parameters, a float named x and an int named n, and should return the approximate

value of e

x using the terms up to that power. The other should be called fact: it should take an int n as input, and

return n factorial.

16. A pyramidal number is a number that is the sum of the first n consecutive square integers. So, the first pyramidal

number is 1 (since 12 = 1); the second pyramidal number is 5 (since 12 + 22 = 5); the third pyramidal number is 14

(since 12 + 22 + 32 = 14); and so on.

Write a program that allows the user to input an integer n, and the prints out the first n pyramidal numbers. For

example, if the user enters 3, the program would print out the first 3 pyramidal numbers: 1, 5, and 14, each on a

different line.

For full credit, write and use a function called pyr whose input is an integer x, and whose output is the xth pyramidal

number. For example, the value of pyr(3) should be 14.

Your program and function only need to work if the inputs are positive integers.

17. Write a program that asks the user to enter integer values n and k, and then computes n choose k (you may have seen

this written as nCk or 

n

k



), which is given by the formula n!

k!(n ? k)!. For example, 5C2 =

5!

2!3! =

120

2 · 6

= 10.

For full credit, use a function as part of your program – you probably want to write the factorial operation as a

function; otherwise, you will need several loops, instead of just one!

Your program only needs to work if the entered n and k values are 0 or positive.

18. Write a whole program that does the following: The program should create 8-letter passwords, made up of 8 random

letters, until the user is satisfied.

Specifically, it should do the following repeatedly: first, it should print out a random password. Then, it should ask the

user if the password is satisfactory. If the user enters y, the program ends; if the user enters n, everything repeats. (You

may assume the user enters only y or n.)

For full credit, you should use a FUNCTION that takes NO arguments, and returns a string (the random password).

Hints: to create a random letter, import random and string, and use random.choice(string.ascii letters). To

create the full random password, start with an empty string, and += random lowercase letters on to the end, one letter

at a time.

19. Two words are called granagrams if they have the same number of g’s AND the same number of r’s in them. For

instance, greening and reigning are granagrams, because they each have two g’s and one r. ggrrrh and rrxkabgrg

are granagrams, while rage and garbage are not.

Write a whole program that does the following: first, it asks the user to enter two words. Then, the program will print

Granagrams or Not Granagrams depending on whether those two words are granagrams. ASSUME that all letters

entered are LOWERCASE, and each word contains no spaces.

3

For full credit, you should use a FUNCTION – or perhaps a couple, your choice – which returns a count of the number

of appearances of a certain letter in a string. So your function(s) should have at least one argument which is a string,

and should return an int – beyond that is up to you. DO NOT USE .count()!

20. A palindrome is a word that reads the same forwards and backwards, for example racecar or abba. Write a program

that checks whether an integer entered by the user is a palindrome. Example run:

Enter a word: racecar

That’s a palindrome!

or:

Enter a word: plant

Nope, not a palindrome.

(In these examples, racecar and plant are user input.)

You must do it as follows for full credit: first, have the user enter the word. Then, you should write a function called

my reverse, which takes in a string as an argument, and then returns a new string which is the input reversed. (So, for

example, if x = "Hello", then when I write print(my reverse(x)) it would print out olleH.) You should also use this

function!

Hints: write the main() function first; hopefully that is easy. Then write the function. In the function, you should start

with a new empty string for output, and then loop through the input backwards, adding on one character to the input

at a time. DO NOT USE reversed().

21. Consider the following code, which performs a sort on a list called numbers:

for pos in range(len(numbers)):

min_pos = pos

for j in range(pos+1, len(numbers)):

print("Hey")

if numbers[j] < numbers[min_pos]:

min_pos = j

temp = numbers[pos]

numbers[pos] = numbers[min_pos]

numbers[min_pos] = temp

The code also contains a print statement. If the length of numbers is 4, exactly how many times will "Hey" print? If

the length of numbers is 400, approximately how many times will "Hey" print?

22. The function below is a broken version of the binary search.

def search(s_list, value):

"""Return True if value is in the sorted list called s_list, return False otherwise"""

lower_bound = 0

upper_bound = len(sorted_list) - 1

while lower_bound <= upper_bound:

halfway = (lower_bound + upper_bound)//2 #

if s_list[halfway] == value:

return True

return False

a. Give an example of a list x and a value val such that search(x, val) returns True as intended.

b. Give an example of a list x and a value val such that search(x, val) does not work. Explain what happens instead.

23. Illustrate the steps of the selection sort working on the list [4, 12, 2, 8, 16, 1].

24. Suppose that I perform the merge sort on the list [4, 12, 2, 8, 16, 1, 9, 10]. The merge sort involves performing several

different merges of sorted sub-lists. Write down all the different lists that are produced after a merge has taken place.

(For example: [4, 12] is produced after merging the list [4] and the list [12], so that would be the first list. There should

be 6 other lists of various sizes that are produced by merges; write them all down.)

25. If I perform mergesort on a list of 1000 numbers, approximately how many comparisons will be made between numbers

as part of the merges? (Note: 1000 ≈ 2

10.)

4

26. Here’s a slightly different version of selection sort:

def selectionSort(my_list):

for fill_slot in range(len(my_list)-1,0,-1):

pos_of_max=0

for location in range(1,fill_slot+1):

if ??????????????????????:

pos_of_max = location

temp = my_list[fill_slot]

my_list[fill_slot] = my_list[pos_of_max]

my_list[pos_of_max] = temp

Fill in the question mark line carefully.

27. I have a dictionary defined by

the_dict = {"a":1, "b":3, "c":5, "d":2, "e":6}

Write code that adds the key "f" to this dictionary with value 0. Then, write code (using a loop) which prints each

key-value pair in the dict on its own line.

28. I have a dictionary defined by

new_dict = {"a":1, "b":3, "c":5, "d":2, "e":6}

Write code that asks the user to input a letter, and then either adds 1 to the appropriate value (if the input is already a

key in new dict), or creates a new entry in new dict (if the input is not already a key).

29. Suppose that I have the following code:

n = ["Joey", "Frank", "Lenny", "Mary", "Caroline", "Tony"]

values = [40, 80, 225, 60, 90, 55]

Write code that will combine these lists into a dictionary named d, using a loop (or a zip, if you prefer). The names

should be the keys, so that afterwards, for example,

print(d["Joey"] + d["Frank"])

would cause 120 to print on the console.

30. Write a function called find value, which takes a dictionary dic and a value val as arguments. The function should

return a list of all the keys whose value in dic is equal to val.

31. Suppose that I have a sentence contained in a long string variable named x. For example

x = "this is a long sentence it is a sentence with words"

Create a dictionary called counts. The keys in counts will be all the words that appear in x; the values will be the

number of times that each word appears. You may assume no punctuation, all the characters are lowercase, and there is

a space between each word in the string.

5