| כותב |
|
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 08 October 2007 בשעה 19:15 | | IP רשוּם
|
|
|
|
מישהו יכול להראות לי את הפתרון הכי יעיל של התרגיל הבא:
נתון מערך 3,7,2
ומבקשים להדפיס את כל האופציות האפשרויות מהמספרים האלו.
כמו 3,7,2
3,27
7,3,2
וכו'
זה אמור להדפיס את כולם
מישהו מכיר את הדרך היעילה ביותר לביצוע התרגיל ?
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 08 October 2007 בשעה 19:50 | | IP רשוּם
|
|
|
|
יש n עזרת סידורים אפשריים, אז זה לא יהיה יותר יעיל מזה, משמע לא יעיל בכלל...
נגיד שהמספרים הם 3, 7, 2, ...
לצורך נוחות סמור אותם במערך,
אני אגיד להדפיס מספר, הכוונה למספר ששמור במערך במקום הזה.
אתה שומר מערך בוליאני ( גלובאלי) באורך של המערך, ומאתחל אותו לאפסים.
והפונקציה מקבלת אינדקס (אתה מעביר לה 0)
אם האינדקס מעבר לאורך אז היא יורדת שורה, או סתם רווח או מה שזה לא יהיה.
אם הוא בטווח של המערך אז אתה עובר על המערך הבוליאני, כל איבר בו שהוא
אפס אתה שם בו 1, מדפיס את האיבר המתאים, קורא קריאה רקורסיבית עם
האינדקס הבא, ומחזיר אותו להיות 0.
זהו.
כמובן יהיה נחמד לממש בלי רקורסיה, כמו כל דבר אחר, אבל זה הרעיון.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 08 October 2007 בשעה 21:14 | | IP רשוּם
|
|
|
|
אתה יכול לכתוב לי את הפונקציה בשפת C\C++ או Java?
כי לא בדיוק הבנתי את הרעיון.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 08 October 2007 בשעה 21:45 | | IP רשוּם
|
|
|
|
עם הידע המועט שלי ב-CPP אני אשתדל D:
קוד:
#include <iostream>
using namespace std;
const int N = 6;
const char c[N] = {'a','s','d','f','g','h'};
int p[N];
bool o[N];
void do_comb_print(int i)
{
if (i == 0)
for (int j = 0 ; j < N ; ++j)
o[j] = false;
if (i == N){
for (int j = 0 ; j < N ; ++j)
cout << c[p[j]];
cout << endl;
return;
}
for (int j = 0 ; j < N ; ++j)
if (!o[j])
{
o[j] = true;
p[i]=j;
do_comb_print(i+1);
o[j] = false;
}
}
int main()
{
do_comb_print(0);
return 0;
} |
|
|
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 11 October 2007 בשעה 11:18 | | IP רשוּם
|
|
|
|
ניסיתי להבין את התוכנית כבר יומיים ולא הבנתי את הרעיון הרקרוסיה הזה מאוד מסבך אותי..
אולי תוכל לתת לי הסברים על המערכים מה כל אחד אמור לעשות ולמה הוא משמש?
מצטער שאני חופר אבל אני פשוט ממש רוצה להבין את זה..
|
| חזרה לתחילת העמוד |
|
| |
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 11 October 2007 בשעה 11:22 | | IP רשוּם
|
|
|
|
ואולי אתה מכיר איזה שהוא מהדר או תוכנה שיכולה להראות לי ויזואלית איך הרקרוסיה הזאת עובדת?
כי אני זוכר בבית ספר הייתה לנו תוכנה שמראה ויזואלית איך נקראות הפונקציות ברקרוסיה וכו..
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 11 October 2007 בשעה 11:44 | | IP רשוּם
|
|
|
|
N - מספר הסימנים שצריך לסדר בכל הסדרים האפשריים.
המערך C זה האותיות/הסימנים להדפסה.
המערך P מסמל את הרצף הנוכחי, אם התא הראשון שלו מופיע X זה אומר שבמילה
הנוכחית צריך להדפיס בתור האות הראשונה את C במקום X (האות/הסימן ה-X)
המערך O מסמל את האותיות שכבר בשימוש במילה הנוכחית, מכיוון שאנחנו
מסדרים מספר אותיות בלי לשכפל אותן אנחנו צריכים להגביל את שאר האותיות
במילה שלא ישתמשו באות שאנחנו משתמשים בה שנית.
הקוד הזה זה סתם קוד אתחול של המערך O, לא ממש חלק מהפונקציה:
קוד:
if (i == 0)
for (int j = 0 ; j < N ; ++j)
o[j] = false; |
|
|
I שווה 0 רק פעם אחת בקריאה הראשונית.
עכשיו בודקים לתנאי יציאת מהרקורסיה, אם I שווה ל-N אז יש לננו כבר מילה
באורך מלא, אנחנו מדפיסים את כולה, יורדים שורה, ויווצאים בלי עוד קריאה
רקורסיבית כמובן.
קוד:
if (i == N){
for (int j = 0 ; j < N ; ++j)
cout << c[p[j]];
cout << endl;
return;
} |
|
|
ועכשיו הפעילולת הרגילה של הפונקציה:
עבור כל אות שעדיין לא בשימוש במילה, היא שמה את האות במקום הנוכחי,
מסמלת את האות בכתופה, וקוראת קריאה רקורסיבית, אחרי שמוצו כל תת
האפשרויות כשהאות במקומה יש חזרה והיא מסמנת את האות כפנוייה מחדש.
קוד:
for (int j = 0 ; j < N ; ++j)
if (!o[j])
{
o[j] = true;
p=j;
do_comb_print(i+1);
o[j] = false;
} |
|
|
זאת רקורסיית עץ (מכל קריאה עם פרמטר I, יש N - I קריאות רקורסיביות, כולן עם
אותו פרמטר, I+1, אבל המערך של האותיות בשימוש ושל האותיות של המילה שונה)
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 11 October 2007 בשעה 11:59 | | IP רשוּם
|
|
|
|
לדוגמא עבור A S D אמור להיות עץ כזה:
קוד:
do_comb_print(0):
puttuing 'a' at 0
do_comb_print(1):
puttuing 's' at 1
do_comb_print(2):
puttuing 'd' at 2
do_comb_print(3):
asd
clearing 'd' from 2
clearing 's' from 1
puttuing 'd' at 1
do_comb_print(2):
puttuing 's' at 2
do_comb_print(3):
ads
clearing 's' from 2
clearing 'd' from 1
clearing 'a' from 0
puttuing 's' at 0
do_comb_print(1):
puttuing 'a' at 1
do_comb_print(2):
puttuing 'd' at 2
do_comb_print(3):
sad
clearing 'd' from 2
clearing 'a' from 1
puttuing 'd' at 1
do_comb_print(2):
puttuing 'a' at 2
do_comb_print(3):
sda
clearing 'a' from 2
clearing 'd' from 1
clearing 's' from 0
puttuing 'd' at 0
do_comb_print(1):
puttuing 'a' at 1
do_comb_print(2):
puttuing 's' at 2
do_comb_print(3):
das
clearing 's' from 2
clearing 'a' from 1
puttuing 's' at 1
do_comb_print(2):
puttuing 'a' at 2
do_comb_print(3):
dsa
clearing 'a' from 2
clearing 's' from 1
clearing 'd' from 0 |
|
|
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 11 October 2007 בשעה 12:01 | | IP רשוּם
|
|
|
|
אגב, להדפסה עם דיבוג כמו עכשיו,
קוד:
#include <iostream>
#define DEBUGRECUR
using namespace std;
const int N = 3;
const char c[N] = {'a','s','d'};
int p[N];
bool o[N];
void do_comb_print(int i)
{
#ifdef DEBUGRECUR
for (int k = 0 ; k < i ; ++k)
cout << '\t';
cout << "do_comb_print(" << i << "):" << endl;
#endif
if (i == 0)
for (int j = 0 ; j < N ; ++j)
o[j] = false;
if (i == N){
for (int j = 0 ; j < N ; ++j)
cout << c[p[j]];
cout << endl;
return;
}
for (int j = 0 ; j < N ; ++j)
if (!o[j])
{
#ifdef DEBUGRECUR
for (int k = 0 ; k <= i ; ++k)
cout << '\t';
cout << "puttuing '" << c[j] << "' at " << i << endl;
#endif
o[j] = true;
p[I]=j;
do_comb_print(i+1);
#ifdef DEBUGRECUR
for (int k = 0 ; k <= i ; ++k)
cout << '\t';
cout << "clearing '" << c[j] << "' from " << i << endl;
#endif
o[j] = false;
}
}
int main()
{
do_comb_print(0);
return 0;
} |
|
|
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 11 October 2007 בשעה 15:49 | | IP רשוּם
|
|
|
|
תודה רבה על הזמן שלך ועל ההשקעה..
הצלחתי להבין סוף סוף ;]
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 11 October 2007 בשעה 16:15 | | IP רשוּם
|
|
|
|
NP ;)
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
