算法作业01-02

Python

0313 压缩目录

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

#!/usr/bin/python
# -*- coding: UTF-8 -*-
import os, tarfile, sys
# 解除递归次数限制
sys.setrecursionlimit(20000);
# --------------------------------------
# 解压.tar.gz
# @Param:file - 文件路径
# --------------------------------------
def unpack(file):
    arch = tarfile.open(file, 'r:gz');
    for tarinfo in arch:
        arch.extract(tarinfo, os.getcwd());
    arch.close();
# --------------------------------------
# 判断一个路径是否为.tar.gz
# @Param:_path - 文件路径
# @Return - True / False
# --------------------------------------
def is_gz(_path):
    return (os.path.splitext(_path)[1] == '.gz');
# --------------------------------------
# 判断一个路径是否为文件夹
# @Param:_path - 文件路径
# @Return - True / False
# --------------------------------------
def is_dir(_path):
    return os.path.isdir(_path);
# --------------------------------------
# 去掉一个.tar.gz的后缀和前置路径
# @Param:_path - 文件路径
# @Return - Base Name
# --------------------------------------
def base_name(_path):
    base_path = os.path.basename(_path);
    return os.path.splitext(os.path.splitext(base_path)[0])[0];
# --------------------------------------
# 从一个文本文件中读取数字
# @Param:_path - 文件路径
# @Return - 文本中的数字
# --------------------------------------
def read_number(_path):
    fo = open(_path, "r");
    str_num = fo.read();
    fo.close();
    num = int(str_num);   
    return num;
# --------------------------------------
# 读取一个目录下所有成员
# @Param:_path - 文件路径
# @Return - 一个string list, 包含_path目录下全部路径名
# --------------------------------------
def get_dir_list(_path):
    return os.listdir(_path);
# --------------------------------------
# 读取一个目录下所有成员，并将内容分类保存在一个字典中
# @Param:_path - 文件路径
# @Return - {'gz':[gz 文件列表], 'dir':[目录名列表], 'num':[文本文件列表]}
# --------------------------------------
def get_dir_dict(_path):
    ret = {'gz':[], 'dir':[], 'num':[]};
    file_list = os.listdir(_path);
    for file in file_list:
        if is_dir(file):
            ret['dir'].append(file);
        elif is_gz(file):
            ret['gz'].append(file);
        else:
            ret['num'].append(file);
    return ret;
# 所有数字的和
sum = 0;
# 所有文本文件的数量
count = 0;
# 需要删除的目录
dir_to_rm = '';
# 是否再次进入00目录
again = False;
# --------------------------------------
# 递归函数
# @Param:_path - 文件路径，这里其实就是第一步解压的00目录
# --------------------------------------
def deal_dir(_path):
    global sum;
    global count;
    global dir_to_rm;
    global again;
    # 如果目标目录不存在，回退
    if _path != '..' and not (os.path.exists(_path)):
        return;
    # 进入当前目录
    os.chdir(_path);
    # print os.getcwd(); # Debug 输出
    # 递归出口
    # 已经回退到00目录
    if base_name(os.getcwd()) == '00' and again:
        return;
    # 第一次进入就设置标志
    again = True;
    # 把上一次递归已经处理完成的目录删除
    if (len(dir_to_rm) > 0):
        os.rmdir(dir_to_rm);
        dir_to_rm = '';
    # 读取当前目录下的文件字典
    path_dict = get_dir_dict('.');
    # 1: 解压当前目录下所有.tar.gz
    #    再将解压完成的.tar.gz删除
    for gz_file in path_dict['gz']:
        unpack(gz_file);
        os.remove(gz_file); 
    # 重新读取当前目录下的文件字典
    path_dict = get_dir_dict('.');
    # 2: 读取当前目录下所有文本中的数字
    #    将结果累加，并更新文件数量
    #    删除处理完成的文本文件
    for num_file in path_dict['num']:
        sum += read_number(num_file);
        count += 1;
        os.remove(num_file);
        print (count, sum); # Debug 输出
    # 3: 处理目录
    #    如果当前目录下已经没有子目录，递归到上层目录
    #    否则，继续递归处理当前目录下的子目录
    if (len(path_dict['dir']) == 0):
        dir_to_rm = os.getcwd();
        deal_dir('..');
    else:
        for dir in path_dict['dir']:
            deal_dir(dir);
# 执行入口
deal_dir('00');
print sum;
print count;

0315 数组平移

#!/usr/bin/python
# -*- coding: UTF-8 -*-
# ！！！纯粹图方便，用来监视数值变化的，和算法本身无关，不能算额外的存储空间！！！
output = [];
# --------------------------------------
# 递归函数
# @Param:_arr - 待排序数组
# @Param:k - 右移位数
# --------------------------------------
def foo(_arr, k):
    global buff;
    global output;
    # 数组长度
    n = len(_arr);
    # 递归出口
    # 如果
    # [数组只剩下1个元素]
    # 或 [数组长度小于移动步数 且 k是n的整数倍]
    # 则说明已经移动完成
    if n <= 1 or (n <= k and k % n == 0):
        # -------------------------------
        output += _arr; # Debug 输出
        # -------------------------------
        return;
    # 如果[数组长度小于移动步数 且 k 不是n的整数倍]
    if k >= n:
        k = k % n;
    # 迭代主体，把从[n-k..n-1]，与[0..k-1]对应元素交换
    # 即把需要移动到最左边的元素依次交换过来
    for idx in range(0, k):
        #buff = _arr[idx];
        #_arr[idx] = _arr[n - k + idx];
        #_arr[n - k + idx] = buff;
        _arr[idx], _arr[n - k + idx] = _arr[n - k + idx], _arr[idx];
    # -------------------------------
    output += _arr[0:k]; # Debug 输出
    # -------------------------------
    # 将已经移好的部分去掉，_arr[k..n-1]进入递归
    foo(_arr[k:n], k);
# --------------------------------------
# 前置函数，用于判断K和N的关系进而做第一步的处理
# @Param:_arr - 待排序数组
# @Param:k - 右移位数
# --------------------------------------
def bar(_arr, k):
    global output;
    # 数组长度
    n = len(_arr);
    # 应对k > n的情况，取模
    k = k % n;
    # 如果 [移动的步数与数组长度相同] 或 
    # [移动的步数为0] 或 
    # [待排序数组长度小于2]
    # 直接返回
    if (n == k or k == 0 or n <= 1):
        # -------------------------------
        output = org; # Debug 输出
        # -------------------------------
        return;
    # 执行递归函数
    foo(_arr, k);
#bar(org, to_move);
#print output;
# --------------------------------------
# 测试函数
# 查看输出矩阵的对称性就可以知道对错
# --------------------------------------
for end in range(2, 12):
    org = tuple(range(0, end));
    for i in range(0, len(org) + 1):
        arr = list(org);
        output = [];
        bar(arr, i);
        print output;
    print "";