Số cấp cộng

Số cấp cộng - gia sư tin học, pascal nâng cao.

           Tìm các số tự nhiên lẻ có ba chữ số. Ba chữ số này, theo trật tự từ trái qua phải tạo thành một cấp số cộng.

Đặc tả

1.  x là số tự nhiên có ba chữ số: x = 100*a + 10*b + c.

2.  x là số lẻ nên chữ số hàng đơn vị c phải là số lẻ: c = 1, 3, 5, 7, 9.

3.  Chữ số hàng trăm của x phải khác 0: a = 1..9.

4.  Nếu dãy a, b, c lập thành một cấp số cộng thì số đứng giữa b là trung bình cộng của hai số đầu và cuối: b = (a + c)/2 hay 2b = a+c.

Từ (4) ta suy ra (a + c) là số chẵn. Do c lẻ, (a + c) chẵn nên a lẻ.

Nếu biết a và c ta tính được x = 100a +10(a + c) / 2 + c

                                                 = 100a + 5(a + c) + c = 105a + 6c.

Vì chỉ có 5 chữ số lẻ là 1, 3, 5, 7 và 9 nên tổ hợp của a và c sẽ cho ta 25 số.

Tổ chức dữ liệu

Ta tạo sẵn mảng nguyên 5 phần tử ChuSoLe[1..5] và gán trước các giá trị 1, 3, 5, 7, 9 cho mảng này. Trong Turbo Pascal (TP) việc này được thực hiện thông qua khai báo:

const ChuSoLe: array[1..5] of integer = (1,3,5,7,9);

Chú ý rằng khai báo này phải đặt trong mục const là nơi khai báo hằng.

Trong C# ta khai báo như sau:

int [] ChuSoLe = {1,3,5,7,9};

Ý nghĩa của dòng khai báo trên là như sau: Xin cấp phát một biến mảng kiểu nguyên có 5 phần tử với chỉ dẫn từ 1 đến 5, tên biến là ChuSoLe. 5 phần tử của biến được gán trước các trị 1, 3, 5, 7 và 9.

Sau đó, mỗi khi cần, ta chỉ việc duyệt mảng ChuSoLe là thu được toàn bộ các chữ số lẻ theo trật tự đã khai báo trước.

Chú ý

           Thủ tục inc(d) trong chương trình TP dưới đây tăng giá trị của biến d lên thêm 1 đơn vị, tức là tương đương với câu lệnh d := d + 1 và ++d (C#). Tương tự, thủ tục dec(d) sẽ giảm giá trị của biến d xuống 1 đơn vị, tương đương với câu lệnh d := d – 1 và --d (C#).

Tổng quát hơn, ta có thể viết:

          inc(d,n) tương đương với d := d + n và

          dec(d,n) tương đương với d := d – n.

Khi n = 1 thì có thể bỏ qua tham số thứ hai.

(*  Pascal  *)

(---------------------------------------

       Cac so tu nhien le 3 chu so

         lap thanh cap so cong

---------------------------------------*)

program CapCong;

uses crt;

const

ChuSoLe: array [1..5] of integer = (1,3,5,7,9);

var s: array [1..25] of integer;

    n: integer;

(*-----------------------------------

     Phat sinh cac so dang

     105a+6c; a,c = 1,3,5,7,9

------------------------------------*)

Function Tim: integer;

var a,c,d,x: integer;

begin

d := 0;

for a := 1 to 5 do

begin

    x := 105*ChuSoLe[a];

     for c := 1 to 5 do

     begin

       inc(d); s[d] := x + 6*ChuSoLe[c];

     end;

   end;

Tim := d;

end;

(*---------------------------------------

   Hien thi mang s[1..n] moi dong 20 so

-----------------------------------------*)

procedure Xem(n: integer); tự viết

BEGIN

n := Tim; Xem(n); writeln;

write('Tong cong ',n,' so'); readln;

END.

Gia sư tin học - Chú ý

1. Dựa vào nhận xét: dãy ba số a, b, c tạo thành cấp số cộng khi và chỉ khi b là trung bình cộng của a và c, tức là 2b = a + c ta có thể giải bài toán trên bằng phương pháp vét cạn dùng ba vòng for như sau:

for a := 1 to 9 do

  for b := 0 to 9 do

    for c := 0 to 9 do

     if odd(c) and (2*b=a+c) then

       Ghi nhận số 100*a+10*b+c;

Hàm odd(c) kiểm tra tính lẻ của số nguyên c.

Phương pháp vét cạn đòi hỏi khoảng 10*10*10 = 1000 lần duyệt trong khi chỉ có 25 số, tức là một phần bốn mươi các số thoả mãn điều kiện của đầu bài. Phương pháp mô tả trong chương trình được gọi là phương pháp sinh: nó sinh ra đúng 25 số cần tìm.

      2. Ta cần ghi nhận phương pháp sinh

Phương pháp sinh

Thay vì duyệt tìm các đối tượng  hãy sinh ra chúng.