Chào cả nhà, vẫn lại là mình và lần này vẫn là anh mình cho mình 1 bài toán nên lên mời cả nhà mần cùng cho nó vui:
Con Ếch Sang Sông
Chú ếch đang chuẩn bị để nhảy từ bên này sông sang bờ bên kia sông để về nhà. Giữa 2 bờ là vô vàn các tảng đá mà ếch Hương có thể nhảy lên và các cọc nhọn nếu mà nhảy vào là lòi phèo tại chỗ. Vì thể hình lực lưỡng của mình, chú ếch Hương chỉ có thể nhảy được 1 bước và tối đa là 2 bước từ vị trí đang đứng. Sẽ không có 2 cọc nhọn liên tục giữa dòng sông để đảm bảo là không ai triệt đừng sống của chú ếch. Các em hãy giúp chú ếch Hương tính toán xem cần tối thiểu bao nhiêu bước nhảy để có thể qua được sông.
Ví dụ: nhận vào 1 mảng mô phỏng dòng sông [0,0,0,1,0] với 1 là vị trí cây cọc nhọn.
để từ bên này qua bên kia sông, có 2 cách để chú ếch có thể nhảy:
- 3 lần: lần 1 bước nhảy là 1 lên tảng đá gần nhất, lần 2 bước nhảy cũng là 1, lần 3 bước nhảy 2 để qua cọc nhọn và lên bờ
- (đáp án) 2 lần: lần 1 bước nhảy là 2 đến vị trí gần cây cọc, lần 2 nhảy qua cọc lên bờ.
Cách mình làm:
import time
# Dup cho cái mảng bự bự 1 tí
unit = 10000000
ar = [0,0,1,0,0,1,0]*unit
def jumps():
count = 0
index = 0
max = len(ar)-1
while(max>=index):
jump_step = 2 if (index+2<max and ar[index+2]!=1) else 1
index+=jump_step
count+=1
print("->Count: ", count)
# Test
for i in range(10):
start = time.time()
jumps()
end = time.time()
time_result = round(end-start,5)
print("Time: {}".format(time_result))
times.append(time_result)
print('AVG: {}'.format(round(sum(times)/len(times),5)))
Rất mong được cả nhà chỉ ra điểm yếu trong cách làm của mình và ủng hộ cả nhà cùng tham gia cho vui nhà vui cửa. 
tất nhiên ko phải bài nào cũng đúng vì đơn giản là do xét thiếu khả năng.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?