4.常用基础算法（学考）知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（必修）

第四章 常用基础算法 一、算法概念 1.广义的讲，“算法”指的是解决问题或完成任务的一系列步骤。在计算机科学领域内，“算法”指的是计算机解决问题的步骤，是为了解决问题而需要让计算机有序执行的，无歧义的，有限步骤的集合。 2.算法的特征： (1)有穷性：一个算法的处理步骤必须是有限的。 (2)可行性：每一步的操作与要求都是可行的，并且能够在有限时间内完成。 (3)确定性：每一步的执行描述必须是明确的 (4)0个或多个输入 (5)1个或多个输出 3.描述算法的方法：1.自然语言描述；2.流程图描述；3.伪代码描述；4.用程序设计语言描述 4.编程解决问题的一般过程：1.抽象与建模；2.设计算法；3.编写程序；4.调试运行程序 二、解析算法和枚举算法 1.解析算法：根据问题的前提条件与所求结果之间的关系，找出求解问题的数据表式，并通过表达式计算来实现问题的求解。 2.枚举算法：把问题所有可能的解一一例举，然后判断每一个列举出的可能解是否为正确的解。 以鸡兔同笼问题为例：今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何? 1.解析写法 head,foot = eval(input("请输入头和足的数量，格式是:头,足")) rabbit = (foot-head*2)/2 chick = head-rabbit print("兔子有{}只，鸡有{}只".format(rabbit,chick)) 2.枚举写法 head,foot = eval(input("请输入头和足的数量，格式是:头,足")) for rabbit in range(head+1): if rabbit*4+(head-rabbit)*2==foot: print("兔子有{}只，鸡有{}只".format(rabbit,head-rabbit)) 思考：百钱百鸡问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，问翁、母、雏各几何？请编写Python程序解决该问题，思考应该用枚举还是用解析。 三、常见数据处理程序 1.数值处理类 (1)辗转相除法求两个正整数的最大公约数 (2)判断num是否为素数 def gcd(m,n): if m<n: m,n = n,m while n != 0: m,n = n,m%n return m print(gcd(15,24)) def prime_number(num): flag = True for i in range(2,num): if num%i==0: flag = False return flag print(prime_number(15)) (3)角谷猜想：以一个正整数n为例，当n是奇数时，下一步变为3n+1；当n是偶数时，下一步变为n/2。不断重复这样的运算，经过有限步后，一定可以得到1。 def conjecture(num):     s = str(num)+"->"     while True:         if num == 1:             break         elif num%2==1:             num = num*3+1         else:             num = num/2         s = s + str(num)+"->"     return s[:-2] import random print(conjecture(random.randint(0,1000))) 2.进制转换类 (1)十进制数转二进制字符串 (2)二进制字符串转十进制数(除2取倒余) def B2D(str): num = 0 for ch in str: num = num*2 + int(ch) return num print(B2D("100101")) def D2B(num): s = "" while num>0: r = num % 2 s += str(r) #s = str(r)+s num //= 2 return s[::-1] #return s print(D2B(45)) 思考：十六进制和十进制的转换如何用代码实现。 3.字符处理类 (1)字符大小写转换（ASCII码方式） def change(str1): ans = "" for ch in str1: i