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

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

היי,
אני קצת חלש בנושא של backtracking יש לי את השאלה הבאה:

כתבו תכנית המציגה את המספר בן 9 הספרות השונות זו מזו הגדול ביותר האפשרי שמתחלק ב-11.
מספר מתחלק ב-11 אם ההפרש בין סכום הספרות במקומות האי-זוגיים, וסכום הספרות במקומות הזוגיים שלו, מתחלק ב-11.
למשל: במספר: 1529 סכום הספרות במקומות האי זוגיים בו הוא 14 וסכום הספרות במקומות הזוגיים בו הוא 3, לכן הוא מתחלק ב: 11
הערה: מומלץ להשתמש במשתנים מטיפוס long long כדי לאחסן מספרים גדולים בעלי 9 ספרות.

חשבתי להתחיל ב-987654321 ולהתחיל לבדוק למטה, ולהשתמש במערך בוליאני כדי לעקוב אחרי הספרות שבשימוש. אבל מעבר לזה אני לא ממש מצליח להבין מה לעשות.

אודה לכל עזרה. גם אם זה בשפה אחרת.

#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.