book_learning_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 《Problem Solving with Algorithms and Data Structures using Python》 的学习笔记和课后作业答案（一. intro）\n",
    "\n",
    "```\n",
    "对应本书第一章。\n",
    "```\n",
    "\n",
    "## 目录\n",
    "\n",
    "* [0.简介](#0.简介)\n",
    "* [1.intro](#1.intro)\n",
    "    + [笔记](#笔记)\n",
    "    + [作业](#作业)\n",
    "        + [q1-to-q9 Fraction类](#q1-to-q9)\n",
    "        + [q10 实现NAND, NOR, 和 XOR](#q10)\n",
    "        + [q11 实现half-adder](#q11)\n",
    "        + [q12 实现full adder](#q12)\n",
    "        \n",
    "# 0.简介\n",
    "\n",
    "![](https://raw.githubusercontent.com/applenob/algorithm_note/master/res/cover.jpg)\n",
    "\n",
    "这本书的[豆瓣评分](https://book.douban.com/subject/3098386/)高达9.3，python作为接近算法伪码的一种脚本语言，其实用它写算法是极好的，可以将注意力集中在算法本身。\n",
    "\n",
    "但是由于python性能的问题，用python写算法不算太主流，因此市面上介绍算法的书也多以使用c/c++或者Java居多。\n",
    "\n",
    "这本书几乎是用python介绍算法豆瓣评分最高的一本书了，网上可以下到pdf，但最好的阅读方式是直接使用这本书的[网站](http://interactivepython.org/courselib/static/pythonds/index.html)。这本书貌似也是拿ipython notebook写的，还可以直接在网站上运行示例程序。self check的部分还有作者视频讲解，这才是编程类书籍的未来嘛！\n",
    "\n",
    "这里我记录每章的学习笔记，同时记录每章课后作业的个人解决代码，统一使用python3。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1.intro\n",
    "\n",
    "## 笔记 \n",
    "\n",
    "这章主要给python做了个简短介绍，魔术方法部分以前没有仔细学习过，看看感觉挺好用，可以让自定义的方法看起来像内建的方法。\n",
    "\n",
    "[python 官方文档关于operator的表格](https://docs.python.org/2/library/operator.html)\n",
    "\n",
    "![](https://raw.githubusercontent.com/applenob/algorithm_note/master/res/table1.png)\n",
    "![](https://raw.githubusercontent.com/applenob/algorithm_note/master/res/table2.png)\n",
    "\n",
    "两个不错的学习链接：\n",
    "\n",
    "- [PYTHON-进阶-魔术方法小结(方法运算符重载)](http://wklken.me/posts/2012/10/29/python-base-magic.html)\n",
    "\n",
    "- [Python 魔术方法指南](http://pycoders-weekly-chinese.readthedocs.io/en/latest/issue6/a-guide-to-pythons-magic-methods.html)\n",
    "\n",
    "## 作业\n",
    "\n",
    "[作业链接](http://interactivepython.org/courselib/static/pythonds/Introduction/ProgrammingExercises.html)\n",
    "\n",
    "### q1 to q9\n",
    "\n",
    "完善处理分式的Fraction类。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def gcd(m,n):\n",
    "    \"\"\"求两个数最大公因数\"\"\"\n",
    "    while m%n != 0:\n",
    "        oldm = m\n",
    "        oldn = n\n",
    "\n",
    "        m = oldn\n",
    "        n = oldm%oldn\n",
    "    return n\n",
    "\n",
    "class Fraction:\n",
    "    \"\"\"处理分数的类\"\"\"\n",
    "    def __init__(self,top,bottom):\n",
    "        # q5 检查分子分母是否都是整数\n",
    "        if not isinstance(top, int) or not isinstance(bottom, int):\n",
    "            raise Exception(\"top or bottom of Fraction is not int type!\")\n",
    "        # q2 初始化时直接约分\n",
    "        common = gcd(top,bottom)\n",
    "        self.num = top//common\n",
    "        self.den = bottom//common\n",
    "        \n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.num)+\"/\"+str(self.den)\n",
    "\n",
    "    def show(self):\n",
    "        print(self.num,\"/\",self.den)\n",
    "\n",
    "    def __add__(self,other):\n",
    "        # q2\n",
    "        newnum = self.num*other.den + \\\n",
    "                 self.den*other.num\n",
    "        newden = self.den * other.den\n",
    "        return Fraction(newnum,newden)\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        firstnum = self.num * other.den\n",
    "        secondnum = other.num * self.den\n",
    "\n",
    "        return firstnum == secondnum\n",
    "    \n",
    "    # q1\n",
    "    def getNum(self):\n",
    "        return self.num\n",
    "    \n",
    "    def getDen(self):\n",
    "        return self.den\n",
    "    \n",
    "    # q3\n",
    "    def __sub__(self, other):\n",
    "        newnum = self.num*other.den - \\\n",
    "                 other.num*self.den\n",
    "        newden = self.den * other.den\n",
    "        return Fraction(newnum, newden)\n",
    "    \n",
    "    def __mul__(self, other):\n",
    "        return Fraction(self.num*other.num, self.den*other.den)\n",
    "    \n",
    "    def __truediv__(self, other):\n",
    "        return Fraction(self.num*other.den, self.den*other.num)\n",
    "    \n",
    "    # q4\n",
    "    def __gt__(self, other): \n",
    "        if self.num*other.den > self.den*other.num:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def __ge__(self, other): \n",
    "        if self.num*other.den >= self.den*other.num:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def __lt__(self, other): \n",
    "        if self.num*other.den < self.den*other.num:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def __le__(self, other): \n",
    "        if self.num*other.den < self.den*other.num:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def __ne__(self, other): \n",
    "        if self.num*other.den != self.den*other.num:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    # q7\n",
    "    def __radd__(self,other_int):\n",
    "        \"\"\"\n",
    "        Python will first try (4).__add__(myobj), \n",
    "        and if that returns NotImplemented Python will check if \n",
    "        the right-hand operand implements __radd__, and if it does, \n",
    "        it will call myobj.__radd__(4) rather than raising a TypeError.\n",
    "        \"\"\"\n",
    "        newnum = self.num + \\\n",
    "                 self.den*other_int\n",
    "        return Fraction(newnum,self.den)\n",
    "    \n",
    "    # q8\n",
    "    def __iadd__(self, other):\n",
    "        \"\"\"a = iadd(a, b) is equivalent to a += b.\"\"\"\n",
    "        newnum = self.num*other.den + \\\n",
    "                 self.den*other.num\n",
    "        newden = self.den * other.den\n",
    "        return Fraction(newnum, newden)\n",
    "        \n",
    "    # q9\n",
    "    def __repr__(self):\n",
    "        \"\"\"\n",
    "        In short, the goal of __repr__ is to be unambiguous and __str__ is to be readable.\n",
    "        也就是说，__repr__是用于输出更多的关于对象的信息的，而__str__是为了print好看的。\n",
    "        \"\"\"\n",
    "        return \"num:{}, den:{}\".format(self.num, self.den)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7/6\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "x = Fraction(1,2)\n",
    "y = Fraction(2,3)\n",
    "print(x+y)\n",
    "print(x == y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# q1\n",
    "print(x.getNum())\n",
    "print(x.getDen())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2/1\n"
     ]
    }
   ],
   "source": [
    "# q2\n",
    "z = Fraction(10, 5)\n",
    "print(z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3/4\n"
     ]
    }
   ],
   "source": [
    "# q3\n",
    "print(x/y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "False\n",
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# q4\n",
    "print(x>y)\n",
    "print(x>=y)\n",
    "print(x<y)\n",
    "print(x<=y)\n",
    "print(x!=y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "Exception",
     "evalue": "top or bottom of Fraction is not int type!",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mException\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-7-49b67a4c3ca5>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# q5\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mFraction\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1.1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-1-501ce21d5123>\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, top, bottom)\u001b[0m\n\u001b[1;32m     14\u001b[0m         \u001b[0;31m# q5 检查分子分母是否都是整数\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     15\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtop\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbottom\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 16\u001b[0;31m             \u001b[0;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"top or bottom of Fraction is not int type!\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     17\u001b[0m         \u001b[0;31m# q2 初始化时直接约分\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     18\u001b[0m         \u001b[0mcommon\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mgcd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtop\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mbottom\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mException\u001b[0m: top or bottom of Fraction is not int type!"
     ]
    }
   ],
   "source": [
    "# q5\n",
    "Fraction(1.1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1/2\n",
      "-1\n",
      "2\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "# q6\n",
    "w=Fraction(1, -2)\n",
    "print(w)\n",
    "print(w.getNum())\n",
    "print(w.getDen())\n",
    "print(w>x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3/2\n"
     ]
    }
   ],
   "source": [
    "# q7\n",
    "print(1+x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7/6\n"
     ]
    }
   ],
   "source": [
    "# q8\n",
    "x += y\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "num:7, den:6\n"
     ]
    }
   ],
   "source": [
    "# q9\n",
    "\n",
    "print(repr(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "数字电路部分："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter Pin A input for gate G1-->1\n",
      "Enter Pin B input for gate G1-->1\n",
      "Enter Pin A input for gate G2-->1\n",
      "Enter Pin B input for gate G2-->1\n",
      "0\n",
      "Enter Pin A input for gate G1-->1\n",
      "Enter Pin B input for gate G1-->1\n",
      "Enter Pin A input for gate G2-->1\n",
      "Enter Pin B input for gate G2-->1\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# 作者实现的部分\n",
    " \n",
    "class LogicGate:\n",
    "    \"\"\"逻辑门总类\"\"\"\n",
    "    def __init__(self,n):\n",
    "        self.name = n\n",
    "        self.output = None\n",
    "\n",
    "    def getName(self):\n",
    "        return self.name\n",
    "\n",
    "    def getOutput(self):\n",
    "        self.output = self.performGateLogic()\n",
    "        return self.output\n",
    "\n",
    "\n",
    "class BinaryGate(LogicGate):\n",
    "    \"\"\"两个输入引脚的门\"\"\"\n",
    "    def __init__(self,n):\n",
    "        LogicGate.__init__(self,n)\n",
    "\n",
    "        self.pinA = None\n",
    "        self.pinB = None\n",
    "\n",
    "    def getPinA(self):\n",
    "        if self.pinA == None:\n",
    "            return int(input(\"Enter Pin A input for gate \"+self.getName()+\"-->\"))\n",
    "        else:\n",
    "            return self.pinA.getFrom().getOutput()\n",
    "\n",
    "    def getPinB(self):\n",
    "        if self.pinB == None:\n",
    "            return int(input(\"Enter Pin B input for gate \"+self.getName()+\"-->\"))\n",
    "        else:\n",
    "            return self.pinB.getFrom().getOutput()\n",
    "    \n",
    "\n",
    "    def setNextPin(self,source):\n",
    "        \"\"\"有其他逻辑门连接该门的输入\"\"\"\n",
    "        if self.pinA == None:\n",
    "            self.pinA = source\n",
    "        else:\n",
    "            if self.pinB == None:\n",
    "                self.pinB = source\n",
    "            else:\n",
    "                print(\"Cannot Connect: NO EMPTY PINS on this gate\")\n",
    "\n",
    "\n",
    "class AndGate(BinaryGate):\n",
    "    \"\"\"与门\"\"\"\n",
    "    def __init__(self,n):\n",
    "        BinaryGate.__init__(self,n)\n",
    "\n",
    "    def performGateLogic(self):\n",
    "\n",
    "        a = self.getPinA()\n",
    "        b = self.getPinB()\n",
    "        if a==1 and b==1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "class OrGate(BinaryGate):\n",
    "    \"\"\"或门\"\"\"\n",
    "    def __init__(self,n):\n",
    "        BinaryGate.__init__(self,n)\n",
    "\n",
    "    def performGateLogic(self):\n",
    "\n",
    "        a = self.getPinA()\n",
    "        b = self.getPinB()\n",
    "        if a ==1 or b==1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "class UnaryGate(LogicGate):\n",
    "    \"\"\"单个输入引脚的门\"\"\"\n",
    "    def __init__(self,n):\n",
    "        LogicGate.__init__(self,n)\n",
    "\n",
    "        self.pin = None\n",
    "\n",
    "    def getPin(self):\n",
    "        if self.pin == None:\n",
    "            return int(input(\"Enter Pin input for gate \"+self.getName()+\"-->\"))\n",
    "        else:\n",
    "            return self.pin.getFrom().getOutput()\n",
    "\n",
    "    def setNextPin(self,source):\n",
    "        \"\"\"有其他逻辑门连接该门的输入\"\"\"\n",
    "        if self.pin == None:\n",
    "            self.pin = source\n",
    "        else:\n",
    "            print(\"Cannot Connect: NO EMPTY PINS on this gate\")\n",
    "\n",
    "\n",
    "class NotGate(UnaryGate):\n",
    "    \"\"\"非门\"\"\"\n",
    "    def __init__(self,n):\n",
    "        UnaryGate.__init__(self,n)\n",
    "\n",
    "    def performGateLogic(self):\n",
    "        if self.getPin():\n",
    "            return 0\n",
    "        else:\n",
    "            return 1\n",
    "\n",
    "\n",
    "class Connector:\n",
    "    \"\"\"引线\"\"\"\n",
    "    def __init__(self, fgate, tgate):\n",
    "        self.fromgate = fgate\n",
    "        self.togate = tgate\n",
    "\n",
    "        tgate.setNextPin(self)\n",
    "\n",
    "    def getFrom(self):\n",
    "        return self.fromgate\n",
    "\n",
    "    def getTo(self):\n",
    "        return self.togate\n",
    "\n",
    "\n",
    "def main():\n",
    "    g1 = AndGate(\"G1\")\n",
    "    g2 = AndGate(\"G2\")\n",
    "    g3 = OrGate(\"G3\")\n",
    "    g4 = NotGate(\"G4\")\n",
    "    c1 = Connector(g1,g3)\n",
    "    c2 = Connector(g2,g3)\n",
    "    c3 = Connector(g3,g4)\n",
    "    print(g4.getOutput())\n",
    "    print(g4.getPin())\n",
    "\n",
    "main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q10\n",
    "\n",
    "实现NAND, NOR, 和 XOR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# q10 \n",
    "\n",
    "class NANDGate(BinaryGate):\n",
    "    \"\"\"与非门\"\"\"\n",
    "    def __init__(self,n):\n",
    "        BinaryGate.__init__(self,n)\n",
    "\n",
    "    def performGateLogic(self):\n",
    "\n",
    "        a = self.getPinA()\n",
    "        b = self.getPinB()\n",
    "        if a ==1 and b==1:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1\n",
    "        \n",
    "class NORGate(BinaryGate):\n",
    "    \"\"\"或非门\"\"\"\n",
    "    def __init__(self,n):\n",
    "        BinaryGate.__init__(self,n)\n",
    "\n",
    "    def performGateLogic(self):\n",
    "\n",
    "        a = self.getPinA()\n",
    "        b = self.getPinB()\n",
    "        if a ==0 and b==0:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "        \n",
    "class XORGate(BinaryGate):\n",
    "    \"\"\"异或门\"\"\"\n",
    "    def __init__(self,n):\n",
    "        BinaryGate.__init__(self,n)\n",
    "\n",
    "    def performGateLogic(self):\n",
    "\n",
    "        a = self.getPinA()\n",
    "        b = self.getPinB()\n",
    "        if a == b:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q11 \n",
    "\n",
    "实现half-adder\n",
    "\n",
    "half adder的定义可参考[wikipedia](https://en.wikipedia.org/wiki/Adder_(electronics)\n",
    "\n",
    "![](https://raw.githubusercontent.com/applenob/algorithm_note/master/res/Halfadder.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter Pin input for gate I1-->1\n",
      "Enter Pin input for gate I2-->0\n",
      "1\n",
      "Enter Pin input for gate I1-->1\n",
      "Enter Pin input for gate I2-->0\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "class InGate(UnaryGate):\n",
    "    \"\"\"输入门\"\"\"\n",
    "    def __init__(self,n):\n",
    "        UnaryGate.__init__(self,n)\n",
    "\n",
    "    def performGateLogic(self):\n",
    "        if self.getPin():\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "class HalfAdder(BinaryGate):\n",
    "    \n",
    "    def __init__(self, n):\n",
    "        BinaryGate.__init__(self, n)\n",
    "        self.i1 = InGate(\"I1\")\n",
    "        self.i2 = InGate(\"I2\")\n",
    "        self.x1 = XORGate(\"X1\")\n",
    "        self.a1 = AndGate(\"A2\")\n",
    "        c1 = Connector(self.i1, self.x1)\n",
    "        c2 = Connector(self.i2, self.x1)\n",
    "        c3 = Connector(self.i1, self.a1)\n",
    "        c4 = Connector(self.i2, self.a1)\n",
    "         \n",
    "    def setNextPin(self,source):\n",
    "        if self.i1.pin == None:\n",
    "            self.i1.pin = source\n",
    "        elif self.i2.pin == None:\n",
    "            self.i2.pin = source\n",
    "        else:\n",
    "            print(\"Cannot Connect: NO EMPTY PINS on this gate\")\n",
    "\n",
    "    def getSum(self):\n",
    "        return self.x1.getOutput()\n",
    "    \n",
    "    def getCarry(self):\n",
    "        return self.a1.getOutput()\n",
    "        \n",
    "half_adder = HalfAdder(\"Half_Adder\")\n",
    "print(half_adder.getSum())\n",
    "print(half_adder.getCarry())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的实现还是有些缺点，就是因为输出有两个，所以相同的输入要输两次。\n",
    "\n",
    "### q12\n",
    "\n",
    "实现full adder\n",
    "\n",
    " $$ S=A\\oplus B\\oplus C_{in}$$\n",
    " $$ {\\displaystyle C_{\\text{out}}=(A\\cdot B)+(C_{\\text{in}}\\cdot (A\\oplus B))} $$\n",
    " \n",
    " ![](https://raw.githubusercontent.com/applenob/algorithm_note/master/res/Fulladder.gif)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter Pin input for gate I1-->1\n",
      "Enter Pin input for gate I2-->0\n",
      "Enter Pin input for gate I3-->0\n",
      "1\n",
      "Enter Pin input for gate I1-->1\n",
      "Enter Pin input for gate I2-->0\n",
      "Enter Pin input for gate I3-->0\n",
      "Enter Pin input for gate I1-->1\n",
      "Enter Pin input for gate I2-->0\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "# q12\n",
    "\n",
    "class FullAdder(LogicGate):\n",
    "\n",
    "    def __init__(self, n):\n",
    "        LogicGate.__init__(self, n)\n",
    "        self.i1 = InGate(\"I1\")\n",
    "        self.i2 = InGate(\"I2\")\n",
    "        self.i3 = InGate(\"I3\")\n",
    "        self.x1 = XORGate(\"X1\")\n",
    "        self.x2 = XORGate(\"X2\")\n",
    "        self.a1 = AndGate(\"A1\")\n",
    "        self.a2 = AndGate(\"A2\")\n",
    "        self.o1 = XORGate(\"O1\")\n",
    "        c1 = Connector(self.i1, self.x1)\n",
    "        c2 = Connector(self.i2, self.x1)\n",
    "        c3 = Connector(self.x1, self.x2)\n",
    "        c4 = Connector(self.i3, self.x2)\n",
    "        c5 = Connector(self.x1, self.a1)\n",
    "        c6 = Connector(self.i3, self.a1)\n",
    "        c7 = Connector(self.i1, self.a2)\n",
    "        c8 = Connector(self.i2, self.a2)\n",
    "        c9 = Connector(self.a1, self.o1)\n",
    "        c10 = Connector(self.a2, self.o1)\n",
    "         \n",
    "    def setNextPin(self,source):\n",
    "        if self.i1.pin == None:\n",
    "            self.i1.pin = source\n",
    "        elif self.i2.pin == None:\n",
    "            self.i2.pin = source\n",
    "        elif self.i3.pin == None:\n",
    "            self.i3.pin = source\n",
    "        else:\n",
    "            print(\"Cannot Connect: NO EMPTY PINS on this gate\")\n",
    "\n",
    "    def getSum(self):\n",
    "        return self.x2.getOutput()\n",
    "    \n",
    "    def getCarry(self):\n",
    "        return self.o1.getOutput()\n",
    "        \n",
    "full_adder = FullAdder(\"Full_Adder\")\n",
    "print(full_adder.getSum())\n",
    "print(full_adder.getCarry())"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:py35]",
   "language": "python",
   "name": "conda-env-py35-py"
  },
  "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}