Số thân thiện – Friendly number

seven

        Số thân thiện là số tự nhiên có 2 chữ số mà khi đảo trật tự của 2 chữ số đó sẽ thu được một số nguyên tố cùng nhau với số đã cho. Yêu cầu tìm tất cả các số có 2 chữ số thõa mãn yêu cầu là một số thân thiện. Ở đây, tôi sẽ trình bày từng bước từ việc hiểu bài toán đến việc cài đặt bài toán bằng ngôn ngữ C++ (có project C# viết trên visual studio 2010 kèm theo để các bạn tiện theo dõi.

1. Hiểu vấn đề bài toán

-  Ta ký hiệu (a, b) là ước chung lớn nhất (ucln) của 2 số tự nhiên a và b. Hai số tự nhiên a và b được gọi là 2 số nguyên tố cùng nhau khi và chỉ khi (a, b) = 1. Chẳng hạn:

  •      (23, 32) = 1,  vậy 23 là một số cần tìm. Theo đúng tính chất đối xững, ta có ngay 32 cũng là một số cần tìm.
  •     (12, 21) = 3,  vậy 12 và 21 không phải là những số cần tìm và không phải là 2 số nguyên tố cùng nhau.

-  Đặc tả: gọi 2 chữ số tự nhiên cần tìm x là a và b, ta có:

(1)    x = ab.

(2)    a, b = 0…9 (a và b biến thiên trong khoảng từ 0 đến 0).

(3)    a > 0 vì x là số có 2 chữ số.

(4)   (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 ta như sau:

(5)   x = 10 …. 99 (x biến thiên từ 10 đến 99, vì x là số có 2 chữ số).

(6)   (x, x’) = 1

-  Nếu x = ab thì x’ = ba. Ta có thể tính giá trị 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).

(7) x’ = Đơn(x)*10 + Chục(x).

(8) (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 mã giả (pseudo code)  tựa C++ như sau:

for (int x = 10; x < 100; x++)
{
     if (ucln(x, đơn(x) * 10 + chục(x)) == 1)
     {
         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ố.

int ucln(int a, int b)
{
    int r;
    while(b > 0)
    {
        r = b;
        b = a % b;
        a = r;
    }
    return a;
}
  • Đơn(x) = (x % 10): số dư của phép chia nguyên x cho 10, thí dụ:

Đơn(19) = 19 % 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 /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.

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

int s[99] ;

-  Phương án 1 của chương trình sẽ hoạt động theo hai bước như sau:

1. n = Tim;

2. 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 % 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 / 10

3. Cài đặt chương trình

Chương trình có thể cài đặt đơn giản trên console application như sau: (đã test trên devC++ 4.9.9.2 và visual studio 2010)

// University of Information Technology - VietNam National University HCM city
// Create by thanhcuong1990@gmail.com

#include <stdio.h>
#include <conio.h>
#include <iostream>

using namespace std;
int s[90];

//  Find Greatest Common Devisor
int ucln(int a, int b)
{
    if ((a == 0) || (b == 0))
        return a+b;
    while (a !=b)
    {
       if(a>b)
          a=a-b;
       else
          b=b-a;
    }
    return a;

}

// Find So Dao
int soDao(int x)
{
    int y = 0;
    y = ((x % 10) * 10) + (x /10);   
    return y;
}

// Find Friendly number
int Find()
{
    int d = 0;
    for(int x = 10; x < 100; x++)
    {
            if(ucln(x, soDao(x)) == 1)
            {
                       s[d++] = x;
            }
    }
    return d;
}

// Print result
void Run()
{
    int n = Find();
     cout<< "Total (Friendly number) is: "<< n <<" number. \n";
     for(int i = 0; i < n; i++)
     {
             cout<< s[i] << " ";
     } 
     cout<<endl;
}

int main()
{
    Run();
    system("pause");
    return 0;
}

-  C#
// University of Information Technology - VNU
// Create by: Lâm Thanh Cường - thanhcuong1990@gmail.com - thanhcuong.wordpress.com

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Friendly_number_Csharp
{
    class Program
    {
        static int[] s = new int[90];

        //  Find Greatest Common Devisor
        static int ucln(int a, int b)
        {
            if ((a == 0) || (b == 0))
                return a+b;
            while (a !=b)
            {
               if(a>b)
                  a=a-b;
               else
                  b=b-a;
            }
            return a;

        }

        // Find So Dao
         static int soDao(int x)
         {
             int y = 0;
             y = ((x % 10) * 10) + (x /10);   
             return y;
         }

        // Find Friendly number
        static int Find()
        {
            int d = 0;
            for(int x = 10; x < 100; x++)
            {
                    if(ucln(x, soDao(x)) == 1)
                    {
                               s[d++] = x;
                    }
            }
            return d;
        }

        // Print result
        static void Run()
        {
            int n = Find();
             Console.WriteLine("Total (Friendly number) is:  {0} number.", n);
             for(int i = 0; i < n; i++)
             {
                     Console.Write( s[i] + " ");
             } 
             
           }

        static void Main(string[] args)
        {
            Run();
            Console.ReadLine();
        }
    }
}

* 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ả.

-  Như vậy hàm soDao(int x) ở 2 đoạn đoạn code trên sẽ không còn tác dụng nữa. Do đó, trong phần cải tiến này chúng ta bỏ hàm soDao(int x) đi. Và hàm Find() được viết lại như sau:

// Find Friendly number
        int Find()
        {
            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 * b + a;
                        s[d++] = 10 * a + b;
                    }

                }
            }
            return d;
        }

 

-  Click vào đây để download chương trình tìm số thân thiện bằng C++.

-  Click vào đây để download chương trình tìm số thân thiện bằng C# (viết trên visual studio 2010).

About these ads

About thanhcuong1990

Handsome and talent!! ^^
This entry was posted in Data structure and Algorithms. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s