W4D4_pair.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def prob1(int):\n",
    "    sum=0\n",
    "    for x in range(math.floor(int/5)):\n",
    "        sum+=1\n",
    "    return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob1(12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob1(75)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prob2(int):\n",
    "    x = math.floor(int/5)\n",
    "    y = math.floor(int/10)\n",
    "    return x+y+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob2(77)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prob3(int):\n",
    "    x = math.floor(int/5)\n",
    "    y = math.floor(int/10)\n",
    "    z =  math.floor(int/25)\n",
    "    return x+y+z+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob3(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "def prob1(cents):\n",
    "    ways = 0\n",
    "    for n in range(0,cents+1):\n",
    "        for p in range(0,cents+1):\n",
    "            if 5*n + p == cents:\n",
    "                ways +=1\n",
    "    return ways\n",
    "\n",
    "def prob2(cents):\n",
    "    ways = 0\n",
    "    for n in range(0, cents+1):\n",
    "        for p in range(0, cents+1):\n",
    "            for d in range(0, cents+1):\n",
    "                if 10*d + 5*n + p == cents:\n",
    "                    ways +=1\n",
    "    return ways\n",
    "\n",
    "def prob3(cents):\n",
    "    ways = 0\n",
    "    for q in range(0, cents+1):\n",
    "        for p in range(0, cents+1):\n",
    "            for d in range(0, cents+1):\n",
    "                for n in range(0, cents+1):\n",
    "                    if 25*q + 10*d + 5*n + p == cents:\n",
    "                        ways +=1\n",
    "    return ways"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "72"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob2(77)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "121"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob3(77)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "17%5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "math.floor(17/5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prob4(cents, list):\n",
    "    ways = 0\n",
    "    for item in list:\n",
    "        for x in range(0, cents+1):\n",
    "            if item*x == cents:\n",
    "                ways +=1\n",
    "    return ways\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def recur4(cents, types):\n",
    "    for item in types:\n",
    "        if cents == 0:\n",
    "            return 1\n",
    "    return recur4(cents-item)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ways2(cents, coins=[25,10,5,1]):\n",
    "    if cents <0 or not coins:\n",
    "        return 0\n",
    "    if cents == 0:\n",
    "        return 1\n",
    "    return ways2(cents - coins[0], coins) + ways2(cents, coins[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "242"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ways2(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ways4(cents, coins=[1,5,10,25]):\n",
    "    nb_combinations = [1]+[0]*5\n",
    "    for coin in coins:\n",
    "        for sub_case in range(coin, cents+1):\n",
    "            nb_combinations[sub_case] += nb_combinations[sub_case-coin]\n",
    "            \n",
    "    return nb_combinations[cents]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-59-156ce658c757>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mways4\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m21\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-58-7db36c1de1b9>\u001b[0m in \u001b[0;36mways4\u001b[0;34m(cents, coins)\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mcoin\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcoins\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m         \u001b[0;32mfor\u001b[0m \u001b[0msub_case\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcoin\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcents\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m             \u001b[0mnb_combinations\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0msub_case\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0mnb_combinations\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0msub_case\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0mcoin\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mnb_combinations\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mcents\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "ways4(21)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}