kết quả từ 1 tới 7 trên 7

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

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    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



    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    Kiên Giang
    Thành Viên Thứ: 362089
    Giới tính: Nam
    Bài gửi
    1

    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[i]);
    close(fi);
    assign(fo,'dayso.out');
    rewrite(fo);
    for i:=1 to n do
    if (a[i] mod 2<>i mod 2) then
    begin
    s:=s+1;
    b[s]:=a[i];
    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[s]:=a[j];
    hoandoi:=a[i];
    a[i]:=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[i],' ');
    close(fo);
    end;
    readln
    end.

  3. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    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[i] ở đúng vị trí thì ko cần phải đổi nó đi đâu cả.
    - Nếu a[i] 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[i] và b[i] 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.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  4. Đã cảm ơn tengiday:


  5. #4
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    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

  6. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Trích Nguyên văn bởi vansonqtqb Xem bài viết
    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
    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[i] và b[i] 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[i] thì phải lưu index thành số âm để đánh dấu cho bắt đầu, nếu là b[i] thì lưu index thành số dương để đánh dấu cho kết thúc.
    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;

    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.

  7. Đã cảm ơn tengiday:


  8. #6
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    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[i]<x do inc(i);
    while a[j]>x do dec(j);
    if i<=j then
    begin
    tmp:=a[i];
    a[i]:=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[i] và b[i] thành mảng 2n như thế này phải ko bạn
    A[i] 1 2 2 3
    index -1 2 -3 4 ..

  9. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    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".
    Mã:
    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[i] < x do inc(i);
            while a[j] > x do dec(j);
            if i <= j then
            begin
                swap(a[i], a[j]);
                swap(index[i], index[j]);
                inc(i);
                dec(j);
            end;
        until i > j;
        if L < j then QuickSort(L, j);
        if i < H then QuickSort(i, H);
    end;

    Về chiếu a[i] và b[i] lên trục số thì mình ví dụ thế này:
    Đây là dữ liệu ban đầu:
    i 1 2 3 4 5 6
    a[i] 1 2 2 5 6 9
    b[i] 2 3 5 7 7 11

    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.
    i 1 2 3 4 5 6 7 8 9 10 11 12
    a[i] 1 2 2 3 2 5 5 7 6 7 9 11
    index[i] -1 1 -2 2 -3 3 -4 4 -5 5 -6 6


    Bạn có thể tham khảo đoạn code đọc input của mình ở trên.