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

Ai pro Pascal giải giúp em bài Thử thách này

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

    Question Ai pro Pascal giải giúp em bài Thử thách này

    Trước nghỉ tết, cô em cho cả lớp 1 bài thử thách có dạng mở như sau. Anh chị giỏi Pascal giúp em giải bài này với.
    Dàn đèn:
    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. Giải thích cách làm.

    Dữ liệu vào: N được nhập từ bàn phím.
    Dữ liệu ra: In 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.

    Em có thể giải được tới N bao nhiêu?

    Ví dụ:
    N = 3
    Vòng 1: on, on, on
    Vòng 2: on, off, on
    Vòng 3: on, off, off
    Kết quả: 1

    N = 6
    Vòng 1: on, on, on, on, on, on
    Vòng 2: on, off, on, off, on, off
    Vòng 3: on, off, off, off, on, on
    Vòng 4: on, off, off, on, on, on
    Vòng 5: on, off, off, on, off, on
    Vòng 6: on, off, off, on, off, off
    Kết quả: 2
    Quick reply to this message Trả lời       


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

    Reply: Ai pro Pascal giải giúp em bài Thử thách này

    Anh chị nào làm được giúp em với.

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

    Reply: Ai pro Pascal giải giúp em bài Thử thách này

    Hàng về nè, bài này đơn giản nên mình code cả bài luôn cho bạn. Có gì không hiểu có thể comment lại nhé.
    Mã:
    uses crt;var a: array [1..100] of boolean;
        i,j,n, dem: integer;
    begin
      clrscr;
      write('Nhap so luong cac bong den n= ');
      readln(n);
      for i:= 1 to n do
       for j:=1 to (n div i) do
         if a[i*j] then a[i*j]:=false
         else a[i*j]:=true;
    
    
      dem:=0;
      for i:=1 to n do
      if a[i] then inc(dem);
    
    
      writeln('=====================================');
      writeln('So luong cac bong den dang bat = ',dem);
      readln;
    end.
    Hãy nhấn nút Thank nếu thấy bài viết hữu ích
    Bộ sưu tập cực khủng


  4. Đã cảm ơn quanltv:

    nngoc 

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

    Reply: Ai pro Pascal giải giúp em bài Thử thách này

    Cám ơn anh quanltv nhiều. Ý của anh là cứ theo như trong đề bài để bật tắt bóng đèn có phải không? Còn câu giải N tối đa được bao nhiêu thì phải làm sao vậy anh? Cô em nói sẽ chạy ct trên máy chủ trong trường, cũng khá mạnh. Khi đó thời gian chạy có quá 5s không?
    Em có vài bài khác liệu có thể hỏi luôn được không?

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

    Reply: Ai pro Pascal giải giúp em bài Thử thách này

    Trích Nguyên văn bởi nngoc Xem bài viết
    Cám ơn anh quanltv nhiều. Ý của anh là cứ theo như trong đề bài để bật tắt bóng đèn có phải không? Còn câu giải N tối đa được bao nhiêu thì phải làm sao vậy anh? Cô em nói sẽ chạy ct trên máy chủ trong trường, cũng khá mạnh. Khi đó thời gian chạy có quá 5s không?
    Em có vài bài khác liệu có thể hỏi luôn được không?
    Code trên mình viết tổng quát cho cả trường hợp n=1, hoặc n=2. Theo mình đề bài là thực hiện N vòng, trong lần thứ i thì đổi trạng thái của các đèn ở vị trí chia hết cho i thôi. Trong code thì a[i*j] là phần tử có chỉ số là bội của i nhưng không vượt quá a[n].

    N tối đa phụ thuộc vào kiểu dữ liệu và giới hạn bộ nhớ cũng như cấu hình máy tính, bạn đưa cấu hình máy chủ trường bạn lên đây nhé.

    Bài khác thì bạn cứ đưa lên, post thành topic mới trong mục Pascal nhé, nhưng bạn nên nói rõ vướng mắc ở bước nào, hoặc post code bạn đã viết để hỏi mọi người cách sửa lỗi thì sẽ hay hơn

  7. Đã cảm ơn quanltv:

    nngoc 

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

    Reply: Ai pro Pascal giải giúp em bài Thử thách này

    Em không rành máy tính lắm. Cô nói máy chủ là Xeon E5 3 phẩy mấy Gi gì đó. Như vậy N tới bao nhiêu vậy anh? Code của em viết thường chạy chậm, không nhanh. Cô nói bài này cho làm ăn tết luôn nên em nghĩ nó khó.

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

    Reply: Ai pro Pascal giải giúp em bài Thử thách này

    Câu trả lời bài này chỉ có 1 dòng duy nhất:
    Mã:
    trunc(sqrt(n))

    Tại sao?
    - Một bóng đèn được bật sáng khi và chỉ khi nó được chuyển trạng thái số lẻ lần.
    - Tại một vòng k, bóng đèn thứ i được chuyển trạng thái khi và chỉ khi i chia hết cho k.
    Như vậy, bóng đèn thứ i được bật sáng khi và chỉ khi số lượng ước số của i là lẻ.
    Số nào có số lượng ước số là lẻ?

    - Là số chính phương.
    - Bởi vì ước số của một số luôn là 1 cặp. Nếu k là ước số của i thì i / k cũng là ước số của i, và chỉ có số chính phương mới có 2 ước số bằng nhau.
    Như vậy chúng ta chỉ cần đếm số lượng số chính phương không vượt quá N, tức là trunc(sqrt(n)) (trong C/C++ thì đó là (int)sqrt(n)).

    Em có thể giải được tới N bao nhiêu?
    - Khi có được câu trả lời ở trên thì thấy được, đây là câu hỏi mở bởi vì nếu dùng kiểu int64 để lưu N thì tối đa chỉ làm được tới 2^64 - 1, tức là 19-20 chữ số.
    - Nếu bạn lưu số bằng chuỗi hay array rồi dùng cách khai căn bằng tay (lấy phần nguyên) đã học ở cấp 2, thì có thể làm bài này với N tới hàng chục nghìn chữ số thì máy Xeon đó vẫn chạy không quá 5s. Đương nhiên, với cách này thì bạn cần phải viết thủ tục xử lý số lớn, đòi hỏi kỹ thuật lập trình kha khá.

    Good luck.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  10. 2 thành viên đã cảm ơn tengiday:


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

    Reply: Ai pro Pascal giải giúp em bài Thử thách này

    Cám ơn anh nhiều. Em k ngờ còn có thể làm bài này như vậy! Em biết làm cộng trừ số lớn chứ chưa làm nhân chia bao h. Lấy căn thì em chưa nghe. Hy vọng cô k yêu cầu.

  12. Đã cảm ơn nngoc:


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

    Reply: Ai pro Pascal giải giúp em bài Thử thách này

    Cách làm của anh @tengiday tuyệt quá!!! Em công nhận mấy bài anh làm lúc nào cũng hay, dễ xem, và dễ hiểu hết!
    Dd mà có ngàn like là em cho ngay ấy chứ.

  14. Đã cảm ơn LanSG9x: