БлогNot. 32 не пригодившихся задачи за июнь 2021

32 не пригодившихся задачи за июнь 2021

Так как месяц обещает быть "неполным" и планируется отъезд в нормальные (безинетные) места, опубликую очередную коллекцию задачек заранее.

Все программы выполнялись в консоли актуальной сборки Visual Studio 2019, для поиска на странице нужных слов нажимайте комбинацию клавиш Ctrl+F в браузере. Предыдущая заметка серии была здесь.

Ещё могут пригодиться комбинаторные задачки 6 - 11, любопытны для дальнейшего варьирования 28, 32.

1. Разобрать строку в формате CSV на лексемы и записать их в контейнер (вектор).

#include <vector>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;
 
int main() {
 string str = "1,2,Hello, world, CSV";
 stringstream ss(str);
 vector<string> result;
 
 while (ss.good()) {
  string substr;
  getline(ss, substr, ',');
  result.push_back(substr);
 }
 for (size_t i = 0; i < result.size(); i++)
  cout << result[i] << endl;
}

"Лишние" пробелы или другие разделители при этом останутся в лексемах.

2. Определить принадлежит ли точка полуокружности радиуса 3 с центром в начале координат, находящейся выше оси 0x. Составить программу, которая выдает одно из сообщений: "Да", "Нет", "На границе".

Можно исходить из того, что "на границе" для вещественных чисел и без указания ширины границы - это не совсем корректная постановка, и тогда считать толщину границы заданной как eps = 10-6.

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
 double x = 3, y = 0.0001, r = sqrt(pow(x , 2) + pow(y, 2)), eps = 1e-6;
 if (abs(y) > eps) {
  if (abs(r - 3) < eps) cout << "Egde";
  else if (r < 3) cout << "Yes";
  else cout << "No";
 }
 else cout << "No";
 return 0;
}

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

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

int main() {
 double x = 1.8, y = 2.5, r = pow(x, 2) + pow(y, 2);
 if (r < 9 && y > 0.) cout << "Yes";
 else if (r > 9 && y < 0.) cout << "No";
 else cout << "Egde";
 return 0;
}

3. Все положительные элементы массива, кроме максимального, занести в другой массив. Использовать поэлементную обработку, а не контейнеры STL.

#include <iostream>
using namespace std;
 
int main() {
 const int n = 10;
 int a[n] = { 1, -2, 3, 9, 4, -2, 5, 0, -3, 9 };
 int b[n];
 int max = a[0];
 for (int i = 1; i < n; i++) {
  if (a[i] > max) max = a[i];
 }
 if (max <= 0) {
  cout << "Maximum <= 0";
  return 1;
 }
 int k = 0;
 for (int i = 0; i < n; i++) {
  if (a[i] > 0 && a[i] < max) b[k++] = a[i];
 }
 for (int i = 0; i < k; i++) {
  cout << b[i] << ' ';
 }
 return 0;
}

4. Имеется структура с элементами x и y типа integer. Структура реализует закрытый интервал [x, y].

Напишите программу, которая проверяет, есть ли перекрытия между интервалами в векторе, и отображает эти перекрытия.

Если два интервала имеют только один общий конец, перекрытие не рассматривается. Используемая память будет выделяться динамически, вектор структур занимает только необходимую память.

#include <iostream>
#include <vector>
#include <algorithm>
#include <clocale>

using namespace std;
struct interval
{
 int x, y;
 friend ostream& operator<<(ostream& os, const interval& b)
 {
  os << '[' << b.x << ',' << b.y << ']';
  return os;
 }
};

int main()
{
 setlocale(LC_ALL, "Rus");
 vector<interval> v;
 const int n = 7;
 v.push_back(interval{ 1, 2 });
 v.push_back(interval{ 2, 5 });
 v.push_back(interval{ 3, 3 });
 v.push_back(interval{ -1, 1 });
 v.push_back(interval{ 4, 10 });
 v.push_back(interval{ 1, 2 });
 v.push_back(interval{ 8, 9 });
 
 cout << "Все интервалы\n";
 for (int i = 0; i < n; i++) cout << v[i] << endl;
 cout << "Пересекающиеся интервалы\n";
 for (int i = 0; i < n - 1; i++)
 {
  for (int j = i + 1; j < n ; j++) {
   if (v[j].y > v[i].x && v[j].x < v[i].y)
    cout << v[i] << '-' << v[j] << endl;
  }
 }
 
 cin.get();
 return 0;
}

5. Найти сумму и количество элементов целочисленного массива, расположенных после максимального по модулю элемента.

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

В этом коде ищутся сумма и количество после первого максимума по модулю:

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

int main() {
 const int n = 10;
 int a[n] = { 1, -3, 5, 6, 8, -9, 1, 0, 5, -9 };
 int imax = 0;
 for (int i = 1; i < n; i++)
  if (abs(a[i]) > abs(a[imax])) imax = i;
 cout << "K = " << (n - 1 - imax) << endl;
 int sum = 0;
 for (int i = imax + 1; i < n; i++) 
  sum += a[i];
 cout << "S = " << sum;
 return 0;
}

Поменяем в операторе if знак ">" на ">=" - ответами будут нули, так как найдётся последний элемент массива. Также предполагается, что это задача на "ручную" алгоритмическую обработку массива, а не на STL.

То же самое с использованием шаблона функции:

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

template <typename T> T myFunc(T a[], int n, int& nmax) {
 int imax = 0;
 for (int i = 1; i < n; i++)
  if (abs(a[i]) > abs(a[imax])) imax = i;
 T sum = 0;
 for (int i = imax + 1; i < n; i++)
  sum += a[i];
 nmax = n - 1 - imax;
 return sum;
}

int main() {
 const int n = 10;
 int a[n] = { 1, -3, 5, 6, 8, -9, 1, 0, 5, -9 };
 int nmax;
 int sum1 = myFunc (a, n, nmax);
 cout << "K = " << nmax << ", S = " << sum1 << endl;
 double b[5] = { 2, -2.5, -13.5, 12.5, -9.25 };
 double sum2 = myFunc(b, 5, nmax);
 cout << "K = " << nmax << ", S = " << sum2 << endl;
 return 0;
}

6. Получить все размещения из 9 элементов 1, 2, 3, ..., 9 по 3 элемента в каждом. Элементы размещений не повторяются.

#include <iostream>
using namespace std;

/* arr[] входной массив
data[] временный массив
start, end начальный и конечный индексы в arr
index индекс в data
r какого размера комбинации нужны */
void combinationUtil(int arr[], int data[], int start, int end, int index, int r) {
 if (index == r) {
  for (int j = 0; j < r; j++) cout << data[j] << " ";
  cout << endl;
  return;
 }
 for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
  data[index] = arr[i];
  combinationUtil(arr, data, i + 1, end, index + 1, r);
 }
}

void printCombination(int arr[], int n, int r) {
 int* data = new int[r];
 combinationUtil(arr, data, 0, n - 1, 0, r);
 delete[] data;
}

int main() {
 int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 int r = 3;
 int n = sizeof(arr) / sizeof(arr[0]);
 printCombination(arr, n, r);
}

7. Решить задачу 6 для размещений из цифр 1, 2, 3, ..., 9 по 3 цифры с сортировкой полученных перестановок как десятичных чисел по возрастанию.

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

/* arr входная строка
data временная строка
start, end начальный и конечный индексы в arr
index индекс в data
r какого размера комбинации нужны 
combinations вектор с комбинациями
*/
void combineUtil (string arr, string data, int start, int end, int index, int r, 
 vector <string>& combinations) {
 if (index == r) {
  combinations.push_back (data);
  return;
 }
 for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
  data[index] = arr[i];
  combineUtil(arr, data, i + 1, end, index + 1, r, combinations);
 }
}

void combine (string arr, int n, int r, vector <string> &combinations) {
 string data;
 data.resize (arr.size(),'\0');
 combineUtil (arr, data, 0, n - 1, 0, r, combinations);
}

int main() {
 string str = "123456789";
 int r = 3;
 int n = str.size();
 vector <string> combinations;
 combine(str, n, r, combinations);
 sort(combinations.begin(), combinations.end());
 for (int i = 0; i < combinations.size(); i++) cout << combinations.at(i) << endl;
}

8. Получить все перестановки из четырёх различных между собой элементов массива. Если делать без стандартного средства, то

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

/* a[] входной массив
   n размерность массива
   l, r начальный и конечный индексы в arr
*/
void permute(int a[], int n, int l, int r) {
 if (l == r) {
  for (int i = 0; i < n; i++) cout << a[i] << " ";
  cout << endl;
  return;
 }
 for (int i = l; i <= r; i++) {
  swap(a[l], a[i]);
  permute (a, n, l + 1, r);
  swap(a[l], a[i]);
 }
}

int main() {
 int arr[] = { 1, 2, 3, 4 };
 int n = sizeof(arr) / sizeof(arr[0]);
 permute(arr, n, 0, n - 1);
}

9. Решить задачу 8 для перестановок из цифр 1, 2, 3, 4 с сортировкой полученных перестановок как десятичных чисел по возрастанию.

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

/* a входная строка
   l, r начальный и конечный индексы в a
   permutations - перестановки
*/
void permute(string a, int l, int r, vector <string> &permutations) {
 if (l == r) {
  permutations.push_back (a);
  return;
 }
 for (int i = l; i <= r; i++) {
  swap(a[l], a[i]);
  permute (a, l + 1, r, permutations);
  swap(a[l], a[i]);
 }
}

int main() {
 string str = "1234";
 int n = str.size();
 vector <string> permutations;
 permute(str, 0, n - 1, permutations);
 sort(permutations.begin(), permutations.end());
 for (int i = 0; i < permutations.size(); i++) cout << permutations.at(i) << endl;
}

10. Реализовать размещения с повторениями по k элементов из n для элементов целочисленного массива.

В отличие от задачи 8, выбранные элементы могут повторяться в выборке, а значит, размер выборки k не ограничен значением n, например, для массива из двух элементов {1, 2} при k = 3 имеем наборы 111, 112, 121, 122, 211, 212, 221, 222.

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

void getAllKPerm(int set[], string prefix, int n, int k, vector <string>& perm) {
 if (k == 0) {
  perm.push_back(prefix);
  return;
 }
 for (int i = 0; i < n; i++) {
  string newPrefix;
  newPrefix = prefix + to_string(set[i]) + ' ';
  getAllKPerm(set, newPrefix, n, k - 1, perm);
 }
}

int main() {
 int arr[] = { 1, 2 };
 int n = sizeof(arr) / sizeof(arr[0]);
 int k = 3;
 vector <string> perm;
 getAllKPerm(arr, "", n, k, perm);
 for (int i = 0; i < perm.size(); i++) cout << perm.at(i) << endl;
}

11. Реализовать комбинации с повторениями по k элементов из n для элементов целочисленного массива.

В отличие от задачи 6, выбранные элементы могут повторяться в выборке, например, для массива из четырёх элементов {1, 2, 3, 4} при k = 2 имеем наборы {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}, {2, 3}, {2, 4}, {3, 3}, {3, 4}, {4, 4}.

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

/* arr[] - входной массив
  chosen[] - временный массив
  start, end - начальный и конечный индексы в arr
  r - размер текущей комбинации */
void combRepUtil(int chosen[], int arr[], int index, int r, int start, int end) {
 if (index == r) {
  for (int i = 0; i < r; i++) cout << " " << arr[chosen[i]];
  cout << "\n";
  return;
 }
 for (int i = start; i <= end; i++) {
  chosen[index] = i;
  combRepUtil(chosen, arr, index + 1, r, i, end);
 }
 return;
}

void combRep(int arr[], int n, int r) {
 int *chosen = new int [r + 1];
 combRepUtil(chosen, arr, 0, r, 0, n - 1);
 delete[] chosen;
}

int main() {
 int arr[] = { 1, 2, 3, 4 };
 int n = sizeof(arr) / sizeof(arr[0]);
 int k = 2;
 combRep(arr, n, k);
 return 0;
}

12. Составить функцию для вывода двух различных между собой наименьших значений элементов целочисленного массива.

Следует учесть, что минимальных значений может оказаться больше одного, особенно если данные целочисленные. Также может не быть второго минимума, если все элементы массива совпадают по значению.

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

void print2Smallest(int arr[], int arr_size) {
 int i, first, second;
 if (arr_size < 2) {
  cout << " Invalid Input ";
  return;
 }
 first = second = INT_MAX;
 for (i = 0; i < arr_size; i++)  {
  if (arr[i] < first) {
   second = first;
   first = arr[i];
  }
  else if (arr[i] < second && arr[i] != first) {
   second = arr[i];
  }
 }
 if (second == INT_MAX)
  cout << "No second smallest element" << endl;
 else
  cout << "First smallest element is " << first << " and second is " << second << endl;
}

int main() {
 int arr[] = { 12, 13, 1, 10, 34, 1 };
 int n = sizeof(arr) / sizeof(arr[0]);
 print2Smallest(arr, n);
 return 0;
}

13. Решить задачу 12 для случая, когда искомые два минимальных элемента массива не обязательно различны между собой по значению и выводятся индексы найденных элементов (нумерация с единицы).

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

void print2Smallest(int arr[], int arr_size) {
 int i, first = 0, second = 1;
 if (arr_size < 2) {
  cout << " Invalid Input ";
  return;
 }
 for (i = 1; i < arr_size; i++) {
  if (arr[i] < arr[first]) {
   second = first;
   first = i;
   continue;
  }
  if (arr[i] < arr[second]) {
   second = i;
  }
 }
 cout << "First smallest element has a number " << first + 1 <<
  " and second has a number " << second + 1 << endl;
}

int main() {
 int arr[] = { 5, 13, 9, 3, 34, 11, 2 };
 int n = sizeof(arr) / sizeof(arr[0]);
 print2Smallest(arr, n);
 return 0;
}

14. Найти и вывести количество вхождений для каждого элемента целочисленного массива.

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

int main() {
 int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 };
 int n = sizeof(arr) / sizeof(arr[0]);
 vector<bool> visited(n, false);
 for (int i = 0; i < n; i++) {
  if (visited[i] == true) continue;
  int count = 1;
  for (int j = i + 1; j < n; j++) {
   if (arr[i] == arr[j]) {
    visited[j] = true;
    count++;
   }
  }
  cout << arr[i] << " " << count << endl;
 }
 return 0;
}

15. Дана информация о пяти школах. Запись имеет вид: номер школы, год, количество выпускников, количество поступивших в ВУЗы. Вывести данные о школе с самым большим отношением количества поступивших к количеству выпускников.

#include <iostream>
#include <clocale>
#include <climits>
using namespace std;

struct stud {
 string number;
 int year;
 int graduates;
 int students;
};
int main() {
 setlocale(LC_ALL, "RUS");
 stud school[5];
 school[0] = { "21", 2020, 60, 10 };
 school[1] = { "27", 2020, 150, 159 };
 school[2] = { "40", 2021, 480, 390 };
 school[3] = { "6", 2020, 705, 593 };
 school[4] = { "18", 2021, 129, 78 };
 double otn[5], max = INT_MIN;
 for (int i = 0; i < 5; i++) {
  cout << "Школа №" << i + 1 << endl;
  cout << "Номер школы - " << school[i].number << endl;
  cout << "Год выпуска - " << school[i].year << endl;
  cout << "Количество выпускников - " << school[i].graduates << endl;
  cout << "Число поступивших в ВУЗы - " << school[i].students << endl;
  otn[i] = (double)school[i].students / school[i].graduates;
  if (otn[i] > max) max = otn[i];
 }
 cout << "Максимальное отношение = " << max << endl << "Номера школ:" << endl;
 for (int i = 0; i < 5; i++) {
  if (otn[i] == max) {
   cout << school[i].number << endl;
  }
 }
 return 0;
}

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

16. Задана строка текста и один символ. Определить количество этих символов в тексте, предшествующих первой запятой. Если запятая отсутствует, определить общее количество данных символов.

#include <iostream>
#include <string>
using namespace std;
int main() {
 string text("Hello, world!");
 char letter = 'l';
 size_t end_pos = text.length();
 size_t comma_pos = text.find(',');
 if (comma_pos != string::npos) end_pos = comma_pos;
 size_t cnt = 0;
 for (size_t i = 0; i < end_pos; i++) {
  if (text[i] == letter) cnt++;
 }
 cout << cnt;
 return 0;
}

Как вариант решения "за один проход", без предварительного поиска запятой:

#include <iostream>
using namespace std;

int main() {
 size_t i = 0, cnt = 0;
 string s = "Hello, world!";
 char ch = 'l';
 while (s[i]) {
  if (s[i] == ch) cnt++;
  else if (s[i] == ',') break;
  i++;
 }
 cout << cnt << "\n";
 return 0;
}

17. Преобразовать римское число в арабское и обратно. Как минимум, обрабатываются значения от 1 до 3999 включительно.

Код не слишком обдумывал, основываясь на старом PHP-решении, но для текущего года сработало :)

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

string arabic_to_roman (int val) {
 if (val < 0) val = -val;
 if (!val) return "0";
 int thousands = val / 1000;
 val -= thousands * 1000;
 string result(thousands, 'M');
 map <int,string, greater<int>> table = {
  make_pair(900,"CM"),
  make_pair(500,"D"),
  make_pair(400,"CD"),
  make_pair(100,"C"),
  make_pair(90,"XC"),
  make_pair(50,"L"),
  make_pair(40,"XL"),
  make_pair(10,"X"),
  make_pair(9,"IX"),
  make_pair(5,"V"),
  make_pair(4,"IV"),
  make_pair(1,"I")
 };
 while (val) {
  map <int, string>::iterator it;
  for (it = table.begin(); it != table.end(); it++)
   if (it->first <= val) {
    int amount = val / it->first;
    val -= it->first * amount;
    string fragment;
    for (size_t f = 0; f < amount; f++) fragment += it->second;
    result += fragment;
   }
 }
 return result;
}

int roman_to_arabic(string val) {
 map <char, int> table = {
  make_pair('M',1000),
  make_pair('D',500),
  make_pair('C',100),
  make_pair('L',50),
  make_pair('X',10),
  make_pair('V',5),
  make_pair('I',1)
 };
 int len = val.length();
 int active = 0, result = 0;
 for (int i = len - 1; i > -1; i--) {
  char key = (char)val[i];
  if (table.find(key) == table.end()) {
   cout << "Bad digit " << key << " in roman number";
   return -1;
  }
  int next = table[key];
  if (next < active) result -= next;
  else result += next;
  active = next;
 }
 return result;
}

int main() {
 int n = 2021;
 string s = arabic_to_roman(n);
 cout << s << endl;
 int v = roman_to_arabic(s);
 cout << v;
 return 0;
}

18. Задано натуральное значение N. Реализовать функцию, создающую массив из N значений типа bool, каждое из которых хранит один бит заданного числа, индекс элемента массива равен соответствующему разряду исходного числа. Массив создать с помощью вектора.

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

vector <bool> createBoolVector(int val) {
 const int n = sizeof(val)*8;
 vector <bool> bits;
 for (size_t i = 0; i < n; i++) {
  bits.push_back(val & 1 ? true : false);
  val >>= 1;
 }
 reverse(bits.begin(), bits.end()); //биты переворачиваем, младшие разряды будут в конце
 return bits; 
}

int main() {
 int val = 15;
 vector <bool> bits = createBoolVector (val);
 bitset<sizeof(val)*8> set(val); //только для иллюстрации вывода
 cout << endl << "Binary number: " << set.to_string() << ", size=" << sizeof(set) << " bytes" << endl;
 for (vector<bool>::iterator it = bits.begin(); it != bits.end(); ++it)
  cout << *it << ' ';
 cout << endl << bits.size() << " item(s)" << endl;
 return 0;
}

19. С помощью рекурсивной функции вычислить значение по формуле, показанной на рисунке:

функция задачи 19
функция задачи 19

Проверил в Excel для x = 1, вроде бы, совпало :)

#include <iostream>
using namespace std;
 
double repa(double x, int n1, int dn, int n2) {
 if (n1 <= n2) return n2;
 return n1 / (x + repa(x, n1 + dn, dn, n2));
}
 
int main() {
 double x = 1;
 cout << repa(x,8,-2,1) + repa(2*x, 13,-3,1);
 return 0;
}

Можно добавить проверки на то, что x не равен -1 или -0.5.

20. Найти максимальное и минимальное значения элементов целочисленного массива, заполненного случайными значениями от -5 до 5 включительно. Вывести на экран исходный массив и массив, в котором поменялись местами значения минимальных и максимальных элементов.

Цикл 1. Сгенерировали и заодно нашли значения макс. и мин. элемента сравнением, дав минимуму начальным значением заведомо большое число, а максимуму - заведомо малое, чтобы условия сравнения гарантированно выполнились.

Цикл 2. Так как искомых значений может несколько, и вообще все элементы массива могут быть одинаковы, при неравенстве макс. и мин. каждый макс. заменили на мин. и наоборот. Получилось 2 прохода по массиву, зато учтена не оговоренная в условии возможная не-единственность макс. и мин.

#include <iostream>
#include <cstdlib>
#include <climits>
#include <ctime>
using namespace std;
 
int main() {
 const int n = 10;
 int a[n], min = INT_MAX, max = INT_MIN;
 srand(time(0)); //инициализируем генератор, чтобы каждый раз иметь другой массив
 cout << "Initial array: ";
 for (int i = 0; i < n; i++) { //1
  a[i] = -5 + rand() % 11; //от -5 до 5 включительно
  if (a[i] < min) min = a[i];
  else if (a[i] > max) max = a[i];
  cout << a[i] << ' ';
 }
 cout << endl << "Result array:  ";
 for (int i = 0; i < n; i++) { //2
  if (a[i] == min) a[i] = max;
  else if (a[i] == max) a[i] = min;
  cout << a[i] << ' ';
 }
 return 0;
}

21. Дата описана структурой с полями int day; char month[20]; int year. Для заданного массива структур отобразить только даты, относящиеся к летним месяцам.

#include <iostream>
using namespace std;

struct date {
 int day;
 char month[20];
 int year;
};

bool is_summer_date(date& d) {
 const char* months[12] = { "January", "February", "March", "April", "May", "June", 
  "July", "August", "September", "October", "November", "December" };
 int month = 0;
 for (int i = 0; i < 12; i++) {
  if (_stricmp(months[i], d.month) == 0) {
   //в Studio _stricmp, а не stricmp
   month = i + 1; break;
  }
 }
 return (month > 5 && month < 9);
}

int main() {
 const int n = 5;
 date dt[n] = {
  {1, "january", 2021},
  {9, "may", 1945},
  {23, "june", 1980},
  {13, "april", 1913},
  {8, "august", 2021}
 };
 cout << "Summer dates is: " << endl;
 for (int i = 0; i < n; i++) {
  if (is_summer_date(dt[i]))
   cout << dt[i].day << ' ' << dt[i].month << ' ' << dt[i].year << endl;
 }
 return 0;
}

22. Реализовать метод Фибоначчи (метод золотого сечения) для поиска минимума функции одной переменной на заданном интервале [a,b]. Предполагается, что решение существует и единственно на указанном интервале.

Проверено для функции func(x)=x2+1 на интервале [-2;2] с единственным решением x = 0.

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

double f(double x) {
 return pow(x,2)+1;
}

double gold (double(*func)(double), double a, double b, double eps) {
 const double g = (sqrt(5) - 1.0) / 2;
 double a1, b1;
 int k = 0;
 a1 = a + (1 - g) * (b - a);
 b1 = a + g * (b - a);
 while (abs(b - a) > eps) {
  if (func(a1) > func(b1)) {
   a = a1; a1 = b1;  b1 = a + g * (b - a);
  }
  else  {
   b = b1; b1 = a1; a1 = a + (1 - g) * (b - a);
  }
  if (++k > 1e5) break; //во избежание зацикливания
 }
 return (a + b) / 2;
}

int main() {
 double a = -2., b = 2., eps = 0.0001;
 double x = gold(f, a, b, eps);
 cout.precision(7);
 cout << "x=" << fixed << x << ", f(x)=" << f(x) << endl;
 return 0;
}

23. Вывести все трёхзначные числа, в записи которых присутствует цифра "3".

#include <iostream>
using namespace std;
 
int main() {
cout << "All numbers from [100;999] with '3': ";
 for (int i = 100; i < 1000; i++) {
  int d3 = i % 10, d2 = (i - d3) / 10 % 10, d1 = (i - d2 * 10 - d3) / 100;
  if (d1 == 3 || d2 == 3 || d3 == 3) {
   cout << i << ' ';
  }
 }
 return 0;
}

24. Реализовать алгоритм Bitonic Sort (Битонная сортировка, сортировка Бэтчера). Количество сравнений оценивается как O(n Log 2 n).

#include <iostream>
using namespace std;

void sortdir(int a[], int i, int j, int dir) { //возрастание или убывание
 if (dir == (a[i] > a[j])) swap(a[i], a[j]);
}

/* Pекурсивно сортирует последовательность в порядке возрастания
   (dir == 1), или убывания (dir == 0).
   Сортируемая последовательность начинается с младшей позиции индекса,
   параметр cnt - это количество элементов для сортировки. */
void merge(int a[], int low, int cnt, int dir) {
 if (cnt > 1) {
  int k = cnt / 2;
  for (int i = low; i < low + k; i++) sortdir(a, i, i + k, dir);
  merge(a, low, k, dir);
  merge(a, low + k, k, dir);
 }
}

/* Создаём последовательность рекурсивно.
   Сортируем две половинки, затем вызываем merge */
void sort(int a[], int low, int cnt, int dir) {
 if (cnt > 1) {
  int k = cnt / 2;
  sort(a, low, k, 1);
  sort(a, low + k, k, 0);
  merge(a, low, cnt, dir);
 }
}

int main() {
 int a[] = { 3, 7, 4, 8, 6, 2, 1, 5 };
 int N = sizeof(a) / sizeof(a[0]);
 sort(a, 0, N, 1); //по возрастанию
 cout << "Sorted array: ";
 for (int i = 0; i < N; i++) cout << a[i] << ' ';
 return 0;
}

25. Вычислить разность двух множеств А и В. Элементы множества А вычисляются по формуле ai = i/2, элементы множества В вычисдяются как bi = (i+1)/2. Вывести на экран исходные множества и результат.

#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>
#include <iterator>
using namespace std;

int main() {
 set <double> a, b;
 const int n1 = 10;
 for (int i = 1; i <= n1; i++) a.insert((double)i/2);
 const int n2 = 12;
 for (int i = 1; i <= n2; i++) b.insert((double)(i+1) / 2);
 cout << "A=";
 copy(a.begin(), a.end(), ostream_iterator<double>(cout, " "));
 cout << endl;
 cout << "B=";
 copy(b.begin(), b.end(), ostream_iterator<double>(cout, " "));
 cout << endl;
 set <double> c;
 set_difference(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.end()));
 cout << "A-B=";
 copy(c.begin(), c.end(), ostream_iterator<double>(cout, " "));
 cout << endl;
 cin.get(); return 0;
}

26. Решить задачу 25 без контейнеров STL. Данные хранятся в одномерных массивах, для операции вычитания множеств реализована шаблонная функция.

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

template <typename T> void delete_equal(int* n0, T* a) {
 //Удаляет из массива повторяющиеся элементы и вычисляет новую размерность n0
 int n = *n0;
 int i = 0;
 while (i < n) {
  int j = i + 1;
  while (j < n) {
   if (a[i] == a[j]) {
    for (int k = j; k < n - 1; k++) a[k] = a[k + 1];
    n--;
   }
   else j++;
  }
  i++;
 }
 *n0 = n;
}

template <typename T> int find_item(int na, T* a, T b) {
 //Ищет элемент b в массиве a[na] и возвращает его индекс или -1 (не найдено)
 for (int i = 0; i < na; i++) if (a[i] == b) return i;
 return -1;
}

template <typename T> void copy_array(int n, T* a, T* c) {
 //Копирует массив a в новый массив c
 for (int i = 0; i < n; i++) c[i] = a[i];
}

template <typename T>  void diff_array(int na, T *a, int nb, T *b, int* nc, T *c) {
 //Разность массивов a и b с размерностями na и nb
 //в новый массив c (в массив войдут уникальные элементы,
 //присутствующие в массиве a, но отсутствующие в b)
 if (na < 1) return;
 delete_equal(&na, a);
 if (nb < 1) {
  copy_array(na, a, c);
  return;
 }
 delete_equal(&nb, b);
 //Вычисляем количество элементов в массиве a, отсутствующих в b
 *nc = 0;
 for (int i = 0; i < na; i++) {
  int kc = 0;
  if (find_item(nb, b, a[i]) != -1) kc++;
  if (kc == 0) (*nc)++;
 }
 //Формируем массив c
 int k = 0;
 for (int i = 0; i < na; i++) if (find_item(nb, b, a[i]) == -1) c[k++] = a[i];
}

template <typename T> void print_array(int n, T* a) { //Выводит массив на экран
 cout << endl;
 for (int i = 0; i < n; i++) cout << setw(5) << a[i];
}

int main() {
 const int na = 10, nb = 12; //Размерности массивов a,b
 double a[na], b[nb]; //Описали множества как динамические массивы

 for (int i = 1; i <= na; i++) a[i - 1] = (double)i / 2;
 for (int i = 1; i <= nb; i++) b[i - 1] = (double)(i+1) / 2;
 cout << endl << "A=";
 print_array(na, a);
 cout << endl << "B=";
 print_array(nb, b);
 int nc;
 cout << endl << "A-B=";
 double* c = new double (na);
 if (c == nullptr) return -1;
 diff_array(na, a, nb, b, &nc, c);
 print_array(nc, c);
 return 0;
}

27. Суперчислом называется число, являющееся суммой двух простых чисел из диапазона [2,B]. Требуется найти все суперчисла из заданного диапазона [A,B].

Входные данные - два числа A и B (2≤A≤B≤40000), выходные данные - все найденные суперчисла из заданного диапазона в возрастающем порядке.

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

const int MAX_SIZE = 40000; //максимальный размер
bool arr[MAX_SIZE+1];

bool checkPrime(int n) { 
 return arr[n];
}

int main() {
 //готовим решето максимального размера, можно размера b+1
 fill_n(arr, MAX_SIZE, true);
 int n = floor(sqrt(MAX_SIZE));
 for (int i = 2; i <= n; i++) {
  if(arr[i] == true) for (int j = i * i; j <= MAX_SIZE; j += i) arr[j] = false;
 }
 
 //перебираем нужные числа
 vector <int> nums;
 const int a = 2, b = 100;
 for (int n = a; n <= b; n++) {
  for (int i = 2; i <= n/2; i++) {
   if (checkPrime(i) && checkPrime(n - i)) {
    cout << n << '=' << i << '+' << (n-i) << endl; //просто для проверки, можно убрать
    nums.push_back (n);
    break; //можно не смотреть другие комбинации для n
   }
  }
 }

 //выводим, что вышло - числа автоматом будут в векторе по возрастанию
 cout << endl;
 for (int i = 0; i < nums.size(); i++) cout << nums.at(i) << ' ';
 return 0;
}

28. Вычислить количество n-значных чисел в системе счисления с основанием k, таких что их запись не содержит двух подряд идущих нулей.

Нас здесь не интересуют числа с лидирующими нулями. Например, при n = 4, k = 2 имеем ответ 5 (1010, 1011, 1101, 1110, 1111), а при n = 2, k = 10 ответ равен 90 (числа 10, 11, ..., 99). При k = 10 и n = 3 имеем всего 900 трёхзначных чисел, убираем из списка 100, 200, ..., 900, получаем 891, как на моём тесте.

Логика решения такова: d1 - это количество чисел, состоящих ровно из i цифр и оканчивающихся на цифру, отличную от нуля, а d0 - количество i-значных чисел, оканчивающихся на нуль.

Так как по условию n больше 1, числа с лидирующими нулями не рассматриваем даже при i = 1, поэтому даём начальные значения d1 = k - 1, d0 = 0.

Потом выражаем d1, d0 через их предыдущие значения в цикле от 2 до n включительно, рассматривая только те числа, которые не содержат в своей записи двух нулей подряд.

#include <iostream>
using namespace std;

int main() {
 const int n = 3, k = 10;
 int d1 = k - 1, d0 = 0, d;
 for (int i = 2; i <= n; i++) {
  d = d1;
  d1 = (d1 + d0)*(k - 1);
  d0 = d;
 }
 cout << d1 + d0;
 return 0;
}

29. Вычислить сумму бесконечного ряда c точностью eps = 0.0001.

Ряд для задачи 29
Ряд для задачи 29

На самом деле, в таких задачах - куча нюансов, связанных с конкретным критерием достижения заданной точности. Порядок расчёта тоже имеет значение. Вот пара вариантов.

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

int main() {
 double x = 0.25; // |x| < 1
 double f = log((1 + x) / (1 - x));
 double s = x, s0 = x, z = x, eps = 0.0001;
 int i = 1;
 do {
  //точность - в смысле модуля разности 2 соседних сумм
  z *= ((2 * i - 1) * x * x) / (2 * i + 1);
  i++;
  s0 = s;
  s += z;
 } while (abs(s - s0) > eps);
 s *= 2;
 cout.precision(9);
 cout << "S=" << fixed << s << ", F=" <<
  f << ", |F-S|=" << abs(f - s);
 return 0;
}
#include <iostream>
#include <cmath>
using namespace std;

int main() {
 double x = 0.25; // |x| < 1
 double f = log((1 + x) / (1 - x));
 double s = x, z = x, eps = 0.0001;
 int i = 1;
 while (abs(z) > eps) {
  //точность - в смысле модуля очередного элемента
  z *= ((2 * i - 1) * x * x) / (2 * i + 1);
  i++;
  s += z;
 }
 s *= 2;
 cout.precision(9);
 cout << "S=" << fixed << s << ", F=" <<
  f << ", |F-S|=" << abs(f - s);
 return 0;
}

30. Передать консольной программе список абсолютных или относительных путей к файлам, проверить существование каждого файла.

#include <iostream>
#include <fstream>
using namespace std;
 
class Filer {
 fstream fileStream;
public:
 bool available;
 Filer(char* name) {
  fileStream.open(name);
  if (fileStream.fail()) available = false;
  else available = true;
 }
};
 
int main (int argc, char *argv[]) {
 for (int i = 1; i < argc; i++) { //argv[0] - путь к самой программе
  Filer f(argv[i]);
  cout << argv[i] << ": " << f.available << endl;
 }
 return 0;
}

В Studio при запуске указал аргументы командной строки в свойствах проекта:

Visual Studio, указать аргументы командной строки
Visual Studio, указать аргументы командной строки

Второй файл при этом существовал:

test.txt: 0
d:\temp\1.txt: 1

То же самое я мог сделать, запустив программу не из оболочки, а из любого файл-менеждера с командной строкой:

Запуск программы с аргументами командной строки из файл-менеджера Far
Запуск программы с аргументами командной строки из файл-менеджера Far

31. Найти и вывести на экран самую длинную последовательность элементов целочисленного массива, удовлетворяющих условию вида A[i+1] = A[i]+1.

Если искомых последовательностей несколько, программа найдёт первую.

#include <iostream>
using namespace std;

int getLongestSequence(int a[], int n, int &maxidx) {
 int maxlen = 0, currlen = 0, curridx = 0;
 if (n < 2) return 0;
 for (int i = 0; i < n - 1; i++) {
  if (a[i+1] == a[i] + 1) {
   currlen++;
   if (currlen == 1) curridx = i;
  }
  else {
   if (currlen > maxlen) {
    maxlen = currlen + 1;
    maxidx = curridx;
   }
   currlen = 0;
  }
 }
 if (maxlen == 0 && currlen > 0) { maxlen = currlen + 1; maxidx = n - 1 - currlen; }
 return maxlen;
}

int main() {
 int arr[] = { 1,1,2,3,-5,-4,-3,7,8,9 };
 int n = sizeof(arr) / sizeof(int);
 int maxidx = -1;
 int maxlen = getLongestSequence(arr, n, maxidx);
 if (maxlen > 0) {
  cout << "Length=" << maxlen << ", index (from 1)=" << maxidx + 1 << endl;
  for (int i = maxidx; i < maxidx + maxlen; i++) cout << arr[i] << " ";
 }
 else cout << "No sequence found" << endl;
 return 0;
}

32. Требуется посчитать количество последовательностей длины n, состоящих из цифр от 0 до k−1 включительно, таких, что никакие два соседних элемента последовательности не равны нулю одновременно. Заданы натуральные числа N и K, 2≤K≤10; 2≤N; 4≤N+K≤18). Программа выводит целое число — ответ на задачу.

В отличие от задачи 28, здесь нас интересуют все числа, включая те, что имеют лидирующие нули. Решение методами динамического программирования может быть таким (двойная перекрестная рекурсия):

#include <iostream>
using namespace std;

unsigned long long g(int, int);

unsigned long long f (int n, int k) {
 if (n == 1) return k;
 return (k - 1) * (f(n - 1, k) + g(n - 1, k));
}

unsigned long long g (int n, int k) {
 if (n == 1) return 1;
 return f(n - 1, k);
}

int main() {
 cout << f(2, 2) << endl; //3
 cout << f(2, 10) << endl; //99
 cout << f(3, 9) << endl; //712
 cout << f(3, 10) << endl; //981
 cout << f(9, 9) << endl; //353603584
 return 0;
}

21.06.2021, 10:26 [381 просмотр]


теги: список c++ алгоритм