đề thi học sinh giỏi

[lehang_gb1]

Hôm nay thi học sinh giỏi cấp trường mình có bài toán này các bạn tham khảo và giải nhé
Cho hai dãy số nguyên U=(u1,u2,.....,um) và V=(v1,v2,....,vm). Các phần tử của mỗi dãy được sắp xếp theo thứ tự không giảm, mỗi phần tử có giá trị tuyệt đối không quá 32000. Hãy hòa hai dãy U và V thành dãy không giảm.

[hcvtpt]

bài này hay phết, cũng k đơn giản, k phức tạp

[máterl]

theo cách của rieng minh thui nhé.. tạo thêm một mảng để lưu kết quả, khởi tạo mảng này bằng 0 bằng câu lệnh fillchar.
bạn đọc dãy u sau đó i:=u[j]; inc(i);
bạn đọc dãy v và làm như trên.. nhớ i là chỉ số phần tử của mảng mới..
sau đó: for i to 32000
if a[i]>1 then xuất ra...
bạn thử làm nhé.. có gi để lại lời nhắn..

[Heroboss12]

m giới hạn là mấy thế lehang_gb1

[lehang_gb1]

m đơn giản là số nguyên, giới hạn m khôg quan trọng đâu

[=========> Bổ sung bài viết <=========]


theo cách của rieng minh thui nhé.. tạo thêm một mảng để lưu kết quả, khởi tạo mảng này bằng 0 bằng câu lệnh fillchar.
bạn đọc dãy u sau đó i:=u[j]; inc(i);
bạn đọc dãy v và làm như trên.. nhớ i là chỉ số phần tử của mảng mới..
sau đó: for i to 32000
if a[i]>1 then xuất ra...
bạn thử làm nhé.. có gi để lại lời nhắn..

Thực sự tớ thấy ý tưởng của bạn chẳng ra thế nào. Thế bạn thử viết chương trình xem sao nào?

[máterl]

lehang_gb1 d thu lam theo cach cua minh chua????

[duynhan1]

Hôm nay thi học sinh giỏi cấp trường mình có bài toán này các bạn tham khảo và giải nhé
Cho hai dãy số nguyên U=(u1,u2,.....,um) và V=(v1,v2,....,vm). Các phần tử của mỗi dãy được sắp xếp theo thứ tự không giảm, mỗi phần tử có giá trị tuyệt đối không quá 32000. Hãy hòa hai dãy U và V thành dãy không giảm.

Var i,j:integer;
m:integer;
u,v:array[1..100] of integer;
Begin
Readln(m);
For i:=1 to m-1 do Read(u[i]); Readln(u[m]);
For i:=1 to m do Read(v[i]):
u[m+1]:=-32000;
v[m+1]:=-32000;
i:=1;
j:=1;
While (i<m+1) or (j<m+1) do
Begin
If (u[i]>v[j]) then
Begin
Write(u[i]:5);
inc(i);
End else
Begin
Write(v[j]:5);
inc(j);
End;
End;{End While}
Readln;
End.

[máterl]

duynhan1 có cố gắng nhưng sai rồi.. hi... bạn thử test 2 dãy u và v có số âm và có phần tử giống nhau xem.. sai.. hjk hjk :((

[technolt]

Bài này tư tưởng rất đơn giản, nó là phần hợp của thuật toán Merge sort.
Merge sort là thuật toán sắp xếp dựa trên tư tưởng chia để trị. Một thuật toán chia để trị thường gồm 3 phần: phần chia, phần trị, và phần hợp. Bạn có thể đọc thêm sách để tham khảo.

[lehang_gb1]

code đây


Var A,B,C:array[1..100] of integer;
i,m,h,k:integer;
Begin
write('Nhap vao so phan tu:');
Readln(m);
For i:=1 to m do
Begin
write('A[',i,']=');
Readln(A[i]);
End;
For i:=1 to m do
Begin
write('B[',i,']=');
Readln(B[i]);
End;
h:=1;k:=1;A[m+1]:=32001;B[m+1]:=32001;
For i:=1 to 2*m do
if A[h]<B[k] then
begin
C[i]:=A[h];
inc(h);
End
else
begin
C[i]:=B[k];
inc(k);
End;
For i:=1 to 2*m do write(C[i]:3);
Readln
End.

[duynhan1]

Var i,j:integer;
m:integer;
u,v:array[1..100] of integer;
Begin
Readln(m);
For i:=1 to m-1 do Read(u[i]); Readln(u[m]);
For i:=1 to m do Read(v[i]):
u[m+1]:=-32000;
v[m+1]:=-32000;
i:=1;
j:=1;
While (i<m+1) or (j<m+1) do
Begin
If (u[i]>v[j]) then
Begin
Write(u[i]:5);
inc(i);
End else
Begin
Write(v[j]:5);
inc(j);
End;
End;{End While}
Readln;
End.

Sai ở đâu nhỉ :o. So sánh lần lượt rồi in ra chứ cóchi đâu mà sai :O

[lehang_gb1]

sắp xếp không giảm cơ mà, bạn sắp xếp không tăng rồi

[duynhan1]

sắp xếp không giảm cơ mà, bạn sắp xếp không tăng rồi

:D thì đổi dấu :(
duynhan1 có cố gắng nhưng sai rồi
Tớ chỉ tức câu này thôi. Nghe hơi kiêu >"<

Var i,j:integer;
m:integer;
u,v:array[1..100] of integer;
Begin
Readln(m);
For i:=1 to m-1 do Read(u[i]); Readln(u[m]);
For i:=1 to m do Read(v[i]):
u[m+1]:=-32000;
v[m+1]:=-32000;
i:=1;
j:=1;
While (i<m+1) or (j<m+1) do
Begin
If (u[i]<v[j]) then
Begin
Write(u[i]:5);
inc(i);
End else
Begin
Write(v[j]:5);
inc(j);
End;
End;{End While}
Readln;
End.

[hcvtpt]

@lehang_gb1: bạn thi hsg cấp trường THCS hay THPT vậy?

[nguyenthong1593]

bài này đơn giản bạn có thể quy tất cả về một mảng rồi sắp xếp cũng được vậy! nhưng hơi bị lâu rồi nhưng không bị sai! thuật toán hơi bị tệ!hjhj
Đứa cũng về một mảng có cả số âm cũng không sao cả! Sắp xếp tăng dần!
Có gì không đúng mong các bác bỏ qua!!
(_DongHwa_)

[mini_bestboy]

duynhan1 có cố gắng nhưng sai rồi.. hi... bạn thử test 2 dãy u và v có số âm và có phần tử giống nhau xem.. sai.. hjk hjk :((


Mình thì không thấy nó sai gì cả ngoại trừ việc không tăng - không giảm. Nhưng cái đó không quan trọng, chủ yếu là cái thuật toán đã đúng rôi kìa. Và việc số âm hay hai số bằng nhau thì có ảnh hưởng gì ?

Cách của bạn cũng được, nhưng nếu đề cho |u[i]| hay |v[i]| >> (cỡ vài trăm triệu) thì thuật toán bạn chạy không nổi đâu há, và cách của bạn nhìn chung ko hiệu quả ở nhiều trường hợp ( độ chênh lệch các số lớn)

Mình thì nghĩ cách bạn duynhan1 là tối ưu rồi, độ phức tạp cũng cỡ O(m) thôi !