03b-exercises.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programming with Python\n",
    "#### Vedran Šego, [vsego.org](http://vsego.org/)\n",
    "\n",
    "## Exercises: Functions\n",
    "\n",
    "When asked to write a function as a part of a problem, also write a program that lets us test that function. This program should get whatever input is meaningful for testing this function, call it with these arguments, and print (in some form) what it returned."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 1.** Write a function `max_digit(n, d, r)` that works like `digit_sum` from the lectures but, instead of returning the sum of the digits of `n`, returns the maximum digit of `n` that gives the reminder `r` when divided by `d`. Assign the appropriate default values for any of the parameters for which it makes sense to do so.\n",
    "\n",
    "Notice that this maximum is undefined for some numbers. Situations like this are usually handled with exceptions, which will be covered later in this course. For now, detect the problematic case(s) and return an invalid value `-1`.\n",
    "\n",
    "Do not forget to write a program that tests this function, i.e., that loads numbers `n`, `d`, and `r`, and prints maximum digit of `n` that  gives the reminder `r` when divided by `d`. If such a digit doesn't exist, the program has to print an appropriate message (instead of printing `-1`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 2.** Write a function `binom(n, k)` that returns the [binomial coefficient](http://en.wikipedia.org/wiki/Binomial_coefficient)\n",
    "$$\\binom{n}{k} := \\frac{n!}{k!(n-k)!}$$\n",
    "for given natural numbers `n` and `k`. Return zero when $n < 0$ or $k < 0$.\n",
    "\n",
    "Be careful to compute and return an integer (not a floating point number).\n",
    "\n",
    "Also, write `binomf(n, k)` which does the same thing using the floating point arithmetics (but otherwise exactly the same algorithm).\n",
    "\n",
    "Write a program that will load `n` and `k`, and print `binom(n, k)`, `binomf(n, k)`, and the difference of these two values. See what happens for fairly large inputs (for example, `(n, k) = (100, 50)`).\n",
    "\n",
    "If you want to make a more general function that will work correctly for all real values of $n$, you can check your results at [Wolfram|Alpha](http://www.wolframalpha.com/), for example like [this](http://www.wolframalpha.com/input/?i=binomial%28100%2C50%29)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 3.** Write a function `prime(n)` that returns `True` if `n` is a [prime number](http://en.wikipedia.org/wiki/Prime_number) and `False` otherwise. You may use the definition as a criterion:\n",
    "\n",
    "> A number $n$ is prime if it is a natural number with exactly two distinct divisors.  \n",
    "> Equivalently, $n$ is prime if $n > 1$ and is not divisible by any integer strictly between 1 and `n`.\n",
    "\n",
    "We shall look at a more efficient algorithm in one of the future lectures.\n",
    "\n",
    "Write a program that loads integers until it gets a negative number of a zero. Using the function `prime(n)`, the program should print the product of all the loaded prime numbers. If no primes were loaded, the program should instead write an appropriate descriptive message."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 4.** We say that a number $n$ is *rich* if its absolute value is smaller than the sum of all its divisors except itself. For example, $12 < 1+2+3+4+6 = 16$ is considered rich, while $16 > 1+2+4+8 = 15$ is not.\n",
    "\n",
    "Write a function `rich(n)` that returns `True` if `n` is rich and `False` otherwise.\n",
    "\n",
    "Further, write a program that loads a number $k \\in \\mathbb{N}$ and prints all the rich numbers between $1$ and $k$ (inclusive).\n",
    "\n",
    "For example, the rich numbers smaller than $50$ are: $12, 18, 20, 24, 30, 36, 40, 42, 48$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursive functions\n",
    "\n",
    "The next two problems go beyond the scope of the course. However, they may be useful, especially to those students interested in combinatorics, so they are here for those who want to try them.\n",
    "\n",
    "**These two will not be part of any exams!**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 5.** Write a function `f` that takes an integer parameter `x` and returns the value\n",
    "$$f(x) = \\begin{cases}\n",
    "   f(17 - |x|), & x < 2, \\\\\n",
    "   f(d), & \\text{$x$ is a composite number and $d$ is its largest divisor such that $d < x$}, \\\\\n",
    "   x, & \\text{otherwise}.\n",
    "\\end{cases}$$\n",
    "We say that $x$ is a composite number if $x > 1$ and $x$ is not a prime.\n",
    "\n",
    "Write a program that loads `x` until it loads `x = 0` and writes the value `f(x)` for each of the loaded numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 6.** Write a function `f` that takes an integer parameter `x` and returns the value\n",
    "$$f(x) = \\begin{cases}\n",
    "   x^2, & x < 9, \\\\\n",
    "   f(g(x)), & \\text{$x \\ge 9$ is even}, \\\\\n",
    "   f(h(x+1)), & \\text{otherwise},\n",
    "\\end{cases}$$\n",
    "where $g(x) = \\left\\lceil \\frac{x}{2} \\right\\rceil$ is the [ceiling](http://en.wikipedia.org/wiki/Floor_and_ceiling_functions) of $\\frac{x}{2}$ and $h(x) = \\left\\lfloor \\frac{x}{2} + 1 \\right\\rfloor$ is the floor of $\\frac{x}{2}+1$.\n",
    "\n",
    "Write a program that loads `x` until it loads `x = 0` and writes the value `f(x)` for each of the loaded numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Hints for Problems 5 and 6:**\n",
    "\n",
    "* These are simple examples of [recursive functions](http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursive_functions_and_algorithms). A function in Python (and most other modern languages) can invoke itself just like it can invoke any other function. However, there are two major things to remember:\n",
    "  * As we have mentioned before, the local variables are local to each invocation. So, if a function that invokes itself has a parameter `x`, then there will be two variables `x` in the memory, each belonging to its own invocation. The two are in no way related (apart from having the same name), and each invocation will see only its own `x`.\n",
    "  * There must exist values of the input parameters for which the function does not invoke itself (so called *terminating cases*). Without that, the function will invoke itself indefinitely (or, more precisely, until the program runs out of the available memory).\n",
    "\n",
    "* Here is a sketch how such a function may look:\n",
    "\n",
    "    ```python3\n",
    "    def f(x):\n",
    "        if some_condition:\n",
    "            return f(some_expression)\n",
    "        if some other condition:\n",
    "            return f(some_other_expression)\n",
    "        ...\n",
    "        return an_expression_that_covers_the_case_when_no_prior_condition_was_met\n",
    "    ```\n",
    "\n",
    "* Write auxiliary functions (the one for finding $d$ in Problem 5, $h$ and $g$ in Problem 6), to make it easier to organize and read your code."
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 0
}