מספר הפעולות המינימלי להשגת תוצאה

בביטוי האריתמטי (arithmetic expression) אנחנו משתמשים בארבע פעולות חשבון (אופרטורים): חיבור, חיסור, כפל וחילוק, ובאופרטורים (האופרטורים) עליהם אנחנו מפעילים את האופרטורים.

נתון לנו מספר שלם חיובי ממשי:

  • num שהוא המספר הבסיסי;
  • result שהוא מספר התוצאה אליו צריך להגיע;

אנחנו מעוניינים למצוא את מספר הפעמים (המינימלי החשבונאי) שנפעיל את האופרטורים כדי להגיע למספר result על-ידי שימוש במספרים שמוסרים לנו ובשימוש בארבע פעולות החשבון והחילוק.

הערות חשובות:

  • פעולת החשבון מבוצעת אחת אחרי השניה משמאל לימין, ולא לפי הכללים של סדר פעולות חשבון. (למשל: 5+5*5 = 50, לא נחשב כ- 5+(5*5) = 50).
  • פעולת החילוק מבוצעת על שארית (למשל, 10/4 = 2).
  • אם מצאנו דרך להגיע לתוצאה המבוקשת result , אז אין להמשיך בדרך זו. כלומר, דרכים שמתחילות בה ורק מוסיפות עליה עוד פעולות לא נספרות. (למשל, הביטוי 5+5*5-5+5 = 50 לא ייספר, כי הביטוי 5+5*5 כבר הגיע לתוצאה 50, ורק נוספו כאן הפעולות -5+5 שסכומן הוא 0).

לדוגמה, נניח שהדרך היחידה בה ניתן בחמש דרכים להגיע אל התוצאה 36 (result) רק עם המספר 3 (num)ועם ארבע פעולות חשבון (maxOp) היא:

  • 3 + 3 + 3 + 3 + 3 + 3 = 36
  • 3 * 3 * 3 * 3 = 36
  • 3 / 3 * 3 * 3 * 3 = 36
  • 3 * 3 / 3 * 3 * 3 = 36
  • 3 / 3 * 3 * 3 * 3 = 36

במקרה זה, התוצאה הנכונה היא, המספר הנמוך ביותר של הפעולות הוא

3 * 3 + 3 + 3 - 3 = 36

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

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

דוגמה 1:
קלט: 
num = 3,
result = 36,
maxOp = 4
פלט: 
4

הסבר: הדרך היעילה ביותר להגיע ל-36 עם 3 היא 3 * 3 + 3 + 3 - 3 = 36 עם 4 פעולות.

דוגמה 2:
קלט: 
num = 2,
result = 16,
maxOp = 4
פלט: 
4

הסבר: 2 * 2 * 2 * 2 = 16 עם 4 פעולות.

דוגמה 3:
קלט: 
num = 5,
result = 25,
maxOp = 2
פלט: 
2

הסבר: 5 * 5 = 25 עם 2 פעולות.

דוגמה 4:
קלט: 
num = 1,
result = 10,
maxOp = 9
פלט: 
9

הסבר: 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 10 עם 9 פעולות.

דוגמה 5:
קלט: 
num = 10,
result = 100,
maxOp = 1
פלט: 
1

הסבר: 10 * 10 = 100 עם 1 פעולות.

דוגמה 6:
קלט: 
num = 4,
result = 64,
maxOp = 3
פלט: 
3

הסבר: 4 * 4 * 4 = 64 עם 3 פעולות.

דוגמה 7:
קלט: 
num = 7,
result = 49,
maxOp = 1
פלט: 
1

הסבר: 7 * 7 = 49 עם 1 פעולות.

דוגמה 8:
קלט: 
num = 6,
result = 36,
maxOp = 1
פלט: 
1

הסבר: 6 * 6 = 36 עם 1 פעולות.

Loading...
נשמרLn 1, Col 1

קלט:

num = 3,
result = 36,
maxOp = 4

הפלט המבוקש:

4