Hỏi bài: Bóng đèn

4) Cho N bóng đèn được xếp thành hàng và đánh số từ 1 tới N. Đầu tiên tất cả các bóng đèn đều tắt. Lần lượt thực hiện N thao tác sau:
Vòng 1: Bật sáng toàn bộ các bóng đèn.
Vòng 2: Tắt tất cả bóng đèn ở vị trí chẵn.
Vòng 3: Thay đổi trạng thái của những bóng đèn ở vị trí chia hết cho 3. Thay đổi trạng thái bằng cách tắt đèn nếu nó đang sáng, và bật đèn nếu nó đang tối.
...
Vòng thứ i (3 < i < N): Thay đổi trạng thái của những bóng đèn ở vị trí chia hết cho i.
...
Vòng thứ N: Thay đổi trạng thái của bóng đèn cuối cùng.

Cho biết sau khi thực hiện những thao tác trên thì còn lại bao nhiêu bóng đèn còn sáng.


- Dữ liệu nhập vào từ bàn phím số N với 3 < N < 10^9.
- In kết quả ra màn hình một số duy nhất là số bóng đèn còn sáng sau khi thực hiện N thao tác như trên.

Em cám ơn đã giúp đỡ.
 
Sửu Nguyễn

Sửu Nguyễn

⭐️⭐️⭐️⭐️⭐️
Với N < 10^9 thì tức là bạn có thể dung mảng
Đặt trạng thái bóng tắt là 0 mở là 1
Thêm 1 biến tong là tổng số đèn sang
Đầu tiên tại vòng 1 gán tất cả là 1
=> tong = N
Sang vòng 2: nếu chỉ số của mảng là chẵn thì gán là 0
=> tại vị trí chuyển tong = tong -1
Sang vòng 3: nếu chia hết cho 3 => lại có nếu = 1 thì gán về 0 và ngược lại
(nếu gán sang 0 thì tong = tong -1 nếu gán sang 1 tong = tong +1)
Sang các vòng tiếp theo tương tự cứ gán sang 0 thì là - gán sang 1 là +
Kết thúc in ra tong
 
Em yêu Vforum

Em yêu Vforum

Cần tìm anh trai nuôi :)
365 Designer:
Với N < 10^9 thì tức là bạn có thể dung mảng
Đặt trạng thái bóng tắt là 0 mở là 1
Thêm 1 biến tong là tổng số đèn sang
Đầu tiên tại vòng 1 gán tất cả là 1
=> tong = N
Sang vòng 2: nếu chỉ số của mảng là chẵn thì gán là 0
=> tại vị trí chuyển tong = tong -1
Sang vòng 3: nếu chia hết cho 3 => lại có nếu = 1 thì gán về 0 và ngược lại
(nếu gán sang 0 thì tong = tong -1 nếu gán sang 1 tong = tong +1)
Sang các vòng tiếp theo tương tự cứ gán sang 0 thì là - gán sang 1 là +
Kết thúc in ra tong
Nhấn để mở rộng...
Bác cho em hỏi ngu cái là việc đếm tổng làm 1 lần lúc cuối được không?
 
L

LanSG9x

Em viết như sau, nhưng chạy chậm quá. Với lại lên n = 10^9 tức là mảng 1 tỷ phần tử, k được...
Mã: 
int bong_den(int n) {
    int *a = (int *)malloc((n + 1) * sizeof(int)), s = n, i, j;
    for (i = 1; i <= n; i++)
        a[i] = 1;
    for (i = 2; i <= n; i++)
        for (j = 2; j <= n; j++)
            if (j % i < 1) {
                a[j] = 1 - a[j];
                s += a[j] ? 1 : -1;
            }
    return s;
}
 
Sửu Nguyễn

Sửu Nguyễn

⭐️⭐️⭐️⭐️⭐️
LanSG9x:
Em viết như sau, nhưng chạy chậm quá. Với lại lên n = 10^9 tức là mảng 1 tỷ phần tử, k được...
Mã: 
int bong_den(int n) {
    int *a = (int *)malloc((n + 1) * sizeof(int)), s = n, i, j;
    for (i = 1; i <= n; i++)
        a[i] = 1;
    for (i = 2; i <= n; i++)
        for (j = 2; j <= n; j++)
            if (j % i < 1) {
                a[j] = 1 - a[j];
                s += a[j] ? 1 : -1;
            }
    return s;
}
Nhấn để mở rộng...

Viết theo cách tường minh ra đi bạn
Dùng 1 vòng for là đủ rồi
 
Em yêu Vforum

Em yêu Vforum

Cần tìm anh trai nuôi :)
365 Designer:
Khác nhau chỗ nào :troll2:
Nhấn để mở rộng...
Chỉ đếm không thì trẻ con 3 tuổi đã biết, còn tính tổng thì phải đi học lớp 1 trở lên mới làm được bác Trâu ạ. Tính tổng cần nhiều mana hơn :D

LanSG9x:
Em ko hiểu ý anh lắm. Em viết cũng bình thường mà. Anh viết em xem làm sao dùng 1 vòng for được ạ?
Nhấn để mở rộng...
Ý là trường hợp Vòng 1 thì cũng nhét hết vào trường hợp tổng quảt.
Bạn thử cách này sẽ nhanh hơn nhé
Mã: 
for i=1 -> n
        for j=1 -> int(n chia i)
           a[i*j] = 1 - a[i*j]

Với i =1, chỉ đổi các vị trí là bội của 1
i=2: bội của 2
i=3: bội của 3
chứ không phải duyệt n*(n-1) phần tử
 
Sửa lần cuối:
L

LanSG9x

K đúng nha bạn. Phải có vòng for đầu tiên vì khai báo mảng thì các phần tử có giá trị đầu là rác. Khi gặp a[i * j] = 1 - a[i * j] sẽ cho giá trị rác. Như vậy làm sao dùng 1 vòng for được???????
Đoạn code em sửa lại chạy tới n*sqrt(n) cũng quá chậm. 10^7 chạy cũng k nổi thì k chạy được 10^9. Cái quan trọng là mảng 10^9 chiếm bao nhiêu bộ nhớ ạ?
Mã: 
int bulb(int n) {
	int *a = (int *)malloc((n + 1) * sizeof(int)), s = n;
	for (int i = 1; i <= n; i++)
		a[i] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= n / i; j++) {
			a[i * j] = 1 - a[i * j];
			s += a[i * j] ? 1 : -1;
		}
	return s;
}
 
Đăng nhập bằng tài khoản VFO hoặc Google

Bài viết mới nhất

Bài viết đang hot

Thống kê

Chủ đề
100,591
Bài viết
467,315
Thành viên
339,811
Thành viên mới nhất
Hoàng Mai

Bài viết được quan tâm nhiều

Top