代写四个C++的算法小程序，写出规定的时间复杂度的算法即可。
Fibonacci numbers
The Fibonacci numbers are defined by the following recurrence:
F(0) = 0
F(1) = 1, and
F(i) = F(i−1) + F(i−2) for i ≥ 2.
(a) Consider the following algorithm for computing the nth Fibonacci number.
Algorithm 1 Fibonacci
procedure Fibonacci(n)
if n = 0 then
return 0
if n = 1 then
return 1
return Fibonacci(n − 1) + Fibonacci(n − 2)
—|—
Derive a recurrence for Fibonacci(n) and determine the time taken by
Fibonacci(n) in
terms of the input n, expressed in Θ()-notation.
(b) Prove that for any n ≥ 2, F(n) equals A, where A is the nth power of the
following matrix.
(c) Use part (b) to obtain an algorithm that computes F n in O(log n) time.
Selection from two sorted lists
Design an O(log n) time algorithm to select the median from a set of 2n keys
given in the form of two sorted lists, each of length n. For convenience, you
may assume that all of the keys are all distinct.
Briefly justify the correctness of the algorithm. Analyze its running time.
A fault-tolerant OR-gate
Assume we are given an infinite supply of two-input, one-output gates, most of
which are OR gates and some of which are AND gates. Unfortunately the OR and
AND gates have been mixed together and we can’t tell them apart. For a given
integer k ≥ 0, we would like to construct a two-input, one-output
combinational “k-OR” circuit from our supply of two-input, one output gates
such that the following property holds: If at most k of the gates are AND
gates then the circuit correctly implements OR. Assume for simplicity that k
is a power of two.
For a given integer k ≥ 0, we would like to design a k-OR circuit that uses
the smallest number of gates.
(a) Design a 1-OR circuit with the smallest number of gates. Argue the
correctness of your circuit.
(b) Using a 1-OR circuit as a black box, design a 2-OR circuit. Argue the
correctness of your circuit.
(c) Generalizing the above approach, or using a different approach, design the
best possible k-OR circuit you can and derive a Θ-bound (in terms of the
parameter k) for the number of gates in your k-OR circuit. Argue the
correctness of your circuit.
Reconstructing a total order
A group of n runners finished a close race. Unfortunately, the officials at
the finish line were unable to note down the order in which the racers
finished. Each runner, however, noted the jersey number of the runner
finishing immediately ahead of her or him. (There were no ties.) The race
officials ask each runner to give an ordered pair, containing two pieces of
information: (i) first, his or her own jersey number and (ii) second, the
jersey number of the runner who finished immediately ahead of him or her. The
winner of the race, who did not see anybody finish ahead of her, did not turn
any information in.
You have been asked to design an algorithm that takes as input the n − 1 pairs
and returns the order in which the runners finished the race. Assume each
runner is honest.
(a) Give a deterministic O(n log n) time algorithm.
(b) Give a randomized algorithm with expected running time O(n).
You need not prove the correctness of your algorithms. In each case, analyze
the running time of your algorithm.
