bạn chỉ cần đổi công thức tính là
a= 1 - 3 + 5 -7 +...+(-1)^(n-1)(2*n-1)
giờ bạn có thể làm được rồi chứ
vd: mình muốn tính bài toán này
a = 1 - 3 + 5 - 7 + 9 ... (+/-) (2*n-1).
điều kiện nhập vào số n (nguyên dương) và viết bằng đệ quy.
unsigned long ketqua(int n)
{
// làm sao giải quyết cài dấu +,-
}
bạn chỉ cần đổi công thức tính là
a= 1 - 3 + 5 -7 +...+(-1)^(n-1)(2*n-1)
giờ bạn có thể làm được rồi chứ
có nhiều cách để làm điều này, cách dễ thấy là:
bạn cần phát hiện tính chất của dãy số đó
ví dụ như
n=1 -> dấu +
n=2 -> dấu -
n=3 -> dấu +
...
từ đó suy ra cách làm. Với tính chất như trên thì 1 cách làm cụ thể là:
bạn nói đúng, mình cũng đồng ý như thế, nhưng cái công thức của bạn sử dụng pow (hàm mũ) rất hao tốn performanceCode:long ketqua(int n) /*bạn dùng unsigned long là chưa chính xác*/ { if (n==0) return 0 /*điều kiện thoát đệ quy, điều kiện thoát là điều bắt buộc khi viết đệ quy */ int sign=-1; if (n%2 > 0) sign=1; /* 2 dòng trên là để xử lý dấu như bạn mong muốn */ return (sign*2*(n-1)) + ketqua(n-1); }
bạn nên biết
những phép toán trên số thực luôn tốn hơn gấp nhiều lần về thời gian thực hiện so với số nguyên
những phép toán trên số thực dấu chấm động ví dụ như hàm pow, sqrt, ... luôn tốn hơn gấp nhiều lần về thời gian thực hiện so với số thực dấu chấm tĩnh
Tui nghĩ mình có thể làm:
hàm ketqua(unsigned int n, int sign): sẽ gọi đệ qui ketqua(n+2, -sign)
Hàm này có thể tính:
sign*n
hoặc:
nếu sign > 0 thì xài n, ngược lại thì xài -n
(có gì sai sót mong được góp ý, xin cám ơn)
-thân
Đầu tiên bạn xem đoạn giả lập hàm mủ của tôi.
http://forums.congdongcviet.com/showthread.php?t=909
Tiếp theo tôi giải quyết bài trên của bạn như sau (không dùng đệ quy):
Từ đây tôi tổng quát hóa lên:Code:n=1 KQ=1 n=2 KQ=1+3 n=3 KQ=1+3-5=1-2 n=4 KQ=1+3-5+7=1-2+7 n=5 KQ=1+3-5+7-9=1-2-2=1-2*2 n=6 KQ=1+3-5+7-9+11=1-2*2+11 n=7 KQ=1+3-5+7-9+11-13=1-2-2-2=1-2*3
Từ đây ta có thuật toán sau:Code:nếu n=1 KQ=1 nếu n!=1 n chẳn KQ=1-2*((n-1)/2)+(2*n-1) nếu n!=1 n lẻ KQ=1-2*((n-1)/2). chú ý :(n-1)/2 phải là phép chia lấy phần nguyên.
Code:long Ketqua(unsigned int n) { int KQ; if(n==0)return 0; if(n==1)return 1; KQ=1-2*((n-1)/2); if(n%2==0) KQ=KQ+(2*n-1); return KQ; }
Đã được chỉnh sửa lần cuối bởi shinichi_haha : 04-12-2006 lúc 04:18 PM.
=> tui nghĩ bạn bị lộn về dấu:n=1 KQ=1
n=2 KQ=1+3
n=3 KQ=1+3-5=1-2
n=4 KQ=1+3-5+7=1-2+7
n=5 KQ=1+3-5+7-9=1-2-2=1-2*2
n=6 KQ=1+3-5+7-9+11=1-2*2+11
n=7 KQ=1+3-5+7-9+11-13=1-2-2-2=1-2*3
n=7 KQ=1-3+5-7+9-11+13 chớ không phảI KQ=1+3-5+7-9+11-13
Thêm nữa tui nghĩ có lẽ người ra đề muốn mình tập dợt đệ qui.
Cách giải của bạn ra ngoài luồng suy nghĩ bình thường (có lẽ mọi người bị chữ "đệ qui" làm cho không suy nghĩ ra hướng khác) => rất hay !!!
Nếu làm theo hướng của bạn, để cho chặt chẽ tui nghĩ nên xài hiệu của 2 cấp số cộng
(có gì sai sót mong được góp ý, xin cám ơn)
-thân
Còn viết theo đệ quy như sau:
Ta thấy bài toán được phân tích là f(n)=f(n-1) + [-] (2*n-1)
với + khi n chẳn. - khi n lẻ.
code bài toán đơn giản như sau:
Code:long Ketqua(unsigned int n) { if(n==0)return 0; if(n==1)return 1; if(n%2==0)return Ketqua(n-1)+(2*n-1); return Ketqua(n-1)-(2*n-1); }
cảm ơn các bạn đã có nhiều góp ý.
bài này mình muốn làm đệ quy, với giá trị nhập vào là n, kết thúc là (+/-) (2*n-1).
xét phần (+/-) dùng cách của bạn "buianhtuanhn" (-1)^(n-1) => đã giải quyết rất tốt. (một số bạn có nhầm lẫn, ở đây không có giá trị chẵn, nên không dùng chẳn lẻ để xét dấu)
phần giá trị cuối (2*n-1) hình như các bạn chưa làm đúng. mong tiếp tục nhận được góp ý.
Đúng rồi mình có hơi nhầm dấu!==>Sai bài toán
Ở đây a = 1 - 3 + 5 - 7 + 9 ... (+/-) (2*n-1).Nguyên bản được gửi bởi def
thì hàm đệ quy của nó như sau f(n)=f(n-1)+ (-1)^(n-1)*(2*n-1);
thì nếu n là chẳn thì có phải f(n)=f(n-1)-(2*n-1);
nếu n là lẻ thì f(n)=f(n-1)+(2*n-1) đúng không ?Ở đây mình xét chẳn lẻ của n.
Vậy code chuong trình viết theo đệ quy là:
Code:long f(unsigned int n) { if(n==0)return 0; if(n==1)return 1; if(n%2==0)return f(n-1)-(2*n-1); return f(n-1)+(2*n-1); }
mình chạy thử:Nguyên bản được gửi bởi shinichi_haha
gọi hàm printf ("%d",f(2));
Code:=> f(n = 2) => (n%2=0) = TRUE return f(1) - (1); đệ quy f(1) => f(n = 1) => return 1; => vây bài này sẽ là 1 - 1 = 0; nhưng theo ý mình gọi f(2) => triển khai ra sẽ là f = 1 - 3 = -2; có lẽ bài này vẫn sai.