ושוב, בעיה עם רקורסיה. כרגיל, אודה לעוזרים :)

[anatoli]

אז הפעם התרגיל הוא ביצוע של merge sort בעזרת רקורסיות בלבד, אסור שום לולאות.

כתבתי את הפונקציות הבאות:

void mizugmiun (int source[],int target[],int start,int end){

int center,left[size/2],right[size/2];

center=(start+end)/2;

if (start==end){

target[0]= source[0];

return;

}

mizugmiun (source,left,start,center);

mizugmiun (source,right,center+1,end);

mizug (left,right,target,center+1-start,end-center,0,0);

}

void mizug (int a[],int b[],int target[],int end1,int end2,int place1,int place2){

if (place1==end1)

mizugsof(b,target,place1-1,place2,end2);

if (place2==end2)

mizugsof(a,target,place2-1,place1,end1);

if (a[place1]>b[place2]){

target[place1+place2]=b[place2];

mizug (a,b,target,place1,place2+1,end1,end2);

}

else{

target[place1+place2]=a[place1];

mizug (a,b,target,place1+1,place2,end1,end2);

}

}

void mizugsof (int source[],int target[],int start,int place,int end){

if (start==end)

return ;

else{

target[place]=source[start+place];

mizugsof (source,target,start,place+1,end);

}

}

לצערי, זה לא עובד. סך הכל זה רושם לי press any key to continue במקום להמשיך בתוכנה.

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

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

תודה,

Anatoli.

[exercise]

http://ds4beginners.wordpress.com/2007/01/12/merge-sort-algorithm-using-recursion/

[Boomerang]

תגיד, איך נראה ה- main שלך?

[anatoli]

printf ("Enter Array Size:");

scanf ("%d",&n);

input(arr,n,0);

mergesort (arr,target,0,n-1);

arrprint (target,0,n);

כאשרinput היא פונקציה שקולטת את המספרים למערך, arrprint היא פונקציה שמדפיסה אותם.

Anatoli.

[ofir_yair]

בפונקציה mizugim לא הבנתי איפה הגדרת את המשתנה size (או שמא זה מוגדר כקבוע? מה שלא הגיוני עבור הפונקציה הרקורסיבית הזאת) ואיפה הקריאה לפונקציה הזאת ב-main? (או ששינית את השם ל-mergesort?).

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

[anatoli]

שלום,

זו ה,תוכנה כולה:

#include <stdio.h>

#include <string.h>

void input (int [],int ,int);

void spaceprint (int [],int ,int);

void mergesort (int [],int [],int ,int );

void merge (int [],int [],int [],int ,int ,int ,int );

void main (){

int n,arr[100],sorted[100];

while (1){

printf ("Enter Number: ");

scanf ("%d",&n);

input (arr,n,0);

mergesort (arr,sorted,0,n-1);

spaceprint (sorted,0,n);

}

}

void input (int arr[],int n,int place){

if (place==n)

return;

else{

printf ("arr[%d]:",place);

scanf ("%d",&arr[place]);

input (arr,n,place+1);

}

}

void spaceprint (int arr[],int j,int i){

if (i==j){

printf ("\n");

return ;

}

printf ("%d ",arr);

spaceprint (arr,j,i+1);

}

void mergesort (int arr[],int sorted[],int start,int end){

int center, left[50], right[50];

if (start==end){

sorted[0]=arr[start];

return ;

}

else{

center=(start+end)/2;

mergesort(arr,left,start,center);

mergesort(arr,right,center+1,end);

merge (left,right,sorted,center-start+1,end-center,0,0);

}

}

void merge (int left[],int right[],int target[],int leftend,int rightend,int placea,int placeb){

if (placea==leftend){

if (placeb<rightend){

target[placea-1+placeb]=right[placeb];

merge (left,right,target,leftend,rightend,placea,placeb+1);

}

if (placeb==rightend)

return ;

}

if (placeb==rightend){

if (placea<leftend){

target[placeb-1+placea]=left[placea];

merge (left,right,target,leftend,rightend,placea+1,placeb);

}

if (placea==leftend)

return ;

}

if (left[placea]<right[placeb]){

target[placea+placeb]=left[placea];

merge (left,right,target,leftend,rightend,placea+1,placeb);

}

else{

target[placeb+placea]=right[placeb];

merge (left,right,target,leftend,rightend,placea,placeb+1);

}

}

תודה,

Anatoli.[br]פורסם בתאריך: 20.12.2007 בשעה 22:55:30ד"א, עליתי על זה שהטעות נמצאת איפשהו במערכת ה-merge ולא mergesort. אני בינתיים לא הצלחתי למצוא אותה.

Anatoli.[br]פורסם בתאריך: 20.12.2007 בשעה 23:03:00עריכה, מצאתי את הטעות.

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

Anatoli.

[שניצל]

לא הבנתי, התכנית עובדת עכשיו או לא?

(אגב, ה-main צריכה להחזיר int)

[anatoli]

עובדת כמו מלכה

ד"א, למה היא צריכה להחזיר 1? עד עכשיו מעולם לא נדרשתי לכתוב main שמחזירה משהו. מה גם, פה ה-main הוא לא מהתוכנה האמיתית, זה מתוכנית חדשה שפתחתי רק כדי לעשות את הרקורסיה הזו (סעיף אחד מתוך שמונה).

Anatoli.

[שניצל]

לא אמרתי שהיא צריכה להחזיר 1, היא צריכה להחזיר int.

היא בכלל צריכה להחזיר 0.

כל תהליך שרץ במערכת ההפעלה צריך להחזיר מספר שמציין את ה-error code של התכנית. 0 אומר הצלחה, כל מספר אחר אומר כשלון (כשהמשמעות של המספרים נקבעות באופן שרירותי ע"י המתכנת, הוא רק צריך לדאוג לתעד אותם).

לפני שהיה תקן מסודר ל-C, היו קומפיילרים שאפשרו ל-main לא להחזיר ערך, ובעצם דאגו שהיא תמיד תחזיר 0.

התקן הנוכחי של C קובע שה-main חייבת להחזיר int, וקומפיילרים חדשים לא יאפשרו לך לעשות אחרת.

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

[anatoli]

אז כנראה שאני לומד לפני התקן החדש. עד עכשיו כבר הגשנו 3 עבודות, ובאף אחת מהן לא ראיתי מישהו ששם ערך שהפונקציה מחזירה. לאף אחד לא העירו על כך. גם לא ראיתי בשום דוגמא של המתרגלים החזרה של int כלשהו מה-main. אני מניח שזה לא רלוונטי כל כך כרגע (לפחות כיוון שאנחנו לא מכינים exe אלא שולחים את הקוד אשר נבדק בעזרת בדיקה אוטומטית בעיקרון).

ד"א, הקומפיילר הוא ה-visual c++ 2005.

Anatoli.

[eli33]

כי visual c++ 2005 הוא קומפיילר של c++ שגם אם תיצור קובץ עם סיומת c (ולא cpp ) יתן לך קצת מעבר ליכולות של השפה האמיתית לפי ANSI-C.

דוגמא אחת לפי תקן ה ANSI-C הפונציה main חייבת להחזיר ערך int.

עוד דוגמא בשפת C לפי התקן אתה יכול לרשום הערות לקוד רק עם /**/ בניגוד למה שהקומפיילר visual c++ 2005 נותן לך לרשום הערות רק עם // (אפשרות שנוספה ב c++)

תשאל אותי למה זה חשוב.

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

[דנדן]

עוד דוגמא בשפת C לפי התקן אתה יכול לרשום הערות לקוד רק עם /**/ בניגוד למה שהקומפיילר visual c++ 2005 נותן לך לרשום הערות רק עם // (אפשרות שנוספה ב c++)

לפי זכרוני בTURBO C שהייתי כותב שם פעם, היה אפשר לכתוב הערות על //...

ושם לא היינו מחזירים INT לMAIN, כמו שאני ואנטולי לא עושים עכשיו...

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

[anatoli]

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

Anatoli.

[exercise]

גם Visual Studio וגם GCC (במצב C) הכי חדשים שהם הקומפיילרים הכי פופלרים, לא מחייבים להגדיר את main כמחזיר int.

[Zelig]

ולמרות הכל, זה התקן וככה צריך לכתוב.

אם תקמפל ב-gcc עם -Wall הוא גם יזהיר על זה, לדעתי. יתכן שגם VS2005 יזהיר על זה עם תקנפג אותו להפעיל את כל האזהרות.