שלום לכולם,

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

לדוגמה, בתרגיל הראשון התבקשתי לכתוב פונקציה רקורסיבית שמקבלת מספר ומחזירה את המְחַלְקִים הראשוניים שלו, מהגדול לקטן. זה הפתרון שלי:

קוד:

void printPrimeFactors(int num) {
	if(num == 1)
		return;
	else {
		int i;
		i = 2;
		while (num%i != 0)
			i++;
		cout<<i<<" ";
		printPrimeFactors(num/i);
	}
}

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

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

מה דעתכם בנושא?

תודה

ציטוט:

במקור נכתב על ידי CM0S לדוגמה, בתרגיל הראשון התבקשתי לכתוב פונקציה רקורסיבית שמקבלת מספר ומחזירה את המְחַלְקִים הראשוניים שלו, מהגדול לקטן. זה הפתרון שלי:

אני לא יודע אם ניסית להריץ את הקוד, אבל אתה מדפיס את המחלקים מהקטן לגדול ולא מהגדול לקטן...

דווקא כי אתה עובר על המספרים מהקטן לגדול, אין צורך בבדיקה שהמספר אכן ראשוני.
למה?
בוא נניח בשלילה שהמספר i אליו הגעת, אותו אתה מדפיס, שמחלק את num הוא פריק.
זה אומר שקיימים שני מספרים אחרים, j ו-k שהם המחלקים שלו, ו-j ו-k קטנים מ-i. (המחלקים של מספר קטנים ממנו...)
j ו-k, המחלקים של i הם כמובן גם מחלקים של num ולכאורה פספסת אותם...
אבל בוא נזכור שבדרך ל-i עברת על כל המספרים הקטנים ממנו החל מ-2, ולכן זה אומר שעברת גם על j ו-k.
מה שעומד בסתירה לכך שפספסת אותם...
מסקנה: מסתבר שהמספר שאתה מדפיס הוא ראשוני.

נראה לי.

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

קודם כל תודה.

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

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

כי זה נכתב בשלוש בבוקר.

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

תודה רבה!

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

אם במקרה היינו מדברים על שדה המספרים הטבעיים מודולו p, היינו בבעיה. קוד כזה הוא לא נכון:

קוד:

template<typename T>
void printPrimeFactors(const T& num) {
	if(num == 1)
		return;
	else {
		T i = 2;
		while (num%i != 0)
			i++;
		cout<<i<<" ";
		printPrimeFactors(num/i);
	}
}

כי יכול לדוגמה, בשדה [tex]Z_5[/tex] נגלה ש-[tex]3 \cdot 4 = 2[/tex] (כי [tex]3 \cdot 4 = 12[/tex] וכידוע [tex]12 \equiv 2 (mod 5)[/tex] כי השארית של חלוקה 12 ב-5 היא 2), ולכן [tex]{2 \over 3} = 4[/tex], כלומר, המחלקים של מספר יכולים להיות גדולים ממנו.
אם מישהו היה כותב במקרה מחלקה כזו (http://drdobbs.com/cpp/184401858) אי-אפשר היה לסמוך על הקוד.

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

בוודאי שמדובר על המספרים הטבעיים, אחרת התמונה הייתה נראית שונה לגמרי.

החלק העצוב פה הוא שהבנתי את מה שכתבת.

אתה מבין שזו שלא בדיוק מצאת את הגורמים הראשוניים, אלה את הפרוק לפי גורמים ראשוניים?("המשפט היסודי של האריתמטיקה")

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

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

תודה גם לך