Question

Viết các số tự nhiên từ 1 đến 2009 theo một vòng tròn cùng chiều quay kim đồng hồ. Cũng theo chiều đó, bắt đầu từ số 1, cứ đếm từ 1 đến số thứ 612 thì xoá số đó đi. Lại bắt đầu từ số còn lại đứng ngay sau số vừa bị xoá, lặp lại quá trình đến khi còn 1 số thì dừng lại.
a) Hỏi số còn lại là số nào?
b) Muốn số còn lại là số thứ L (0

Answer 1

Ý tưởng cho lời giải:

• Dùng một mảng a có 2009 phần tử (từ 1 đến 2009) kiểu boolean. Khởi động cho tất cả các giá trị của mảng làtrue (chưa được đánh dấu).
• Duyệt và đếm xuất phát từ phần tử đầu tiên, phần tử nào của mảng có giá trị true (chưa đánh dấu) thì mới đếm, khi đếm đủ 612 số thì đánh dấu phần tử thứ 612 đó (False), khi duyệt đến phần tử cuối cùng của mảng thì quay lại đầu mảng. Khi nào chỉ còn 1 phần tử chưa đánh dấu thì dừng lại và phần tử đó chính là đáp án câu a.
• Đáp án câu b được suy ra từ câu a. Bởi các số từ 1 đến 2009 xếp theo một vòng tròn cùng chiều quay kim đồng hồ

Chương trình viết bằng pascal để các bạn tham khảo:

var a:array[1..2009] of boolean;
  i,j,n,dem,L,b:integer;
  begin
       Write('L=');readln(L);
       for i:=1 to 2009 do a[i]:=true;
       n:=2009; j:=1;
       while n>1 do
        begin
            dem:=0;
            while dem < 612 do
              begin
                  if a[j] then dem:=dem+1; if dem = 612 then a[j]:=false;
                  if j=2009 then j:=1 else j:=j+1;
              end;
            n:=n-1;
        end;
       for i:= 1 to 2009 do if a[i] then j:=i;
       writeln('so doc dac:',j);

       b:=1+L-j;
       if b>2009 then b:=b-2009;while b

Còn đây là chương trình học sinh của mình (Minh) viết bằng cách sử dụng đệ quy:

PROGRAM So_doc_dac;
USES crt;
VAR dem,x,L:WORD;
    a:ARRAY[1..2009] OF WORD;
PROCEDURE try(x:WORD);
VAR i:WORD;
BEGIN
  i:=0;
  WHILE i<612 DO
    BEGIN
      IF a[x]<>0 THEN i:=i+1;
      IF i=612 THEN a[x]:=0;      
      x:=x+1;                     
      IF x>2009 THEN x:=1;
    END;
  dem:=dem+1;
  IF dem=2008 THEN exit
  ELSE try(x);
END;

BEGIN
  clrscr;                     
  write('L = '); readln(L);
  WHILE (L=0) OR (L>2009) DO
    BEGIN
      writeln;
      writeln('So ban nhap khong hop le');
      write('Nhap lai: L =  ');
      readln(L);  
    END;
  {cau a}
  FOR x:=1 TO 2009 DO a[x]:=x;
  x:=1; dem:=0;
  try(x);
  x:=1;
  WHILE a[x]=0 DO x:=x+1;
  writeln('So doc dac la ',a[x]);
  {cau b}
  IF L>=80 THEN x:=L-79
  ELSE x:=L+1930;
  writeln('Muon so con lai la ',L,' thi xuat phat tu so ',x);
  readln;  
END.