ETH_Informatik/Informatik_I/Exercise_3/Task_3

Task 3: Loop Analysis

• Task
• Solution

This task is a mixed text/programming task. You need to update the content of loop.cpp according to the instructions provided in the file. For the code part, please check the autograder output.

Task

Consider the following program:

int n;
std::cin >> n;

int x = 1;
if (n > 0) {
  bool e = true;
  do {
    if (--n == 0) {
      e = false;
    }
    x *= 2;
  } while (e);
}
std::cout << x << std::endl;

1. Describe the output of the program as a function of its input \(n\).
2. For which values of \(n\) do you expect a correct output \(x\)? Explain why.
3. Show that this program terminates for all values of \(n\) found in (2). Hint: Make an argument based on the following idea. First prove that the program terminates for the \(n=0\) and \(n=1\). Then show that it terminates for any other \(n\) knowing that it terminates for \(n-1\). This creates a domino effect where the fact that the program terminates for \(n=1\) proves that the program must also terminate for \(n=2\), and this in turn proves that the program must terminate for \(n=3\), and so on. This technique is called "proof by induction".
4. Provide a more elegant implementation of this function using another type of loop. This part is autograded.

Solution

#include "loop.h"
#include <iostream>

// Fill out the file with the required answers

/*

  Subtask 1: Describe the output of the program as a function of its input n.

  This code snippte computes the powers of 2 with a positive exponential. The
  exponential is the input by the user.

*/

/*

  Subtask 2: For which values of n do you expect a correct output x? Explain
  why.

  For a exponential between 0 and 30. Anything below zero would result in the
  wrong answer (1) and anything above 30 would result in an overflow. In
  addition, if we imporved the code to calculate the powers of 2 with negative
  exponents, it would not work since the result of the powers of 2 with negative
  exponents are variables of type float or double and the code snippet is
  working with integers.

*/

/*

  Subtask 3: Show that this program terminates for all values of n found in (2).

  If the input is 31, the output is -2147483648.
  If the input is -1, the output is 1.

*/

/*
  Subtask 4: Provide a more elegant implementation of this function using
  another type of loop.
*/

void loop() {

  int n;
  std::cin >> n;

  int x = 1;

  for (; n > 0; --n)
    x *= 2;

  std::cout << x << std::endl;
}

---

Made by JirR02 in Switzerland 🇨🇭