SPOJ.COM - Thuật toán bài WILLITST - Will it ever stop

Đề bài:

Khi Bob đang ở trong thư viện của trường đại học Warsaw, anh ta nhìn thấy một đầu đề ở mặt chính ngôi nhà là "Will it ever stop?" và phía dưới là đoạn code huyền bí:

while n > 1
  if n mod 2 = 0 then
    n := n/2
  else
    n := 3*n+3

Hãy giúp anh ấy tìm ra lời giải đáp.

Đầu vào

Một dòng chứa một số n với n <= 10^14

Đầu ra

In ra "TAK" nếu chương trình có dừng lại, ngược lại thì in ra "NIE"

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/WILLITST/

Phân tích

• Ở đây, mình sử dụng thuật toán tham lam Greedy
• Rõ ràng vòng lặp dừng lại khi n <= 1. Mà điều này chỉ xảy ra khi số n được biểu diễn dưới dạng 2^k, Khi đó, sau k vòng lặp kết quả sẽ được n == 1. Và khi đó vòng lặp sẽ bị thoát.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include <iostream>
using namespace std;

typedef unsigned long long ull;

int main()
{
	//freopen("input.txt","r",stdin);
	ull n = 0;
	cin >> n;
	bool checkStop =  true;
	while(true)
	{
		if(n <= 2) break;

		// Nếu số n có một ước số > 2 mà lẻ thì chắc chắn
		// ở trong vòng lặp đề bài n = 3*n + 3 , n sẽ tăng
		// do đó vòng lặp đó sẽ không bao giờ dừng
		if(n > 2 && n%2 != 0)
		{
			checkStop = false;
			break;
		}
		n = n/2;
	}
	if(checkStop) cout << "TAK" << endl;
	else cout << "NIE" << endl;
	return 0;
}

Code Python:

n = long(input())
checkStop = 1

while(1):
    if n <= 2:
        break
    if (n > 2 and n%2 != 0):
        checkStop = 0
        break
    n = n/2

if checkStop == 1 :
    print "TAK\n"
else:
    print "NIE\n"