תרגילים ללימוד בשפת C

חיפוש לעומק

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

רמה קלה

תרגיל 1

כתוב פונקציה רקורסיבית המקבלת מערך, את גודלו ומספר נוסף k.

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

תרגיל 2

כתוב תוכנית הפותרת את בעית 8 המלכות, כפי שהיא מוגדרת להלן:

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

כתוב תוכנית הפותרת את המקרה הכללי יותר: לוח בגודל NxN, בו צריך למקם N מלכות. (N קבוע).

רמה בינונית

תרגיל 1

נתונה הפונקציה f1 המקבלת מערך של מספרים טבעיים שונים a, מערך עזר b אשר כולו מאותחל לאפסים, lena, lenb – הגדלים של המערכים a, b ובנוסף מקבלת הפונקציה שני פרמטרים x ו-k כך שמתקיים .

כתוב את הפונקציה f1 כך שאם קיימים k איברים שונים ב-a שסכומם הוא x, הפונקציה תדפיס את k האינדקסים של האיברים האלו. אחרת לא יודפס דבר. הפונקציה אמורה להדפיס את כל הפתרונות החוקיים לבעיה – כלומר את כל הקבוצות בעלות k האיברים השונים שסכומם הוא x.

דוגמא: עבור הקלט int a[] = { 5, 12, 1, 4, 7 } והערכים x=12, k=2 יודפס: 0, 4.