//
you're reading...
00 - Chủ đề chung

Số thân thiện

Tìm tất cả các số tự nhiên hai chữ số mà khi đảo trật tự của hai chữ số đó sẽ thu được một số nguyên tố cùng nhau với số đã cho.
Hiểu đầu bài
Ta kí hiệu (a, b) là ước chung lớn nhất (ucln) của hai số tự nhiên ab. Hai số tự nhiên ab được gọi là nguyên tố cùng nhau khi và chỉ khi (a, b) = 1. Khi đó, chẳng hạn:

  1. (23, 32) = 1, vậy 23 là một số cần tìm. Theo tính chất đối xứng, ta có ngay 32 cũng là một số cần tìm.
  1. (12, 21) = 3, vậy 12 và đồng thời 21 không phải là những số cần tìm.

Đặc tả: Gọi hai chữ số của số tự nhiên cần tìm xab, ta có:

  • x = ab.
  • a, b = 0..9 (a và b biến thiên trong khoảng .9).
  • a > 0 vì x là số có hai chữ số.
  • (ab, ba) = 1.

Ta kí hiệu x’ là số đối xứng của số x theo nghĩa của đầu bài, khi đó ta có đặc tả như sau:

  • x = 10..99 (x biến thiên từ 10 đến 99, vì x là số có hai chữ số).
  • (x, x’) = 1.

Nếu x = ab thì x’ = ba. Ta có thể tính giá trị của x’ theo công thức:
x’ = (chữ số hàng đơn vị của x) * 10 + (chữ số hàng chục của x).
Kí hiệu Đơn(x) là toán tử lấy chữ số hàng đơn vị của số tự nhiên x và kí hiệu Chục(x) là toán tử lấy chữ số hàng chục của x, ta có:
x’ = Đơn(x)*10 + Chục(x).
Tổng hợp lại ta có đặc tả:
Số cần tìm x phải thoả các tính chất sau:x = 10..99 (x nằm trong khoảng từ 10 đến 99).

  • x’ = Đơn(x)*10 + Chục(x).
  • (x, x’) = 1 (ước chung lớn nhất của x và x’ bằng 1).

Đặc tả trên được thể hiện qua ngôn ngữ phỏng trình tựa Pascal như sau:

  • for x:=10 to 99 do

if ucln(x, đơn(x)*10+Chục(x))=1 then Lấy(x); trong đó, ucln(a,b)là hàm cho ước chung lớn nhất của hai số tự nhiên ab; Lấy(x) là toán tử hiển thị x lên màn hình hoặc ghi x vào một mảng nào đó với mục đích sử dụng lại, nếu cần.
Ta làm mịn đặc tả (10):
ucln(a, b): Thuật toán Euclid là chia liên tiếp, thay số thứ nhất bằng dư của nó khi chia cho số thứ hai rồi hoán vị hai số.
(*———————————–
Tim  uoc chung lon nhat cua hai so a va b. Thuat toan Euclid
————————————–*)
function Ucln(a,b: integer): integer;

var r: integer;
begin

while b > 0 do begin
r:= a mod b; a:= b; b:= r; end;
Ucln:= a;
end;

Đơn(x) = (x mod 10): số dư của phép chia nguyên x cho 10, thí dụ:
Đơn(19) = 19 mod 10 = 9.
Chục(x) = (x div 10): thương nguyên của phép chia x cho 10, thí dụ:
Chục(19) = 19 div 10 = 1.
Lấy(x): write(x) hoặc nạp giá trị x vào mảng s theo các thao tác sau: n := n + 1;
s[n] := x;
n đếm số phần tử hiện đã nạp trong mảng s.
Biểu diễn dữ liệu
Ta dùng mảng s để lưu các số tìm được. Dễ thấy s phải là một mảng nguyên chứa tối đa 90 phần tử vì các số cần khảo sát nằm trong khoảng từ 10 đến 99.
var s: array[1..90] of integer;
Phương án 1 của chương trình sẽ hoạt động theo hai bước như sau:

  1. n := Tim;
  1. Xem(n);

Bước 1. Tìm và ghi vào mảng s các số thoả điều kiện đầu bài, n là số lượng các số tìm được.
Bước 2. Hiển thị các phần tử của mảng s[1..n] chứa các số đã tìm được.
Toán tử x’ được viết dưới dạng hàm cho ta số tạo bởi các chữ số của x theo trật tự ngược lại. Ta đặt tên cho hàm này là SoDao (số đảo). Hàm có thể nhận giá trị vào là một số tự nhiên có nhiều chữ số.
Để tạo số đảo y của số x cho trước, hàm SoDao lấy dần các chữ số hàng đơn vị của x để ghép vào bên phải số y:
y := y*10 + (x mod 10)
Sau mỗi bước, chữ số hàng đơn vị đã lấy được loại hẳn khỏi x bằng toán tử: x := x div 10
Chỉ thị {$B-} trong chương trình NTCN (nguyên tố cùng nhau) dưới đây đặt chế độ kiểm tra biểu thức lôgic vừa đủ. Khi đã xác định được giá trị chân lí cần thiết thì không tiến hành tính tiếp giá trị của biểu thức đó nữa. Thí dụ, với các lệnh
x := 1; y := 5;
if (x > 5) and (x + y < 7)then y := y + 1 else y := y-1;
trong chế độ {$B-}, sau khi tính được giá trị chân lí (x > 5) = false, chương trình sẽ bỏ qua nhân tử logic (x + y < 7), vì tích lôgic của false với giá trị tuỳ ý cho ta false. Trong trường hợp này lệnh y := y – 1 sẽ được thực hiện. Ngược lại, nếu ta đặt chỉ thị {$B+} thì chương trình, sau khi tính được (x > 5) = false vẫn tiếp tục tính giá trị của (x + y < 7) rồi lấy tích của hai giá trị tìm được (false and true = false) làm giá trị của biểu thức điều kiện trong cấu trúc rẽ nhánh nói trên. Cuối cùng toán tử y := y – 1 cũng được thực hiện giống như trường hợp trên nhưng khối lượng tính toán lại nhiều hơn.

(* Pascal *)
(*———————————-
So than thien (xy,yx) = 1
———————————-*)

program SoThanThien;
{$B-} uses Crt;
const MN = 90;
var s: array[1..MN] of integer;
function Ucln(a,b: integer): integer; tự viết

function SoDao(x: integer): integer;
var y: integer;
begin

y := 0;
repeat

{ ghep chu so hang don cua x vao ben phai y }
y := 10*y + (x mod 10);
x := x div 10; { loai chu so hang don } until (x = 0);
SoDao := y;
end;

(*————————————–

Tim cac so thoa dieu kien dau bai ghi vao mang s.

Output: so luong cac so tim duoc

—————————————-*)

function Tim: integer;
var x,d: integer;
begin

d := 0; {So luong cac so can tim }
for x := 10 to 99 do
if Ucln(x,SoDao(x)) = 1 then
begin
d := d + 1;
s[d]:= x;
end;
Tim := d;
end;

(*————————————

Hien thi mang s[1..n] tren man hinh.

————————————–*)
procedure Xem(n: integer);

var i: integer;
begin
writeln;
for i := 1 to n do write(s[i]:4);
writeln;
end;

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

write(‘ Tong cong ‘,n,’ so’); readln; END.

  • C#

using System; namespace SangTao1

{

/***********************************
So Than Thien: (xy, yx) = 1

**********************************/

class SoThanThien

{

static int mn = 90;
static int [] s = new int[mn];
static void Main(string[] args)
{   Run();
Console.ReadLine();
}

static void Run()

{   int n = Find();
for (int i=0;i<n;++i)
Console.Write(s[i] + " ");
Console.WriteLine("\n Tong cong: "+n+" so");
}

static int Find()

{   int d = 0;
for (int x = 10; x < 100; ++x)
if (Ucln(x,SoDao(x))==1)  s[d++] = x;
return d;
}

static int Ucln(int a, int {}b)

{   int r;
while (b != 0){ r = a%b;a = b;b = r; }
return a;
}

static int SoDao(int x)

{   int y = 0;
do { y = y*10+(x%10); x /= 10; } while (x!=0);
return y;
}

} // SoThanThien } // SangTao1

Cải tiến

Ta vận dụng tính đối xứng đã nhận xét ở phần trên để cải tiến chương trình. Như vậy chỉ cần khảo sát các số x = ab, với a > b ³   0. Trường hợp a = b ta không xét vì khi đó x’ = x và do đó Ucln(x, x) = x ³   10 ¹  1.

Nếu b = 0  ta có x = 10ax’ = a. Ta thấy Ucln(10a,       a) = a = 1 khi và chỉ khi a = 1. Do đó ta xét riêng trường hợp này. Khi ab =     10 ta có (10, 1) = 1.

Vậy 10 chính là một số cần tìm và là số đầu tiên.
Mỗi khi tìm được hai chữ số a và b thoả điều kiện a > b và Ucln(a*10 + b, b*10 + a) = 1 ta đưa a*10 + b vào kết quả, nếu b > 0 ta đưa thêm số đảo b*10 + a vào kết quả.

(* Pascal *)

(*————————————-

So Than thien: Phuong an 2

—————————————*)
function Tim2: integer;

var a,b,d: integer; begin

d:= 1; {So luong cac so can tim} s[d] := 10;

for a := 1 to 9 do

for b := 1 to a-1 do

if Ucln(a*10+b,b*10+a)=1 then begin

d := d + 1; s[d] := a*10 + b; d := d + 1; s[d] := b*10 + a;

end; Tim2 := d;

end;

// C#

// Phuong an 2 static int Find2() { int a,b, d = 0;

s[d++] = 10;

for (a = 1; a <= 9; ++a) for (b = 1; b < a; ++b)

if (Ucln(10*a + b, 10*b + a) == 1) { s[d++]=10*a+b; s[d++]=10*b+a; }

return d;

}

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

Fast-flying Falcon

sunset and fishing nets

Force of Life - Pushing Boundaries I

More Photos

Thống kê

  • 81,544 lượt xem

%d bloggers like this: