Week06.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Programming Problems"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" GCD - method 1 \"\"\"\n",
    "def GCD(x, y):\n",
    "    gcd = 1\n",
    "    for i in range(1, min(x, y)):  # could pick one\n",
    "        if x % i == 0 and y % i == 0:\n",
    "            gcd = i\n",
    "    return gcd\n",
    "\n",
    "print(GCD(6, 8))  # should be 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" GCD - method 2 \"\"\"\n",
    "def GCD(x, y):\n",
    "    while y != 0:\n",
    "        temp = y\n",
    "        y = x % y\n",
    "        x = temp\n",
    "    return x\n",
    "\n",
    "print(GCD(6, 8))  # should be 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" nth fibonacci number \"\"\"\n",
    "def fibonacci(x):\n",
    "    return x if x <= 1 else fibonacci(x - 1) + fibonacci(x - 2)\n",
    "\n",
    "# sequence goes 0, 1, 1, 2, 3, 5, ...\n",
    "print(fibonacci(4)) # should be 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" Challenge: square root \"\"\"\n",
    "def sqrt(x):\n",
    "    digit = 1.0\n",
    "    # find first digit\n",
    "    while x % digit >= 10.0:\n",
    "        digit *= 10.0\n",
    "    ans = 0\n",
    "    # add at each digit until highest\n",
    "    while digit > pow(0.1, 6):\n",
    "        for i in range(10):\n",
    "            ans += digit\n",
    "            if ans * ans > x:\n",
    "                ans -= digit\n",
    "                break\n",
    "        digit /= 10.0\n",
    "    # NOTE: this solution doesn't round.\n",
    "    return ans\n",
    "\n",
    "print(sqrt(4))  # should be 2\n",
    "print(sqrt(2))  # should be 1.41421"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "aee8b7b246df8f9039afb4144a1f6fd8d2ca17a180786b69acc140d282b71a49"
  },
  "kernelspec": {
   "display_name": "Python 3.9.1 64-bit",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.10"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}