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ự (cac uoc so khong ke chinh no) của p bang q và tổng các số thực của q bang p.
giúp với :xuan-2015:
giúp với :xuan-2015:
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
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?
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?
Sửa lần cuối:
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 = 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
là tổng các ước của n ko tính chính nó, như vậy,
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.
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
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).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.
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 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.
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.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
Đầ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.
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.
#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.
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 đã.
Sau đó thì viết theo như lúc trc mình ghi ở post #4.
Đầ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;
}
Sửa lần cuối:
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ó.
- 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ó.
Bài viết mới nhất
-
Kho truyện ngắn cực hay- shopoga
-
Sách Hay Mỗi Ngày
- shopoga
-
COLORFUL công bố mini PC mang tên gọi CMNH01-12450- maychucongnghe
