אתגר תכנותי: האם מספר שמח :-)

כתוב פונקציה שתבדוק אם מספר שלם חיובי נתון n הוא "מספר שמח".

מספר שמח הוא מספר המוגדר על ידי התהליך הבא:

1. תתחיל מכל מספר שלם חיובי, ואז תחליף את המספר בסכום הריבועים של הספרות שלו.
2. חזור על התהליך עד שהמספר שווה ל-1 ( מספר שמח :-) ) או עד שהוא חוזר על מספר שאינו 1.

המספרים שהתהליך הזה מסתיים עבורם ב-1 הם מספרים שמחים :-).

לדוגמה:

Input: n = 13
Output: True

הסבר:

1^2 + 3^2 = 10
1^2 + 0^2 = 1 :-) Definitely a happy number!

• בסיומו של תהליך, סכום הספרות הוא 1 ולכן המספר שמח :-).

דוגמה נוספת:

Input: n = 91
Output: True

הסבר:

9^2 + 1^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1 :-) Definitely a happy number!

• בסיומו של תהליך, סכום הספרות הוא 1 ולכן המספר שמח :-).

דוגמה נוספת:

Input: n = 18
Output: False

הסבר:

1^2 + 8^2 = 65
6^2 + 5^2 = 61
6^2 + 1^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 2 :-( Not a happy number!!

• סכום הספרות לא יכול להיות 1 ולכן זה אינו מספר שמח.

פתרון האתגר "האם מספר שמח" באמצעות רקורסיה

הפתרון המתבקש ביותר הוא פתרון רקורסיבי במסגרתו הפונקציה מעבדת את הקלט, מעריכה את התוצאה, וקוראת לעצמה עד להשגת תנאי הבסיס.

במקרה שלפנינו יש שני מקרי בסיס. אם הסכום הוא 1 אז המספר שמח :-). להבדיל, אם הספרות מסתכמות למספר חד ספרתי שאינו 1 או שמספר שאינו 1 הופיע כבר בתהליך אז המספר לא יכול להיות שמח.

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

def is_happy_number_recur(number, seen_numbers=None):
   # Initialize the set of seen numbers if not provided
   if seen_numbers is None:
       # Set to track seen numbers to prevent infinite loops
       seen_numbers = set()


   # Break the number into its digits
   digits = str(number)
  
   # Sum the squares of the digits
   digit_sum = sum(int(digit) ** 2 for digit in digits)
  
   # If the sum equals 1, the number is a happy number
   if digit_sum == 1:
       return True
  
   # If the sum is a single-digit number (and not 1), or the number is in seen_numbers, it's not a happy number
   if digit_sum < 10 or digit_sum in seen_numbers:
       return False
  
   # Otherwise, run the function recursively on the sum of the current stage
   seen_numbers.add(digit_sum)
   return is_happy_number_recur(digit_sum, seen_numbers)

נבדוק את הפתרון:

# Test cases
print(is_happy_number_recur(91))  # True 
print(is_happy_number_recur(19))  # True
print(is_happy_number_recur(18))  # False
print(is_happy_number_recur(13))  # True
print(is_happy_number_recur(10))  # True
print(is_happy_number_recur(9))   # False
print(is_happy_number_recur(1))   # True

נסביר את הפתרון הרקורסיבי לאתגר "האם מספר שמח":

הפונקציה הרקורסיבית חוזרת על התהליך של חישוב סכום ריבועי הספרות עד לקיום אחד מתנאי הבסיס.

1. פונקציה רקורסיבית: הפונקציה

   is_happy_number_recur(number)

   • מקבלת מספר שלם כקלט ומחזירה True אם הוא מספר שמח, אחרת False.

2. הסט `seen_numbers` הכרחי לזיהוי מספרים חוזרים, ומניעת לולאות אינסופיות במידה והתוצאה לא מגיעה ל-1.

3. פירוק לספרות:

   digits = str(number)

   • ממיר את המספר למחרוזת כדי להקל על טיפול בספרות בודדות.

4. חישוב סכום הריבועים:

   digit_sum = sum(int(digit) ** 2 for digit in digits)

   • מחשב את סכום הריבועים של כל הספרות במספר באמצעות list comprehension.

5. בדיקת תנאי בסיס:

   • אם סכום הריבועים שווה ל-1 אז מחזירה True כי זהו מספר שמח.
   • אם הסכום הוא חד-ספרתי שאינו 1 או שהמספר כבר נצפה בתהליך אז מחזירה False כי זה אינו מספר שמח.

6. קריאה רקורסיבית במידה ולא התקיימו תנאי הבסיס:

   • מתבצעת קריאה רקורסיבית לפונקציה עם סכום הריבועים הנוכחי כקלט כדי להמשיך את התהליך. הקריאות הרקורסיביות חוזרות ונשנות עד לקיום אחד ממקרי הבסיס.

7. החזרה:

   כאשר הפונקציה מגיעה לתנאי הבסיס, היא מחזירה תשובה בוליאנית True או False.

ניתוח יעילות זמן וזיכרון של הפונקציה הרקורסיבית

סיבוכיות זמן:

את רובו של זמן הביצוע דורשות הפעולות של חישוב סכום ריבועי הספרות והקריאות הרקורסיביות. חישוב סכום ריבועי הספרות הוא בעל סיבוכיות זמן לינארית של O(N), כאשר N הוא מספר הספרות במספר הקלט. מספר הקריאות הרקורסיביות תלוי באורך השרשרת של סכומים ביניים לפני ההגעה למקרה בסיס. במקרה הגרוע ביותר (כאשר השרשרת היא הארוכה ביותר האפשרית לפני לולאה או הגעה ל-1), מספר הקריאות הרקורסיביות הוא גם כמעט לינארי כתלות במספר הספרות, מה שמוביל לסיבוכיות זמן כוללת של O(N^2) במקרה הגרוע ביותר.

סיבוכיות מקום:

שני גורמים עיקריים לסיבוכיות המקום של הפונקציה הם המערך `seen_numbers` ומחסנית הקריאות הרקורסיביות:

• הסט seen_numbers משמש למניעת לולאות אינסופיות ומאחסן עד N סכומים ביניים במקרה הגרוע ביותר, מה שמוביל לסיבוכיות מקום של O(N).
• מחסנית קריאות רקורסיביות: כל קריאה רקורסיבית מוסיפה מסגרת למחסנית הקריאות, אך העומק המקסימלי של המחסנית מוגבל גם על ידי מספר הספרות N. לכן, סיבוכיות המקום הקשורה למחסנית הקריאות היא גם O(N).

יעילות כוללת:

• סיבוכיות זמן: מקרה גרוע ביותר: O(N^2)
• סיבוכיות מקום: O(N)

בדיקה האם מספר הוא שמח :-) באמצעות לולאה

שימוש בלולאה במקום ברקורסיה יכול להפחית את צריכת משאבי המערכת. בייחוד את המקום בזיכרון הנדרש לאחסון מחסנית הקריאות.

הלולאה הבאה מיישמת פתרון יעיל לבעיה:

def is_happy_number(n):
    """Determines if a given number is a happy number."""

    # Set to track seen numbers to prevent infinite loops
    seen_numbers = set()  

    # Loop until a cycle is found or 1 is reached
    while n not in seen_numbers and len(str(n)) > 1:  

        # Add the current number to the seen set
        seen_numbers.add(n)     
     
        # Calculate the sum of squared digits
        n = sum([int(digit)**2 for digit in str(n)])  

    # True if the final number is 1 (happy number), False otherwise
    return n == 1

נבדוק את הפתרון:

# Test cases
print(is_happy_number(91))  # True 
print(is_happy_number(19))  # True
print(is_happy_number(18))  # False
print(is_happy_number(13))  # True
print(is_happy_number(10))  # True
print(is_happy_number(9))   # False
print(is_happy_number(1))   # True

נסביר את שלבי הביצוע של הפונקציה האיטרטיבית (=מבוססת לולאה):

1. הפונקציה מתחילה באתחול סט ריק במטרה לאחסן את המספרים בתהליך.

   seen_numbers = set()

   • הסט חיוני לזיהוי מחזורים ומניעת לולאות אינסופיות.

2. לולאת while רצה עד לפגיעה באחד משני תנאי בסיס:

   • • n not in seen: זה מבטיח שהמספר הנוכחי לא נראה בעבר. אם מספר נראה שוב, זה מצביע על מחזור, והתהליך לא יגיע ל-1, אז זה לא מספר שמח.
     • len(str(n)) > 1: תנאי זה ממשיך את הלולאה רק אם למספר יש יותר מספרה אחת. מספרים בעלי ספרה אחת ימשיכו לשלב הבא.

   • במסגרת הלולאה נאספים המספרים בתהליך לתוך הסט `seen_numbers`.

     seen_numbers.add(n)

   • בנוסף, מחושב סכום הספרות בריבוע.

     n = sum([int(digit)**2 for digit in str(n)])

3. מחוץ ללולאה מעריכים אם הסכום שווה ל-1 ומחזירים את התוצאה. True אם הסכום שווה ל-1, אחרת False.

הערכת ביצועים של הפתרון האיטרטיבי לבדיקה האם מספר הוא שמח :-)

סיבוכיות זמן:

• הלולאה החיצונית רצה כל עוד n לא נראה בתהליך ומספר הספרות ב-n גדול מ-1.
• הלולאה הפנימית מחשבת את סכום הספרות בריבוע, ומספר הספרות יכול לגדול באופן לינארי עם n.

שילוב שתי הלולאות מוביל לסיבוכיות זמן כוללת של O(n^2).

סיבוכיות מקום:

סיבוכיות המקום נקבעת בעיקר על ידי סט ה-`seen_numbers`, אשר מאחסן מספרים ייחודיים כדי למנוע לולאות אינסופיות. תרחיש המקרה הגרוע ביותר הוא כאשר כל מספר מהטווח 1 עד n הוא ייחודי ונוסף לסט. לכן, סיבוכיות המקום מוערכת כ-O(n), בהתחשב ביחס הלינארי בין המספרים הייחודיים לבין הערך המקסימלי של n.

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

רקורסיה בפייתון - כל מה שרצית לדעת ועוד כמה דברים חשובים

שימוש בטכניקות שני המצביעים לפתרון בעיות תכנותיות

אלגוריתם חיפוש בינארי - מהבנה ליישום

אלגוריתם חיפוש לעומק DFS - מהבנה ליישום

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים