חישוב מספר מזל מקסימלי שמתחלק ב-11 בעזרת Backtracking

מדעי המחשב ואלקטרוניקה
2

התוכנית בשפת C++:

#include <iostream>
#include <string>

using namespace std;

bool isLucky(int n) {
    bool arr[10]; 
    for (int i = 0; i < 10; i++) {
        arr[i] = false; 
    }

    while (n > 0) { 
        int digit = n % 10; 
        if (arr[digit]) {
           return false; 
        }
        arr[digit] = true; 
        n = n/10; 
    } 
    return true; 
} 


bool isDivisible(long long number) {
    if (number == 11) {
        return true;
    }
    if (number < 11) {
        return false;
    }
    if (!(isLucky(number))) {
        return false;
    }
 
    std::string num_str = std::to_string(number);
    int odd_digits_sum = 0, even_digit_sum = 0; 
    for (int i = 0; i < num_str.size(); i++)  { 
        if (i % 2  == 0) {
            odd_digits_sum += (num_str[i]-'0'); 
        } else {
            even_digit_sum += (num_str[i]-'0'); 
        }
    } 
  
    return isDivisible(odd_digits_sum - even_digit_sum);
}

int main() {
    for (long long current_num = 999999999; current_num >= 100000000; --current_num) {
        bool result = isDivisible(current_num);
        if (result) {
            std::cout << "Biggest number: " << current_num << std::endl;
            break;
        }
    }

    return 0;
}

הגדרתי שתי פונקציות עזר:

  • הפונקציה isLucky בודקת אם המספר הוא מספר מזל. מספר מזל הוא מספר שאין בו ספרות זהות. כלומר למשל 123 הוא מספר מזל אבל 122 הוא לא מספר מזל. לשם כך, הגדרנו מערך בגודל עשר (שכן יש רק עשר ספרות) ונמלא אותו ב-false. נעבור על המספר ועבור כל ספרה נבדוק אם כבר ראינו אותה. אם כן, אז נחזיר false כי זה לא מספר מזל. אחרת, נשים true במקום המתאים במערך ונמשיך לספרה הבאה.
  • הפונקציה isDivisible בודקת אם המספר הוא מספר מזל שמתחלק ב-11. הפונקציה עובדת בשיטת Backtracking בצורה כזו שכל פעם אנחנו נעביר את ההפרש בין סכום הספרות במקומות האי-זוגיים, וסכום הספרות במקומות הזוגיים שלו, ברקורסיה. תנאי העצירה הוא שאם הגענו ל-11 אז זה אומר שהמספר מתחלק ב-11 ואם המספר קטן מ-11 אז הוא לא מתחלק ב-11.

ב-main אנחנו יוצרים לולאה שעוברת מהמספר הגדול ביותר בעל תשע ספרות עד המספר הקטן ביותר בעל תשע ספרות. בכל איטרציה נבדוק אם הוא מספר מזל שמתחלק ב-11 ואם כן אז נדפיס אותו וניצא מהלולאה.
הערה: אפשר לבצע פה אופטיזציה קטנה על-ידי התחלה מהמספר 987654321 כמו שהצעת.

תוצאה: מספר המזל הגדול ביותר בעל תשע ספרות שמתחלק ב-11 הוא 987652413.