אלגוריתמים של STL

חלק מהיחידה תכנות מונחה עצמים במסלול ה-C++ של Coddy. שיעור 73 מתוך 104.

אלגוריתמי STL הם פונקציות תבנית שפועלות על טווחים המוגדרים באמצעות איטרטורים. הם נמצאים בכותרות <algorithm> ו־<numeric> ופועלים עם כל מכל שמספק איטרטורים תואמים.

std::sort מסדרת איברים בסדר עולה כברירת מחדל:

#include <algorithm>
#include <vector>

std::vector<int> nums = {5, 2, 8, 1};
std::sort(nums.begin(), nums.end());
// nums: {1, 2, 5, 8}

std::find מחפשת ערך ומחזירה איטרטור להתאמה הראשונה, או end() אם הערך לא נמצא:

auto it = std::find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    std::cout << "Found at index: " << (it - nums.begin());
}

std::transform מחילה פעולה על כל איבר ושומרת את התוצאות בטווח יעד:

std::vector<int> doubled(nums.size());
std::transform(nums.begin(), nums.end(), doubled.begin(),
               [](int x) { return x * 2; });
// doubled: {2, 4, 10, 16}

std::accumulate מתוך <numeric> משלבת את כל האיברים לערך יחיד:

#include <numeric>

int sum = std::accumulate(nums.begin(), nums.end(), 0);
// sum: 16 (1 + 2 + 5 + 8)

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

אתגר

קל

בואו נבנה מנתח ציונים שמעבד אוסף של מספרים באמצעות אלגוריתמי STL. תיצרו פונקציות עזר שידגימו כיצד sort, find, transform ו־accumulate פועלים יחד כדי לנתח נתונים.

תארגנו את הקוד בשני קבצים:

ScoreAnalyzer.h: הגדירו פונקציות עזר שמשתמשות באלגוריתמי STL כדי לעבד מערכים של מספרים שלמים.
צרו פונקציה בשם sortScores שמקבלת std::vector<int>& וממיינת אותו בסדר עולה באמצעות std::sort.

צרו פונקציה בשם findScore שמקבלת const std::vector<int>& וערך יעד מסוג int. השתמשו ב־std::find כדי לחפש את ערך היעד. אם הוא נמצא, החזירו את האינדקס (המרחק מתחילת המערך). אם הוא לא נמצא, החזירו -1.

צרו פונקציה בשם applyBonus שמקבלת const std::vector<int>& וכמות בונוס מסוג int. השתמשו ב־std::transform כדי ליצור ולהחזיר מערך חדש שבו הבונוס נוסף לכל ציון.

צרו פונקציה בשם calculateAverage שמקבלת const std::vector<int>& ומחזירה את הממוצע בתור double. השתמשו ב־std::accumulate כדי לחשב את הסכום, ואז חלקו בגודל המערך.

צרו פונקציה בשם printVector שמקבלת const std::vector<int>& ומדפיסה את כל האיברים כשהם מופרדים ברווחים, ולאחריהם ירידת שורה.
main.cpp: קראו שישה קלטים (כל אחד בשורה נפרדת):
1. הציון הראשון (מספר שלם)
2. הציון השני (מספר שלם)
3. הציון השלישי (מספר שלם)
4. הציון הרביעי (מספר שלם)
5. ציון לחיפוש (מספר שלם)
6. כמות בונוס להחלה (מספר שלם)
צרו מערך עם ארבעת הציונים והדגימו את האלגוריתמים:
1. הדפיסו Original: ולאחריו את תוכן המערך
2. מיינו את הציונים והדפיסו Sorted: ולאחריו את המערך הממוין
3. חפשו את ציון היעד במערך הממוין. אם הוא נמצא, הדפיסו Found <value> at index <index>. אם הוא לא נמצא, הדפיסו <value> not found
4. החילו את הבונוס על הציונים הממוינים והדפיסו With bonus: ולאחריו את המערך החדש
5. חשבו והדפיסו את הממוצע של הציונים המקוריים הממוינים (לפני הבונוס) בתור Average: <value> עם ספרה אחת אחרי הנקודה העשרונית

לדוגמה, עם הקלטים 75, 90, 60, 85, 85 ו־5:

Original: 75 90 60 85 
Sorted: 60 75 85 90 
Found 85 at index 2
With bonus: 65 80 90 95 
Average: 77.5

עם הקלטים 100, 80, 95, 70, 50 ו־10:

Original: 100 80 95 70 
Sorted: 70 80 95 100 
50 not found
With bonus: 80 90 105 110 
Average: 86.2

זכרו לכלול את <algorithm> עבור sort, find ו־transform, ואת <numeric> עבור accumulate. השתמשו ב־std::fixed וב־std::setprecision(1) מתוך <iomanip> לעיצוב הממוצע.

נסו בעצמכם

#include <iostream>
#include <vector>
#include <iomanip>
#include "ScoreAnalyzer.h"

using namespace std;

int main() {
    // קראו שישה ערכי קלט
    int score1, score2, score3, score4;
    int searchTarget, bonusAmount;
    
    cin >> score1;
    cin >> score2;
    cin >> score3;
    cin >> score4;
    cin >> searchTarget;
    cin >> bonusAmount;
    
    // TODO: צרו וקטור עם ארבעת הציונים
    
    // TODO: הדפיסו "Original:" ואחריו את תוכן הווקטור
    
    // TODO: מיינו את הציונים והדפיסו "Sorted:" ואחריו את הווקטור הממוין
    
    // TODO: חפשו את ציון היעד בווקטור הממוין
    // אם נמצא, הדפיסו "Found <value> at index <index>"
    // אם לא נמצא, הדפיסו "<value> not found"
    
    // TODO: הוסיפו את הבונוס לציונים הממוינים והדפיסו "With bonus:" ואחריו את הווקטור החדש
    
    // TODO: חשבו והדפיסו את ממוצע הציונים הממוינים (לפני הבונוס)
    // השתמשו ב-fixed וב-setprecision(1) לעיצוב הפלט
    // הדפיסו בפורמט "Average: <value>"
    
    return 0;
}