Số may mắn (Lucky Numbers)

Giới thiệu

Số may mắn là những số nguyên đặc biệt. Từ các số cơ bản, một số số đặc biệt bị loại bỏ theo vị trí của chúng. Thay vì theo giá trị, các số bị loại bỏ vì vị trí của chúng. Các số không bị xóa là các số may mắn.

Quy tắc xóa số tuân theo quy luật: Lúc đầu, mọi số thứ 2 bị xóa, sau đó tất cả các số thứ 3 bị xóa, và cứ thế tiếp tục.

Dưới đây là một số ví dụ:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 (1 – 25 tất cả)
1 3 5 7 9 11 13 15 17 19 21 23 25 (xóa tất cả số thứ 2)
1 3 7 9 13 15 19 21 25 (Tất cả số thứ 3 bị xóa, bắt đầu từ 5)
1 3 7 9 13 15 21 25 (Tất cả số thứ 7 bị xóa bắt đầu từ 19)

Đầu vào và Đầu ra

Đầu vào: Nhập một số để kiểm tra xem nó có phải số may mắn hay không. Giả sử số là 13 Đầu ra: 13 là một số may mắn.

Thuật toán

isLuckyNumber(number)
Đầu vào: Một số.
Đầu ra: Kiểm tra số có phải số may mắn hay không.

Begin
    counter := 2 (Là dữ liệu tĩnh, không được khởi tạo lại trong gọi đệ quy)
    if counter > n, then
        return 1
    if n mod counter = 0, then
        return 0
    n := n – (n / counter)
    counter := counter + 1
    isLuckyNumber(n)
End

Ví dụ (C++)

#include <iostream>
using namespace std;

int counter = 2;  // sử dụng trong đệ quy
bool isLuckyNumber(int n) {
    if(counter > n)
        return 1;
    if(n % counter == 0)
        return 0;
    n -= n/counter;  // n sẽ là vị trí tiếp theo cho đệ quy
    counter++;
    return isLuckyNumber(n);
}

int main() {
    int x = 13;
    if(isLuckyNumber(x))
        cout << x << " is a lucky number.";
    else
        cout << x << " is not a lucky number.";
}

Kết quả

13 is a lucky number.