-
Thông báo quan trọng: Nâng cấp diễn đàn sang nền tảng mới. Vui lòng đọc kỹ
[Tin] Pascan và vấn đề thi HSG Tin học
- Người khởi tạo thanhkhoeo
- Ngày bắt đầu
Re: pascan vấn đề thi hgs tin học
Cái này học ở học kì 1 rồi mà.
Tìm kiếm cái gì thế Thành?thành rất muôn thi hsg tin học vì thế thành lập topic này
có vấn đề này thanh nghiz mãi khônbg ra
tìm kiếm nhị phân dẫy sô gồm n số (n rất lớn 100 chữ số)
Cái này học ở học kì 1 rồi mà.
Re: pascan vấn đề thi hgs tin học
Cây nhị phân tổng quát là một tập hợp hữu hạn các đỉnh được xác định đệ quy như sau:
- Một tập trống là một cây nhị phân.
- Giả sử T1 và T2 là hai cây nhị phân không cắt nhau và r là một đỉnh mới không thuộc T1, T2. Khi đó ta có thể thành lập một cây nhị phân mới T với gốc r có T1 là cây con bên trái, T2 là cây con bên phải của gốc.
Cây nhị phân có thể trống, mỗi đỉnh của nó luôn luôn có hai cây con là cây con bên trái và cây con bên phải. Mỗi đỉnh của cây nhị phân chỉ có nhiều nhất là hai đỉnh con: một đỉnh con bên trái (đó là gốc của cây con trái) và một đỉnh con bên phải (đó là gốc của cây con phải).
Giải thích: http://buithetam.wordpress.com/2009/11/20/cay-tim-kiem-nhi-phan/
Cây nhị phân tổng quát là một tập hợp hữu hạn các đỉnh được xác định đệ quy như sau:
- Một tập trống là một cây nhị phân.
- Giả sử T1 và T2 là hai cây nhị phân không cắt nhau và r là một đỉnh mới không thuộc T1, T2. Khi đó ta có thể thành lập một cây nhị phân mới T với gốc r có T1 là cây con bên trái, T2 là cây con bên phải của gốc.
Cây nhị phân có thể trống, mỗi đỉnh của nó luôn luôn có hai cây con là cây con bên trái và cây con bên phải. Mỗi đỉnh của cây nhị phân chỉ có nhiều nhất là hai đỉnh con: một đỉnh con bên trái (đó là gốc của cây con trái) và một đỉnh con bên phải (đó là gốc của cây con phải).
Mã:
uses crt;
type nodePtr= ^node;
node= record
key: integer;
left,right: NodePtr
end;
var root,tk: nodePtr; x,chon,i,n: integer;
a: array[1..100] of integer; f: text;
procedure Chen(x: integer);
var p,q: nodePtr;
begin new(q); q^.key:=x; q^.left:=Nil; q^.right:=nil;
if root=NIL then root:=q else
begin p:=root;
while p<>NIL do
begin if x <>nil then p:=p^.left
else begin p^.left:=q; p:=nil end
end
else begin if x>p^.key then begin
if p^.right<>nil then p:=p^.right
else begin p^.right:= q; p:=nil end
end
else p:=nil;
end
end;
end;
end;
procedure TimKiem(x: integer; var p: nodePtr);
var found: boolean;
begin p:= root; found:= false;
while(p<>nil) and (not found) do
if p^.key=x then found:= true
else if x
end;
procedure InRong;
const max =50;
var truoc,cuoi,dem: integer; p,q: nodePtr;
h: array[1..max] of nodePtr;
begin h[1]:=root; truoc:=1; cuoi:=1; dem:=1;
while (dem>0) do
begin q:=h[truoc]; write(q^.key,’ : ‘); p:= q^.left;
if p<>nil then begin write(p^.key,’ – ‘); inc(cuoi);
h[cuoi]:=p; inc(dem);
end else write(‘NIL – ‘);
p:= q^.right;
if p<>nil then begin writeln(p^.key);
inc(cuoi); h[cuoi]:=P; inc(dem);
end else writeln(‘NIL’);
h[truoc]:=nil; inc(truoc); dec(dem);
end;
end;
procedure Xoa(var p: nodePtr);
var q,q1: nodePtr;
begin
if p^.right=NIL then begin q:=p; p:=p^.left end
else if p^.left=NIL then begin q:=p; p:=p^.right end
else begin q:= p^.left;
if q^.right=nil then begin p^.key:=q^.key;
p^.left:=q^.left
end
else begin
repeat q1:=q; q:=q^.right until q^.right=nil;
p^.key:=q^.key; q1^.right:= q^.left;
end
end;
dispose(q);
end;
procedure PreOrder(p: nodePtr);
begin if p<> nil then
begin writeln(p^.key); PreOrder(p^.left); PreOrder(p^.right) end;
end;
procedure InOrder(p: nodePtr);
begin if p<> nil then
begin InOrder(p^.left);writeln(p^.key); InOrder(p^.right) end;
end;
procedure PostOrder(p: nodePtr);
begin if p<> nil then
begin PostOrder(p^.left); PostOrder(p^.right); writeln(p^.key) end;
end;
begin root:=nil; clrscr;
repeat
writeln(’1.Chen 2.Xoa 3.TimKiem 4.InRong 5.PreOder ‘);
write(’6.InOrder 7.PostOrder 8.NhapTep 9.Exit. Chon:’);
readln(chon);
case chon of
1: begin write(‘Nhap khoa moi: ‘); readln(x); Chen(x);
end;
2: begin write(‘Nhap khoa can xoa: ‘); readln(x);
TimKiem(x,tk);
if tk<>nil then Xoa(tk)
else writeln(‘Khong tim thay gia tri khoa’);
end;
3: begin write(‘Nhap khoa can tim : ‘); readln(x);
TimKiem(x,tk);
if tk<>NIL then writeln(‘Da tim thay dinh co khoa : ‘,tk^.key)
else writeln(‘Khong tim thay dinh co khoa nay’);
end;
4: InRong;
5: begin writeln(‘Danh sach PreOrder: ‘); PreOrder(Root) end;
6: begin writeln(‘Danh sach InOrder: ‘); InOrder(Root) end;
7: begin writeln(‘Danh sach PostOrder: ‘); PostOrder(Root) end;
8: begin assign(f,’Cay.dat’); reset(f); readln(f,n);
for i:=1 to n do begin read(f,a[i]); Chen(a[i]) end;
close(f); write(‘Da nhap xong cay tu tep…’); readln;
end;
end
until chon=9;
end.Giải thích: http://buithetam.wordpress.com/2009/11/20/cay-tim-kiem-nhi-phan/
Re: pascan vấn đề thi hgs tin học
À tớ hiểu rồi! có phải ví dụ như:
cho trước 1 dãy số từ 1 đến 100 chẳng hạn
Sau đó cho x
Và tìm xem giá trị của x có nằm trong dãy không à?
Hay quá nhỉ !
Tớ muốn nhờ xem có ai chương trình tính tổng hình vuông của các cạnh mà mỗi ô lại là một hình vuông!
Ví dụ như tình tổng hình vuông của bàn cờ vua hay bàn cờ vây chẳng hạn!
Hoặc tình tổng những ô vuông có giá trị lơn hơn rất nhiều như 1tỉ ô chẳng hạn!
Sau đó xem tổng của chúng là chẵn hay lẽ. Nếu là lẽ thì có phải là số nguyên tố hay không!
À tớ hiểu rồi! có phải ví dụ như:
cho trước 1 dãy số từ 1 đến 100 chẳng hạn
Sau đó cho x
Và tìm xem giá trị của x có nằm trong dãy không à?
Hay quá nhỉ !
Tớ muốn nhờ xem có ai chương trình tính tổng hình vuông của các cạnh mà mỗi ô lại là một hình vuông!
Ví dụ như tình tổng hình vuông của bàn cờ vua hay bàn cờ vây chẳng hạn!
Hoặc tình tổng những ô vuông có giá trị lơn hơn rất nhiều như 1tỉ ô chẳng hạn!
Sau đó xem tổng của chúng là chẵn hay lẽ. Nếu là lẽ thì có phải là số nguyên tố hay không!
Re: pascan vấn đề thi hgs tin học
Nếu là y/c này của chú thì không khó:
1.Sắp xếp dãy tăng dần , mục đích để chia dãy thành 2 nửa khoảng (khoảng giá trị bé và khoảng giá trị lớn)
2.Viết hàm đệ qui để xác định nửa khoảng mà số x thuộc vào.
3.Nếu x = giá trị biên của nửa khoảng mà ta đã chia -->dừng lại, kết luận x thuộc dãy, nếu không thì quay lại bước 2.
Pascal thì a ngu lắm, nên anh chỉ nói giải thuật được thôi. (Chú thông cảm vì anh là dân Chăn Nuôi Trồng Trọt)
Nếu là y/c này của chú thì không khó:
1.Sắp xếp dãy tăng dần , mục đích để chia dãy thành 2 nửa khoảng (khoảng giá trị bé và khoảng giá trị lớn)
2.Viết hàm đệ qui để xác định nửa khoảng mà số x thuộc vào.
3.Nếu x = giá trị biên của nửa khoảng mà ta đã chia -->dừng lại, kết luận x thuộc dãy, nếu không thì quay lại bước 2.
Pascal thì a ngu lắm, nên anh chỉ nói giải thuật được thôi. (Chú thông cảm vì anh là dân Chăn Nuôi Trồng Trọt)
Re: pascan vấn đề thi hgs tin học
anh ơi giúp em ở câu hỏi trên với! Em thấy anh có vẻ giỏi trò này ghê!
anh ơi giúp em ở câu hỏi trên với! Em thấy anh có vẻ giỏi trò này ghê!
Re: pascan vấn đề thi hgs tin học
không hiểu đề bài kậu ạk hiểu chết liền . cho đề sâu hơn đê toàn ơi
không hiểu đề bài kậu ạk hiểu chết liền . cho đề sâu hơn đê toàn ơi
V
Re: pascan vấn đề thi hgs tin học
Cái này hình như trong sách nó có lời giải ở phần cuối mà ?
Néu dây tuột thì đó là cơ may đấy!
Cái này hình như trong sách nó có lời giải ở phần cuối mà ?
Néu dây tuột thì đó là cơ may đấy!
Sửa lần cuối:
Re: pascan vấn đề thi hgs tin học
Bài 2: Hoán vị đầu tầu
Xét một cơ cấu đường tầu vào kho để sửu chữa, với đường vào và đường ra cùng đi vào kho (giống stack). Giả sử đường vào có 4 đầu tầu 1, 2, 3, 4. Gọi V, R là phép đưa đầu tầu vào, ra khỏi kho. Nếu ta thực hiện một dãy VVRVVRRR thì thứ tự các đầu tầu trên đường ra sẽ là 2, 4, 3, 1. Như vậy ta có thể coi như hoán vị 2, 4, 3, 1 được tạo ra từ dãy VVRVVRRR.
Lập chương trình cho n đầu tầu và hoán vị tương ứng với n, xác định dãy sinh ra hoán vị đó nếu có, nếu không thông báo không tồn tại.
làm hộ với
Bài 2: Hoán vị đầu tầu
Xét một cơ cấu đường tầu vào kho để sửu chữa, với đường vào và đường ra cùng đi vào kho (giống stack). Giả sử đường vào có 4 đầu tầu 1, 2, 3, 4. Gọi V, R là phép đưa đầu tầu vào, ra khỏi kho. Nếu ta thực hiện một dãy VVRVVRRR thì thứ tự các đầu tầu trên đường ra sẽ là 2, 4, 3, 1. Như vậy ta có thể coi như hoán vị 2, 4, 3, 1 được tạo ra từ dãy VVRVVRRR.
Lập chương trình cho n đầu tầu và hoán vị tương ứng với n, xác định dãy sinh ra hoán vị đó nếu có, nếu không thông báo không tồn tại.
làm hộ với
V
Re: pascan vấn đề thi hgs tin học
Muốn làm hộ lắm ! Nhưng hông hiểu đề ?
Muốn làm hộ lắm ! Nhưng hông hiểu đề ?
Sửa lần cuối:
![[NT]kut3](/data/avatars/m/3/3998.jpg?1792605345){kind=avatar}
Re: pascan vấn đề thi hgs tin học
cái này trả bik nhưng nếu muốn làm thì lên hẳn cái web về IT + lập trình nhờ làm hộ nhiều thằng rảnh lắm.....
Re: pascan vấn đề thi hgs tin học
bài này dễ hơn mọi người làm thử xem sao nhé
Có n loại đồng xu, mỗi đồng có giá trị tương ứng là d1, d2, …dn. Muốn đổi một lượng tiền tương đương có giá trị là N xu ra tiền xu sao cho số đồng xu là ít nhất. Với giả thiết rằng, số đồng xu nhiều tuỳ ý.
bài này dễ hơn mọi người làm thử xem sao nhé
Có n loại đồng xu, mỗi đồng có giá trị tương ứng là d1, d2, …dn. Muốn đổi một lượng tiền tương đương có giá trị là N xu ra tiền xu sao cho số đồng xu là ít nhất. Với giả thiết rằng, số đồng xu nhiều tuỳ ý.
Sửa lần cuối:
V
Re: pascan vấn đề thi hgs tin học
Bài này ta chỉ cần dùng lệnh DIV và MOD là đổi được hết !
Bài này ta chỉ cần dùng lệnh DIV và MOD là đổi được hết !
Sửa lần cuối:
Thông báo pháp lý
Diễn đàn Trường THPT Đào Duy Từ - Thanh Hóa thành lập từ năm 2001 bởi các cựu học sinh trong trường.
Trường THPT Đào Duy Từ - 33 Lê Quý Đôn, phường Hạc Thành, tỉnh Thanh Hóa.