22 не пригодившихся задачи за начало 2018 года

Весьма и бесплатно занят, почти нет времени на бложеки и жизнь. Но "не пригодившихся" задач что-то давно не было, так что выберу время скинуть накопившиеся учебные программки за начало года.

Задачи, как обычно, очень разные - от совсем простых до более-менее интересных. Все программы проверены в консоли Visual Studio 2015 и написаны на C++.

1. Дано трёхзначное число. Используя одну операцию деления нацело, вывести первую цифру данного числа (количество сотен).

#include <iostream>
 
int main () {
    int n = 345;
    std::cout << n/100;
    system("pause>nul"); return 0;
}

2. Для заданного целого числа n вычислить сумму ряда

сумма ряда

#include <iostream>
 
int main () {
    int n = 10;
    double s = 0;
    for (int i=1; i<n; i++) s+=100./(i*i)+3*i;
    std::cout << s;
    system("pause>nul"); return 0;
}

3. Найти произведение элементов ряда по заданной формуле:

#include <iostream>
 
int main () {
    int n = 10;
    double p = 1;
    for (int i=1; i<=n; i++) p *= 1-1/(2.*i);
    std::cout << p;
    system("pause>nul"); return 0;
}

4. Птицы летят клином: в 1-м ряду —1 птица, во 2-м ряду — 3 птицы, в 3-м ряду — 5 птиц и т.д. Сколько птиц летит в 11 ряду? Сколько всего птиц летит в 11 рядах?

#include <iostream>
 
int main () {
    int all = 0;
    for (int n=1; n<=11; n++) all += 2*n-1;
    std::cout << "11 column=" << 2*11-1 << std::endl << "All=" << all;
    system("pause>nul"); return 0;
}

Ну или просто без цикла:

#include <iostream>

int main()
{
 constexpr int N = 11, an = 2 * N - 1;
 std::cout << an << " " << (1 + an) * N / 2 << std::endl;
 system("pause>nul"); return 0;
}

Ответы - 21 и 121 птица

5. Дано количество покупателей n, количество касс m и массив T, i-ый элемент которого равен количеству минут, за которое i-ая касса обслуживает одного покупателя.

В предположении, что любой покупатель занимает любую свободную кассу, найти минимальное количество времени, за которые можно обслужить всех покупателей.

Думаю, цепи Маркова тут ни к чему, достаточно минимума и максимума.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
int minNumber(int T[], int Tbusy[], int m) { 
 //Номер минимальной по времени обслуживания не занятой кассы
 int mNumber = -1, min = INT_MAX;
 for (int i = 0; i < m; i++) {
  if (Tbusy[i] == 0 && T[i] < min) {
   min = T[i]; mNumber = i;
  }
 }
 return mNumber;
}
 
int maximum(int T[], int m) { //Максимум в массиве
 int max = T[0];
 for (int i = 0; i < m; i++) if (T[i]>max) max = T[i];
 return max;
}
 
int main() {
 int n = 100; //клиентов
 const int m = 8; //касс
 int T[m] = {3,3,2,2,3,4,1,1}; //время обслуживания каждой из касс
 int Tbusy[m] = { 0,0,0,0,0,0,0,0 }; //состояние "свободно-занято" для касс
 int time = 0;
 if (n <= m) time = maximum(T, m);
  //Если клиентов не больше, чем касс - просто берем самое долгое время обслуживания
 else {
  while (n) {
   int number;
   do {
    number = minNumber(T, Tbusy, m);
    if (number != -1) {
     Tbusy[number] = T[number]; n--;
    }
   } while (number != -1 && n > 0); //Пока не все обслужены и есть свободные кассы
   time++; //прошла минута
   
   if (n == 0) {
    time += maximum(Tbusy, m); //добавить время, пока с последней кассы не уйдет последний клиент
    break;
   }
   
   cout << endl << "Time=" << time << ", state=";
   for (int i = 0; i < m; i++) cout << Tbusy[i] << " ";
   
   for (int i = 0; i < m; i++) { //изменить текущее время обслуживания занятых касс
    if (Tbusy[i] > 0) Tbusy[i]--;
   }
  }
 }
 cout << endl << "Total time=" << time;
 cin.sync(); cin.get(); return 0;
}

6. Создать шаблон функции для сортировки числового массива и проверить его на 2 различных типах данных.

#include <iostream>
using namespace std;
 
template <typename T> void swp(T &a, T &b) {
 T c = a; a = b; b = c;
}
 
template <typename T> void sort(T v[], int n) {
 for (int i = 0; i < n - 1; i++)
  for (int j = i + 1; j < n; j++)
   if (v[i]>v[j]) swp(v[i], v[j]);
}
 
template <typename T> void print(T v[], int n) {
 cout << endl;
 for (int i = 0; i < n; i++) cout << v[i] << " ";
}
 
int main() {
 int a[] = { 5,3,4,2,1 };
 sort(a,5); print(a,5);
 double b[] = { 35.12,-3,-14.7,8.9 };
 sort(b, 4); print(b, 4);
 cin.sync(); cin.get(); return 0;
}

7. Задан вектор a из элементов <pair<int, int>>. Удалить все повторяющиеся по первому полю пары значений.

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

using IntPair = pair<int, int>;

void cleanDuplicates (vector <IntPair> &vec) {
 unordered_set <int> distinct;
 auto it = remove_if (begin(vec), end(vec), [&distinct](const IntPair& p) {
  return !distinct.insert(p.first).second;
 });
 vec.erase(it, end(vec));
}

int main() {
 vector <pair<int, int>> a;
 a.push_back(make_pair(1, 2));
 a.push_back(make_pair(2, 1));
 a.push_back(make_pair(2, 2));
 a.push_back(make_pair(1, 3));
 a.push_back(make_pair(3, 3));
 cleanDuplicates (a);
 
 //вывод вектора из элементов <pair<int, int>> (С++11)
 for (const auto& p : a) { 
  cout << p.first << ", " << p.second << endl;
 }
 
 system("pause >nul"); return 0;
}

8. Имеется класс Apple, описывающий яблоко и класс applesArray, описывающий массив яблок.

В классе Apple предусмотреть методы, определяющие, упало ли яблоко и съедание определённой в процентах части яблока, свойства - цвет яблока, статус (упало с дерева или нет), доля съеденного. Когда яблоко съедено, оно удаляется из массива яблок.

Примечательно в коде - как передавать перечисление enum в качестве аргумента конструктора класса.

Если оператор [] обращается к недопустимому номеру яблока, возвращается новое "пустое" яблоко.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Apple {
public:
 enum statuses { EMPTY, HANGING, FALLING };
private:
 string color;
 statuses status;
 int eated;
 int min (int a,int b) { return (a<b ? a : b); }
 string getStatus() {
  string statusStr[] = {"EMPTY","HANGING","FALLING"};
  return statusStr[this->status];
 }
public:
 void fall() { this->status = FALLING; }
 int eat(int ps = 0) {
  if (this->status == FALLING) this->eated += min(100 - this->eated, ps);
  return 100 - this->eated;
 }
 Apple::Apple(string color, Apple::statuses status=HANGING) {
  this->color = color;
  this->status = status;
  this->eated = 0;
 }
 string Apple::get() {
  return "("+color+", "+this->getStatus()+", "+to_string(this->eated)+")";
 }
};

class applesArray {
 vector <Apple> apples;
public:
 applesArray::applesArray() { }
 void applesArray::put(Apple a) {
  this->apples.push_back(a); 
 }
 void applesArray::print() {
  int len = this->size();
  for (int i = 0; i<len; i++) {
   if (this->apples[i].eat()==0) {
    this->apples.erase(this->apples.begin()+i);
    i--; len--;
    cout << endl << "Eated!";
   }
   else cout << endl << this->apples[i].get();
  }
  cout << endl << "Total size: " << len << " item(s)";
 }
 const int applesArray::size () { return this->apples.size(); }
 Apple & applesArray::operator [] (int index) {
  if (index > -1 && index < this->size()) return this->apples[index];
  return *(new Apple("empty",Apple::EMPTY));
 }
};


int main() {
 applesArray a;
 a.put(*(new Apple("green"))); //передаём объект в push_back
 a.put(*(new Apple("red")));
 a.put(*(new Apple("yellow")));
 a.print();

 a[0].fall();
 a[0].eat(25);
 a[1].eat(20); //не выйдет, не упало
 a.print();

 a[2].fall();
 a[2].eat(50);
 a[0].eat(100); //удалится
 a.print();

 //нумерация яблок теперь изменилась!
 a[0].fall();
 a[0].eat(200);
 a[1].eat(50); //удалили всё
 a.print(); //пусто

 a[1000].eat(); //недопустимый вызов
 a.print(); //пусто

 system("pause >nul"); return 0;
}

9. Написать программу определения дня недели по заданным значениям "день", "месяц" и "год".

Примечание: используйте формулу Зеллера

Здесь [] – обозначение целой части числа, % - взятие остатка от деления, D- день месяца, M – номер месяца, Y – год столетия (0-99), C – номер столетия (=20 для 21 века), dday – полученный день недели (0-Сб, 1-Вс, …, 6-Пт). Январь и февраль считаются как месяцы 13 и 14 предыдущего года.

#include <cstdio>
#include <cmath>

int leapyear(int y) {
 //Високосный ли год y (1/0)
 return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
}

int lastday(int m, int y) {
 //Последний день месяца m года y
 switch (m) {
 case 1: case 3: case 5: case 7:
 case 8: case 10: case 12: return 31;
 case 4: case 6: case 9: case 11: return 30;
 case 2: return (leapyear(y) ? 29 : 28);
 default: return 0;
 }
}

int weekday(int day, int month, int year) {
 // День недели по формуле Зеллера;
 // 1=Пн, ..., 7=Вс; 0=ошибка
 if (year<1 || month<1 || month>12 || day<1 ||
  day>lastday(month, year)) {
  return 0;
 }
 if (month<3) {
  month += 12; year--;
 }
 int c = year / 100;
 int y = year % 100;
 int nday = (
  (int)(floor(26 * (month + 1) / 10) + day + y +
   floor(y / 4) + floor(c / 4) - 2 * c)) % 7;
 return nday < 2 ? nday + 6 : nday - 1;
}

int main()
{
 printf("\n%d", weekday(29, 2, 2000));
 //2 - вт
 printf("\n%d", weekday(29, 2, 2100));
 //0 - неверная дата
 printf("\n%d", weekday(1, 1, 2018));
 //1 - пн
 getchar();
 return 0;
}

10. Реализовать и проверить функцию strins – вставку в строку другой строки, начиная с заданного номера позиции. Класс string не используем, только строки char *

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
/*
В Studio права указателей ограничены, проще всего сделать
за несколько проходов по строке
*/
char *strins(char *dest, const char *src, unsigned pos) {
 int lendest = strlen(dest);
 if (pos<0 || pos>lendest) return dest; //
 int lensrc = strlen(src);
 int newlen = lendest + lensrc + 1;
 char *newstr = new char[newlen];
 strncpy(newstr, dest, pos);
 strncpy(&newstr[pos], src, lensrc);
 strncpy(&newstr[pos + lensrc], &dest[pos], lendest - pos + 1);
 newstr[newlen] = '\0';
 return newstr;
}

int main() {
 char *src = "Hello"; //что вставляем
 char *dest = new char[80]; 
 strcpy(dest, "12345"); //куда
 dest = strins(dest, src, 3);
 puts(dest);
 getchar(); return 0;
}

11. Реализовать и проверить функцию memcpy – копирование строки в строку с ограничением максимального количества копируемых символов. Использовать строки char *

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

char *memcpy_(char *dest, const char *src, unsigned count) {
 char *addr = dest;
 for (int i = 0; i < count; i++) *dest++ = *src++;
 return addr;
}

int main() {
 char *dest = new char[80];
 char src[80];
 strcpy(src, "Hello, i'm a string from your program!");
 dest = (char *)memcpy(dest, src, 19); //сделали стандартной функцией
 dest[19] = '\0';
 puts(dest); 
 dest = (char *)memcpy_(dest, src, 19); //и нашей
 dest[19] = '\0';
 puts(dest);
 getchar(); return 0;
}

12. Реализовать и проверить функцию memcmp – сравнение указанного количества байт в двух областях памяти. Использовать строки char *

#include <iostream> 
#include <cstring>
using namespace std;

int memcmp_(const char *buf1, const char *buf2, unsigned count) {
 for (unsigned i = 0; i<count; i++) {
  if (*buf1 != *buf2) 
   return (int)*buf1 - (int)*buf2;
  buf1++; buf2++;
 }
 return 0;
}

int main() {
 char *s1 = "abcd";
 char *s2 = "abcd";
 char *s3 = "abc";
 char *s4 = "abzd";
 int i1 = memcmp_(s1, s2, 4);
 cout << endl << "s1 and s2 [4]: " << i1;
 int i2 = memcmp_(s1, s3, 4);
 cout << endl << "s1 and s3 [4]: " << i2;
 int i3 = memcmp_(s1, s3, 3);
 cout << endl << "s1 and s3 [3]: " << i3;
 int i4 = memcmp_(s1, s4, 4);
 cout << endl << "s1 and s4 [4]: " << i4;
 cin.get();
 return 0;
}

13. Реализовать и проверить функцию trim – удаление лишних разделителей в начале и конце строки. Использовать строки char *

#include <iostream>
#include <cstring>
using namespace std;

bool is_div(char c) {
 return strchr(" \t\r\n\v", c) == nullptr ? false : true;
}

char *trim(const char *s) {
 int i = 0, n = strlen(s);
 while (is_div(s[i])) { i++; if (i == n) return ""; }
 int j = n - 1;
 while (is_div(s[j])) j--;
 char *news = new char[j - i + 2];
 strncpy_s(news, j - i + 2, &s[i], j - i + 1); //безопасная версия strncpy
 news[j - i + 1] = '\0'; return news;
}

int main() {
 cout << endl << trim("\t  abc  ");
 cout << endl << trim("def");
 cout << endl << trim("    \t\n");
 cout << endl << trim("  123    456     \r\n");
 cin.get(); return 0;
}

14. Реализовать и проверить функцию strcmp – сравнение двух строк char *

#include <cstring>
#include <iostream>
using namespace std;

int strcmp_(const char *s1, const char *s2) {
 while (*s1 || *s2) { //пока одна из строк не кончилась
  if (*s1 == *s2) { //если очередные 2 символа равны
   s1++; s2++;  //перейти к следующей паре символов
  }
  else return *s1 - *s2; //иначе вернуть разность кодов отличающихся символов
 }
 //Проверить случаи, когда кончилась только одна из строк
 if (*s1 == '\0' && *s2 != '\0') return 1;
 else if (*s1 != '\0' && *s2 == '\0') return -1;
 else return 0; //если обе кончились одновременно - это равенство!
}
int main() {
 char *s1 = "abcde";
 char *s2 = "abcd";
 cout << strcmp_(s1, s2);
 cin.get();  return 0;
}

15. Реализовать и проверить функцию, возвращающую только те из символов строки s, которые встречаются в строке c. Использовать строки char *

#include <iostream>

char *f(char *s, char *c) {
 int ls = strlen(s), lc = strlen(c);
 char *r = new char[ls]; 
 int k = 0;
 for (int i = 0; i < ls; i++) {
  char next = s[i];
  bool found = false;
  for (int j = 0; j < lc; j++)
   if (next == c[j]) {
    found = true;
    break;
   }
  if (found) r[k++] = next;
 }
 r[k] = '\0';
 return r;
}
int main() {
 char *s = "Symbols from string"; char *c = "ybSstr";
 std::cout << f(s, c); //Остались из s символы, входящие в c
 std::cin.get();  return 0;
}

16. Из динамического целочисленного массива переписать все положительные элементы в новый динамический массив.

#include <iostream>
#include <cstdlib>
using namespace std;

int *vvod(int n) {
 int *a = new int[n];
 if (a == NULL) return NULL;
 for (int i = 0; i<n; i++) {
  cout << "a[" << (i + 1) << "]=";
  cin >> a[i];
 }
 return a;
}

int *obrabotka(int *a, int n, int &bk) {
 int k = 0;
 bk = 0;
 for (int i = 0; i<n; i++) if (a[i]>0) k++;
 if (k == 0) return NULL;
 int *b = new int[k];
 if (b == NULL) return NULL;
 for (int i = 0, k = 0; i<n; i++) if (a[i]>0) b[k++] = a[i];
 bk = k;
 return b;
}

void vivod(int *a, int n) {
 cout << endl;
 for (int i = 0; i<n; i++) cout << a[i] << " ";
}

int main() {
 int n; cout << "Size of array N="; cin >> n;
 int *a = vvod(n);
 int bn = 0;
 int *b = obrabotka(a, n, bn);
 vivod(b, bn);
 system("pause >nul"); return 0;
}

17. Средствами библиотеки iostream организовать ввод динамической матрицы вещественных чисел с проверкой корректности ввода.

#include <iostream>
using namespace std;

int main() {
 const int n = 3, m = 3;
 int i, j;
 double val;

 //Выделение памяти под матрицу
 double **a = new double *[n];
 for (i = 0; i<n; i++) a[i] = new double[m];

 //Ввод динамической матрицы с проверкой корректности ввода (через cin)
 for (i = 0; i < n; i++) {
  for (j = 0; j < m; j++) {
   cout << endl << "Item A[" << i << "," << j << "]=";
   while (!(cin >> val)) { //Простой вариант без try-catch
    cin.clear();
    while (cin.get() != '\n') continue;
    cout << "Error! Please, type it again" << endl;
   }
   a[i][j] = val;
  }
 }

 //Вывод матрицы по строкам
 for (i = 0; i < n; i++) {
  cout << endl;
  for (j = 0; j < m; j++) cout << a[i][j] << " ";
 }

 cin.get(); cin.get(); return 0;
}

18. Продемонстрировать передачу динамически созданной целочисленной матрицы в качестве параметра функции. Функция возвращает вектор, состоящий из максимальных элементов строк матрицы.

#include <iostream>
#include <cstdlib>
using namespace std;

int *maxRows(int n, int m, int **a) {
 int *r = new int[n];
 if (!r) return NULL;
 for (int i = 0; i<n; i++) {
  r[i] = a[i][0];
  for (int j = 1; j<m; j++)  if (a[i][j]>r[i]) r[i] = a[i][j];
 }
 return r;
}

int main() {
 const int n = 4, m = 2;
 int **a = new int *[n];
 for (int i = 0; i < n; i++) a[i] = new int[m];
 a[0][0] = 4; a[0][1] = 4;
 a[1][0] = 3; a[1][1] = 4;
 a[2][0] = 5; a[2][1] = 5;
 a[3][0] = 4; a[3][1] = 5;
 int *s = maxRows(n, m, a);
 for (int i = 0; i<n; i++) cout << s[i] << " ";
 cin.get(); return 0;
}

19. Прочитать из текущей папки файл data.txt с символами кириллицы, показать коды символов. Учесть, что Visual Studio по умолчанию интерпретирует тип char как знаковый.

В несложных случаях с однобайтовой кодировкой, такой как стандартная Windows-1251, может помочь вот такой простой подход:

#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;

void error(int c) {
 cout << "\nExitcode:" << c; system("pause>nul"); cin.get(); exit(c);
}

int main() {
 ifstream file("data.txt");
 if (!file) error(1);
 char c; int ci;
 while (!file.eof()) {
  file.read(&c, 1);
  if (c < 0) ci = (int)c + 256; //для Studio, где по умолчанию char - знаковый
                                //работаем с кодом символа ci как с unsigned char
  cout << ci << " ";
 }
 error(0);
}

20. Заданы вектор A размерностью m, определяющий объем производимой продукции, и матрица X размерностью m*n, характеризующая распределение производимой продукции по n потребителям. Напишите программу, которая:

1. Вычисляет невязки в векторе А как разность между компонентой a[i] и суммой элементов i-ой строки матрицы X.

2. Вычисляет общую сумму невязок S в векторе A. Если S = 0, т.е. вся продукция распределена, то программа выводит на печать текст: “План перевозок оптимален”. При S, не равном нулю, печатается значение S и текст “План перевозок не оптимален”.

#include <iostream>
using namespace std;

int main() {
 const int m = 3, n = 4;
 int x[m][n] = {
  { 0, 0, 5, 5 },
  { 10, 0, 0, 0 },
  { 0, 5, 5, 0 }
 };
 int a[m] = { 10, 10, 10 };
 int r[m], s = 0, sumi, i, j;
 for (i = 0; i<m; i++) {
  sumi = 0;
  for (j = 0; j<n; j++) sumi += x[i][j];
  r[i] = a[i] - sumi;
  s += r[i];
 }
 cout.precision(2);
 cout << endl << "s=" << s;
 cout << endl << "Plan is" << (s ? " not " : " ") << "optimal";
 cin.get();
 return 0;
}

21. Сравнить по быстродействию большой массив int[] с вектором той же размерности.

#include <cstdlib>
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;

int main() {
 const int size = 10000000;
 int *a;
 vector <int> v;
 int i, n;
 cout << "Type 1 (int *) or 2 (vector) "; cin >> n;
 long t1 = clock(); //время начала
 if (n == 1) { //заполнение средствами int *
  a = new int[size];
  if (!a) { cout << "No memory for int *!";  exit(1); }
  for (i = 0; i < size; i++) a[i] = i;
  delete a; //время обработки <100 ms
 }
 else { //заполнение средствами vector <int>
  v.resize(size);
  int n = v.size();
  if (n != size) { cout << "No memory for vector!";  exit(2); }
  for (i = 0; i < size; i++) v[i] = i;
   //c v.push_back(i) ещё намного медленее, >12000 ms
  v.clear(); //время обработки >3000 ms
 }
 long t2 = clock() - t1; //время окончания
 cout << t2 << "ms";

 cout << endl; system("pause >nul");
 return 0;
}

Следует учесть, что по умолчанию в Studio выбрана конфигурация Debug, в ней vector и впрямь будет намного медленнее.

В конфигурации Release заметных отличий не будет.

Кстати, в QT 5.X vector медленнее всего в 1,5 - 2 раза.

22. В классе String, хранящем данные в строке Си, заданной указателем, перегрузить операцию "=" таким образом, что она скопирует строку без скобок всех видов.

Решение примитивно, буфер под строки всегда одинакового размера.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <cstring> 
#define SIZE 256 
using namespace std;
 
class String {
private:
 char *str;
public:
 String(char *s = "");
 ~String();
 int length();
 void print();
 String& operator = (String &ob);
};
String::String(char *s) {
 str = new char[SIZE]; strcpy(str, s);
}
String::~String() {
 //delete[] str; //не надо, будут объекты в стеке
}
int String::length() {  return strlen(str); }
void String::print() { cout << endl << str; }
String & String::operator = (String &ob) {
 int l = ob.length();
 char *divs = "(){}[]"; //а лучше std::string, #include <algorithm> и str.erase
 int k = 0;
 for (int i=0; i<l; i++) if (!strchr(divs, ob.str[i])) this->str[k++] = ob.str[i];
 this->str[k]='\0';
 return *this;
}
int main () {
 String str1 ("(Hello, [] {world})");
 String str2 ("()");
 String str3 = str2 = str1;
 str1.print();
 str2.print();
 str3.print();
 cin.get(); return 0;
}

18.01.2018, 14:09 [2069 просмотров]