work4/work_4.2/task5.cpp - develop - novd7/algirithms_sem2

work4/work_4.2/task5.cpp
93 строки3 KB
Новиков Владимир
Рабочая тетрадь 4.2
30 май 2026, 14:10
30 май 2026, 14:100a353cb
#include <array>
#include <iostream>
#include <unordered_map>
#include <vector>

class StudentGradeSystem {
 private:
  std::unordered_map<int, int> studentGrades;
  std::array<int, 4> gradeCount;

 public:
  StudentGradeSystem() { gradeCount.fill(0); }

  void addRecord(int studentId, int grade) {
    if (grade < 2 || grade > 5) {
      throw std::invalid_argument("Grade must be between 2 and 5");
    }

    auto it = studentGrades.find(studentId);
    if (it != studentGrades.end()) {
      int oldGrade = it->second;
      gradeCount[oldGrade - 2]--;
    }

    studentGrades[studentId] = grade;
    gradeCount[grade - 2]++;
  }

  int getStudentGrade(int studentId) {
    auto it = studentGrades.find(studentId);
    if (it == studentGrades.end()) {
      throw std::runtime_error("Student not found");
    }
    return it->second;
  }

  int countStudentsWithGrade(int grade) {
    if (grade < 2 || grade > 5) {
      throw std::invalid_argument("Grade must be between 2 and 5");
    }
    return gradeCount[grade - 2];
  }

  size_t getMemoryUsage() const {
    return studentGrades.size() * (sizeof(int) * 2 + sizeof(void*)) +
           sizeof(gradeCount);
  }

  size_t getStudentCount() const { return studentGrades.size(); }
};

int main() {
  StudentGradeSystem system;

  system.addRecord(1001, 5);
  system.addRecord(1002, 4);
  system.addRecord(1003, 5);
  system.addRecord(1004, 3);
  system.addRecord(1005, 5);

  std::cout << "Оценка студента 1003: " << system.getStudentGrade(1003)
            << std::endl;
  std::cout << "Количество студентов с оценкой 5: "
            << system.countStudentsWithGrade(5) << std::endl;
  std::cout << "Количество студентов: " << system.getStudentCount()
            << std::endl;
  std::cout << "Приблизительный объем памяти: " << system.getMemoryUsage()
            << " байт" << std::endl;

  std::cout << "\nАнализ решений" << std::endl;
  std::cout << "Вариант 1 (Хеш-таблица + массив счетчиков):" << std::endl;
  std::cout << "  - Поиск по ID: O(1) в среднем" << std::endl;
  std::cout << "  - Подсчет по оценкам: O(1)" << std::endl;
  std::cout << "  - Память: O(N) с накладными расходами на хеш-таблицу"
            << std::endl;

  std::cout << "\nВариант 2 (Массив для всех студентов):" << std::endl;
  std::cout << "  - Поиск по ID: O(1)" << std::endl;
  std::cout << "  - Подсчет по оценкам: O(N) при каждом запросе" << std::endl;
  std::cout
      << "  - Память: O(maxId), может быть неэффективно при разреженных ID"
      << std::endl;

  std::cout << "\nОптимальное решение: Хеш-таблица + массив счетчиков"
            << std::endl;
  std::cout << "Trade-off: дополнительные накладные расходы на хеш-таблицу"
            << std::endl;
  std::cout << "против быстрого доступа и обновления." << std::endl;
  std::cout << "Для 10 миллионов записей потребуется около 160-240 МБ памяти."
            << std::endl;

  return 0;
}