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

Очередная ставшая традиционной подборка текущих учебных задач на C++, коды проверялись в консоли Visual Studio 2015, возможно, что-то и в QT 5.X.

Если вы вошли на эту страницу из поисковика, для быстрого поиска нужного слова используйте в браузере комбинацию клавиш Ctrl+F.

1. Составить массив, состоящий из индексов элементов исходного массива, отсортированного по возрастанию.

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

int main() {
 vector <int> x = { 15, 3, 0, 20 };
 vector <int> y(x.size());
 int n=0;
 generate (begin(y), end(y), [&] { return n++; });
 sort (begin(y),end(y),[&] (int i1, int i2) { return x[i1] < x[i2]; });

 cout << endl;
 for (auto v : y) cout << v << ' '; //2 1 0 3 - индексы

 cin.get();
 return 0;
}

Увы, очевидно выглядящие решения не всегда верны, например, это не работает на массиве { 3, 2, 1, 2, 3 }, выдавая индексы 2, 1, 3, 0, 4. Ещё несколько опробованных кодов удовлетворительного решения для массива с повторяющимися элементами не дали, пришлось сделать вот так, сортируя при этом "лишнюю"копию вектора:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
 vector <int> x = { 3,2,1,2,3 }; //C++11 only!
 int n = x.size();
 vector <int> y(n);
 vector <pair <int, int> > a;
 for (int i = 0; i < n; i++) a.push_back(make_pair(x[i], i));
 sort(a.begin(), a.end());
 for (int i = 0; i < n; i++) {
  cout << a[i].first << " " << a[i].second << endl;
 }
 cin.get(); return 0;
}

2. Вывести элементы первого массива, которых нет во втором массиве, в третий массив (найти разность множеств).

Если не использовать библиотек алгоритмов, то вот так:

#include <cstdio>
int main() {
 const int n = 9;
 const int m = 2;
 int a[n] = { 1,2,3,4,2,3,4,5,3 };
 int b[m] = { 3,4 };
 int c[n];
 bool d;
 int k = 0;
 for (int i = 0; i<n; i++) {
  d = false;
  for (int j = 0; j<m; j++) {
   if (a[i] == b[j]) { 
    d = true; break; 
   }
  }
  if (!d) {
   bool d2=false;
   for (int l=0; l<k; l++) if (c[l]==a[i]) { d2=true; break; }
   if (!d2) c[k++] = a[i];
  }
 }
 for (int i=0; i<k; i++)  printf("%d ", c[i]);
 getchar();
 return 0;
}

3. Получить бинарное представление числа (без реализации классического алгоритма с делением на 2 и остатками от деления).

Если так, то остаётся решение стандартными средствами C++.

#include <iostream>
#include <bitset>
using namespace std;
 
int main() {
 int n = 17;
 string s = bitset <32> (n).to_string();
 cout << endl << s;
 
 cin.get();
 return 0;
}

4. Как сделать так, чтобы в консоли при вводе числа с клавиатуры пользователь не мог ввести определённое значение, например, 0?

Если всегда ожидаем нужный тип данных (например, целое число, а не строку), то достаточно

#include <iostream>
using namespace std;
 
int main() {
 int n;
 do {
  cout << "Input n: ";
  cin >> n;
 } while (n == 0);
 
 system("pause");
 return 0;
}

Если хотим ещё и контролировать тип данных, то есть, "не пускать дальше", например, при вводе строки вместо числа, то как-то так:

#include <iostream>
using namespace std;
 
int main() {
 int n;
 do {
  cout << "Input n: ";
  while (!(cin >> n)) {
   cin.clear();
   while (cin.get() != '\n') continue;
   cout << "Error! Please, type it again" << endl;
  }
 } while (n == 0);
 
 cout << endl << "n=" << n;
 system("pause");
 return 0;
}

5. Сравнить 2 слова (строки) с неповторяющимися символами на количество одинаковых букв в них.

#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
 
string::size_type matching_characters (string s1, string s2) {
 sort(begin(s1), end(s1));
 sort(begin(s2), end(s2));
 string intersection;
 set_intersection (begin(s1), end(s1), begin(s2), end(s2), back_inserter(intersection));
 return intersection.size();
}
 
int main() {
 cout << matching_characters("qwerty", "ytresa") << '\n'; //4
 system("pause>nul"); return 0;
}

6. Переставить элементы массива в обратном порядке без использования дополнительного массива.

#include <iostream>
using namespace std;
 
int main() {
 const int n=5;
 int a[n] = {1,2,3,4,5};
 for (int i = 0; i < n / 2; i++) {
  int temp=a[i]; a[i]=a[n-1-i]; a[n-1-i]=temp;
 }
 for (int i = 0; i < n ; i++) cout << a[i] << " ";
 system("pause>nul"); return 0;
}

7. Извлечь из произвольной строки все двоичные числа и показать их десятичные значения. Длина цепочки нулей и единиц ограничена 64 символами.

Из кода видно, как с помощью sregex_iterator найти все вхождения нужного регулярного выражения в строку.

#include <iostream>
#include <regex>
#include <bitset>
using namespace std;

int main() {
 const string s = "aabb10011ccdd11ee"; //данные
 regex rgx("([0-1]+)"); //шаблон двоичного числа
 smatch match;
 sregex_iterator i; //берём все вхождения rgx из s
 for (i = sregex_iterator(s.begin(), s.end(), rgx);  i != sregex_iterator(); ++i) {
  smatch m = *i;
  string sm = m.str(); //извлекаем вхождение как строку
  unsigned long long value = bitset <64> (sm).to_ullong(); //переводим в число
  cout << sm << "=" << value << endl;
 }
 
 system("pause > nul");
 return 0;
}

8. Счастливая ли Ваша дата рождения? Дата рождения "очень счастливая", если если все остатки от деления на 7 сумм цифр года, месяца и дня совпадают, "счастливая", если совпадают два любых остатка, обычная - если совпадений нет.

#include <iostream>
using namespace std;
 
int sumOfDigits(int n) {
 int s = 0;
 do {
  s += n % 10;
  n /= 10;
 } while (n);
 return s;
}
 
int main() {
 int d = 23, m = 5, y = 1990; 
 int dm = sumOfDigits(d)%7;
 int mm = sumOfDigits(m)%7;
 int ym = sumOfDigits(y)%7;
 if (dm==mm && mm==ym) cout << "Very happy";
 else if (dm!=mm && mm!=ym && ym!=dm) cout << "Unhappy";
 else cout << "Happy";
 system("pause > nul ");
 return 0;
}

9. Найти все целочисленные значения A, B, C, такие, что произведение A*B*C равно D и подсчитать количество комбинаций этих значений.

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

#include <iostream>
 
using namespace std;
 
int main() {
 int d = 296;
 int cnt = 0;
 for (int a = -d; a <= d; a++)
 for (int b = -d; b <= d; b++)
 for (int c = -d; c <= d; c++)
  if (a*b*c == d) {
   cout << endl << a << " " << b << " " << c;
   cnt++;
 }
 cout << endl << "Cnt=" << cnt;
 
 cin.get();
 return 0;
}

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

#include <cstdio>
#include <cctype>

char *trim(char* output,char* input) {
    int inputIndex = 0;
    int outputIndex = 0;
    while (isspace(input[inputIndex])) inputIndex++;
    while (input[inputIndex]) {
        output[outputIndex] = input[inputIndex];
        if (isspace(input[inputIndex])) {
            while(isspace(input[inputIndex + 1])) {
                inputIndex++;
            }
        }
        outputIndex++;
        inputIndex++;
    }
    output[outputIndex] = '\0';
    return output;
}

int main() {
    char input[] = "  2    \t\nasfa sas    f f dgdgd  dg   ggg  \t";
    char output[100];
    trim(output,input);

    puts ("Input string");
    puts(input);
    puts ("Output string");
    puts(output);

    getchar(); return 0;
}

11. Подсчитать, сколько символов строки string повторяются (встречаются в ней более 1 раза)

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

int cnt(string s) {
 set <char> set;
 for (int i = 0; i < s.length(); ++i) {
  for (int j = 0; j < i; ++j) {
   if (s[j] == s[i]) {
    if (set.find(s[i]) == set.end()) {
     set.insert(s[i]);
     cout << s[i]; //Debug
    }
   }
  }
 }
 return set.size();
}

int main() {
 string s("123  32222222222222220#!!");
 cout << endl << cnt(s);
 system("pause > nul"); return 0;
}

12. Подсчитать, сколько символов строки string уникальны (встречаются в ней ровно 1 раз)

#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

int cnt(string s) {
 set <char> set;
 for (int i = 0; i < s.length(); ++i) {
  int n = count(s.begin(), s.end(), s[i]);
  if (n == 1) {
   set.insert(s[i]);
   cout << s[i]; //Debug
  }
 }
 return set.size();
}

int main() {
 string s("123  32222222222222220#!!");
 cout << endl << cnt(s);
 system("pause > nul"); return 0;
}

Можно приспособить решение и к предыдущей задаче. Конечно, оно трудоёмко, порядка O(n²)

13. Подсчитать в строке string количество различных между собой символов.

Это решится буквально одной строкой на основе предыдущих 2 задач.

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

int cnt(string s) {
 set <char> set(s.begin(),s.end());
 for (char const& c : set) cout << c; //Печать множества char - для отладки
 return set.size();
}

int main() {
 string s("123  32222222222222220#!!");
 cout << endl << cnt(s);
 system("pause > nul"); return 0;
}

А если нужно просто вывести каждый символ строки string и количество раз, которые он встречается в строке?

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

#include <cstdlib>
#include <iostream>
#include <string>
#include <map>
#include <iterator>
using namespace std;
 
int main() {
 string s("123  32222222222222220#!!");
 
 map < char, int > mymap;
 for (int i = 0; i < s.size(); i++) mymap[s[i]] ++;
 
 for (map<char, int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
    cout << it->first << " => " << it->second << endl;
 system("pause > nul"); return 0;
}

14. Создать массив из n случайных чисел, распределённых в диапазоне значений от -d до d. Написать программу, которая подсчитывает, сколько раз указанное значение x встречается в массиве.

Используем генератор случайных чисел и алгоритм.

#include <cstdlib>
#include <iostream>
#include <random>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

int main() {
 const int d = 10; //диапазон значений
 const int n = 100; //размерность массива
 default_random_engine generator { random_device()() };
 uniform_int_distribution<> distribution(-d, d);
 vector <int> a(n);
 generate(a.begin(), a.end(), 
  [&distribution, &generator] { return distribution(generator); } //генерация значений
 );
 copy(a.begin(), a.end(), ostream_iterator<int>(cout, " ")); //вывод массива
 cout << endl;
 int x=5; //искомое значение
 cout << count(a.begin(), a.end(), x); //подсчёт и вывод
 system("pause > nul"); return 0;
}

14.04.2018, 15:07 [2353 просмотра]