目录
7-3 集合相似度
给定两个整数集合，它们的相似度定义为：Nc/Nt×100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入格式
输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤104），是集合中元素的个数；然后跟M个[0,109]区间内的整数。
之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。
输出格式
对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。
输入样例
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
输出样例
50.00%
33.33%代码展示
def getele()->list:
a = input().split(' ')
a = [int(a[i]) for i in range(len(a))]
return a
my_list=[]
num1=int (input())
while num1>0:
num1-=1
cont = getele()
my_set=set()
for i in cont[1:]:
my_set.add(i)
my_list.append(my_set)
num2=int (input())
while num2:
num2-=1
cont=getele()
len1=len(my_list[cont[0]-1])
len2=len(my_list[cont[1]-1])
if len1>=len2:
newset=my_list[cont[0]-1].difference(my_list[cont[1]-1])
ans=float ((len1-len(newset))/len(my_list[cont[0]-1].union(my_list[cont[1]-1])))
else:
newset = my_list[cont[1] - 1].difference(my_list[cont[0] - 1])
ans = float((len2-len(newset))/ len(my_list[cont[1] - 1].union(my_list[cont[0] - 1])))
ans=ans*100
print('%.2f' %ans,end='')
print('%')知识点
保留小数的几种方法： 1、 print('%.2f' %ans,end='') print('%') 2、round默认去掉多余的零，末尾只保留一个0 print(round(ans,2),end='') print('%')- 集合操作：
difference()差集，union()并集，都是生成新的集合返回
7-5 构造散列表
设散列表a[18]，散列函数是hask(k)=k%17，用开放地址法解决冲突hi=(h0+di)%m。冲突时，使用增量序列di=5i。计算输入序列(值>=0)对应的散列地址值。（输入个数不会超过15个）
输入格式
第一行为输入个数；
第二行为对应的输入值，用空格隔开。
输出格式
按输入顺序输出其散列地址。每行对应一个值及其散列地址，中间用空格隔开（即pos前后均有一个空格）
输入样例
5
141 73 95 112 56
输出样例
141 pos: 5
73 pos: 10
95 pos: 15
112 pos: 2
56 pos: 7代码展示
def hask(i:int):
return i%17
def add(i:int):
con=i
i=hask(i)
while my_list[i]!=0:
i+=5
if i>18:
i=i-18
my_list[i]=con
def getele()->list:
a = input().split(' ')
a = [int(a[i]) for i in range(len(a))]
return a
num1=int (input())
cont=getele()
my_list=[]
new_list=[]
for i in range(18):
my_list.append(int (0))
for c in cont:
new_list.append(c)
add(c)
for i in range(num1):
print(new_list[i],end=' ')
print(f"pos:",end=' ')
print(my_list.index(new_list[i]))散列表7.10 集合运算
★实验任务
有一天，你正在学习算法与数据结构。突然看到一个很有趣的知识点，集合运算！聪明的你很快的就掌握了并集运算、交集运算和差集运算。这里就出小小的问题帮你检验一下掌握情况吧。 给你三组数。当你用集合的定义将他们转化成三个集合A、B、C后，如果A集合与B集合能通过上述三种集合运算（并集运算、交集运算和差集运算）得到集合C。则从小到大输出集合C的所有元素，否则输出“What a pity!”（不含引号）。
★数据输入
第一行输入包括n、m、k三个整数。 第二行输入n个整数，即A数组。 第三行输入m个整数，即B数组。 第四行输入k个整数，即C数组。
★数据输出 如果A集合与B集合最后运算结果与C集合相同，即输出这个结果（按升序），否则输出“What a pity！” （不含引号）。
输入示例
5 5 4
1 2 3 4 5
2 3 4 5 6
2 3 4 5
输入示例
2 3 4 5
代码展示
def getele()->list:
a = input().split(' ')
a = [int(a[i]) for i in range(len(a))]
return a
input()
k=0
my_list1=getele()
my_list2=getele()
my_list3=getele()
A=set()
B=set()
C=set()
for i in my_list1:
A.add(i)
for i in my_list2:
B.add(i)
for i in my_list3:
C.add(i)
new1=A.union(B)
new2=A.difference(B)
new3=A.difference(new2)
my_list3.sort()
if new1==C:
for i in my_list3:
if k < 0:
print(' ', end="")
k -= 1
print(i, end='')
elif new2==C:
for i in my_list3:
if k < 0:
print(' ', end="")
k -= 1
print(i, end='')
elif new3==C:
for i in my_list3:
if k < 0:
print(' ', end="")
k -= 1
print(i, end='')
else:
print("What a pity!")散列表7.12 三角形游戏
★实验任务
给定n个三角形，用a,b,c表示三角形的三条边（三角形可能有重复）。之后有m次询问，每次询问一个三角形在给定的n个三角形中出现的次数。
★数据输入
第一行为n，之后n行，每行有a,b,c三个数字表示三角形的三条边；接下来一行为m，之后有m行询问，每行有a,b,c三个数字，表示要询问的三角形的三边。 数据保证a,b,c为正整数且可以构成一个三角形，且a,b,c不一定有序 对于40％的数据，n<=100，m<=100，a,b,c<=100 对于70％的数据，n<=1000，m<=1000，a,b,c<=1000 对于100％的数据，n<=5,000，m<=100,000，a,b,c<=999999
★数据输出
对于每次询问，输出此三角形在之前给定的n个三角形中出现的次数
输入示例
3
2 2 3
3 3 4
2 3 2
3
2 3 2
3 3 4
1 1 1
输出示例
2
1
0
代码展示
def getele()->list:
a = input().split(' ')
a = [int(a[i]) for i in range(len(a))]
return a
num1=int (input())
my_list1=[]
my_list2=[]
while num1:
num1-=1
cont=getele()
s=[]
for i in cont:
s.append(i)
s.sort()
my_list1.append(s)
num2=int (input())
while num2:
num2-=1
cont=getele()
s = []
for i in cont:
s.append(i)
s.sort()
my_list2.append(s)
for i in my_list2:
count=0
for j in my_list1:
if i==j:
count+=1
print(count)