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

 

[nngoc]

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

 

[quanltv]

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é.

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.

 

[nngoc]

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?

 

[quanltv]

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

 

[nngoc]

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ó.

 

[tengiday]

Câu trả lời bài này chỉ có 1 dòng duy nhất:
[ah]

trunc(sqrt(n))

[/ah]
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ẻ?
[ah]
- 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) (trong C/C++ thì đó là (int)sqrt).
[/ah]
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.

 

[nngoc]

Cám ơn anh nhiều. Em k ngờ còn có thể làm bài này như vậy! :facebook9: 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.

 

[LanSG9x]

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! :nhay:
Dd mà có ngàn like là em cho ngay ấy chứ.

 

[kidteam]

Câu trả lời bài này chỉ có 1 dòng duy nhất:
[ah]

trunc(sqrt(n))

[/ah]
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ẻ?
[ah]
- 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) (trong C/C++ thì đó là (int)sqrt).
[/ah]
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.

Cách giải của bạn rất hay.
Cám ơn bạn rất nhiều.