Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Thuật toán chặt nhị phân (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 2
  • Trang:
  • << < 1 2 > >>
CHỦ ĐỀ - Thuật toán chặt nhị phân
#69442
hung1xpro (Thành viên)
hung1xpro
Đang tập code
Bài viết: 2
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Thuật toán chặt nhị phân 8 năm, 1 tháng trước   (+0)
Theo như em biết là thuật toán này ~ với thuật toán tìm kiếm nhị phân đúng ko ạ ?
Nhưng em không biết ứng dụng của nó để làm gì ? Mọi người có thể chỉ cho em + cho em ít vd được ko ạ
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69447
lady96 (Thành viên)
Biết code binary-indexed tree
Bài viết: 21
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán chặt nhị phân 8 năm, 1 tháng trước   (+0)
Hình như là chặt nhị phân để cho c/t chạy nhanh hơn
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69448
yugi139 (Thành viên)
stupider-
Super fast coder
Bài viết: 54
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán chặt nhị phân 8 năm, 1 tháng trước   (+0)
chặt nhị phân được dùng để tìm kiếm với tốc độ cao
thông thường khi tìm kiếm trên 1 dãy ta phải for cả dãy để tìm thì chi phí mất là O(n)
còn khi chặt nhị phân ta chỉ mất O( log n ) tốc độ hiệu quả hơn rất nhiều

trường họp bạn có n=1.000.000 ( 1.000.000 phần tử ) thì bạn tìm kiếm bằng vòng for hết 1.000.000 phần tử này sẽ mất ~ 0,5s gần hết thời gian 1s cho phép thông thường
trong khi chặt nhị phân sẽ mất ~ 20 lần chặt chạy còn chưa tới 0,01s
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69449
lady96 (Thành viên)
Biết code binary-indexed tree
Bài viết: 21
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán chặt nhị phân 8 năm, 1 tháng trước   (+0)
em định nghĩa chặt nhị phân như vầy anh xem thử đúng ko nha :
Đầu tiên là sắp xếp tăng dần
vd : với dãy 100 - > 100000000 họ hỏi tìm vị trí của số 999999
thì đầu tiên là em tìm số ở giữa so sánh với số cần tìm
nếu nó lớn hơn thì làm típ với đoạn từ 1 đến số giữa
còn ko thì tìm từ đoạn số giữa đến hết đúng ko ạ @@
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69450
yugi139 (Thành viên)
stupider-
Super fast coder
Bài viết: 54
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán chặt nhị phân 8 năm, 1 tháng trước   (+0)
có vẻ chuẩn rùi ^^
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69451
lady96 (Thành viên)
Biết code binary-indexed tree
Bài viết: 21
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán chặt nhị phân 8 năm, 1 tháng trước   (+0)
nhưng mà em thấy có mấy cái gì mà đồ thị áp dụng chặt nhị phân gì gì đó thì làm sao ạ @@
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69452
yugi139 (Thành viên)
stupider-
Super fast coder
Bài viết: 54
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán chặt nhị phân 8 năm, 1 tháng trước   (+0)
có thể nói là một ứng dụng của chặt nhị phân để chọn các đường đi
( mình khá non trong đồ thị nên không dám giảng lại cho bạn )
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69453
lady96 (Thành viên)
Biết code binary-indexed tree
Bài viết: 21
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán chặt nhị phân 8 năm, 1 tháng trước   (+0)
Vậy có ai chỉ cho em về cái ứng dụng tìm đường đi đó được ko ạ
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69456
vietthaitink21 (Thành viên)
vietthaitink21-
Đã code là AC
Bài viết: 85
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán chặt nhị phân 8 năm, 1 tháng trước   (+0)
lady96 viết:
QUOTE:
Vậy có ai chỉ cho em về cái ứng dụng tìm đường đi đó được ko ạ

Trong đồ thị nhé, giả sử đề bài yêu cầu tìm thời gian nhở nhất hoặc lớn nhất để hoàn thành công việc nào đó, thì một trong những cách có thể sử dụng đó là bạn sẽ đi chặt nhị phân thời gian nhỏ nhất hoặc lớn nhất đó, với mỗi thời gian đó, bạn kiểm tra xem liệu công việc có thể hoàn thành trong thời gian này hay không. Đó là một trong ứng dụng của chặt nhị phân trong đồ thị
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69547
lady96 (Thành viên)
Biết code binary-indexed tree
Bài viết: 21
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Thuật toán chặt nhị phân 8 năm trước   (+0)
anh có thể cho em bài toán + code cụ thể được không ạ
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
  • Trang:
  • << < 1 2 > >>
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS