Python编程及项目开发 第3章-项目开发

3.5项目开发1.查找算法查找算法是计算机科学中用于在数据集合中定位特定元素的一类基础算法。查找的方法也很多，这些方法各有利弊。本例介绍两种最常用的查找方法，更多的查找方法可以查阅数据结构方面的资料了解。(1)顺序查找从第一个元素开始逐一比较，直到末尾。算法：一列数放在无序的数组a[1]----a[n]中，待查找的数放在x中，把x与a数组中的元素从头到尾一一比较查找。用变量pos表示a数组元素下标，pos初值为0，使x与a[pos]比较。如果x不等于a[pos]，则使p=p+1，不断重复这个过程；一旦x等于a[pos]则退出循环。另外，如果pos大于数组长度，循环也应该停止。以下代码中的布尔变量found初始值为False，如果找到就被赋值True。函数返回值是布尔值。代码如下：1a=[1a=[1,2,3,4,5,6,8,20,24,31,35]2x=243defsequentialSearch(a,n):4pos=05found=False6whilepos<len(a)andnotfound:7ifa[pos]==n:8found=True9else:10pos=pos+111returnfound13print(sequentialSearch(a,x))上述代码的输出结果如下：True如果将第2行中x的值改为25，则输出结果如下：False分析上面的程序，如果数据项不在列表里，唯一的判定办法就是把全部项逐个比较。如果表中有n个数据，顺序查找就需要n次比较。但是分析没有这么简单，有三种情形可能发生：最好的情况下，第一个项就是我们要找的，只有1次比较；最差的情况下，需要n次比较，全部比较过后才知道找不到；在平均情况下，我们会发现是列表的一半，即平均要比较n/2次。假如表中数据项以某种方式排序了，怎样来快速查找呢？下面来介绍折半查找，也就是二分法查找。(2)折半查找算法：设n个有序数(从小到大)存放在数组a[1]----a[n]中，要查找的数为x。用变量low、high、middle分别表示查找数据范围的底部(数组下界)、顶部(数组的上界)和中间，middle=(low+high)//2，折半查找的算法如下：lx=a[middle]，则已找到退出循环，否则进行下面的判断。lx<a[middle]，x必定落在low和middle-1的范围之内，即high=middle-1。lx>a[middle]，x必定落在middle+1和high的范围之内，即low=middle+1。l在确定了新的查找范围后，重复进行以上比较，直到找到或者low<=high。若找到则返回该数所在的下标值，没找到则返回-1。将上面的算法写成如下函数，代输出结输出结果如f1a=[1,1a=[1,2,3,4,5,6,8,20,24,31,35]2x=243defbinary_Search(a,n):4low=0indfailed-1果将第2行改为x=24则代16return-117print(binary_Search(a,x))5high=len(a)-16whilelow<=high:7middle=(low+high)//28ifa[middle]==n:9print('findit')10returnmiddle+111elifa[middle]<n:12low=middle+114high=middle-115print('findfailed')输出结果如下：findit92.数组元素的排序排序是将一组数据按照递增或递减的次序排列。排序有以下经典算法：选择法排序、冒泡法排序、比较法排序等。下面主要介绍选择法排序和冒泡法排序。(1)选择法排序算法：l对有n个数的序列(存放在数组a[n]中)，从中选出最小的数，与第1个数交换位置。l除第1个数外，其余n-1个数中选最小的数，与第2个数交换位置。l依次类推，选择了n-1次后，这个数列已按升序排列。代码如下：1a1a=[0,70,20,10,30,40,50]2defselection_sort(a):3foriinrange(0,len(a)):4min=i5forjinrange(i+1,len(a)):6ifa[j]<a[min]:7min=j8temp=a[i]99a[i]=a[min]10a[min]=temp12selection_sort(a)13print('Thesortedlistis:',a)(2)冒泡法排序算法：①从最后一个数开始，与相邻的数比较。若小于该数，则交换位置。一轮排序后，最小数换到了最前面(即小数往上冒，大数往下沉)。②除第一个数外，其他n-1个数按步骤1的方法使次小的数冒出。③重复步骤(1)n-1遍，最后构成递增序列。代码如下：1a1a=[21,44,2,45,33,4,3,67]2defbubble(l):3flag=True4foriinrange(len(l)-1,0,-1):5ifflag:6flag=False7forjinrange(i):8ifl[j]>l[j+1]:9l[j],l[j+1]=l[j+1],l[j]10flag=True12break13print(l)15bubble(a)(3)用插入排序法，将一个新数据插入到一个有序表中，使该有序表成为新的、数据增加的有序表。算法：先找出key应在数组中的位置i，然后从最后一个数开始共n-i个数据依次后移，直到位置i空出，将数据key放入数组中相应位置上，一个数据的插入就此完成。代码如下：13break13break1l=[0,10,20,30,40,50]2print('Thesortedlistis:',l)3n=len(l)4key=int(input('Inputanumber:'))5l.append(key)67definsert_array(l,key):8foriinrange(n):9ifkey<l[i]:10forjinrange(n,i,-1):11l[j]=l[j-1]12l[i]=key1515insert_array(l,key)16print('Thesortedlistis:',l)程序运行的结果如下：Thesortedlistis:[0,10,20,30,40,50]Inputanumber:15Thesortedlistis:[0,10,15,20,30,40,50]3.递归已知有五位朋友在一起，第五位朋友说自己比第4个人大2岁；问第4个人年龄，他说比第3个人大2岁；问第三个人，又说比第2人大两岁；问第2个人，说比第一个人大两岁；最后问第一个人，他说是10岁。求第5个人的年龄是多少？解题思路：此题利用递归的方法来解决。要想知道第五个人岁数，需知道第四人的岁数，依次类推，推到第一人是10岁。这样再往回推。代码如下：1#1#-*-coding:UTF-8-*-23defage(n):4ifn==1:c=105else:c=age(n-1)+26returnc7printage(5)1.项目名称自动化文件备份工具2.项目需求(1)备份指定目录下的文件到目标目录。(2)支持按文件扩展名筛选备份。(3)自动跳过未修改的文件(基于修改时间)。(4)支持恢复最近一次备份。3.项目设计(1)项目模块划分：该项目主要分为4个模块：backup.py模块：主备份功能；restore.py模块：文件恢复功能；config.py模块配置管理；utils.py模块：一些工具函数。文件夹结构如图3-2所示。(2)项目主要模块流程图：4.项目实现项目主要函数实现的代码如下backup.py1importos2importshutil3from.configimportload_config,save_config4from.loggerimportlog_action5from.utilsimportensure_dir_exists,get_files_to_backup,is_file_modified67defrun_backup():8"""执行备份操作"""9config=load_config()#读取配置文件11ifnotconfig["source_dir"]ornotconfig["backup_dir"]:12log_action("ERROR","请先设置源目录和备份目录")13returnFalse15source_dir=config["source_dir"]16backup_dir=config["backup_dir"]17extensions=config["extensions"]19ifnotos.path.exists(source_dir):20log_action("ERROR",f"源目录不存在:{source_dir}")21returnFalse2223ensure_dir_exists(backup_dir)2425files_to_backup=get_files_to_backup(source_dir,extensions)26total_files=len(files_to_backup)27backed_up=028skipped=02930log_action("INFO",f"开始备份:源目录={source_dir},备份目录={backup_dir}")3132forsource_pathinfiles_to_backup:33rel_path=os.path.relpath(source_path,source_dir)34backup_path=os.path.join(backup_dir,rel_path)3536ensure_dir_exists(os.path.dirname(backup_path))3738ifis_file_modified(source_path,backup_path):39shutil.copy2(source_path,backup_path)40log_action("BACKUP",f"已备份:{rel_path}")41backed_up+=142else:43skipped+=14445config["last_backup_time"]=time.time()46save_config(config)47returnTrue1importos2importshutil3from.configimportload_config4from.loggerimportlog_action5from.utilsimportensure_dir_exists67defrestore_latest_backup():8"""恢复最近一次备份"""9config=load_config() 11ifnotconfig["backup_dir"]ornotconfig["source_dir"]:12log_action("ERROR","请先设置源目录和备份目录")13returnFalse15backup_dir=config["backup_dir"]16source_dir=config["source_dir"]18ifnotos.path.exists(backup_dir):19log_action("ERROR",f"备份目录不存在:{backup_dir}")20returnFalse2122ensure_dir_exists(source_dir)2324log_action("INFO",f"开始恢复:从{backup_dir}恢复到{source_dir}")2526forroot,_,filesinos.walk(backup_dir):27forfileinfiles:28backup_path=os.path.join(root,file)29rel_path=os.path.relpath(backup_path,backup_dir)30source_path=os.path.join(source_dir,rel_path)3132ensure_dir_exists(os.path.dirname(source_path))33shutil.copy2(backup_path,source_path)34log_action("RESTORE",f"已恢复:{rel_path}")35log_action("INFO","恢复完成")36returnTrueutils.py1importos2importshutil3importfnmatch45