[关闭]
@Pigmon 2016-03-16T11:07:56.000000Z 字数 4283 阅读 277

算法作业01-02

Python


0313 压缩目录

这里为了程序更简洁,要先把00.tar.gz先手动解压成一个00目录,和源程序放在同一目录下再运行

  1. #!/usr/bin/python
  2. # -*- coding: UTF-8 -*-
  3. import os, tarfile, sys
  4. # 解除递归次数限制
  5. sys.setrecursionlimit(20000);
  6. # --------------------------------------
  7. # 解压.tar.gz
  8. # @Param:file - 文件路径
  9. # --------------------------------------
  10. def unpack(file):
  11. arch = tarfile.open(file, 'r:gz');
  12. for tarinfo in arch:
  13. arch.extract(tarinfo, os.getcwd());
  14. arch.close();
  15. # --------------------------------------
  16. # 判断一个路径是否为.tar.gz
  17. # @Param:_path - 文件路径
  18. # @Return - True / False
  19. # --------------------------------------
  20. def is_gz(_path):
  21. return (os.path.splitext(_path)[1] == '.gz');
  22. # --------------------------------------
  23. # 判断一个路径是否为文件夹
  24. # @Param:_path - 文件路径
  25. # @Return - True / False
  26. # --------------------------------------
  27. def is_dir(_path):
  28. return os.path.isdir(_path);
  29. # --------------------------------------
  30. # 去掉一个.tar.gz的后缀和前置路径
  31. # @Param:_path - 文件路径
  32. # @Return - Base Name
  33. # --------------------------------------
  34. def base_name(_path):
  35. base_path = os.path.basename(_path);
  36. return os.path.splitext(os.path.splitext(base_path)[0])[0];
  37. # --------------------------------------
  38. # 从一个文本文件中读取数字
  39. # @Param:_path - 文件路径
  40. # @Return - 文本中的数字
  41. # --------------------------------------
  42. def read_number(_path):
  43. fo = open(_path, "r");
  44. str_num = fo.read();
  45. fo.close();
  46. num = int(str_num);
  47. return num;
  48. # --------------------------------------
  49. # 读取一个目录下所有成员
  50. # @Param:_path - 文件路径
  51. # @Return - 一个string list, 包含_path目录下全部路径名
  52. # --------------------------------------
  53. def get_dir_list(_path):
  54. return os.listdir(_path);
  55. # --------------------------------------
  56. # 读取一个目录下所有成员,并将内容分类保存在一个字典中
  57. # @Param:_path - 文件路径
  58. # @Return - {'gz':[gz 文件列表], 'dir':[目录名列表], 'num':[文本文件列表]}
  59. # --------------------------------------
  60. def get_dir_dict(_path):
  61. ret = {'gz':[], 'dir':[], 'num':[]};
  62. file_list = os.listdir(_path);
  63. for file in file_list:
  64. if is_dir(file):
  65. ret['dir'].append(file);
  66. elif is_gz(file):
  67. ret['gz'].append(file);
  68. else:
  69. ret['num'].append(file);
  70. return ret;
  71. # 所有数字的和
  72. sum = 0;
  73. # 所有文本文件的数量
  74. count = 0;
  75. # 需要删除的目录
  76. dir_to_rm = '';
  77. # 是否再次进入00目录
  78. again = False;
  79. # --------------------------------------
  80. # 递归函数
  81. # @Param:_path - 文件路径,这里其实就是第一步解压的00目录
  82. # --------------------------------------
  83. def deal_dir(_path):
  84. global sum;
  85. global count;
  86. global dir_to_rm;
  87. global again;
  88. # 如果目标目录不存在,回退
  89. if _path != '..' and not (os.path.exists(_path)):
  90. return;
  91. # 进入当前目录
  92. os.chdir(_path);
  93. # print os.getcwd(); # Debug 输出
  94. # 递归出口
  95. # 已经回退到00目录
  96. if base_name(os.getcwd()) == '00' and again:
  97. return;
  98. # 第一次进入就设置标志
  99. again = True;
  100. # 把上一次递归已经处理完成的目录删除
  101. if (len(dir_to_rm) > 0):
  102. os.rmdir(dir_to_rm);
  103. dir_to_rm = '';
  104. # 读取当前目录下的文件字典
  105. path_dict = get_dir_dict('.');
  106. # 1: 解压当前目录下所有.tar.gz
  107. # 再将解压完成的.tar.gz删除
  108. for gz_file in path_dict['gz']:
  109. unpack(gz_file);
  110. os.remove(gz_file);
  111. # 重新读取当前目录下的文件字典
  112. path_dict = get_dir_dict('.');
  113. # 2: 读取当前目录下所有文本中的数字
  114. # 将结果累加,并更新文件数量
  115. # 删除处理完成的文本文件
  116. for num_file in path_dict['num']:
  117. sum += read_number(num_file);
  118. count += 1;
  119. os.remove(num_file);
  120. print (count, sum); # Debug 输出
  121. # 3: 处理目录
  122. # 如果当前目录下已经没有子目录,递归到上层目录
  123. # 否则,继续递归处理当前目录下的子目录
  124. if (len(path_dict['dir']) == 0):
  125. dir_to_rm = os.getcwd();
  126. deal_dir('..');
  127. else:
  128. for dir in path_dict['dir']:
  129. deal_dir(dir);
  130. # 执行入口
  131. deal_dir('00');
  132. print sum;
  133. print count;

0315 数组平移

  1. #!/usr/bin/python
  2. # -*- coding: UTF-8 -*-
  3. # !!!纯粹图方便,用来监视数值变化的,和算法本身无关,不能算额外的存储空间!!!
  4. output = [];
  5. # --------------------------------------
  6. # 递归函数
  7. # @Param:_arr - 待排序数组
  8. # @Param:k - 右移位数
  9. # --------------------------------------
  10. def foo(_arr, k):
  11. global buff;
  12. global output;
  13. # 数组长度
  14. n = len(_arr);
  15. # 递归出口
  16. # 如果
  17. # [数组只剩下1个元素]
  18. # 或 [数组长度小于移动步数 且 k是n的整数倍]
  19. # 则说明已经移动完成
  20. if n <= 1 or (n <= k and k % n == 0):
  21. # -------------------------------
  22. output += _arr; # Debug 输出
  23. # -------------------------------
  24. return;
  25. # 如果[数组长度小于移动步数 且 k 不是n的整数倍]
  26. if k >= n:
  27. k = k % n;
  28. # 迭代主体,把从[n-k..n-1],与[0..k-1]对应元素交换
  29. # 即把需要移动到最左边的元素依次交换过来
  30. for idx in range(0, k):
  31. #buff = _arr[idx];
  32. #_arr[idx] = _arr[n - k + idx];
  33. #_arr[n - k + idx] = buff;
  34. _arr[idx], _arr[n - k + idx] = _arr[n - k + idx], _arr[idx];
  35. # -------------------------------
  36. output += _arr[0:k]; # Debug 输出
  37. # -------------------------------
  38. # 将已经移好的部分去掉,_arr[k..n-1]进入递归
  39. foo(_arr[k:n], k);
  40. # --------------------------------------
  41. # 前置函数,用于判断K和N的关系进而做第一步的处理
  42. # @Param:_arr - 待排序数组
  43. # @Param:k - 右移位数
  44. # --------------------------------------
  45. def bar(_arr, k):
  46. global output;
  47. # 数组长度
  48. n = len(_arr);
  49. # 应对k > n的情况,取模
  50. k = k % n;
  51. # 如果 [移动的步数与数组长度相同] 或
  52. # [移动的步数为0] 或
  53. # [待排序数组长度小于2]
  54. # 直接返回
  55. if (n == k or k == 0 or n <= 1):
  56. # -------------------------------
  57. output = org; # Debug 输出
  58. # -------------------------------
  59. return;
  60. # 执行递归函数
  61. foo(_arr, k);
  62. #bar(org, to_move);
  63. #print output;
  64. # --------------------------------------
  65. # 测试函数
  66. # 查看输出矩阵的对称性就可以知道对错
  67. # --------------------------------------
  68. for end in range(2, 12):
  69. org = tuple(range(0, end));
  70. for i in range(0, len(org) + 1):
  71. arr = list(org);
  72. output = [];
  73. bar(arr, i);
  74. print output;
  75. print "";
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注