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

Hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng các ước

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

    Exclamation Hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng các ước

    Quick reply to this message Trả lời       


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

    Reply: hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng cá

    p và q có yêu cầu trong khoảng nào không vậy bạn? Bạn viết đc thuật toán đơn giản nhất, tìm ước rồi tính tổng chạy trong bao lâu nếu số nhỏ trong cặp (p, q) nhỏ hơn 1 triệu?
    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.

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

    Reply: hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng cá

    trong khoảng dưới 1 triệu bạn, bạn giúp mình với.. mình chưa hiểu cái đề cho lắm ..

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

    Reply: hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng cá

    Trích Nguyên văn bởi Organvn Xem bài viết
    trong khoảng dưới 1 triệu bạn, bạn giúp mình với.. mình chưa hiểu cái đề cho lắm ..
    Cái cặp số trong đề bài gọi là amicable pair. Ví dụ:
    p = 220, q = 284.
    Tổng các ước số của p = 220 không tính chính nó là 284.
    Tổng các ước số của q = 284 không tính chính nó là 220.
    Đề bài yêu cầu là tìm các cặp số như trên.

    - Mình dùng (220, 284) bởi vì mình biết đây là cặp số nhỏ nhất thỏa mãn đk.
    - Đơn giản nhất là thế này: gọi s(n) là tổng các ước của n ko tính chính nó, như vậy,
    Mã:
    Với i từ 220 tới 1 triệu:
       Tính si := s(i).
       Nếu si > i thì
          Tính s(si).
          Nếu s(si) = i thì in ra cặp số (i, si).
    Bạn làm đơn giản thế trước cho nó chạy đã nhé. Chỉ có 1 cặp trong khoảng 1000.
    Vì giới hạn là 1 triệu, bạn làm đơn giản thì chương trình chạy trong 4 giây. Tối ưu thêm sẽ chạy được chưa tới 1/3 giây.

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

    Reply: hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng cá

    mình đã hiểu đc vấn đề, bạn có giải thích mình them chút nữa đc không .. đoạn mã trên minh chưa hiểu được.. hix thanks bạn nhiều

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

    Reply: hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng cá

    Trích Nguyên văn bởi Organvn Xem bài viết
    mình đã hiểu đc vấn đề, bạn có giải thích mình them chút nữa đc không .. đoạn mã trên minh chưa hiểu được.. hix thanks bạn nhiều
    Bạn đọc và ngẫm lại định nghĩa của cặp số cần tìm thì sẽ thấy mình cần tìm i sao cho s(s(i)) = i, với s(i) là tổng các ước số không tính chính nó của i. Bạn phải hiểu cái này trước mới hiểu được đoạn mã kia.
    Đầu tiên mình tính s(i), gọi kết quả là si. Sau đó tính s(si) rồi so sánh với i. Nếu bằng i thì i và s(i) là cặp số cần tìm.

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

    Reply: hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng cá

    #include<iostream.h>
    int main()
    {
    int n,m;
    int tn=0,tm=0;
    cin>>n>>m;
    for(int i=1;i<n;i++)
    if(n%i==0)
    tn=tn+i;
    for(int j=1;j<n;j++)
    if(m%j==0)
    tm=tm+j;
    if(tn==m&&tm==n)
    cout<<"ok";
    }

    nho ban giup mh vong lap nhap 1 so nhung xuat ra 2 so p va q nhu de bai voi.

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

    Reply: hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng cá

    Đầu tiên bạn cần 1 hàm tính tổng các ước số ko kể chính nó trước đã.
    Mã:
    unsigned sumDivisors(unsigned n) {
        unsigned s = 1;
        unsigned t = (unsigned)sqrt(n);
        for (unsigned i = 2; i <= t; ++i)
            if (n % i == 0)
                s += i + n / i;
        if (t * t == n)
            s -= t;
        return s;
    }
    Sau đó thì viết theo như lúc trc mình ghi ở post #4.

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

    Reply: hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng cá

    làm thế nào để biết độ phức tạp của thuật toán bạn. mh chỉ mới hiểu đc 1 ít . VD như bài nào là O(n2)phai ko a ban.Cam on ban

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

    Reply: hàm tìm tất cả các cặp số p,q; sao cho tổng các ước số thực sự (khong ke chinh no) sao cho tổng cá

    - Câu hỏi của bạn khá rộng. Nếu mà hiểu sơ sơ thì đó là số lần chạy của chương trình cho mỗi một giá trị (kích cỡ) của dữ liệu đầu vào. Sinh viên theo ngành CNTT từ năm thứ 3 sẽ đc học, và bất kỳ 1 lập trình viên thực thụ nào đều phải hiểu biết về độ phức tạp của thuật toán mình viết cả. Khi học về cấu trúc dữ liệu thì ko thể ko học về độ phức tạp của thuật toán.
    - Cái này nói kỹ ra thì phải là cả 1 bài giảng luôn, có hẳn 1 khóa học về cái này. Đơn giản về O(n^2) là 2 vòng lặp trong và ngoài, mỗi vòng chạy n lần.

    PS: Mình rất e dè mấy bài dạng số học, tìm số có tính chất này, tính chất kia; bởi vì thời gian tính toán cho 1 số đã là đa thức. Nếu như tìm nhiều số thì dễ dàng tạo nên n^2. Hầu hết các tối ưu chỉ giảm hệ số thời gian chứ ko giảm đc độ phức tạp của thuật toán. Với lại mấy bài này phải dùng kiến thức toán số học mới làm nhanh đc. Cuối cùng, mấy bài dạng này làm cho ra, làm cho chạy đc với số nhỏ thì rất dễ, nhưng làm cho chạy nhanh, chạy đc với dữ liệu lớn mới khó.