fun, that computes a number obtained by multiplying the previous number by 2 and then subtracting 3. The first number is 7. Thus,
n fun(n) ------------------------ 1 7 2 2*7 - 3 = 11 3 2*11 - 3 = 19 4 2*19 - 3 = 35 etcThe function should return the n-th such number, when given a value for n, and should throw an exception for invalid inputs.
int fun(int n)
{
if (n < 1) // invalid cases
throw std::domain_error("n must be positive.");
else
if (n == 1) // base case
return 7;
else
{
// make the recursive call
return (2 * fun(n-1) - 3);
}
}
num_friends be the number of people to send the message to (in the example above, num_friends was 10) and let depth be the depth of the chain, that is, how many "levels" the message goes through without interruption. For example, if I sent one message to 10 friends, and each of them sent to 10 other friends, we'd have a depth of 2. At this point, there have been 110 messages sent total (10 that I sent, plus 10 sent by each of the 10 people who received it from me).
num_friends and of depth. Let's call that function numMessagesSent, so that its header is
long long int numMessagesSent(int num_friends, int depth)The reason for the
long long int is that we'll be needing very large integers. Now, see if you agree with this reasoning:
num_friends. Each of those people will also send that many messages, so the total number of messages sent because of a single person is:
numMessagesSent(num_friends, depth) =
num_friends + num_friends * numMessagesSent(num_friends, depth - 1)
which you can simplify to
numMessagesSent(num_friends, depth) =
num_friends * (1 + numMessagesSent(num_friends, depth - 1))
Aha! This is a recursive relation, isn't it? Now we need a base case. Going back to the example above, we see that when depth is 1, that is, when I send my messages and no one continues the chain, then the total number of messages sent is simply how many messages I sent, namely, num_friends. Thus, the base case is:
numMessagesSent(num_friends, 1) = num_friendsOk, now for what you have to do. Write the C++ implementation of the recursive function
long long int numMessagesSent(int num_friends, int depth)Don't worry about invalid inputs, since you can make sure that all inputs are valid when you call the function. Then, write a
main() program asking the user for how many friends he wants to send the message to and to which depth he hopes people will keep the chain going. Then, print those two inputs as well as the total number of messages which will be sent. Try your program with num_friends equal to, say, 3 and depth equal to, say, 20. Keep in mind that there are approximately 6.3 billion people in the world today.
#include <iostream>
long long int numMessagesSent(int num_friends, int depth)
{
if (depth == 1) // base case
return num_friends;
else
{
// make the recursive call
return (num_friends *
(1 + numMessagesSent(num_friends, depth - 1)));
}
}
int main()
{
std::cout << "Let's spam-flood the internet!"
<< std::endl;
// use a loop to ask the user for proper input
// num_friends must be greater than zero
int num_friends = 0;
while (num_friends <= 0)
{
std::cout << "Please enter how many people to send a message to..."
<< std::endl;
std::cin >> num_friends;
}
// use a loop to ask the user for proper input
// depth must be greater than zero
int depth = 0;
while (depth <= 0)
{
std::cout << "Please enter how many levels you hope the chain will"
<< " go through unbroken..."
<< std::endl;
std::cin >> depth;
}
std::cout << "This is how many messages total will have been sent: "
<< std::endl
<< numMessagesSent(num_friends, depth)
<< std::endl;
return 0;
}
Here's an actual run:
Let's spam-flood the internet!
Please enter how many people to send a message to...
3
Please enter how many levels you hope the chain will go through unbroken...
20
This is how many messages total will have been sent:
5230176600
Notice that even sending the message to a small number of people and using a reasonably small depth, we still end up sending almost one message per person on the planet! So, please, never join those email chain letters, even if the reason sounds good (virus alerts, pleas to help sick children, environmental causes, etc).
int powersOf2(int n) to compute powers of 2, using the fact that
2^n = 2^(n/2) * 2^(n/2), if n is even 2^n = 2 * 2^((n-1)/2) * 2^((n-1)/2), if n is odd 2^n = 1, if n equals 0Make sure to account for invalid inputs, such as negative n values.
int powersOf2(int n)
{
if (n < 0) // invalid cases
throw std::domain_error("n must be positive.");
else
if (n == 0) // base case
return 1;
else // n > 0
{
// make the recursive calls, depending on
// whether n is even or odd
if (n % 2 == 0)
{
// n is even
int pow = powersOf2(n / 2);
return (pow * pow);
}
else
{
// n is odd
int pow = powersOf2((n - 1) / 2);
return (2 * pow * pow);
}
}
}
Note that: (1) we don't have to worry about integer division when dividing (n-1) by 2 because when n is odd, (n-1) is even, so it's divisible by 2; and (2) it's wise to save the result of the recursive call into a temporary variable so that we don't waste time computing the same thing twice. That is, I wrote
int pow = powersOf2(n / 2); return (pow * pow);rather than
return (powersOf2(n / 2) * powersOf2(n / 2));Likewise for the odd case. Remember: CS 14 is about writing efficient code!
max that returns the maximum element of an array.
template<class T>
T max(const T a[], const unsigned int length)
{
T the_max = a[0];
for (unsigned int i = 1; i < length; ++i)
{
if (a[i] > the_max)
{ the_max = a[i]; }
}
return the_max;
}
sum that returns the sum of all elements of an array.
template<class T>
T sum(const T a[], const unsigned int length)
{
T the_sum = a[0];
for (unsigned int i = 1; i < length; ++i)
{ the_sum += a[i]; }
return the_sum;
}
swap4() that takes four arguments and swaps them cyclically. For example, if the type was int and if a = 1, b = 2, c = 3, and d = 4 before the function is called, then after swap4(a, b, c, d) is called, we'll have a = 2, b = 3, c = 4, and d = 1. Calling it again would result in a = 3, b = 4, c = 1, and d = 2. Calling it one more time would result in a = 4, b = 1, c = 2, and d = 3.
swap function we discussed in lecture. This one, too, must take its arguments by reference.
template<class T>
void swap4(T & a, T & b, T & c, T & d)
{
T temp = a;
a = b;
b = c;
c = d;
d = temp;
}
O(1)." I want an explanation for what O(1) and constant time both mean.
O(1) when the time it takes to execute does not depend on the size of the input to the operation. Thus, for example, the assignment int x = y takes the same time regardless of whether y equals 0 or 1 billion. It is, therefore, an operation taking constant time.
void f(int a[], int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = n - 3; j < n; ++j)
{
a[i] = i + j;
}
}
}
Solution: Nope, it's not O(n^2). Just because you have two nested loops, it does not always mean that you have an O(n^2) operation. Here, it's easy to see that j always goes through only 3 values, regardless of the value of n. Since that happens for each value of the outer loop variable i, which does go through n values, the total number of iterations is 3n, that is, O(n).
void f(int a[], int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = n / 2; j < n; ++j)
{
a[i] = i + j;
}
}
}
Solution: The inner loop variable j goes through (n / 2) values, which does depend on the value of n. Since that happens for each value of the outer loop variable i, which does go through n values, the total number of iterations is n * (n / 2), that is, O(n^2).
void f(int a[], int n)
{
for (int i = 0; i < n; ++i)
{
// some operation that takes O(n*log(n)) to execute
for (int j = 0; j < 5; ++j)
{
// some operation that takes O(log(n)) to execute
}
}
}
Solution: For each iteration of the outer loop variable i, which goes through n values, we have one O(n*log(n)) operation and exactly 5 executions of a O(log(n)) operation. Thus, each i iteration takes time O(n*log(n) + 5*log(n)) = O((n+5)*log(n)). The 5 is irrelevant compared to n (think of what happens when n is very large), so each i iteration takes time O(n*log(n)). Since there are n such iterations, the total time spent executing this function is O(n^2*log(n)).
n! is the factorial of n.
O(n), O(n!), O(log(n)), O(sqrt(n)), O(n^2), O(n*log(n))Solution:
O(n!), O(n^2), O(n*log(n)), O(n), O(sqrt(n)), O(log(n))
© 2003 UC Riverside Department of Computer Science & Engineering. All rights reserved.