Nhằm mục đích tạo không khí học tập xua tan sự nhàm chán của những ngày ở nhà một mình :amazed:. Mình post một bài toán cho các bạn cùng giải cho vui nhé, tiện thể ôn lại kiến thức căn bản luôn. Các bài tập từ dễ đến khó, mình thì không giải hết được đâu, mong các bro như thầy toannv, thầy tuanta, anh truongan, Đăng Châu, Thiên điệp…các bạn trong đội tuyển olympic cũng như các thầy làm cố vấn nhé :love:. Về giải thưởng hay thống kê cho những bạn giải được nhiều bài thì mong BQT giúp đỡ :sexy:. Các bạn có thể dùng ngôn ngữ gì cũng được, chạy chương trình rồi chụp kết quả và post lên :D, post lên code luôn nhé :funny:
Bài toán 1 (thứ 7-7/7/2012):
[SIZE=3]Viết chương trình tính tổng sau: 1/2 + 1/4 + 1/8 + 1/16 +…+1/N[/SIZE]
Cho N là vô cùng lớn N<(10^9), N có dạng 2^K, time limit = 1s.
Dễ mà phải không , 
p/s: đã fix :dribble:
Chú nên nhớ đề bài cho nên có giới hạn time và giới hạn các dữ liệu. VD như time = 1.0s 0<=N<= 10^6
Mình nghĩ đề nó thiếu ràng buộc là N có dạng 2 ^ k :)) Chắc O(n) cũng ngon rùi nhỉ?? :))
E dùng visua studio 2010, thì mình xem thời gian chương trình ở vậy mấy anh?:plaster:
[QUOTE=11520711;64917]E dùng visua studio 2010, thì mình xem thời gian chương trình ở vậy mấy anh?:plaster:[/QUOTE]
Em code = ngôn ngữ gì vậy em?? Mà muốn xem time khi chạy thì em code 1 cái đếm time lun trong code ấy. Mới đầu chạy vào main phát lấy time hệ thống, sau khi kết thúc em lấy time phát nữa! Lấy time sau = time trước :happy:
Cái này được dùng công thức không, được thì ráp một phát được luôn hở :-s
đề của bác là nhập N luôn phải không a? hay lấy N ngẫu nhiên??? chứ mà nhập N nó nhập cho số 3 thì ra sai đề!!! 
(tại e thấy N có dạng là 2^i với i=1;2;3;…)
[QUOTE=09520281;64903]Nhằm mục đích tạo không khí học tập xua tan sự nhàm chán của những ngày ở nhà một mình :amazed:. Mình post một bài toán cho các bạn cùng giải cho vui nhé, tiện thể ôn lại kiến thức căn bản luôn. Các bài tập từ dễ đến khó, mình thì không giải hết được đâu, mong các bro như thầy toàn, thầy tuanta, anh truongan, đăng châu, thiên điệp…các bạn trong đội tuyển olympic cũng như các thầy làm cố vấn nhé :love:. Về giải thưởng hay thống kê cho những bạn giải được nhiều bài thì mong BQT giúp đỡ :sexy:. Các bạn có thể dùng ngôn ngữ gì cũng được, chạy chương trình rồi chụp kết quả và post lên :D, post lên code luôn nhé :funny:
Bài toán 1 (thứ 7-7/7/2012):
[SIZE=3]Viết chương trình tính tổng sau: 1/2 + 1/4 + 1/8 + 1/16 +…+1/N[/SIZE]
Cho N là vô cùng lớn N<(10^9), time limit = 1s.
Dễ mà phải không ,
p/s: đã fix :dribble:[/QUOTE]
góp ý xíu nha, tên riêng viêt hoa :doubt:
Cái đề không rõ ràng nhưng mà chắc là N=2^i 
#include <stdio.h>
#include <conio.h>
#include <math.h>
void main()
{
double i,n,a;
float s=0;
printf("Nhap vao so n");
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
a = pow(2, ((double) i) );
s+= 1/(a);
}
printf("%lf",s);
getch();
}
sao không chạy được ta
tổng cấp số nhân với công bội là 1/2 :beauty:
[QUOTE=11520104;64924]đề của bác là nhập N luôn phải không a? hay lấy N ngẫu nhiên??? chứ mà nhập N nó nhập cho số 3 thì ra sai đề!!! (tại e thấy N có dạng là 2^i với i=1;2;3;…)[/QUOTE]
Bạn có thể nhập N bất kỳ, nhưng chỉ chấp nhận N có dạng 2^K thôi, sai thì bắt nhập lại ^^
[QUOTE=11520132;64923]Cái này được dùng công thức không, được thì ráp một phát được luôn hở :-s[/QUOTE]
Dùng công thức được là 1 cách thông minh nhất :go:
[QUOTE=09520109;64929]tổng cấp số nhân với công bội là 1/2 :beauty:[/QUOTE]
Chuẩn rồi đấy :))
#include <stdio.h>
int main()
{
int i,n=31;
float total=0,t=0.5;
for (i=0;i<n;i++)
{
total=total+t;
t=t/2;
}
printf("%1.70f",total);
}
test với n=100 với máy mình cũng 0.05s
Chỗ này mình thấy cũng kì, dù n lớn cỡ nào thì time vẫn thấp, mình nghĩ khi n quá lớn, số quá bé ~0, chắc nó cho bằng 0 luôn nên tính nhanh zị ( đoán mò thôi )
[QUOTE=10520549;64928]
#include <stdio.h>
#include <conio.h>
#include <math.h>
void main()
{
double i,n,a;
float s=0;
printf("Nhap vao so n");
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
a = pow(2, ((double) i) );
s+= 1/(a);
}
printf("%lf",s);
getch();
}
sao không chạy được ta[/QUOTE]
- scanf(“%d”,&n); —> số double %lf ko phải %d
- printf(“%lf”,s); –> số float %f chứ ko phải %lf nhé
Anh nghĩ bài này n chỉ cần kiểu long là oki rùi 
Và cho nó for(int i = 1; i <= log2(N); i++) là ok:happy:
[QUOTE=11520132;64933]
#include <stdio.h>
int main()
{
int i,n=31;
float total=0,t=0.5;
for (i=0;i<n;i++)
{
total=total+t;
t=t/2;
}
printf("%1.70f",total);
}
test với n=100 với máy mình cũng 0.05s
Chỗ này mình thấy cũng kì, dù n lớn cỡ nào thì time vẫn thấp, mình nghĩ khi n quá lớn, số quá bé ~0, chắc nó cho bằng 0 luôn nên tính nhanh zị ( đoán mò thôi )[/QUOTE] Cái bạn đoán mò chắc là ko đúng rùi! vì n quá lớn số quá bé thì nó vẫn thực hiện phép tính đó! Nó ko ảnh hưởng tới time đâu. Bạn cho n = 100 thì nó chỉ for 1 -> 100 nhanh như chớp
Cái ảnh hưởng tới time trong bài này chủ yếu là cái for() kia nó chạy mấy vòng ấy. Nếu n = 10^9 thì for 1 -> 10^9 sẽ > 1s
[QUOTE=09520500;64937]Cái bạn đoán mò chắc là ko đúng rùi! vì n quá lớn số quá bé thì nó vẫn thực hiện phép tính đó! Nó ko ảnh hưởng tới time đâu. Bạn cho n = 100 thì nó chỉ for 1 -> 100 nhanh như chớp
Cái ảnh hưởng tới time trong bài này chủ yếu là cái for() kia nó chạy mấy vòng ấy. Nếu n = 10^9 thì for 1 -> 10^9 sẽ > 1s[/QUOTE]
Với code của em thì đâu cần tới 10^9 anh, với n=31 thì vòng lặp t cuối cùng = 1/2^31, 2^31 cũng > 10^9 rồi :adore:
[QUOTE=09520500;64936]- scanf(“%d”,&n); —> số double %lf ko phải %d
- printf(“%lf”,s); –> số float %f chứ ko phải %lf nhé
Anh nghĩ bài này n chỉ cần kiểu long là oki rùi Và cho nó for(int i = 1; i <= log2(N); i++) là ok:happy:[/QUOTE]
anh test xem có được không
[QUOTE=11520132;64938]Với code của em thì đâu cần tới 10^9 anh, với n=31 thì vòng lặp t cuối cùng = 1/2^31, 2^31 cũng > 10^9 rồi :adore:[/QUOTE]
code em thì đúng là cái số 2^31 rùi! Ý anh nói là cái chỗ for 1 -> n ấy :baffle: nếu n = 10^9 thì time > 1.0s
Còn code em vs bài toán đưa ra là ok rùi vì cái bài đó để ko chặt chẽ lắm