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

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

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

    Question 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 đỡ.
    Quick reply to this message Trả lời       

  2. #2
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 177479
    Giới tính: Nam
    Bài gửi
    5.748

    Reply: Hỏi bài: Bóng đè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
    Hãy Support theo cách của bạn
    Hãy thank theo cách của tôi



  3. Đã cảm ơn 365 Designer:


  4. #3
    Ðến Từ
    Thái Bình
    Thành Viên Thứ: 263160
    Giới tính: Nữ
    Bài gửi
    935

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

    Trích Nguyên văn bởi 365 Designer Xem bài viết
    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
    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?
    Cách xoá virus, malware, tự nhảy quảng cáo trên trình duyệt máy tính
    http://vforum.vn/diendan/showthread.php?119711

  5. #4
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 177479
    Giới tính: Nam
    Bài gửi
    5.748

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

    Trích Nguyên văn bởi Em yêu Vforum Xem bài viết
    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?
    Cũng được thôi mà nó không khác nhau lắm
    Vẫn cần them 1 vòng for để tính tổng các số 1

  6. Đã cảm ơn 365 Designer:


  7. #5
    Ðến Từ
    Thái Bình
    Thành Viên Thứ: 263160
    Giới tính: Nữ
    Bài gửi
    935

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

    Trích Nguyên văn bởi 365 Designer Xem bài viết
    Cũng được thôi mà nó không khác nhau lắm
    Vẫn cần them 1 vòng for để tính tổng các số 1
    Mình chỉ đếm các số bằng 1 thôi mà không tính tổng có được không bác

  8. #6
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 177479
    Giới tính: Nam
    Bài gửi
    5.748

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

    Trích Nguyên văn bởi Em yêu Vforum Xem bài viết
    Mình chỉ đếm các số bằng 1 thôi mà không tính tổng có được không bác
    Khác nhau chỗ nào

  9. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 402126
    Giới tính: Nữ
    Bài gửi
    38

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

    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;
    }

  10. #8
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 177479
    Giới tính: Nam
    Bài gửi
    5.748

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

    Trích Nguyên văn bởi LanSG9x Xem bài viết
    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;
    }
    Viết theo cách tường minh ra đi bạn
    Dùng 1 vòng for là đủ rồi

  11. #9
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 402126
    Giới tính: Nữ
    Bài gửi
    38

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

    Trích Nguyên văn bởi 365 Designer Xem bài viết
    Viết theo cách tường minh ra đi bạn
    Dùng 1 vòng for là đủ rồi
    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 ạ?

  12. #10
    Ðến Từ
    Thái Bình
    Thành Viên Thứ: 263160
    Giới tính: Nữ
    Bài gửi
    935

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

    Trích Nguyên văn bởi 365 Designer Xem bài viết
    Khác nhau chỗ nào
    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

    Trích Nguyên văn bởi LanSG9x Xem bài viết
    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 ạ?
    Ý 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ử

  13. Đã cảm ơn Em yêu Vforum:


  14. #11
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 402126
    Giới tính: Nữ
    Bài gửi
    38

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

    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;
    }

  15. #12
    Ðến Từ
    Thái Bình
    Thành Viên Thứ: 263160
    Giới tính: Nữ
    Bài gửi
    935

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


  16. 2 thành viên đã cảm ơn Em yêu Vforum: