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

26/10/2016 4 minutes read
Share:

Đề 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"

Các 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, tôi 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:

(Các 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 tôi 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 tôi 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 các 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;
}
view raw WILLITST.cpp hosted with ❤ by GitHub

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"
view raw WILLITST.py hosted with ❤ by GitHub

Code by Phạm Văn Lâm.

Share: