Nhờ các bạn làm bài tập Sắp xếp dãy số Tên file bài làm: DAYSO.PAS

Lập trình thực hiện các công việc sau đây


Bài 1. Sắp xếp dãy số Tên file bài làm: DAYSO.PAS


Cho dãy số nguyên
a1, a2, ..., an (n £ 1000).
Hãy tìm cách thực hiện một số ít nhất phép đổi chỗ hai số hạng bất kỳ của dãy để thu được dãy số mà số lẻ đứng ở vị trí lẻ, số chẵn đứng ở vị trí chẵn.

Dữ liệu: Vào từ file văn bản DAYSO.INP:
· Dòng đầu tiên chứa số nguyên dương n;
· Dòng thứ i trong số n dòng tiếp theo chứa số hạng ai của dãy đã cho (-32767 £ ai £ 32767, i = 1, 2, ..., n).
Kết quả: ghi ra file văn bản DAYSO.OUT:
· Dòng đầu tiên ghi số lượng phép đổi chỗ cần thực hiện k (qui ước k = -1, nếu không thể biến đổi được dãy đã cho thành dãy thoả mãn yêu cầu đầu bài);
· Nếu k > 0, thì dòng thứ j trong số k dòng tiếp theo ghi chỉ số của hai số hạng cần đổi chỗ cho nhau ở lần đổi chỗ thứ j ( j =1, 2, ..., k).
Ví dụ:

DAYSO.INP
DAYSO.OUT
DAYSO.INP
DAYSO.OUT
6
1
2
3
4
6
5
1
5 6
4
1
3
2
5
-1



Bài 2. Thời điểm gặp mặt Tên file bài làm: MEETING.PAS

Một nhóm gồm n bạn học sinh của một lớp tham gia một câu lạc bộ tin học vào dịp nghỉ hè. Biết rằng khoảng thời gian mà bạn thứ i có mặt tại câu lạc bộ là [ai, bi] (ai<bi tương ứng là các thời điểm đến và rời khỏi câu lạc bộ). Cô giáo chủ nhiệm lớp muốn tới thăm các bạn trong nhóm này. Hãy giúp cô giáo chủ nhiệm xác định thời điểm đến câu lạc bộ sao cho tại thời điểm đó cô giáo có thể gặp được nhiều bạn trong nhóm nhất.


Dữ liệu: Vào từ file văn bản MEETING.INP:
· Dòng đầu tiên ghi số nguyên dương n (n <= 1000);
· Dòng thứ i trong số n dòng tiếp theo ghi 2 số nguyên không âm ai, bi , i = 1, 2, ..., n.
Kết quả: Ghi ra file văn bản MEETING.OUT:
· Dòng đầu tiên ghi số nguyên dương k là số lượng bạn đang có mặt ở câu lạc bộ tại thời điểm cô giáo đến;
· Trong k dòng tiếp theo ghi chỉ số của k bạn có mặt ở câu lạc bộ tại thời điểm cô giáo đến, mỗi dòng ghi một chỉ số của một bạn.





Ví dụ:

MEETING.INP
MEETING.OUT
MEETING.INP
MEETING.OUT
6
1 2
2 3
2 5
5 7
6 7
9 11
3
1
2
3
5
1 2
3 5
7 9
11 15
17 21
1
1



 
T

trần đức anh

Reply: Nhờ cácbạn xem hai bai tap nay giúp minh voi ak

e chỉ làm đc bài 1 thou,với lại nó hơi rắc rối vs khó hiểu

uses crt,strutils;
var n,i,j,sohoandoi,hoandoi,s:integer;
a,b:array[1..100]of integer;
fi,fo:text;
begin
sohoandoi:=0;
s:=0;
assign(fi,'dayso.int');
{$i-}
reset(fi);
{$i+}
if ioresult<>0 then write ('loi')else
begin
readln(fi,n);
for i:=1 to n do
readln(fi,a);
close(fi);
assign(fo,'dayso.out');
rewrite(fo);
for i:=1 to n do
if (a mod 2<>i mod 2) then
begin
s:=s+1;
b:=a;
for j:=i+1 to n do
if (j mod 2<>i mod 2)and(a[j] mod 2=i mod 2) then
begin
s:=s+1;
b:=a[j];
hoandoi:=a;
a:=a[j];
a[j]:=hoandoi;
sohoandoi:=sohoandoi+1;
break;
end;
end;
if (sohoandoi=0)or(s mod 2=1) then sohoandoi:=-1;
writeln(fo,sohoandoi);
if sohoandoi>0 then
for i:=1 to s do
write(fo,b,' ');
close(fo);
end;
readln
end.
 
T

tengiday

Happy life
Reply: Nhờ cácbạn xem hai bai tap nay giúp minh voi ak

Bài 1:
Để làm đc bài này thì có một số nhận xét sau:
- Nếu a ở đúng vị trí thì ko cần phải đổi nó đi đâu cả.
- Nếu a là chẵn và ở sai vị trí thì chỉ có thể đổi nó với một a[j] lẻ nào đó và ở sai vị trí (và ngược lại).
- Bởi vậy, bài toán có đáp án nếu số phần tử chẵn đứng sai vị trí bằng số phần tử lẻ đứng sai vị trí.
Cách thực hiện:
- Đọc file lần 1 xác định số phần tử chẵn sai vị trí và số phần tử lẻ sai vị trí. Nếu không bằng nhau thì in ra -1, nếu bằng nhau thì sang bước 2.
- Mình sẽ dùng 1 mảng b lưu vị trí đứng sai của những phần tử, và b_n là số lượng phần tử trong b. Chỉ cần đi 1 lần từ trái sang phải, nếu có 1 số nào đó mà "tương ứng" với một phần tử trong b, thì in ra vị trí của số mới này và b[b_n]; đồng thời giảm b_n đi 1.
Bài này làm khéo thì thuật toán có độ phức tạp O(n), và dùng O(n) bộ nhớ. Ko cần lưu mảng a lại vì có thể đọc file lần nữa.

Bài 2:
- Chiếu toàn bộ a và b lên trục số. Lưu ý rằng cần lưu lại xem số đó là bắt đầu hay kết thúc của những thời gian nào. Bạn sẽ cần 1 mảng 2n để làm điều này.
- Sort mảng này lại. Lưu ý rằng nếu 2 số giống nhau thì lúc nào số là thời gian bắt đầu phải đứng trước số là thời gian kết thúc.
- Đi từ trái sang phải, dùng 1 biến counter để đếm. Nếu nó là bắt đầu của 1 thời gian thì tăng counter lên, nếu là kết thúc của thời gian thì giảm counter. Vị trí mà counter max chính là giá trị cần tìm.
- Lưu ý: chúng ta cần xét thời gian bắt đầu trc bởi vì thời gian tại đầu mút vẫn tính.
Thuật toán có độ phức tạp O(n log n), chủ yếu do quá trình sort.

Bạn đọc và ngẫm nghĩ trước nhé, có gì cứ hỏi. Mình tạm thời chưa có thời gian viết code.
 
V

vansonqtqb

Reply: Nhờ cácbạn xem hai bai tap nay giúp minh voi ak

Cho mình xin code dk ko ak..vì đọc ý tưởng của bạn mình cũng ko hiểu lắm bạn.thank bạn
 
T

tengiday

Happy life
Reply: Nhờ cácbạn xem hai bai tap nay giúp minh voi ak

vansonqtqb:
Cho mình xin code dk ko ak..vì đọc ý tưởng của bạn mình cũng ko hiểu lắm bạn.thank bạn
Nhấn để mở rộng...
Mình viết vội nên chưa test kỹ; bạn cần kết hợp những gì mình nói với code để hiểu nhé.
Bài 1:
Như mình đã nói, mảng a là không cần lưu cũng đc. Vì máy mình ko có Pascal nên mới viết bằng mảng cho nhanh. Đầu tiên bạn đọc file xác định số phần tử chẵn và lẻ đứng sai vị trí theo như bước 1. Bước này đơn giản. Sau đó quét lại một lần nữa đưa phần tử vào mảng 'b' và lấy ra nếu có phần tử "tương ứng". Mảng 'b' này hoạt động giống như stack vậy.
Mã: 
procedure matchUp;
var i, m, OE : integer;
begin
    OE := 0; // 0 for empty, 1 for odd, 2 for even
    m := 0;
    for i := 1 to n do
        if (a[i] mod 2 = 0) and (i mod 2 <> 0) then // số chẵn đứng sai vị trí.
            begin
                if (OE = 0) or (OE = 2) then // b rỗng hoặc chứa vị trí số chẵn đứng sai.
                    begin
                        inc(m);
                        b[m] := i;
                        OE := 2;
                    end
                else // b chứa vị trí số lẻ đứng sai.
                    begin
                        writeln(b[m], ' ', i);
                        dec(m);
                        if (m = 0) then
                            OE := 0;
                    end;
            end
        else if (a[i] mod 2 <> 0) and (i mod 2 = 0) then // số lẻ đứng sai vị trí.
            begin
                if (OE = 0) or (OE = 1) then // b rỗng hoặc chứa vị trí số lẻ đứng sai.
                    begin
                        inc(m);
                        b[m] := i;
                        OE := 1;
                    end
                else // b chứa vị trí số chẵn đứng sai.
                    begin
                        writeln(b[m], ' ', i);
                        dec(m);
                        if (m = 0) then
                            OE := 0;
                    end;
            end;
end;
Bài này có thể cho n tới 20 000 cũng chạy tốt.

Bài 2:
Đầu tiên bạn chiếu hết các a và b lên trục số. Mình dùng mảng index để lưu xem đó là thời gian rỗi của ai. Lưu ý, nếu là a thì phải lưu index thành số âm để đánh dấu cho bắt đầu, nếu là b thì lưu index thành số dương để đánh dấu cho kết thúc.
[ah]
Mã: 
procedure readInput;
var i, n : integer;
begin
    readln(n);
    m := 0;
    for i := 1 to n do
        begin
            inc(m);
            read(a[m]);
            index[m] := -i;
            inc(m);
            readln(a[m]);
            index[m] := i;
        end;
end;
[/ah]
Tiếp theo là dùng quick sort để sort lại, nếu 2 số bằng nhau thì số có index âm đứng trước. Khi đổi chỗ thì bạn nhớ đổi trên mảng index luôn. Phần này mình để lại cho bạn. Cuối cùng thì xử lý như mình đã nói. Nếu là thời điểm bắt đầu thì cộng counter; nếu là kết thúc thì giảm đi. Ngoài ra, lúc nào cũng phải tìm thời điểm bắt đầu trc vì thời gian tại đầu mút vẫn tính.
Mã: 
procedure process;
var i, counter, counterMax, indexMax : integer;
begin
    counter := 0;
    counterMax := 0;
    indexMax := 0;
    for i := 1 to m do
        if (index[i] < 0) then
            begin
                inc(counter);
                if (counter > counterMax) then
                    begin
                        counterMax := counter;
                        indexMax := i;
                    end;
            end
        else
            dec(counter);
    writeln(counterMax);
    while (indexMax > 0) and (index[indexMax] < 0) do
        begin
            writeln(abs(index[indexMax]),' ');
            dec(indexMax);
        end;
end;
Muốn biết cô giáo đến ở thời điểm nào thì nhìn vào 'a[indexMax]' :). Bài này có thể cho n tới 10 000 cũng chạy tốt.
 
Sửa lần cuối:
V

vansonqtqb

Reply: Nhờ cácbạn xem hai bai tap nay giúp minh voi ak

đoạn code sắp sếp của mình đây. mình nhờ bạn đổi chỗ mảng index trên sort này cho mình với.
procedure QuickSort(L,H:longint);
var i,j :longint;
x,tmp :longint;
begin
i:=L;
j:=H;
x:=a[(L+H) div 2];
repeat
while a<x do inc(i);
while a[j]>x do dec(j);
if i<=j then
begin
tmp:=a;
a:=a[j];
a[j]:=tmp;
inc(i);
dec(j);
end;
until i>j;
if L<j then QuickSort(L,j);
if i<H then QuickSort(i,H);
end;
cho mình hỏi cái này luôn. chiếu lên truc số ở đây có nghĩa là mình đưa a và b thành mảng 2n như thế này phải ko bạn
A

[TD]1
[/TD]
[TD]2
[/TD]
[TD]2
[/TD]
[TD]3
[/TD]
[TD]…
[/TD]
[TD]
[/TD]
[TD]
[/TD]
[TD]
[/TD]
[TD]
[/TD]
[TD]
[/TD]
[TD]
[/TD]
[TR]
[TD]index
[/TD]
[TD]-1
[/TD]
[TD]2
[/TD]
[TD]-3
[/TD]
[TD]4
[/TD]
[TD]..
[/TD]
[TD]
[/TD]
[TD]
[/TD]
[TD]
[/TD]
[TD]
[/TD]
[TD]
[/TD]
[TD]
[/TD]
[/TR]
 
T

tengiday

Happy life
Reply: Nhờ cácbạn xem hai bai tap nay giúp minh voi ak

Mình dựa trên đoạn code của bạn. Chỗ màu đỏ là mình thêm vào đổi chỗ trên mảng index. Còn chỗ im đậm màu xanh là bạn phải viết lại để sort cho phù hợp với điều kiện "khi 2 số bằng nhau thì số có index âm phải nhỏ hơn số có index dương".
[ah]
Mã: 
procedure QuickSort(L, H : longint);
var i, j : longint;
     x, tmp : longint;
begin
    i := L;
    j := H;
    [COLOR=#0000ff][B]x := a[(L+H) div 2];[/B][/COLOR]
    repeat
        while [COLOR=#0000ff][B]a[i] < x[/B][/COLOR] do inc(i);
        while [COLOR=#0000ff][B]a[j] > x[/B][/COLOR] do dec(j);
        if i <= j then
        begin
            [COLOR=#ff0000]swap(a[i], a[j]);[/COLOR]
            [COLOR=#ff0000]swap(index[i], index[j]);[/COLOR]
            inc(i);
            dec(j);
        end;
    until i > j;
    if L < j then QuickSort(L, j);
    if i < H then QuickSort(i, H);
end;
[/ah]
Về chiếu a và b lên trục số thì mình ví dụ thế này:
Đây là dữ liệu ban đầu:
i123456
a

[TD]1[/TD]
[TD]2[/TD]
[TD]2[/TD]
[TD]5[/TD]
[TD]6[/TD]
[TD]9[/TD]
[TR]
[TD]b[/TD]
[TD]2[/TD]
[TD]3[/TD]
[TD]5[/TD]
[TD]7[/TD]
[TD]7[/TD]
[TD]11[/TD]
[/TR]


Khi mình đọc file vào thì chiếu lên trục số luôn, ko cần lưu lại mảng a và b riêng.
i123456789101112
a

[TD]1[/TD]
[TD]2[/TD]
[TD]2[/TD]
[TD]3[/TD]
[TD]2[/TD]
[TD]5[/TD]
[TD]5[/TD]
[TD]7[/TD]
[TD]6[/TD]
[TD]7[/TD]
[TD]9[/TD]
[TD]11[/TD]
[TR]
[TD]index[/TD]
[TD]-1[/TD]
[TD]1[/TD]
[TD]-2[/TD]
[TD]2[/TD]
[TD]-3[/TD]
[TD]3[/TD]
[TD]-4[/TD]
[TD]4[/TD]
[TD]-5[/TD]
[TD]5[/TD]
[TD]-6[/TD]
[TD]6[/TD]
[/TR]



Bạn có thể tham khảo đoạn code đọc input của mình ở trên.
 
Đăng nhập bằng tài khoản VFO hoặc Google

Bài viết mới nhất

Thống kê

Chủ đề
100,657
Bài viết
467,424
Thành viên
339,832
Thành viên mới nhất
tiendungmobi

Bài viết được quan tâm nhiều

Top