python演演算法與資料結構朋友圈與水杯實驗題分析範例

2022-12-05 14:01:05

演演算法與資料結構實驗題-朋友圈

實驗任務

朋友圈是由若干個人組成的集體，已知現在有n個人(1到n)，然後給你m個關係x y，表示x和y是朋友，假設朋友的朋友也是朋友，求這n個人中最大的朋友圈人數。

資料輸入

輸入第一行為一個正整數n,m。

接下來有m行，每行有兩個正整數 x 和 y ，表示 x 和 y 是朋友

60%的資料 1<=n,m<=100.

100%的資料1<=n<=100000.

資料輸出

輸出n個人中最大的朋友圈人數。

輸入範例

3 2
1 2
2 3

輸出範例

3

程式碼實現

rel=int (input().split()[1])
my_list=[]
ne=0
while rel:
    rel-=1
    flag=0
    my_set=set()
    my_cont=[int (n) for n in input().split()]
    for n in range(len(my_list)):
        if my_cont[0] in my_list[n]:
            my_list[n].add(my_cont[1])
            flag=1
            ne=n
            continue
        if (my_cont[1] in my_list[n]) and flag==0:
            my_list[n].add(my_cont[0])
            flag = 1
            break
        elif (my_cont[1] in my_list[n]) and flag==1:
            my_list[n]=my_list[n].union(my_list[ne])
            my_list.remove(my_list[ne])
    if flag==0:
        my_set.add(my_cont[0])
        my_set.add(my_cont[1])
        my_list.append(my_set)
ans=0
for n in my_list:
    ans=max(ans,len(n))
print(ans)

tips：union返回一個新的集合，需要賦值

效果展示

演演算法與資料結構實驗題-水杯

實驗任務

有n個水杯疊放在一起

從上到下，編號由1開始一直到n，容量ai不一定滿足也依次增大的關係，如果i號杯子存的水超過了它的容量，則會像i+1號水杯流，以此類推

現在給你兩個操作

操作一： 1 x y 給x號杯子加y容量的水

操作二： 2 x 查詢x杯子裡有多少水。

資料輸入

輸入第一行為一個正整數n

接下來n個元素，表示第i個水杯的容量

接著輸入操作的個數q

接下來q行操作。

60%的資料 1<=n<=100,1<=q<=100,1<=ai,y<=100.

100%的資料1<=n<=100000,1<=q<=100000,1<=ai,y<=1000000000.

資料輸出

對於每個操作二，輸出對應的值。

輸入範例

2
5 10
6
1 1 4
2 1
1 2 5
1 1 4
2 1
2 2

輸出範例

4
5
8

程式碼實現

def action(x,n):
    while n>0 and x<=num:
        if my_cup[x]>=n:
            my_cup[x]-=n
            n=0
        else:
            n-=my_cup[x]
            my_cup[x] = 0
            x+=1
num=int (input())
my_cup=[int (n) for n in input().split()]
old=my_cup.copy()
act=int (input())
while act:
    act-=1
    cont=[int (n) for n in input().split()]
    if cont[0]==1:
        action(cont[1]-1,cont[2])
    if cont[0]==2:
        print(old[cont[1]-1]-my_cup[cont[1]-1])

註釋：這裡的old列表需要用到copy函數進行淺拷貝操作（沒有出現巢狀所以不同考慮深拷貝），若是直接賦值則會導致my_cup改變時old也跟著改變。本程式碼輸出為實時輸出