אהלן,

יש לי תרגיל שבו אני מתבקש לכתוב תוכנית יעילה ככל האפשר שתחשב את המכפלה של 2 מספרים ללא שימוש באופרטור *.

כתבתי את הקוד הבא:

int multiply (int a, int b) {
if (b == 1) return a;
else return (a + multiply(a, b - 1));
{

התרגיל נבדק ע"י סקריפט כלשהו שבודק את היעילות שלו, הנה פלט הסקריפט:

Test 1: Compile answer (0.0 out of 0)
Test 2: Test answer (2.0 out of 2)All tests completed successfully! 
Test 3: Check for use of * (2.0 out of 2)
Test 4: Efficiency check (0.0 out of 6)379 * 268 solved in 267 steps, but there is also a recursive solution which only uses 10 steps 268 * 379 solved in 378 steps, but it could have been done in 268 steps 

למישהו יש מושג איך אפשר להגיע לביצועים הנדרשים ?

האם מותר להשתמש בכל שאר האופרטורים?

נראה לי שהכוונה להשתמש באלגוריתם כלשהו שמתבסס על השיטה שמלמדים ילדים בכיתה ד'-ה' בשביל להכפיל מספרים גדולים.

צריך להבין שאפשר לפרק מספר גדול לגורמים, להכפיל כל גורם בנפרד, ולחבר אותם בסוף לתוצאה.

אפשר להקטין את כמות הקריאות לפונקציה לכמות בסדר גודל log, אם פשוט תחלק את אחד המספרים ב2, בכל שלב שבו מתאפשר לך.

במקרה הטוב logN קריאות

במקרה הגרוע 2xlogN קריאות

עריכה:

מחקתי את הקוד שכתבתי לדוגמא, כי הבנתי בדיעבד שמדובר על תרגיל.