00
עדכונים

מנוי במייל

קבלת עדכונים על רשומות חדשות ישירות לתיבת האמייל
יש להזין אימייל תקין על מנת להרשם לעדכונים
ברגעים אלו נשלח אליך אימייל לאישור/ביטול ההרשמה
*שים/י לב, מרגע עשית מנוי, כותב/ת הבלוג יוכל לראות את כתובת האמייל שלך ברשימת העוקבים.
X

{ [ ( בניית עזר ) ] } - מתמטיקה, תכנות, סיכומים לבחינות הבגרות ואקסל

<<<<
 
   מתמטיקה 
   ונושאים 
   נוספים 
 
משפטים, נוסחאות ומתמטיקאים על ציר הזמן  תורת המספרים  תכנות C++/C  קומבינטוריקה  מתמטיקה/EXCEL  אסטרונומיה

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

שפת ++C תרגילים ופתרונות - פונקציות רקורסיביות - בעיית תרמיל הגב בשלמים

התכנית בשפת ++C מממשת את האלגוריתם הפותר את בעיית תרמיל
הגב בשלמים
באמצעות רקורסיה.

הנתונים:

תרמיל גב מסוגל לעמוד בעומס של M ק"ג.
ברשותנו X חפצים שאנו מעוניינים לארוז בתוך התיק. לכל חפץ משקל משלו.

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

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

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

1. אם המשקל שהצטבר עד כה הוא בדיוק כמשקל התרמיל, אזי סיימנו את המשימה
    ולא נותר עוד מקום בתרמיל (total=0).
2. אם חרגנו מהמשקל המותר, מורידים מהתרמיל את החפץ האחרון שהוכנס וגרם לחריגה.
    כך חוזרים צעד אחד אחורה למצב בו היה המשקל תקין ועדיין לא חרג מהגבולות.
    כעת מדלגים על החפץ הנ"ל ומנסים לבדוק האם הכנסתו של החפץ הבא אחריו בתור
    לא תגרום לחריגה (מדלגים על התא הנוכחי במערך ועוברים לתא הבא).
3. כל עוד לא מלאנו את התרמיל, לא חרגנו ממשקלו ועדיין נשארו במערך חפצים שאפשר
    לאגור, אנו ממשיכים לצבור חפצים (להתקדם לימין המערך).
    איננו לוקחים בחשבון את התנאים שכבר דילגנו עלינם, אלא אם כן מחליטים להתחיל
    מחדש באגירת החפצים ממקום x+1 לאחר שהגענו למסקנה כי אין צירף הולם
    שיכול להצטבר מהמקום x במערך ולמלא את התרמיל.


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

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

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

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


 note 4
אנו מגיעים לביצוע שורה זו ברגע שמתברר כי אל הצלחנו לאגור חפצים כמשקלו המדוייק של התרמיל.
לכן עכשיו נקרא שוב  ל-knap ונאפס את המשקל המצטבר. למעשה, אנו חוזרים לתחילת הדרך
והפרמטר total מקבל את ערכו ההתחלתי כפי שנקבע כאשר הפונקציה knap נקראה בפעם
הראשונה מהתכנית הראשית. אבל הפעם נתחיל לסרוק את המערך מהתא x+1 משום שלפי
תוצאות הקריאה הקודמת, ייתכן שמשקל החפץ בתא x הוא הגורם המפריע
למציאת הקומבינציה המדוייקת.

 

 

 

//description:
//- - - - - - -
//this program determines whether we can create a combination of objects, each of them has is own weight,
//in order to put all the objects, or some of them in a knapsack, by utilizing its load ability accurately.

//- -include and define statements- -
#include <conio.h>
#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>

const int N=5;           //size of array, means number of the given objects.
const int M=16;          //the load ability og the knapsack.

//- -function declartions- - - - - - - - - - -

int  knap(int vec[N],int total,int start,int end);
void init_vec(int vec[N]);

//- -function bodies- - - - - - - - - - -

//function which initialize the vec with user`s input numbers.
void init_vec(int vec[N])
{
    int i;

    cout<<"enter "<<N<<" positive integers: ";

    for (i=0;i<N;i++)
     cin>>vec[i];
}//end of function.



//a recursive function which determines whether we can create a combination of N objects,or some of them,
//each of them has is own weight,in order to put them in a knapsack, by utilizing its load ability accurately.

//parameters: array of objects.
//            the total weight which has been exploited till now.
//            the array`s cell to start the check.
//          the array`s cell to end the check (always the last cell in the array.

//halting conditions : if (total=0)  , we have exploited the ability load accurately, and return TRUE.
//               if (total<0)  , we have digressed the ability load and return FALSE.
//               if (start>end), we have finished scanning the array without finding a solution and return FALSE.


int knap(int vec[N],int total,int start,int end)
{
  if (total==0)                                                                  // note 1                                                           
      return 1;
  if ((total<0) || (start>end))                                             // note 2
      return 0;
  if (knap(vec,total-vec[start],start+1,end))                        // note 3
     //if we have not digressed the load and still in the array borders
     //we continue finding another objects to exploit the knapsack`s load accurately.
     {
      cout<<vec[start]<<" ";                    // note 4 printing recursivly the appropiate objects to be taken to the knapsack.
      return 1;
     }
  return (knap(vec,total,start+1,end)); //this statement is performed when we are in the problem`s borders,namely
                    //we have not digressed the load ability and not reached the array end or
                    //we have digressed the load ability and now we will skip the last cell which cause
                    //the digress and go to the next cell and so on till the array end or till we find solution.
}//end of function








//- -main program- - - - - - - - - - -
void main()
{
 //- -variables- - - - - - - -

  int vec[N];              //array with N cells to store each object`s weight

 //- body and algorithm- - - - - - - - - -

  clrscr();

  init_vec(vec);

  //first calling to "knap" funcrion with the parameters: a given vector,the load ability of the knapsack,
  //the first cell of the array in order to start checking and the last parameter is the last array`s cell,
  //which is remained the same in all the recursive calls.

  if(knap(vec,M,0,N-1))
      cout<<" . this is the solution for load ability "<<M<<"."<<endl;
  else
      cout<<"no solution for the fiven objects and load ability "<<M<<endl;;
  getch();

}//end of main
 

אין לקדם פוסט זה

הוספת תגובה

נשארו 150 תוים
נשארו 1500 תוים

תגובה אחת

© כל הזכויות לתוכן המופיע בדף זה שייכות ל ExcelMath91 אלא אם צויין אחרת