The first tasks are available via jupyter c++
[use of vector]
Write a program that gets a sequence of integer numbers from the standard input stopping the sequence when a character, rather than a number, is encountered.
Output the sequence of numbers in sorted order and indicate the number of elements in the sequence and the largest number.
Output the sequence removing repeated entries.
Modify the program to achieve the same or similar result with words rather than with numbers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
// Create a vector containing integers
vector<int> v = {};
// Add integers to vector
for (int i=0; i<10; i=i+1) {
int n = 0;
cin >> n;
v.push_back(n);
}
cout << "\n";
// Sort vector
sort(v.begin(), v.end());
// Iterate and print values of vector
for(int n : v) {
cout << n << '\n';
}
cout << "\n";
cout << "Length: " << v.size() << "\n";
cout << "\n";
cout << "Largest number: " << v[v.size()-1] << "\n";
cout << "\n";
// Remove repeated entries
v.erase(unique(v.begin(), v.end()), v.end());
// Iterate and print values of vector
for(int n : v) {
cout << n << '\n';
}
}
[use of switch structure]
Write a program that reads from standard input a number and a currency
among yen, dollars and puonds and converts it to Danish krone. For
Example, 1 $ should give 6,50 DKK.
Use the switch structure to decide from which currency to translate.
#include <iostream>
using namespace std;
int main () {
double yen_dkk_rate = 0.0573208;
double dollar_dkk_rate = 6.4808814;
double pound_dkk_rate = 8.5353208;
double amount = 0;
char currency;
cout << "Please enter an amount of money followed by a currency\n" << "Currencies supported:\n" << "y for Japanese yen\n" << "d for US dollars\n" << "p for British pound\n";
cin >> amount >> currency;
switch(currency) {
case 'y':
cout << amount << " Japanese yen equals to " << amount*yen_dkk_rate << " dkk\n";
break;
case 'd':
cout << amount << " US dollars equals to " << amount*dollar_dkk_rate << " dkk\n";
break;
case 'p':
cout << amount << " British pound equals to " << amount*pound_dkk_rate << " dkk\n";
break;
default:
cout << "Invalid currency" << endl;
}
return 0;
}
[use of functions]
Modify the program from task 10 with integers such that it always outputs the median of the sequence. See Wikipedia for a definition of median. Implement the calculation of the median in a function that takes as input the vector and outputs the median.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// new functions how to be declared before the main function
int median(vector<int> v) {
if (v.size() % 2 == 0) {
return (v[v.size() / 2 - 1] + v[v.size() / 2]) / 2;
} else {
return v[v.size() / 2];
}
}
int main()
{
// Create a vector containing integers
vector<int> v = {};
// Add integers to vector
for (int i=0; i<9; i=i+1) {
int n = 0;
cin >> n;
v.push_back(n);
}
cout << "\n";
// Sort vector
sort(v.begin(), v.end());
int m = median(v);
cout << "The result is: " << m << endl;
// if we want to return a decimal value, we have to init the values to be double instead of int
}
This is exercise 5 from Chapter 4 of [BS].
Write a program to play a numbers guessing game. The user thinks of a
number between 1 and 100 and your program asks questions to figure
out what the number is (e.g., “Is the number you are thinking of less than
50?”). Your program should be able to identify the number after asking
no more than seven questions. Hint: Use the < and <= operators and the
if-else construct.
We solve the problem by binary search. We have two alternatives, one in which we check if the value is the same as the thought number and one in which the number will be the one left when the interval becomes closed.
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int max = 100;
cout << "Think about a number between 1 and "<< max << endl;
int left = 1;
int right = max;
while (left != right) {
int m = ceil((left + right) / 2.0);
char reply;
cout << "Is the number < " << m << "?" << endl;
cin >> reply;
if (reply == 'y')
right = m-1;
else
left = m;
}
cout << "the number was: " << left << endl;
return 0;
}
A recursive version:
#include <iostream>
#include <cmath>
using namespace std;
int binary_search(int left, int right) {
if (left == right) return left;
int m = ceil((left + right) / 2.0);
char reply;
cout << "Is the number < " << m << "?" << endl;
cin >> reply;
if (reply == 'y')
return binary_search(left, m-1);
else
return binary_search(m, right);
}
int main() {
int max = 100;
cout << "Think about a number between 1 and "<< max << endl;
int guess = binary_search(1,max);
cout << "the number was: " << guess << endl;
return 0;
}
This is exercise 8 from Chapter 4 of [BS].
There is an old story that the emperor wanted to thank the inventor of
the game of chess and asked the inventor to name his reward. The inven-
tor asked for one grain of rice for the first square, 2 for the second,
4 for the third, and so on, doubling for each of the 64 squares. That
may sound modest, but there wasn’t that much rice in the empire! Write a
program to calculate how many squares are required to give the inventor
at least 1000 grains of rice, at least 1,000,000 grains, and at least
1,000,000,000 grains. You’ll need a loop, of course, and probably an
int to keep track of which square you are at, an int to keep the number
of grains on the current square, and an int to keep track of the grains
on all previous squares. We suggest that you write out the value of all
your variables for each iteration of the loop so that you can see what’s
going on.
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
const vector<int> milestones = {1000, 1000000, 1000000000};
int main()
{
int rice = 0;
int square = 1;
int square_rice = 1;
deque<bool> milestone_flags;
size_t milestone_hits = 0;
for (size_t i=0; i<milestones.size(); ++i)
milestone_flags.push_back(false);
while (milestone_hits < milestones.size()) {
cout << "Square (" << square << "):\n"
<< "\tPrevious rice accumulated:\t " << rice << " grains.\n"
<< "\tRice on current square:\t\t " << square_rice << " grains.\n"
<< "\tTotal rice:\t\t\t " << rice+square_rice << " grains.\n";
rice += square_rice;
for (size_t i=0; i<milestones.size(); ++i) {
if (rice >= milestones[i] && !milestone_flags[i]) {
cout << "\nThe inventor now has at least " << milestones[i]
<< " grains of rice, just by square " << square << "!!!\n\n";
milestone_flags[i] = true;
++milestone_hits;
}
}
square_rice *= 2;
++square;
}
return 0;
}
This is exercise 9 from Chapter 4 of [BS].
Try to calculate the number of rice grains that the inventor asked for
in exercise 8 above. You’ll find that the number is so large that it
won’t fit in an int or a double. Observe what happens when the number
gets too large to represent exactly as an int and as a double. What is
the largest number of squares for which you can calculate the exact
number of grains (using an int)? What is the largest number of squares
for which you can calculate the approximate number of grains (using a
double)?
#include <iostream>
using namespace std;
int main()
{
int rice = 0;
int square_rice = 1;
double drice = 0;
double dsquare_rice = 1;
for (int square=1; square <= 64; ++square) {
rice += square_rice;
drice += dsquare_rice;
square_rice *= 2;
dsquare_rice *= 2;
cout << "Square " << square << ": int rice (" << rice << "), double rice (" << drice << ")\n";
}
return 0;
}
This is exercise 13 from Chapter 4 of [BS].
Create a program to find all the prime numbers between 1 and 100. There is a classic method for doing this, called the “Sieve of Eratosthenes.” If you don’t know that method, get on the web and look it up. Write your program using this method.
// Comments:
// The method (as stated by wikipedia at
// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) is:
// 1 - Create a list of consecutive integers from 2 through n.
// 2 - Initially, let p equal 2, the smallest primer number.
// 3 - Enumerate the multiplies of p by counting to n from 2p in increments
// of p, and mark them in the list. The p itself should not be marked.
// 4 - Find the first number greater than p in the list that is not marked.
// If there was not a such number, stop. Otherwise, let p now equal this
// new number an repeat from step 3.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int limit = 100;
// (step 1) Use a vector as a list of numbers (its indexes)
// and use the values contained as markers (0 not marked, 1 marked).
// As stated in page 118, this vector will have "limit+1" elements
// initialized to zero.
vector<int> primes(limit+1);
for (int i=2; i <= limit; ++i) {
// (step 2 and 4) If not marked, this is the next prime (initially 2, as step 2 of the
// method).
if ( primes[i] == 0 ){
// step 3
int m {i+i};
while (m <= limit) {
primes[m] = 1;
m += i;
}
}
}
cout << "Primes between 1 and " << limit << ":\n";
for (int i=2; i <= limit; ++i)
if (primes[i] == 0) cout << i << '\n';
return 0;
}