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

Bài tập Pascal: Số chính

  1. #1
    Ðến Từ
    Bến Tre
    Thành Viên Thứ: 370515
    Bài gửi
    5

    Bài tập Pascal: Số chính

    Cho một dãy gồm N số. Một số trong dãy gọi là số chính nếu số lần xuất hiện của số đó lớn hơn N / 2. Viết chương trình tìm số chính trong dãy.Input: SOCHINH.INP: dòng đầu tiên gồm số N (N < 10^6), N dòng tiếp theo mỗi dòng ghi 1 số trong dãy, |ai| < 10^9.Output: SOCHINH.OUT: gồm 1 số duy nhất là chỉ số của số chính tìm được, -1 nếu không tồn tại số như vậy.
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    Bến Tre
    Thành Viên Thứ: 370515
    Bài gửi
    5

    Reply: Bài tập Pascal: Số chính

    Ai giúp em với ạ. Cám ơn nhiều.

  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: Bài tập Pascal: Số chính

    Sử dụng nguyên tắc nếu có 2 phần tử khác nhau trong dãy thì sự xuất hiện của nó sẽ cancel lẫn nhau (Moore Voting algorithm), bạn có thể làm bài này bằng 2 lần duyệt mảng.
    Mã:
    function majorityElement : longint;
    var i, index, count : longint;
    begin
        index := 1;
        count := 1;
        for i := 2 to n do
            begin
                if (a[i] = a[index]) then
                    inc(count)
                else
                    dec(count);
                if (count = 0) then
                    begin
                        index := i;
                        count := 1;
                    end;
            end;
        count := 0;
        for i := 1 to n do
            if (a[i] = a[index]) then
                inc(count);
        if (count > n div 2) then
            exit(index);
        exit(-1);
    end;

    Bạn cũng có thể không cần lưu lại mảng cũng đc; khi đó chỉ cần đọc file 2 lần là xong.
    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. 2 thành viên đã cảm ơn tengiday:


  5. #4
    Ðến Từ
    Nam Định
    Thành Viên Thứ: 368445
    Giới tính: Nam
    Bài gửi
    19

    Reply: Bài tập Pascal: Số chính

    Bài này đơn giản ý mà thuật toán của tui tối ưu nè 1 vòng for là ra { xem lại phần khai báo để tối ưu nhé tui làm tổng quát gần hết trường hợp thui }
    Mã:
    program so_chinh;
      Const Fi = 'SOCHINH.INP';
            Fo = 'SOCHINH.OUT';
      Var   F1 , F2 : Text;
            N ,i,max,sc,x: longint;
            A : Array[-1000010..1000010]of longint;
      Begin
    Assign(F1,Fi);
    Reset(F1);
    Assign(F2,Fo);
    Rewrite(F2);
            Readln(F1,N);
            For i:=1 to N do
               Begin
                     Read(F1,x);
                     A[x]:=A[x]+1;
                     if max<a[x] then
                     begin
                          max:=a[x];
                          sc:=x;
                     end;
               end;
    if max> (N div 2) then write(f2,sc)
    else write(f2,-1);
    close(F2);
      End.

  6. Đã cảm ơn hoangtungok123:


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

    Reply: Bài tập Pascal: Số chính

    Bạn xem lại giới hạn dữ liệu: 10^9 = 1 tỷ. Bạn cần 1 mảng 2 tỷ phần tử, mỗi phần tử là longint với 4 byte, tức là cần 8 tỷ byte = ??? GB RAM?
    Độ phức tạp thuật toán của bạn là O(n), cũng bằng với cách kia, nhưng bạn tiêu hao bộ nhớ quá lớn. Đấy là mình chưa tính tới phải tốn thời gian initialize mảng bằng 0 đấy. Mặc dù code ko có nhưng compiler nó vẫn phải chạy qua 2 tỷ phần tử để set từng ô giá trị 0.

    PS: sc = i mới đúng vì in ra chỉ số, chứ ko phải số chính.

  8. Đã cảm ơn tengiday:


  9. #6
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 146858
    Giới tính: Nam
    Bài gửi
    7.397

    Reply: Bài tập Pascal: Số chính

    Trích Nguyên văn bởi tengiday Xem bài viết
    Bạn xem lại giới hạn dữ liệu: 10^9 = 1 tỷ. Bạn cần 1 mảng 2 tỷ phần tử, mỗi phần tử là longint với 4 byte, tức là cần 8 tỷ byte = ??? GB RAM?
    Tính sơ sơ thì 8 tỷ byte bằng 8000 GB RAM thì phải
    Hãy nhấn nút Thank nếu thấy bài viết hữu ích
    Bộ sưu tập cực khủng

  10. Đã cảm ơn quanltv:


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

    Reply: Bài tập Pascal: Số chính

    Trích Nguyên văn bởi quanltv Xem bài viết
    Tính sơ sơ thì 8 tỷ byte bằng 8000 GB RAM thì phải
    Chưa tới 8GB RAM (giga ~ tỷ). Thật ra nếu space (bộ nhớ) ko giới hạn thì đây là 1 cách hay. Ví dụ như trong sort, cứ việc dùng 1 mảng bao trùm range của dữ liệu thì độ phức tạp của thuật toán chỉ còn O(n), chứ ko còn O(n log n) nữa. Cách này gọi là bucket sort.
    Tuy nhiên, quan trọng là cách làm #4 không làm thay đổi độ phức tạp của thuật toán (vẫn là O(n)), bởi vậy sẽ ko đc làm trong thật tế. Ví dụ như mảng input chỉ mỗi 2 phần tử mà phải dùng gần 8GB RAM thì quá nhiều. Ng` ta chỉ trade memory for speed trong một giới hạn nào đó.

  12. Đã cảm ơn tengiday:


  13. #8
    Ðến Từ
    Nam Định
    Thành Viên Thứ: 368445
    Giới tính: Nam
    Bài gửi
    19

    Reply: Bài tập Pascal: Số chính

    Trích Nguyên văn bởi tengiday Xem bài viết
    Chưa tới 8GB RAM (giga ~ tỷ). Thật ra nếu space (bộ nhớ) ko giới hạn thì đây là 1 cách hay. Ví dụ như trong sort, cứ việc dùng 1 mảng bao trùm range của dữ liệu thì độ phức tạp của thuật toán chỉ còn O(n), chứ ko còn O(n log n) nữa. Cách này gọi là bucket sort.
    Tuy nhiên, quan trọng là cách làm #4 không làm thay đổi độ phức tạp của thuật toán (vẫn là O(n)), bởi vậy sẽ ko đc làm trong thật tế. Ví dụ như mảng input chỉ mỗi 2 phần tử mà phải dùng gần 8GB RAM thì quá nhiều. Ng` ta chỉ trade memory for speed trong một giới hạn nào đó.
    Tớ còn nhiều thiếu sót mong mọi người giúp đỡ nhiều ạ!!

  14. Đã cảm ơn hoangtungok123: