Cây nhị phân

[truonghandan0210]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

​

Cây nhị phân đầy đủ độ sâu N là cây mà mọi nút có đúng hai nút con trừ các nút ở độ sâu N đều là nút lá.

Cây nhị phân đầy đủ độ sâu N gồm có 2^N -1 nút, các nút được đánh số từ 0 đến 2^N -2.Nút x nếu không phải là nút lá sẽ có hai con là nút 2x+1và 2x+2.

Trong trò chơi trên cây nhị phân, nút x được gán giá trị Px là số điểm ghi được nếu chiếm được nút x. Đây là trò chơi đối kháng giữa bạn và máy tính. Trò chơi diễn ra như sau: nút xuất phát là nút 0. Tới lượt của mình, bạn hoặc máy tính sẽ chiếm nút hiện thời, cập nhật lại điểm của mình.Sau đó người chơi di chuyển nút hiện thời tới một trong hai nút con của nó (nếu tồn tại nút con) và người chơi kế tiếp sẽ thự hiện nước đi.Nếu không thể di chuyển nút hiện thời (không tồn tại nút con) có nghĩa làtrò chơi đã kết thúc. Người chơi có nhiều điểm hơn là người giành chiến thắng Trong trò chơi này, mỗi lần quyết định sẽ đi vào nhánh con trái hay nhánh con phải sẽ quyết định rất lớn đến sự thắng thua. Bạn biết rằng máy tính luôn đi rất tối ưu, bạn hãy xác định xem bạn có thể thắng cách với biệt lớn nhất là bao nhiêu hoặc thua với cách biệt nhỏ nhất là bao nhiêu.

Dữ liệu vào từ file TREEGAME.INP:

· Dòng đầu tiên ghi số N, 1<=N<=20;trong 50% số test,1<=n<=4.

· Dòng thứ hai chứa 2^N-1 số là số nguyên là các giá trị Px, |Px|<= 10^9

· Dòng thứ ba ghi xâu first hoặc second tương ứng với việc bạn được đi trước hay đi sau.

Kết quả in ra file TREEGAME.OUT:

· Ghi ra cách biệt lớn nhất giữa bạn và máy tính.

 

[Nguyễn Thánh Tiền]

Ai đưa ra thuật toán nào @Trường Thái @huutoan00 @Vuio

 

[Vuio Dev]

Em thì dở về phần cây với quay lui nên giải bài này theo hướng khác.
Ý tưởng của em là cây nhị phân đầy đủ sâu N có 2^N cách chọn khác nhau, lưu tổng của 2^N cách chọn đó vào 1 mảng 2^N phần tử, sau đó tìm max (cách đi của robot tối ưu nhất) và cách đi max2 (của người chơi thua robot) trong mảng tìm được.
Em dùng một biến string lưu các giá trị hoán vị nhị phân có độ dài N-1, sau đó duyệt hết xâu, dùng 1 biến G để định vị (ban đầu g=0), chạy hết xâu nhị phân ở trên, nếu gặp 0 thì cập nhật lại g=2*g+1, là 1 thì g=2*g+2, sau đó tăng tổng lên một đoạn P[g], P là mảng lưu các ptử input từ 0 đến 2^n1.
Anh chị xem thử code

uses crt;
var
        n,i,j,g:byte;
        p,r:array[0..25] of longint;
        s:string;
        max,max2:int64;
procedure readdata;
        begin
                write('Nhap n= ');
                readln(n);
                for i:=0 to round(exp(n*ln(2)))-2 do
                        begin
                                write('Nhap Cay>',i,'= ');
                                readln(p[i]);
                        end;
        end;
procedure getpath;
        begin
                n:=n-1;
                for i:=0 to round(exp(n*ln(2)))-1 do
                        begin
                                s:=binstr(i,n);
                                r[i]:=p[0];
                                g:=0;
                                for j:=1 to n do
                                        if s[j]='0' then
                                                begin
                                                        g:=2*g+1;
                                                        r[i]:=r[i]+p[g];
                                                end
                                        else
                                                begin
                                                        g:=2*g+2;
                                                        r[i]:=r[i]+p[g];
                                                end;
                        end;
        end;
procedure findmax;
        begin
                max:=r[0];
                for i:=1 to round(exp(n*ln(2)))-1 do
                        if max<r[i] then
                                max:=r[i];
                max2:=0;
                for i:=0 to round(exp(n*ln(2)))-1 do
                        if (max2<r[i]) and (r[i]<>max) then
                                max2:=r[i];
        end;
begin
        clrscr;
        readdata;
        getpath;
        findmax;
        writeln;
        writeln('Robot Max= ',max);
        writeln('Player Max= ',max);
        writeln('Nguoi choi Max (thua)= ',max2);
        readln
end.

Không có thời gian để code file nên tạm nhập bằng tay vậy.
Ví dụ:
N=3
______5______
___6_____9___
10__17_1___2_

P: 5 6 9 10 17 1 2
Liệt kê 2^(N-1)=2^(3-1)=2^2=4 hoán vị nhị phân (4 cách chọn đường)
00 (Trái trái)
01 (Trái phải)
10 (Phải trái)
11 (Phải phải)

Tính tổng mỗi đường đi tương ứng với một xâu nhị phân trên
00: 5+6+10=21
01: 5+6+17=28
10: 5+9+1=15
11: 5+9+2=16

Do máy tính luôn đi tối ưu nên ta chỉ có thể hòa hoặc thua.
Nếu hòa thì cách biệt lớn nhất là 0
Nếu thua thì cách biệt nhỏ nhất là hiệu giữa máy và số lớn thứ 2 trong các đường đi.
(Đề có thêm đi trước hay đi sau nhưng mình nghĩ không quan trọng, bên nào cũng phải đi đủ N bước thôi nên trước sau gì cũng vậy)