Ứng dụng Stack vào bài toán chuyển đổi cơ số

Trong hướng dẫn này mình sẽ triển khai giải một bài toán quy đổi cơ số vận dụng Stack. Đây là một bài toán rất thông dụng trong lập trình, để làm được bài này những bạn cần nắm rõ quy tắc quy đổi giữa những cơ số .
Chúng ta sẽ cùng nhau thực thi một chương trình đổi cơ số thập phân sang cơ số nhị phân ( 2 ), bát phân ( 8 ) và thập lục phân ( 16 ) .banquyen png

Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

test php

Mục lục bài viết

1. Gợi ý cách thực hiện

Để giải được bài toán, điều tiên phong những bạn phải biết được số thập phân, nhị phân, bát phân, thập lục phân là gì ? và cách quy đổi giữa những chính sách này ra làm sao thì những bạn mới hoàn toàn có thể làm được. Nếu những bạn chưa từng nghe những cơ số này thì hoàn toàn có thể tìm hiểu thêm trên google. Dưới đây mình sẽ hướng dẫn cụ thể cách quy đổi từ cơ số 10 sang cơ số 2, còn lại những cơ số khác tương tự như nhé .
Hệ nhị phân là một hệ đếm dùng hai kí tự 0 và 1 để miêu tả 1 số ít .
Ví dụ : ta có một số ít nguyên 10 là số thập phân, khi chuyển sang số nhị phân sẽ là 1010 .
Vậy làm thế nào nó hoàn toàn có thể chuyển được như vậy, đơn thuần chỉ là lấy số thập phân đó và chia lấy dư cho 2, khi đó những số lượng phần dư được lấy ngược từ dưới lên chính là hệ nhị phân .

stack he nhi phan PNG

Như những bạn đã biết thì Stack hoạt động giải trí theo quy tắc LIFO ( last in first out ), vậy tại sao tất cả chúng ta không sử dụng Stack vào bài toán này, thay vì ta lưu những số này vào mảng ta chỉ cần lưu nó vào Stack rồi lấy nó ra theo quy tắc LIFO là xong .

Cứ mỗi lần chia lấy dư như vậy ta sẽ lưu vào Stack, cho đến khi số chia bằng 0 thì ta thực hiện lấy phần tử đầu (top) trong Stack ra, như vậy dãy số được lấy ra chính là dãy nhị phân.

Tương tự như vậy, để chuyển sang cơ số 8 và 16 ta cũng thực thi chia lấy dư .

Xem thêm  Bluestacks là gì? Tính năng, cách cài đặt và sử dụng - Wiki Máy Tính

2. Ứng dụng Stack để chuyển đổi cơ số

Trước khi khởi đầu viết hàm quy đổi cơ số, ta cần khởi tạo những cấu trúc Node và Stack, trong bài toán này mình sẽ sử dụng list link để thiết lập Stack .

/* khai báo Node */
struct node
{
	int data;
	struct node *pNext;
};
typedef struct node NODE;

/* khai báo cấu trúc của Stack */ 
struct stack
{
	NODE *pTop; // con trỏ quản lí đầu stack
};
typedef struct stack STACK;

/* hàm khởi tạo Stack */
void KhoiTaoStack(STACK &s)
{
	s.pTop = NULL;
}

/* hàm khởi tạo 1 cái node */
NODE *KhoiTaoNode(int x)
{
  //tạo mới một NODE
	NODE *p = new NODE();
	if (p == NULL)
	{
		cout << "\nKhông đủ bộ nhớ để cấp phát !";
		return NULL;
	}
  // đưa dữ liệu của biến x vào trong cái data của node p
	p->data = x; 
	p->pNext = NULL;
	return p;
}

Tiếp đến ta viết một hàm kiểm tra Stack rỗng, đây là điều kiện kèm theo để hoàn toàn có thể thêm thành phần hoặc xóa thành phần .

/* hàm kiểm tra Stack rỗng*/ 
bool IsEmpty(STACK s)
{
	// nếu stack rỗng
	if (s.pTop == NULL)
	{
		return false;
	}
	return true;
}

Để thêm được dữ liệu và Stack và lấy dữ liệu ra, ta cần có hàm push() và hàm pop().

/* Thêm phần tử vào đầu Stack (top)*/
bool Push(STACK &s, NODE *p)
{
	// node p đang rỗng
	if (p == NULL)
	{
		return false;
	}

	// nếu danh sách rỗng
	if (IsEmpty(s) == false)
	{
    // node p cũng chính là node pTop <=>chính là node đầu stack
		s.pTop = p;
	}
	else
	{
    // B1: cho con trỏ của node p trỏ đến node pTop
		p->pNext = s.pTop; 
    // B2: cập nhật lại node đầu chính là node p
		s.pTop = p;
	}
  // thêm thành công
	return true;
}

/* Lấy phần tử đầu danh sách và hủy nó đi */
bool Pop(STACK &s, int &x) // x chính là giá trị cần lấy ra
{
	// nếu danh sách rỗng
	if (IsEmpty(s) == false)
	{
    // lấy thất bại <=> danh sách đang rỗng
		return false; 
	}
  // gán node đầu danh sách vào node p <=> node p chính là node mà tí nữa ta sẽ xóa nó
	NODE *p = s.pTop; 
   // cập nhật lại node đầu 
	s.pTop = s.pTop->pNext;
  // lấy giá trị của node đầu ra gán vào biến x
	x = p->data; 
  // lấy phần tử thành công
	return true; 
}

Sau khi đã tạo xong các hàm cơ bản bây giờ chúng ta sẽ tạo hàm Chuyen_Co_So() để chuyển cơ số thập phân sang các cơ số khác. Tham số truyền vào của hàm bao gồm một Stack, cơ số cần đổi và số hệ thập phân cần chuyển.

Ta sẽ dùng vòng lặp while để chia lấy dư số cần chuyển đến khi số đó bằng 0, sau mỗi lần chia như vậy sẽ thêm vào Stack .

/* Hàm đổi cơ số 10 sang các cơ số 2, 8, 16 */
void Chuyen_Co_So(STACK &s, int cosocandoi, int hethapphan)
{
	while (hethapphan != 0)
	{
		int x = hethapphan % cosocandoi;
    // thêm x vào node p
		NODE *p = KhoiTaoNode(x); 
    // thêm node p vào stack
		Push(s, p);
    //tiếp tục chia đến hết
		hethapphan /= cosocandoi;
	}
}

Sau khi chia xong tất cả chúng ta sẽ có một Stack gồm có những số là phần dư. Nhiệm vụ của tất cả chúng ta giờ đây là tạo một hàm xuất những giá trị trong Stack ra theo chính sách LIFO .

*Lưu ý: Ở hệ bát phân và thập lục phân, khi giá trị lớn hơn 9 sẽ được quy ước thành các chữ cái, cụ thể như sau: 10 <=> A, 11 <=> B, 12 <=> C, 13 <=> D, 14 <=> E và 15 <=> F.

Vì vậy khi xuất những giá trị trong Stack ra màn hình hiển thị ta cần thêm điều kiện kèm theo, nếu giá trị < 10 thì ta triển khai in thông thường, nếu giá trị > = 10 thì ta sẽ xuất ra những vần âm quy ước .

/* xuất danh sách stack */
void XuatStack(STACK &s)
{
	while (IsEmpty(s) == true)
	{
		int x;
		Pop(s, x);
    //nếu x < 10 thi xuất bình thường
		if (x < 10)
		{
			cout << x;
		}
    //nếu x >= 10 thì xuất chữ cái tương ứng
		else
		{
			if (x == 10)
			{
				cout << "A";
			}
			else if (x == 11)
			{
				cout << "B";
			}
			else if (x == 12)
			{
				cout << "C";
			}
			else if (x == 13)
			{
				cout << "D";
			}
			else if (x == 14)
			{
				cout << "E";
			}
			else if (x == 15)
			{
				cout << "F";
			}
		}
	}
}

Full Code:

#include
using namespace std;

/*
Đổi 1 số nguyên sang cơ số 2 8 16
*/

/* khai báo Node */
struct node
{
	int data;
	struct node *pNext;
};
typedef struct node NODE;

/* khai báo cấu trúc của Stack */ 
struct stack
{
	NODE *pTop; // con trỏ quản lí đầu stack
};
typedef struct stack STACK;

/* hàm khởi tạo Stack */
void KhoiTaoStack(STACK &s)
{
	s.pTop = NULL;
}

/* hàm khởi tạo 1 cái node */
NODE *KhoiTaoNode(int x)
{
  //tạo mới một NODE
	NODE *p = new NODE();
	if (p == NULL)
	{
		cout << "\nKhông đủ bộ nhớ để cấp phát !";
		return NULL;
	}
  // đưa dữ liệu của biến x vào trong cái data của node p
	p->data = x; 
	p->pNext = NULL;
	return p;
}

/* hàm kiểm tra Stack rỗng*/ 
bool IsEmpty(STACK s)
{
	// nếu stack rỗng
	if (s.pTop == NULL)
	{
		return false;
	}
	return true;
}

/* Thêm phần tử vào đầu Stack (top)*/
bool Push(STACK &s, NODE *p)
{
	// node p đang rỗng
	if (p == NULL)
	{
		return false;
	}

	// nếu danh sách rỗng
	if (IsEmpty(s) == false)
	{
    // node p cũng chính là node pTop <=>chính là node đầu stack
		s.pTop = p;
	}
	else
	{
    // B1: cho con trỏ của node p trỏ đến node pTop
		p->pNext = s.pTop; 
    // B2: cập nhật lại node đầu chính là node p
		s.pTop = p;
	}
  // thêm thành công
	return true;
}

/* Lấy phần tử đầu danh sách và hủy nó đi */
bool Pop(STACK &s, int &x) // x chính là giá trị cần lấy ra
{
	// nếu danh sách rỗng
	if (IsEmpty(s) == false)
	{
    // lấy thất bại <=> danh sách đang rỗng
		return false; 
	}
  // gán node đầu danh sách vào node p <=> node p chính là node mà tí nữa ta sẽ xóa nó
	NODE *p = s.pTop; 
   // cập nhật lại node đầu 
	s.pTop = s.pTop->pNext;
  // lấy giá trị của node đầu ra gán vào biến x
	x = p->data; 
  // lấy phần tử thành công
	return true; 
}

/* Xem thông tin của node đầu danh sách */
bool Top(STACK s, int &x) 
// x chính là giá trị cần xem
{
	// nếu danh sách rỗng

	if (IsEmpty(s) == false)
	{
		return false;
	}
	x = s.pTop->data;
	return true;
}

/* Hàm đổi cơ số 10 sang các cơ số 2, 8, 16 */
void Chuyen_Co_So(STACK &s, int cosocandoi, int hethapphan)
{
	while (hethapphan != 0)
	{
		int x = hethapphan % cosocandoi;
    // thêm x vào node p
		NODE *p = KhoiTaoNode(x); 
    // thêm node p vào stack
		Push(s, p);
    //tiếp tục chia đến hết
		hethapphan /= cosocandoi;
	}
}

/* xuất danh sách stack */
void XuatStack(STACK &s)
{
	while (IsEmpty(s) == true)
	{
		int x;
		Pop(s, x);
    //nếu x < 10 thi xuất bình thường
		if (x < 10)
		{
			cout << x;
		}
    //nếu x >= 10 thì xuất chữ cái tương ứng
		else
		{
			if (x == 10)
			{
				cout << "A";
			}
			else if (x == 11)
			{
				cout << "B";
			}
			else if (x == 12)
			{
				cout << "C";
			}
			else if (x == 13)
			{
				cout << "D";
			}
			else if (x == 14)
			{
				cout << "E";
			}
			else if (x == 15)
			{
				cout << "F";
			}
		}
	}
}

int main()
{
	STACK s;
	KhoiTaoStack(s);
	
	int hethapphan,cosocandoi;
	cout << "\nNhập giá trị thập phân cần chuyển: ";
	cin >> hethapphan;
  do{
    cout << "\nNhập cơ số cần chuyển (2, 8, 16):  ";
	  cin >> cosocandoi;
  }while(cosocandoi != 2 && cosocandoi != 8 && cosocandoi != 16);

	Chuyen_Co_So(s, cosocandoi, hethapphan);
	cout << "\nKết quả:\n";
	XuatStack(s);
	cout << endl;

  cout<<"\n-------------------------\n";
  cout<<"Chương trình này được đăng tại Freetuts.net";
}

Kết quả: Mình chỉ thực hiện chuyển số thập phân sang nhị phân, các hệ khác các bạn có thể test thử nhé.

stack chuyen doi co so 1 PNG

3. Kết luận

Như vậy là tất cả chúng ta đã triển khai xong chương trình quy đổi cơ số thập phân sang cơ số nhị phân, bát phân, thập lục phân. Đây là một bài toán khá thông dụng trong những ngôn từ lập trình, vì thế những bạn hãy nắm thật kỹ. Để hoàn toàn có thể hiểu rõ hơn về Stack những bạn hoàn toàn có thể rèn luyện thêm nhiều bài toán khác áp dung Stack. Chúc những bạn thực thi thành công xuất sắc ! ! !

4/5 - (1 bình chọn)

Bài viết liên quan

Để lại ý kiến của bạn:

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *