个人记录：第一次算法作业（python）
个人记录：第一次算法作业（python）
- 输入一个自然数(<90000), 分别用递归法和非递归法求其二机制表示.
算法设计思想：二进制的关键是用除2取余法，定义一个list，将每次的余数存入列表中，最后将列表转化为字符串，然后将字符串逆序输出。
代码展示：# 非递归
s = []
num =int(input(‘请输入一个数：’))
while (num > 0) :
a= num % 2
s.append(a)
num =int( num/2)
str1 = ‘’.join([str(x) for x in s])
print(‘该数的二进制为：’+ str1[::-1])
**# 递归版
def num2Tow(num):
if num == 0:
return 0
else:
s1.append(num%2)
num2Tow(int(num/2))
num = int(input(‘请输入一个数：’))
s1 = []
num2Tow(num)
str2 = ‘’.join([str(x) for x in s1 ])
print(‘该数的二进制为：’+ str2[::-1])
- 分别用递归法和非递归法求Fibonacci数列的前1000位，并比较计算时间的差异.
算法设计思想：Fibonacci数列的表现形式为，从第三项开始，每一项都等于前两项之和，即F(n)=F(n-1)+F(n-2)。
代码展示：# 非递归
import time
start1 = time.time()
s = [1,1]
for i in range (2 ,50):
s.append(s[i-2]+s[i-1]）
print(‘Fibonacci数列的前50位为:’,s)
end1= time.time()
print(‘程序执行时间：%s s’%(end1-start1))
**# 递归
import time
def Fibonacci(num):
if num<2 :
return 1
else:
return Fibonacci(num-2)+Fibonacci(num-1)
start= time.time()
s=[]
print(‘Fibonacci数列的前50位为:’)
for i in range(50):
print(‘第%d项为’%i,Fibonacci(i))
end = time.time()
print(‘程序执行时间：%s s’%(end-start))
时间差异性比较：非递归算法比递归算法在时间效益上更快。
3.用递归算法完成如下问题：有52张牌，使它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下,正面朝下的翻成正面朝上；第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，以此类推，直到第一张要翻的牌超过52为止。统计最后有几张牌正面朝上，以及它们的位置号.
解题思路: ①设一个列表，将正面朝上用0表示，将值全设置为0
②从第i张牌开始，将i的倍数的牌取反，对0 取反
③判断i>51 （0到51） 是否成立，成立则返回，输出列表中为 0的牌
④不成立则 i+1 返回第二步
4. 一个射击运动员打靶，靶一共有10环，连开6枪打中45环的可能性有多少种? （每一枪最少是0环，最多是10环）
解题思路：1.确定枪数num，环数score
2.确定什么情况打靶失败：
①当剩下的num 全中也小于score，则返回
②当n = 1 时，score<0 时
3.记录每枪打靶的环数a[i]（0~10），score-a[i]则为剩下的环数，num-1为剩下的枪数，返回第二步判断是否失败
4.输出成功的a[i],并总计sum
- 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，输出所有摆法。
设计思想：
1 设计一个数组A[],小标表示行，A[i]的值为列
2 从第一行开始赋值，判断已经放下的皇后是否存在同列，同对角
3 如果没有则递归函数，且行数num+1