שפת C - רקורסיה - תרגילים וכללים

רקורסיה - שיטה לבנייה נכונה

פתרונות מהשיעור הקודם:

תשובה 1: (לא רשמי)

#include <stdio.h>
 
int  f1(int x,int y) {
 if (x<y||(x==y&&x%2==1))   // הפונקציה מחזירה את סכום המספרים הזוגיים בין שני מספרים כשהשמאלי גדול או שווה לימיני
  return 0;
 if (y%2==1) 
  y++;
 return 1 + f1(x, y+2);
 }
 
 void main() {
  int x,y;
  printf("Enter 2 numbers: ");
  scanf("%d %d",&x,&y);
  printf("Zugi: %d \n",f1(x,y));
 }

שיעורים Solaris - בעיות אופטימיזציה עם מספר נעלמים - השיטה הקצרה

בעיות אופטימיזציה עם מספר נעלמים - טבלה

משימות:

מבחנים חיצוניים משנים קודמות באלגברה לינארית

אלגברה לינארית - מבחנים חיצוניים מהשנים האחרונות (משרד החינוך) 

2016

2015

2014

2013

2012

סמל 714003

המבחנים הם מאתר משרד החינוך.

שפת C - רקורסיה

רקורסיה - recursion

רקורסיה הוא תהליך בו הפונקציה קוראת לעצמה.

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

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

לדוגמה נתבונן בפונקציה רקורסיבית שמחזירה סכום המספרים מ0 ועד למספר שהיא מקבלת.
עבור 5 הפונקציה תחזיר סכום: 1+2+3+4+5

#include<stdio.h>
 
int f(int n){
 if(n==0)
  return 0;
 return n+f(n-1);
}
 
void main(){
 int n;
 printf("Enter number: ");
 scanf("%d",&n);
 printf("%d\n",f(n));
 
}

שפת C - עבודה עם רשימות מקושרת שמכילות גם מצביעים לרשימות אחרות (יום ראשון)

עבודה מורכבת עם רשימות מקושרות

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

התרגיל היום זה ליצור פונקציה שיוצרת רשימה מקושרת של סטודנטים    ( ) CreateStudentList
ופונקציה שיוצרת רשימה מקושרת של קורסים    ( ) CreateCourseList

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

כל קורס מכיל את השדות הבאים:
שם הקורס
ממוצע ציונים (של כל הסטודנטים שלומדים בקורס)
מצביע לראש (= head) רשימה מקושרת של כל הסטודנטים שלומדים בקורס   (sh)
next לקורס הבא

תכנות מערכות בשפת C ושפת סף - במחנים אמיתיים (משרד החינוך)

תכנות מערכות בשפת C ושפת סף - מבחני משרד החינוך בשנים האחרונות

2016

2015

2014

2013

2012

סמל 714001

המבחנים הם מאתר משרד החינוך.

שפת C - רשימה מקושרת דו סטרית (יום רביעי)

רשימה דו סטרית

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

כפי שה next של האיבר האחרון מכיל NULL, גם ה back של האיבר הראשון מכיל NULL.

struct Item{

int info;       

      stuct Item *next, *back;    

};

משימות

1. לבנות פונקציה CreatList של רשימה דו סטרית.
2. לבנות פונקציה PrintList שמדפיסה הרשימה מהסוף להתחלה וגם מההתחלה לסוף (באותה הפונקציה).
3. לבנות פונקציה DelItem של רשימה דו סטרית.
4. לבנות פונקציה המקבלת שתי רשימות מקושרות דו סטריות ומספר שלם x.
     הפונקציה מכניסה הרשימה השניה לרשימה הראשונה אחרי ההופעה הראשונה
     של  x  ברשימה.
     אם אין איבר כזה , אז לא יבוצע כלום.
5. כתוב הפונקציה:

                                                                           struct Item* head  Del_Even (struct Item* head);

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

בעיות אופטימיזציה (תכנון לינארי)

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

תרגילים:

מבחן חוזר באסמבלי

מבחן חוזר באסמבלי (5.1.17)

1.

שפת C - עוד על רשימות מקושרות (יום רביעי)

עוד על רשימות מקושרות

נתחיל מהתכנית מהשיעור הקודם (+תוספות מהשיעור הזה):

#include <stdio.h>
#include <conio.h> // לפעמים יש צורך בספרייה הזאת, לא קשור לנושא השיעור
#include <stdlib.h>
struct Item {     // מגדירים את סוג איברי הרשימה
 int info;
 struct Item* next;
};
struct Item* CreateList() {     // יוצרים פונקציה שיוצרת רשימה ע"פ קלט מהמשתנה
 struct Item *head = NULL, *tail, *p;
 while( 1 ) {
  printf("Enter Esc to finish, any other key to continue\n");
  flushall();
  if(getch() == 27)       // (הפקודה חוקית מפני שזו פונקציה שמחזירה ערך)
   break;
 
  p = (struct Item*) malloc( sizeof(struct Item) );
  printf("Enter number: ");
  scanf("%d",&p->info);
  p->next = NULL;
 
  if(head == NULL)         // זה המקרה שקיבלו את האיבר הראשון
   head = tail = p;
  else {
   tail->next = p;   // האיבר שקודם היה האיבר האחרון מצביע עכשיו על האיבר החדש
   tail = p;
  }
 }
 return head;
}

שיעור SQL - שאלות (יום שלישי)

שאלות ב SQL

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

מקובצים לפי מספר עובד ומספר לקוח. (כמובן מטבלאות עובדים ולקוחות)

     2. הצג מטבלת הזמנות ועובדים שם עובד, מספר עובד ומספר הזמנות שהעובד עשה.

(GROUP BY)

שפת C - רשימות מקושרות (יום ראשון)

רשימות מקושרות Linked List

- הרשימה המקושרת היא מבנה (struct) לשמירת הרבה נתונים מאותו הסוג.
- איברי הרשימה לא שמורים ברצף בזיכרון.
- כל איבר מכיל 2 דברים:
                          1. שדה/שדות מידע
                          2. שדה קישור (מצביע) לכתובת של האיבר הבא


סוגי רשימות:
רשימה חד סטרית
רשימה דו סטרית
רשימה מעגלית

התחלה [head] >   [ מידע   |next] >   [ מידע   |next] >   [ מידע   |next] >   [ מידע   |NULL] סוף

head הוא מצביע לתחילת הרשימה.
הרשימה מסתיימת באיבר בו שדה המצביע הוא NULL.

שפת C - מבנים struct (יום ראשון)

מבנים - struct

- המבנה מיועד לשמירת הרבה נתונים מסוגים שונים.
- איברי המבנה (השדות) נשמרים ברצף בזכרון.

הגדרה כללית:

        struct Name{

        type1  n1;

        type2  n2;

              .

              .

              .

        };

מחרוזות בשפת אסמבלי (יום חמישי)

מחרוזות בשפת אסמבלי - UnderWarrior PDF

מטרת המסמך היא להציג את פקודות השפה המסייעות בפעולות על מחרוזות.

כאן

Show/Hide me

Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas.

Name:

שפת C - מצביע למצביע (יום רביעי)

מצביע למצביע

מצביע יכול להצביע למצביע אחר עם כוכבית אחת פחות משלו (וכן הלאה "מצביע למצביע למצביע" עוד כוכביות)

הגדרה:

type  **PName; 

שימוש:

int x = 13,*p,**q;  

p = &x;                    

q = &p;                    

הפקודה q = &x לא חוקית!

אם הכתובת של x היא 600 , של p היא 850 ושל q היא 900
אז נתבונן במצב אחרי הפקודות:

x = 13         &x = 600      *x

p = 600      &p = 850      *p = 13        **p

q = 850      &q = 900      *q = 600      **q = 13

הקצאת מטריצה דינאמית:

int n = 5(שורות), m = 4(עמודות), **A;

נעבור לתוכנית:

שפת C - פקודת realloc (יום ראשון)

פקודת realloc

מאמר מאת ויקיספר:

פונקציית שינוי-ההקצאה realloc

שינויי הקצאות אפשר לעשות בעזרת הפונקציה realloc, על ידי קריאות מהצורה הבאה:

realloc(<old_ptr>, <total_size>)

כאשר old_ptr היא כתובת הזיכרון המוקצאת הנוכחית, וtotal_size הוא הגודל החדש המבוקש (בבתים).

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

שפת C - הקצאת זיכרון דינאמי (יום רביעי)

הקצאת זיכרון דינאמי

נדגים מה הצורך בזיכרון דינאמי:

void main(){   

int n;               

scanf(%d,&n);

int A[n];         

הפקודה האחרונה לא חוקית!

למה?

* אסור שגודל מערך יהיה משתנה.

*אסור להגדיר משתנים אחרי שכבר כתבנו פקודות בתוכנית.

לכן יש שימוש בהקצאת זיכרון דינאמית!

- הקצאת זיכרון דינאמית היא האפשרות לייצר זיכרון (להקצות) במהלך ביצוע התוכנית.
- יש לעשות שימוש בספרייה  <stdlib.h>

אנחנו נשתמש בפקודות הבאות:

malloc - לבצע הקצאה חדשה
calloc  - לבצע הקצאה חדשה + לאפס אותה
realloc - להגדיל/להקטין זיכרון דינאמי
free     -  לשחרר זיכרון דינאמי

תירגול מצביע למערך

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

אם כן: הדפס את כל האיברים במערך שנמצאים אחרי המצביע (כולל המצביע).
אם לא: הדפס "NO".







פתרון אפשרי:

שפת C - עוד על מצביעים (יום רביעי וראשון)

עוד על מצביעים:

- שם מערך הוא למעשה גם מצביע, שמצביע על הבית הראשון של האיבר הראשון במערך.

- כדי להצביע על מערך אפשר לעשות בפשטות (כש p הוא מצביע):

p = &A[0];  

  אבל אפשר לעשות גם:

.שכן שניהם מצביעים, ואפשר להשוות שני מצביעים-         p = A;  

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

  לדוגמה:

  אם p הוא מצביע מסוג int שמצביע על האיבר הראשון של המערך A

*p = 13;          =>      A[0] = 13

p++;               =>      p = 1004

*p = 27;          =>      A[1] = 27

p+=2;             =>      p = 1012

*p = 20;          =>      A[3] = 20

צילום מבחן באסמבלי (יום חמישי)

צילום מבחן באסמבלי

1