黑马程序员技术交流社区

标题: 递归函数二 [打印本页]

---

作者: bcair    时间: 2018-10-9 07:44
标题: 递归函数二
函数递归案例二题目

题目出处：Python 点招测试练习题第16题

从 10-200 之间随机获取15个整数，并对这些整数进行如下操作

• 从小到大排序
• 从大到小排序
• 将奇数和偶数分别输出
  
  

代码草稿

函数的思路受 =冒泡排序= 启发

类似上面的案例，先定义一个递归函数 select(L), 每次递归只处理万里长征的一小步。

• 功能：随机在列表 L 索引序列中选出一个索引，将该索引数据和列表最后一位置换，并对自身进行调用（索引范围缩减一）
  
  

  import random
  ​
  def select(L, index_max):
      M = random.randint(len(L))   # for a list, its max index equals to length minus one.
                                   # so M will be selected with the rightly range of list L
      L[index_max], L[M] = L[M], L[index_max]
      select(L, index_max - 1)

由于列表 L 的可变性，每次调用时，直接将其作为参数传递，使得不同调用层的 selec() 函数共享统一的被引用数据对象。

调用 15 次后，列表 L 的后 15 位元素可等价于 在列表中随机选取 15 个数。由于每次置换调用函数的时候，会将最大索引减一，内层调用不会重复选择某个元素。

针对所给例题扩充代码  import random
  ​
  # 创建包含 10 - 200 的列表，索引范围为 [0 - 190]，191 个索引对应列表长度
  list1 = list(range(10, 201))
  index_max = 191 - 1
  ​
  ​
  def select(L, index_max):
      # 程序后面，每次当前调用函数的时候都会最大索引范围减一，排除最大索引，
      # 这样，当前调用在所有的函数调用序列中的次序满足关系
      # order_ = len(list1) - len(L） + 1
      #　例如第一次调用时，参数为 L(和 list1 共享所有引用), len(list1) == len(list_)
      # index_max(L) == len(L) - 1
      order_ = 191 - index_max
      
      if order_ < 15:
          # 调用次数不足 15 次时，随机选取一个索引 index0，将在参数列表中的对应数据和列表最后一个数据交换
          M = random.randint(0, index_max)   # randint 范围为闭区间
          L[M], L[index_max] = L[index_max], L[M]
         
          # `call select()`  + 1
          # 列表参数为当前列表，但将索引最大值减一
          # 每一次调用会排除最后一位索引上的值，避免重复
          select(L, index_max - 1)
      # 第 14 次会成功调用第 15 次，但 15 次不会再次调用，函数递归结束   
      # else: pass
      
      # 在递归结束后，返回列表 L 后 15 位的切片
      return L[-15:]   # don't use L[-15: -0]
  ​
  ​
  # 执行函数 select(), 初始时最大索引为 190
  # 将随机选取列表 list1 中 15 个数，保存到列表 list2 中
  list2 = select(list1, 190)
  ​
  # 打印乱序
  print("the 15 random choosen elements are: %s" % list2)
  ​
  # 从小到大排序，打印
  list2.sort(reverse=False)
  print("stable order of them shows: %s" % list2)
  ​
  # 从大到小, 打印
  list2.sort(reverse=True)
  print("unstable order of them shows: %s" % list2)
  ​
  ​
  # 将奇数和偶数分别输出
  list_odd = []
  list_even = []
  ​
  for _ in list2:
      if _ % 2 == 0:
          list_even.append(_)
      else:
          list_odd.append(_)
  ​
  print("odd numbers are: %s" % list_odd)
  print("even numbers are: %s" % list_even)代码拓展（自定列表，自定选取个数）

上面的代码只能限定在 10 - 190 间取 15 个数，下面的代码可以设定在闭区间 [min0, max0] 内选取最多 max0 - min0 + 1 个数。用一个 shellf 包装一下上面的函数，用 shellf 来输入选择区间和选择数，传给内部的 select 函数，经过两次 return 语句即可得到乱序列表。

对于内层函数来说，以0结尾的局部变量为常数。

  import random
  ​
  min0 = int(input("Set the minimal numer of select range: "))
  max0 = int(input("Set the maximal numer of select range: "))
  num0 = int(input("How many numbers do you want to choose: "))
  ​
  # create function `shellf()` to pass correct paras into `select()` func
  def shellf(min0, max0, num0):
      # generate some useful vars
      list1 = list(range(min0, max0 + 1))
      len0 = max0 - min0 + 1   #  do not ignore the item
      im = max0 - min0         # index_max
  ​
      def select(L, im, len0, num0):
          order_ = len0 - im
          if order_ < num0:
              M = random.randint(0, im)
              L[M], L[im] = L[im], L[M]
              print("%d\tlength of L: %d\t\tindex -> %d\t2 nums for swapping: %d\t*  %d\t*" \
                    % (order_, im + 1, M, L[M], L[im]))
              select(L, im - 1, len0, num0)
          else:
              print("%d\t stop to call"  % order_)
  ​
          return L[(-1 * num0):]   # don't use list_[-num0: -0]
  ​
      print("-" * 60)
      
      list2 = select(list1, im, len0, num0)
  ​
      # scratch order
      print("the %d random choosen elements are: %s" % (num0, list2))
      # from smaller to bigger
      list2.sort()
      print("stable order of them shows: %s" % list2)
      # reverse
      list2.sort(reverse=True)
      print("unstable order of them shows: %s" % list2)
      # separate evens & odds
      lo = []
      le = []
  ​
      for _ in list2:
          if _ % 2 == 0:
              le.append(_)
          else:
              lo.append(_)
  ​
      print("odd numbers are: %s" % lo)
      print("even numbers are: %s" % le)
  ​
      #return list2[:]
  ​
  # call the outter function after input min0, max0, num0
  shellf(min0, max0, num0)

从 [1, 20] 内随机选择 10 个数并排序的输出如下：

  Set the minimal numer of select range: 1
  Set the maximal numer of select range: 20
  How many numbers do you want to choose: 10
  ------------------------------------------------------------
  1   length of L: 20  index -> 9  2 nums for swapping: 20    *  10   *
  2   length of L: 19  index -> 18 2 nums for swapping: 19    *  19   *
  3   length of L: 18  index -> 2  2 nums for swapping: 18    *  3    *
  4   length of L: 17  index -> 4  2 nums for swapping: 17    *  5    *
  5   length of L: 16  index -> 12 2 nums for swapping: 16    *  13   *
  6   length of L: 15  index -> 0  2 nums for swapping: 15    *  1    *
  7   length of L: 14  index -> 13 2 nums for swapping: 14    *  14   *
  8   length of L: 13  index -> 5  2 nums for swapping: 16    *  6    *
  9   length of L: 12  index -> 5  2 nums for swapping: 12    *  16   *
  10   stop to call
  the 10 random choosen elements are: [11, 16, 6, 14, 1, 13, 5, 3, 19, 10]
  stable order of them shows: [1, 3, 5, 6, 10, 11, 13, 14, 16, 19]
  unstable order of them shows: [19, 16, 14, 13, 11, 10, 6, 5, 3, 1]
  odd numbers are: [19, 13, 11, 5, 3, 1]
  even numbers are: [16, 14, 10, 6]

最后一行的输出只是提示不会再次调用函数，实际上本次函数的执行没有问题，会随机选数并置换，懒得写了。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2