примеры задач при изучении C++

[Olej]

4-й транш: указатели и адресная арифметика.

5-я группа ... некоторые библиотечные механизмы.

Некоторые - это:
- строки ... string, но не только ... и char[] в сообществе с string;
- потоковый ввод-вывод (<<, >>, и т.д.), как терминальный, так и файловый;
- параллельные потоки, класс thread:: ...

строки:

1. Реализовать построчное (!) чтение из текстового файла,
с поиском всех вхождений заданного фрагмента в каждой считанной строке.

2. То же, что и п.1, но использовать не string, а char[].

3. 3. То же, что и п.1, но искать не вхождения вообще фрагмента текста (!), а
отдельного слова (токена).

Контроль:
Например, найти "name":
- string name aaa - здесь ОК
- this is namespase aaa - а здесь нет вхождения слова
- this is left-name - и здесь нет
- find name, or return false - а здесь опять же ОК

string.tgz

(1.28 КБ) 472 скачивания

ввод-вывод:

1. 1. Реализовать функциональный эквивалент утилиты cat (при вводе в cat с терминала - повторитель ввода), предполагаем работу только с латиницей (cin -> cout), ввод построчный (!).
В качестве буфера ввода использовать char[].
Отработать конец ввода: ^D.
Выводить длину введенной строки.
Посмотреть длину введенной строки для русскоязычного ввода. Почему несоответствие?

1.2. То же, что п.1.1, но в качестве буфера ввода использовать string.

2. Классы ifstream, ofstream ...
Реализовать эквивалент cp для побайтового копирования произвольного бинарного (или текстового) файла.

3. Реализовать построчное (!!!) копирование для тестовых файлов.
(учесть, что последняя строка может быть без завершающего '\n')

4. То же. что п.1, но обеспечить работу с символами UNICODE в кодировке UTF-8 (wcin -> wcout не подходит ... почему?).
Обеспечить корректную работу с русскими строками (длина, поиск, ...).

5.1. Создать собственную структуру (!!!) с несколькими полями.
Для переменных такой структуры определить собственные операции (функции) ввода и вывода ( <<, >>).
Реализовать программу, заполняющую в диалоге экземпляр структуры.

5.2. Как в пред. п., создать собственный класс (!!!) с несколькими полями.
Для переменных этого класса собственные операции (методы) ввода и вывода ( <<, >>) ввести в определения класса.
Реализовать программу, заполняющую в диалоге экземпляр класса.

wrapers.ios.tgz

(2.7 КБ) 489 скачиваний

P.S. Этот каталог-архив у меня называется wrapers.ios, потому что это только С++ обёртки для системных вызовов библиотеки С из определений <fcntl.h> (int open() и т.д.), а ещё больше из <stdio.h> (FILE *fopen() и т.д.).
Это же касается класса thread:: <thread>, который есть ни чем большим, чем обёрткой POSIX pthread_t.
Только авторы C++ сильно это ... не афишируют, чем вносят изрядную невнятицу для изучающих C++.

wrapers.thread.tgz ещё совсем не готов, и будет добавлен позже.

[Olej]

wrapers.thread.tgz ещё совсем не готов, и будет добавлен позже.

1. Создать несколько потоков на исполнение.
Передать потоковой функции каждого потока разный набор параметров (разный
прототип функций).
Синхронизировать ожидание завершения всех потоков.
Проследите порядок старта сообщений потоков при повторных запусках.

2. Атомарные переменные.
Создать вектор потоков (vector<thread>) произвольной размерности.
В потоках инкрементировать (без синхронизаций) глобальную атомарную переменную
и локальную атомарную переменную передаваемую как параметр функции потока.
Убедиться, что гонок не возникает.

3. При выполнении приложения п.2 максимальное число конкурирующих потоков
может быть ограничено (например величиной порядка 200).
Снимите это ограничение.
Подсказка: команда ulimit

4. Числом используемых задачей процессоров (ядер) можно управлять командой
taskset.
Выполните хронометраж задачи предыдущего пункта на разном числе процессоров.

5. Любую задачу в Linux можно выполнить (или перевести) в режим реалтайм
планирования (вместе с её потоками) с управляемым приоритетом реалтайм,
вытесняющим обычные задачи - команда chrt (только как root).
Выполните задачу пред. п.

[Olej]

wrapers.thread.tgz ещё совсем не готов, и будет добавлен позже.

Туда же, в эту группу добавлен process.tgz - всё что связано с дочерними процессами ... и вообще с процессами.
Первоначально это планировалось в архив wrapers.thread.tgz, но там уже много.

Пока скромно :

1. Написать приложение, запускающее дочерний процесс, записанный его параметрами.
Дочерний процесс должен получать все свои опции и параметры.

[Olej]

Если кому захочется попрактиковаться в C++, то вот здесь лежит >60 формулировок задач, на которых можно "порепетировать": Задачи C++.
Большая часть из них неинтересны ... высосаны из пальца ... но есть и любопытные постановки задач.

[Olej]

Ещё набор уроков + задач по C++ для изучающих язык и применения выплыли (после большого перерыва) из-за контактов с сайтом для школьников C++ для начинающих.

Чтобы не дублировать или не сливать однотипные материалы, сохраним, по крайней мере, связь по ссылке.

[Olej]

На Хабрахабр опубликовали 3 задачи ... такого соревновательного, олимпиадного уровня - Две задачи HeadHunter на Data Science Week: попробуйте решить сами:

В конце августа после серии бесплатных лекций на Data Science Week 2015, организаторы решили провести двухдневный дататон (datathon) – соревнование, где команды программистов и аналитиков решали бизнес-задачи из области Data Science.

На дататоне было три задачи, две из которых подготовила команда HeadHunter и одну компания OZON. Это было, сразу скажу, не самым простым заданием, потому как большая часть наших данных конфиденциальна. Никто не захочет, чтобы программисты и аналитики упражнялись на реальных резюме или закрытых данных по вакансиям. Но кое-что мы все же собрали. Для проверки результатов организаторы написали чекеры.

[Olej]

Эта задача взята из другой здесь темы: идеи задач на C для начинающих

нужно программно определить период периодической дроби и вывести в формате a,(per).
Сложность состоит в том, что система счисления произвольная и выбирается случайно.

Алгоритм решения прост, известен из элементарной математики (см. например, здесь Обращение обыкновенных дробей в десятичные и обратно - простенько и со вкусом ):
- Возьмём к примеру 1/3 в десятичной системе счисления.
- Находим остаток от деления числителя на знаменатель - 1 % 3 = 1. Это число у нас будет выступать в качестве начального значения.
- Сохраняем остатки на каждом шаге.
- Умножаем остаток на основание системы счисления (у нас десятичная) - 1*10 = 10
- Повторяем нахождение остатка от деления числа на знаменатель - 10 % 3 = 1
- Если остаток на каком-то шаге равен нулю, то дробь конечная.
- Иначе ищем остаток в числе ранее сохранённых. Если нашли, то мы нашли период (дальше всё будет периодически повторяться).
- Иначе сохраняем текущий остаток и возвращаемся к вычислению следующего разряда.

А вот реализация этого простого алгоритма достаточно хлопотная...

[Olej]

А вот реализация этого простого алгоритма достаточно хлопотная...

Код: Выделить всё

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

typedef unsigned long long data_t;

inline char simb( data_t val ) {
   return val < 10 ? '0' + val : 'A' + val - 10;
}

// только для отладки:
ostream& operator << ( ostream& stream, vector<data_t>& obj ) {
   stream << "{[" <<  obj.size() << "]: ";
   for( vector<data_t>::iterator i = obj.begin(); i != obj.end(); i++ )
      stream << *i << ( i + 1 != obj.end() ? ", " : " " ); 
   return stream << "}";
};

int main( int argc, char **argv ) {
   bool debug = argc > 1;
   while( true ) {
      int metr;
      cout << "система счисления (2...)?: ";
      cin >> metr;
      data_t ch, zn;
      cout << "числитель (1...)?: ";
      cin >> ch;
      cout << "знаменатель (" << ch + 1 << "...)?: ";
      cin >> zn;
      if( ch >= zn ) {
         cout << "должнв быть правльная дробь!" << endl;
         continue;
      }
      string sval( "0." );
      vector<data_t> list;
      data_t ost = ch % zn;
      while( true ) {
         data_t ch = ost * metr; 
         ost = ch % zn;
         sval.push_back( simb( ch / zn ) );
         if( debug ) cout << ost << " -> " << list << endl;
         if( 0 == ost ) break;
         vector<data_t>::iterator it = find( list.begin(), list.end(), ost );
         if( it == list.end() ) 
            list.push_back( ost );
         else {
            ost = list.end() - it;
            break; 
         }
      };
      if( ost != 0 ) { // периодическая дробь, ost - период
         string::iterator is = sval.end() - ost;
         sval.insert( is, '(' );
         sval += ")";
      }
      cout << "длина периода " << ost << " : "
           << ch << " / " << zn << " = " << sval << endl;
   }
}

Как вы понимаете, всё до цикла while() - это ввод данных и т.п., всей реализации - 12 строк.

Код: Выделить всё

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/period $ ./periodf
система счисления (2...)?: 2
числитель (1...)?: 17
знаменатель (18...)?: 47
длина периода 23 : 17 / 47 = 0.0(10111001001100010000010)
система счисления (2...)?: 10
числитель (1...)?: 53
знаменатель (54...)?: 59
длина периода 58 : 53 / 59 = 0.8(9830508474576271186440677966101694915254237288135593220338)
система счисления (2...)?: 10
числитель (1...)?: 2
знаменатель (3...)?: 5
длина периода 0 : 2 / 5 = 0.4
система счисления (2...)?: 3
числитель (1...)?: 1
знаменатель (2...)?: 9
длина периода 0 : 1 / 9 = 0.01
система счисления (2...)?: ^C

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

Код: Выделить всё

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/period $ ./periodf -v
система счисления (2...)?: 10
числитель (1...)?: 11
знаменатель (12...)?: 13
6 -> {[0]: }
8 -> {[1]: 6 }
2 -> {[2]: 6, 8 }
7 -> {[3]: 6, 8, 2 }
5 -> {[4]: 6, 8, 2, 7 }
11 -> {[5]: 6, 8, 2, 7, 5 }
6 -> {[6]: 6, 8, 2, 7, 5, 11 }
длина периода 6 : 11 / 13 = 0.8(461538)

[Olej]

Как вы понимаете, всё до цикла while() - это ввод данных и т.п., всей реализации - 12 строк.

Но только на каждом шаге мы должны искать (алгоритм find()) очередной остаток во всём массиве (векторе).
Это расточительно. Зная, как работает алгоритм, можно пойти на такой трюк:
- для знаменателя N остаток может иметь только N значений 0...N
- создадим массив из N элементов, и разметим его значением -1, которое означает "такое значение остатка ещё не встречалось"...
- а вот если на очередном шаге мы получим значение M, то в элемент [M] массива запишем номер итерации, на котором было это значение...
- теперь, если после очередного шага, мы получим значение K, то нам не нужно искать это значение во всём массиве, а нужно только проверить элемент [K] массива на его положительность.
И вот что из этого получается:

Код: Выделить всё

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

typedef unsigned long long data_t;

inline char simb( data_t val ) {
   return val < 10 ? '0' + val : 'A' + val - 10;
}

// только для отладки:
string show( long long arr[], data_t size ) {
   char str[ 1000 ];
   strcpy( str, "{ ");
   for( data_t i = 0; i < size; i++ )
      if( arr[ i ] < 0 ) strcat( str, ". " );
      else sprintf( str + strlen( str ), "%lld ",  arr[ i ] );
   strcat( str, "}" );
   return string( str );
}

int main( int argc, char **argv ) {
   bool debug = argc > 1;
   while( true ) {
      int metr;
      cout << "система счисления (2...)?: ";
      cin >> metr;
      data_t ch, zn;
      cout << "числитель (1...)?: ";
      cin >> ch;
      cout << "знаменатель (" << ch + 1 << "...)?: ";
      cin >> zn;
      if( ch >= zn ) {
         cout << "должнв быть правльная дробь!" << endl;
         continue;
      }
      string sval( "0." );
      data_t ost = ch % zn;
      long long *list = new long long [ zn ];
      for( data_t i = 0; i < zn; i++ ) list[ i ] = -1;
      for( int i = 0; ; i++ ) {
         data_t ch = ost * metr; 
         ost = ch % zn;
         sval.push_back( simb( ch / zn ) );
         if( debug ) cout << ost << " -> " << show( list, zn ) << endl;
         if( 0 == ost ) break;
         if( list[ ost ] < 0 ) 
            list[ ost ] = i;
         else {
            ost = i - list[ ost ];
            break; 
         }
      };
      delete [] list;
      if( ost != 0 ) { // периодическая дробь, ost - период
         string::iterator is = sval.end() - ost;
         sval.insert( is, '(' );
         sval += ")";
      }
      cout << "длина периода " << ost << " : "
           << ch << " / " << zn << " = " << sval << endl;
   }
}

Код: Выделить всё

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/period $ ./perioda -v
система счисления (2...)?: 10
числитель (1...)?: 1
знаменатель (2...)?: 12
10 -> { . . . . . . . . . . . . }
4 -> { . . . . . . . . . . 0 . }
4 -> { . . . . 1 . . . . . 0 . }
длина периода 1 : 1 / 12 = 0.08(3)
система счисления (2...)?: 10
числитель (1...)?: 11
знаменатель (12...)?: 13
6 -> { . . . . . . . . . . . . . }
8 -> { . . . . . . 0 . . . . . . }
2 -> { . . . . . . 0 . 1 . . . . }
7 -> { . . 2 . . . 0 . 1 . . . . }
5 -> { . . 2 . . . 0 3 1 . . . . }
11 -> { . . 2 . . 4 0 3 1 . . . . }
6 -> { . . 2 . . 4 0 3 1 . . 5 . }
длина периода 6 : 11 / 13 = 0.8(461538)
система счисления (2...)?: 10
числитель (1...)?: 2
знаменатель (3...)?: 5
0 -> { . . . . . }
длина периода 0 : 2 / 5 = 0.4
система счисления (2...)?: ^C

[Olej]

А вот реализация этого простого алгоритма достаточно хлопотная...

А вот наоборот - задача проще не бывает. Но занятная по формулировке: гипотеза Коллатца – это одна из нерешённых проблем в математике с 1937 года (Гипотеза Коллатца, Collatz conjecture), которую математики не могут ни доказать, ни опровергнуть. Гипотеза состоит в том, для любого натурального числа n>1 последовательное применение функции:


– приведёт к числовому ряду, который, в конечном итоге (рано или поздно) приведёт к числу 1 (то есть, на каждом шаге преобразований для чётных значений следующим шагом вычисляется n/2, а для нечетных – 3n+1). Например, для n=3 это будет ряд преобразований: 3,10,5,16,8,4,2,1. Для некоторых n эта последовательность чисел будет весьма короткой, но для некоторых – очень длинной…

Наше задание не в том, чтобы решить задачу, которую все математики мира не могут решить 80 лет (это уже на любителя ), а в том, чтобы для любого n построить цепочку числовых для такого преобразования (то, что математики называют: чи́сла-гра́дины).

Конечно, как и раньше, одним из критериев качества решения будет: код должен быть записан как можно короче.

Вариант решения:

Код: Выделить всё

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

// гипотеза Коллатца 
void collatz( unsigned long val ) {
   cout << val << " => [";
   while( true ) {
      val = val & 1 ? 3 * val + 1 : val >> 1;
      cout << val << ( val > 1 ? "," : "]\n" );
      if( 1 == val ) return;
   }
}

int main() {
   string e;
   unsigned long d;
   while( true ) {
      cout << "Вводите натуральные числа: ";
      getline( cin, e );
      istringstream ist( e );
      while( ist >> d )
        collatz( d );
   }
}

Выглядит это так:

Код: Выделить всё

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/Collatz $ ./collatz 
Вводите натуральные числа: 6 19
6 => [3,10,5,16,8,4,2,1]
19 => [58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
Вводите натуральные числа: 27
27 => [82,41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
Вводите натуральные числа: 83
83 => [250,125,376,188,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
Вводите натуральные числа: 84
84 => [42,21,64,32,16,8,4,2,1]
Вводите натуральные числа: ^C