Assign-7-10185102232-魏明达.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 华东师范大学计算机科学技术系作业\n",
    "\n",
    " | 华东师范大学计算机科学技术系作业 | |\n",
    ":- | :- | :- \n",
    " 课程名称：编程导论Python | 年级：2018级| 作业成绩：\n",
    " 指导教师：兰曼 | 姓名：魏明达  |  提交作业日期：2018年11月28日  \n",
    " 专业：计算机系 | 学号：10185102232 |  作业编号： 7\n",
    " -----------------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一、异常处理练习。假设输入一组任意长度列表，我们要对该列表中第10个元素进行加1操作，请利用try-except模型自己实现一个异常处理，可以捕获IndexError异常。\n",
    "<br/>\n",
    "（15分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "列表长度不够！\n"
     ]
    }
   ],
   "source": [
    "L = [1,1,1,1,1,1,1,1,1]\n",
    "try:\n",
    "    L[9]+=1\n",
    "except IndexError:\n",
    "    print('列表长度不够！')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二、\t用二分法的递归方式求n个元素列表的最大值和最小值，改写本章的<程序：求数列最大最小值——二分法>，传递参数时不用分片，而是用它在原来列表的索引及长度。然后分析程序的开销，开销的增长趋势是什么？\n",
    "<br/>\n",
    "（15分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 55)\n"
     ]
    }
   ],
   "source": [
    "def find_min_max(L,i,j):\n",
    "    if j==i+1:\n",
    "        if L[i]<L[j]:return L[i],L[j]\n",
    "        else:return L[j],L[i]\n",
    "    if i==j:return L[i],L[i]\n",
    "    if len(L[i:j])==0:return [],[]\n",
    "    min1,max1 = find_min_max(L,i,i+(j-i)//2)\n",
    "    min2,max2 = find_min_max(L,i+(j-i)//2,j)\n",
    "    if min1>min2:min1=min2\n",
    "    if max1<max2:max1=max2\n",
    "    return min1,max2\n",
    "    \n",
    "L = [1,2,3,4,5,0,5,4,8,8,5,1,0,55]\n",
    "print(find_min_max(L,0,len(L)-1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分析：T(n) = 2T(n/2)+θ(0), T(n) = θ(n) 所以增长趋势是线性的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "三、用二分法的递归方式实现求给定数列L中所有元素的平均数。例如给定数列L=[12,32,45,78,22]，则该数列平均数为(12+32+45+78+22)/5=37.8。\n",
    "<br/>\n",
    "（15分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "37.8"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(L):\n",
    "    if len(L) == 1:return L[0]\n",
    "    if len(L) == 0:return 0\n",
    "    return (f(L[:len(L)//2])+f(L[len(L)//2:]))\n",
    "\n",
    "L=[12,32,45,78,22]\n",
    "f(L)/len(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "四、用递归方法实现求给定正整数n的阶乘n!。例如n=3，则n的阶乘为$1*2*3=6$。\n",
    "<br/>\n",
    "（15分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(n):\n",
    "    if n == 1:return 1\n",
    "    return f(n-1)*n\n",
    "f(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "五、用递归方法实现求给定列表L中所有元素的最小值。如L=[11,15,9,14,8,5]，则最小数为5。\n",
    "<br/>\n",
    "（15分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(L):\n",
    "    if len(L) == 1:return L[0]\n",
    "    if f(L[:len(L)//2])<f(L[len(L)//2:]):return f(L[:len(L)//2])\n",
    "    else:return f(L[len(L)//2:])\n",
    "    \n",
    "L=[11,15,9,14,8,5]\n",
    "f(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "六、调用import time库，编写一个程序能测试<程序：非递归实现my_remove>和它的较好程序的时间差异。建议所要删除的元素是一个长列表的最后一个。\n",
    "<br/>\n",
    "（15分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bad：0.000047，good:0.000043\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "def my_remove1(L,x):\n",
    "    if not x in L:return L\n",
    "    A=[]\n",
    "    for i in range(len(L)):\n",
    "        if L[i] == x:A=A+L[i+1:];break\n",
    "        A = A+[L[i]]\n",
    "    return A\n",
    "\n",
    "def my_remove2(L,x):\n",
    "    A=L[:]\n",
    "    for i in range(len(L)):\n",
    "        if L[i]==x:A=A[:i]+A[i+1:];break\n",
    "    return A\n",
    "\n",
    "L = [2,2,2,2,2,2,22,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]\n",
    "start = time.clock()\n",
    "my_remove1(L,2)\n",
    "a = time.clock()-start\n",
    "start = time.clock()\n",
    "my_remove2(L,2)\n",
    "b = time.clock()-start\n",
    "print('bad：%f，good:%f' % (a,b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "七、解释<程序：递归实现my_remove2使用二分法>的终止条件，为何要考虑长度为1的情形？\n",
    "<br/>\n",
    "（10分）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解释：在len(L)==1时，L[len(L)//2:]始终等于L，意味着此时会导致死循环"
   ]
  }
 ],
 "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}