חיפוש

עזרה

הרשמה

התחברות

עדכונים

תיכנות
UnderWarrior Forums : תיכנות

נושא: מיון מערך ברקורסיה

כותב

הודעה

<< נושא קודם | נושא הבא >>

אמנון
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 18 December 2007 בשעה 14:07

| IP רשוּם

מישהו יכול לעזור לי בבקשה עם השאלה הבאה:

נרצה למיין מערך בעזרת מיון מיזוג בשיטה רקורסיבית.

נגדיר את המיון בצורה הבאה:

עבור מערך נתון (להלן source) ומערך יעד שלאליו תכתב התוצאה (להלן target):

נגדיר 2 מערכים A ו B.

נחלק את המערך המקורי לשני חלקים. את חציו השמאלי של source נמיין באופן רקורסיבי לתוך A, את חציו הימני של source נמיין לתוך B.

לאחר מכן נבצע מיזוג של שני החלקים הממוינים A ו B לתוך מערך היעד target.

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

דוגמא:

אם המערך מוגדר להיות

int source[10] = {2,9,11,4,1,20,3,7,5,6}

בשלב הראשון נצטרך למיין שני חלקים החלק הראשון יכלול את {{2,9,11,4,1 A =
והשני יהיה {B={20,3,7,5,6. כל מערך כזה ימוין שוב באופן רקורסיבי באותה שיטה.

לאחר המיון A={1,2,4,9,11} ו B={3,5,6,7,20} ולאחר המיזוג

target = {1,2,3,5,6,7,9,11,20}. שימו לב שעליכם לכתוב פונקציה רקורסיבית נוספת שממזגת שני מערכים.

התוכנית תדפיס למסך

1 2 3 4 5 6 7 9 11 20

ועוד הסבר קצר שהביאו לנו כי זה לא הכי מובן:

צריך למיין בצורה רקורסיבית מערך:

· מתבצעת חלוקה של המערך הנוכחי לשני חלקים.

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

· תנאי העצירה יקבע על ידכם.

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

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

תודה מראש.

חזרה לתחילת העמוד

אמנון
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 18 December 2007 בשעה 22:41

| IP רשוּם

מישהו יכול בבקשה לתת לי רעיון איך לעשות את הדבר הזה?

תודה מראש.
אמנון.

חזרה לתחילת העמוד

11010010110
פורומיסט על

הצטרף / הצטרפה: 23 April 2006
משתמש: מנותק/ת
הודעות: 2621

נשלח בתאריך: 19 December 2007 בשעה 00:16

| IP רשוּם

נתנו לך כבר לא ?

תיצור פונקציה שתחלק את המערך ל 2 חלקים ותקרא לעצמה 2
פעמים (לכל חלק)

האיטראציה הבאה תתנהג באותה צורה

וכך אתה בונה עץ

כשהגעת למערכים באורך 1 העץ מסתיים

בדרך חזרה אתה משלב את המערכים כ שיהיו ממוינים

המיון הראשוני מתחיל בקצוות של העץ כי מערך בגודל 1 הוא
כיאלו ממויין

חזרה לתחילת העמוד

אמנון
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 19 December 2007 בשעה 07:09

| IP רשוּם

נגיד יש לי מערך של 8, אני מתחיל לפרק אותו ל4 ואחרי זה ל2 ולבסוף מגיע ל1, עכשיו בדרך חזרה יש לי קודם כל מערך בגודל 1 ואחרי זה יש לי מערך בגודל 2 ואחרי זה 4, איך אני יכול למיין את זה בהופכי כאילו, זה לא שיש לי משתנים שאני בסך הכל משווה וממיין, יש פה מערכים של חצאים.
אתה מבין למה אני מתכוון (אני מקווה מאוד, כי אני בקושי מבין)?
ועוד משהו, כדאי לשלוח את A B לפונקציה או להגדיר את המערכים האלו בפנים?

תודה מראש.
אמנון.

חזרה לתחילת העמוד

שימי
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 19 December 2007 בשעה 09:24

| IP רשוּם

יש לי בעיה עם המיזוג...
מישהו יודע איפה אפשר למצוא באינטרנט קוד mergesort בC ברקורסיה ובלי לולאות...?

תודה מראש.

חזרה לתחילת העמוד

צחי@
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 19 December 2007 בשעה 09:59

| IP רשוּם

כן, ב-google.

חזרה לתחילת העמוד

צחי@
משתמש חבר

הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209

נשלח בתאריך: 19 December 2007 בשעה 10:02

| IP רשוּם

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

חזרה לתחילת העמוד

שימי
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 19 December 2007 בשעה 19:16

| IP רשוּם

לצערי זה ככה, בראש העבודה רשום שאסור להשתמש בלולאות בכלל...

חזרה לתחילת העמוד

שימי
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 19 December 2007 בשעה 23:31

| IP רשוּם

מישהו יודע איך ליישם את מה ש11010010110 ויכול לעזור לי עם זה?

חזרה לתחילת העמוד

שימי
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 19 December 2007 בשעה 23:32

| IP רשוּם

מישהו יודע איך ליישם את מה ש11010010110 כתב למעלה ויכול לעזור לי עם זה?

חזרה לתחילת העמוד

שימי
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 20 December 2007 בשעה 09:33

| IP רשוּם

מישהו יכול לאשר לי שהתוכנית הזאת בסדר:

קוד:

#include <stdlib.h>
#include <stdio.h>

#define MAX 10

void SplitArray(int source[], int temp[], int left, int right);
void Merge(int source[], int temp[], int left, int middle, int right,
           int left1, int temp1, int n1, int i);



int main()
{
  int i;
  int source[MAX];
  int temp[MAX];

  srand(getpid());

  for (i = 0; i < MAX; i++)
    source = rand();

  SplitArray(source, temp, 0, MAX - 1);

  printf("Done with sort.\n");

  for (i = 0; i < MAX; i++)
    printf("%i\n", source);
}

void SplitArray(int source[], int temp[], int left, int right)
{
  int middle, left1, n1, temp1;

  if (right > left)
  {
    middle = (right + left) / 2;
    SplitArray(source, temp, left, middle);
    SplitArray(source, temp, middle+1, right);

    middle += 1;
    left1 = middle - 1;
    temp1 = left;
    n1 = right - left + 1;

    Merge(source, temp, left, middle, right, left1, temp1, n1, 0);
  }
}


void Merge(int source[], int temp[], int left, int middle, int right,
           int left1, int temp1, int n1, int i){
    if ((left <= left1) && (middle <= right))
  {
    if (source[left] <= source[middle])
    {
      temp[temp1] = source[left];
      Merge(source, temp, left + 1, middle, right, left1, temp1 + 1, n1, 0);
      return;
    }
    else
    {
      temp[temp1] = source[middle];
      Merge(source, temp, left, middle + 1, right, left1, temp1 + 1, n1, 0);
      return;
    }
  }

  if (left <= left1)
  {
    temp[temp1] = source[left];
    Merge(source, temp, left + 1, middle, right, left1, temp1 + 1, n1, 0);
    return;
  }
  if (middle <= right)
  {
    temp[temp1] = source[middle];
    Merge(source, temp, left, middle + 1, right, left1, temp1 + 1, n1, 0);
    return;
  }

  if (i <= n1)
  {
    source[right] = temp[right];
    Merge(source, temp, left, middle, right - 1, left1, temp1, n1, i + 1);
    return;
  }
}

חזרה לתחילת העמוד

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

גרסת הדפסה

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