C++ для начинающих

[Olej]

Вот такой сайт: PureCodeCPP

Сайт освещает основы программирования на языке C++, создан для начинающих программистов и желающих изучить программирование с нуля. Сейчас он находится в процессе создания. День за днём сайт будет наполняться новой интересной информацией и все неактивные пункты содержания интернет-учебника вскоре будут заполнены!

Зачем я его здесь упомнил?

По самым разным причинам:

1. Иногда спрашивают: "С чего начать C++?".
Вот с этого и начните.

2. Мне предложили написать туда некоторые темы.
Я выбрал самые ... скользкие , и к ним понаписывал уже примеры кода.
Те примеры (и, возможно, тексты ... или ссылки на их страницы), которые я для них делаю, я буду выкладывать сюда. Для возможного обсуждения и улучшения.

3. Возможно кто-то здесь подскажет темы или задачи интересные.
Тогда по ним можно будет сделать материал туда на сайт C++.

4. Наконец, они там предлагают всем желающим подзаработать ... называя эту работу копирайтером.
За копирайт везде расценки до неприличного (или до смешного) низкие, но для начинающих - это неплохой вариант попробовать себя ... "что ж ты за Сухов"(с)

[Olej]

Несколько ресурсов подобной тематики (для тех кто начинает изучать C++ ли углубляет свои умения):

Программирование на C и C++ - это книги

Программирование - это лекции (здесь, кстати, есть программирование на ассемблер в MS Visual Studio ... но это, по-моему, для особых извращенцев )

Сайты. Программирование - это сайт ... игрнов ,но здесь даётся перечень ресурсов

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

[Olej]

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

Указатели на объекты

Текст на страничке

Архив вот здесь...

[Olej]

Указатели на функции

Опять же :

Текст на страничке
Архив вот здесь...

[Olej]

1. Иногда спрашивают: "С чего начать C++?".
Вот с этого и начните.

Я от себя добавлю вот такое замечание ... которое не решается опубликовать ни один ресурс по программированию C или C++:

1. Вся кухня с языками программирования начиналась с теории компиляции, компиляторов, компилирующих языков программирования: Algol, FORTRAN, COBOL, PASAL, Modula 2/3 и т.д.
Но на сегодня из более 2-х десятков языков программирования, используемых в практических проектах, осталась фактически одна линия развития компилирующих языков: C - C++ - Go.
Все остальные используемые современные ЯП в той или иной степени интерпретирующие (или интерпретирующие исходный код, или некоторый промежуточный байт-код): Java, Python, Ruby, ... и т.д. - "имя им - легион".

2. Поэтому для глубокого понимания особо интересно сравнивать реализации механизмов в языках этой линии развития: C - C++ - Go.
Учитывая годы появления каждого из них на арене: C - 1970г., C++ - 1985г., Go - 2009г.
Очень интересно проследить как трансформировались со временем понятия "что языку не хватает" и "что в нём лишнее".
Особенно учитывая, с C++ Страуструп начинал как прямую эволюцию C, а Go начинали разрабатывать (на уровне закладывания идеологии) те же люди, которые по молодости создавали язык C ... прям по А.Дюма: "40 лет спустя" или "как бы мы это сделали сегодня".

3. Адепты C++ сиьно отмахиваются от C. Но C++ это как-раз именно надмножество языка C. Об этом пишет не раз и Страуструп, и говорит тот факт, что очень редкую программу (специально для того написанную) на C нельзя скомпилировать (вызовет ошибки) компилятором g++.
Кроме того, из кода C++ можно использовать все библиотечные вызовы стандартной библиотеки C (POSIX).
Меня, кроме того, сильно удивляет, что многие профессиональные разработчики C++ не знают такой простой вещи:
- компилированная программа C++ при выполнении использует не только свою собственную разделяемую библиотеку (разные в зависимости от компиляторов GCC или Clang), но и стандартную библиотеку C (libc.so) - программа компонуется с ней;
- весь интерфейс к системным вызовам Linux осуществляет именно libc.so - библиотеки C++ ничего не знают о системных вызовах ОС;
- при отсутствии стандартную библиотеки C (по доступным путям поиска) программа C++ просто не будет выполняться, будет завершаться аварийно.

4. Это я написал для того, чтобы предположить, что те компоненты, которые C++ наследует из C (типы скалярных данных, операторы, указатели, структур), лучше детально изучать именно по литературе по C. Вопрос - как? (его часто задают и обсуждают ... "можно ли изучать C++ не зная C?").
Наверное, лучший способ: быстро пробежать наследуемые из C возможности, и переходить к специфике C++ (классы, наследование, виртуализация, полиморфизм, темплейты, ...).
А потом позже вернуться к описаниям C, чтобы детально уточниться с его наследием.

5. И очень интересно хотя бы пробежать описания языка Go ... даже если не собираться его использовать.
Посмотреть как другими способами покрываются громоздкие и небезопасные возможности C++ в новой пересмотренной идеологии:
- множественные присвоения и возвраты из функций;
- полный отказ от асинхронной обработки исключений и событий (catch, try, ... etc.);
- и мн. другое.

[Olej]

Задачи.

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

1. Ханойская башня - блистательный пример возможностей рекурсивных вычислений.

2. Решето Эратосфена (фильтр) нахождения всех простых чисел не превосходящих числа N.

В каждом архиве внутри, если кому это интересно, есть .odt (OpenOffice) файл с текстовым описанием, поэтому здесь уточнения ни к чему.

[Olej]

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

P.S. Про Класс NP, NP-полная задача и т.д. - можете почитать по ссылкам для начального знакомства, это терминологические вещи из теории алгоритмов, сложная абстрактная математика ... но к существу наших проблем не имеющая почти никакого касательства (про почти - чуть позже).

1. Задача о ранце

Название своё получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен.
...
В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.

2. поиск максимального подмассива - из-за этой темы, собственно, я и вспомнил целый класс этих задач, но изложение там в теме - безобразное, разве что ссылки на источники, а строгое описание задачи Maximum subarray problem:

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Вольный перевод мой:

Проблемой максимального подмассива является задача нахождения непрерывного подмассива в пределах исходного одномерного массива чисел, содержащего по крайней мере одно положительное число, который (подмассив) имеет самую большую сумму. Например, для последовательности значений -2, 1, -3, 4, -1, 2, 1, -5, 4; непрерывный подмассив с наибольшей суммой составляет 4, -1, 2, 1, с суммой 6.

3. Задача о сумме подмножеств (похожа на предыдущую, но является её более общей формулировой):

Задача заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел этого подмножества равнялась нулю. Например, пусть задано множество { −7, −3, −2, 5, 8}, тогда подмножество { −3, −2, 5} дает в сумме ноль.
Эквивалентной является задача нахождения подмножества, сумма элементов которого равна некоторому заданному числу s. Задачу о сумме подмножеств также можно рассматривать как некоторый специальный случай задачи о ранце.

У этих задач много общего:
- они имеют большое практическое применение ... в экономике-финансах, криптографии и др. - это не пусты олимпиадные задачи "про зайчика"
- для них просятся, в 1-м приближении, рекурсивные решения
- простые решения этих задач имеют настолько высокую скорость роста O(N), что не представляют практической ценности ... а их эффективные решения настолько сложны, что найденные алгоритмы называют по имени авторов

Ну и последнее...
Эти задачи не совсем удобны для решения на C++ (и особенно на C) для них более подходящими будут динамические языки типа Python или Go.
Но они хороши для практики в языке ... любом.
Здесь я их разместил только потому ... что эта тема по времени последняя (в сравнении с темами-задачниками по другим языкам в форуме).

[Olej]

2. поиск максимального подмассива - из-за этой темы, собственно, я и вспомнил целый класс этих задач, но издожение там в теме - безобразное, разве что ссылки на источники, а строгое описание задачи Maximum subarray problem:

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

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

Ввод исходных данных и для этой и для всех задач этой группы можем оставить примерно однотипным:

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

#include <stdlib.h> 
#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
using namespace std;

vector<double> input( char *file ) {
   double data;
   vector<double> arr;
   if( file != NULL ) {
      ifstream fin;
      fin.open( file );
      if( !fin ) {
         cerr << "ошибка открытия " << file << endl;
         exit( 1 );
      }
      while( true ) {
         fin >> data;
         if( fin.eof() ) break;
         arr.push_back( data );
      }
      fin.close();
   }
   else {
      cout << "вводите числа через пробел (Enter + ^D для завершения):" << endl;
      while( true ) {
         cin >> data;
         if( cin.eof() ) break;
         arr.push_back( data );
      }
   }
   return arr;
}

int main( int argc, char **argv, char **envp ) {
   vector<double> arr = input( argv[ 1 ] );
   cout << "массив [" << arr.size() << "]: ";
   for( vector<double>::iterator i = arr.begin(); i != arr.end(); i++ )
      cout << *i << " ";
   cout << endl;

Если в команде не указано параметром имя файла, то данные запрашиваются и вводятся с терминала: произвольное число чисел, разделяемых пробелом, с любыми переводами строк (данных много) и ^D (EOF) как признак конца данных.
Если имя файла указано параметром, то данные в том же виде считываются из заготовленного файла.
А алгоритм полного перебора следует далее:

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

   double suma = -numeric_limits<double>::max();
   uint nb = -1, ne = -1;
   for( uint ib = 0; ib < arr.size(); ib++ )
      for( uint ie = 0; ie < arr.size(); ie++ ) {
         double loc = 0.;
         for( uint j = ib; j <= ie; j++ )
            loc += arr[ j ];
         if( loc > suma ) {
            suma = loc;
            nb = ib;
            ne = ie;
         }
      }
   cout << "максимальная сумма " << suma << ": ";
   for( uint j = nb; j <= ne; j++ )
      cout << arr[ j ] << " ";
   cout << endl;
   return 0;
}

Готовим файл данных, тех же что в описании:

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

olej@nvidia ~/2015_WORK/in.WORK/subarray $ cat a1.dat
-2 1 -3 4 -1 2 1 -5 3

И выполнение:

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

olej@nvidia ~/2015_WORK/in.WORK/subarray $ ./suba_cc a1.dat 
массив [9]: -2 1 -3 4 -1 2 1 -5 3 
максимальная сумма 6: 4 -1 2 1 

В точности то же, что и в описании.

А вот теперь настоящая задача : сделайте этот алгоритм эффективным.

[Olej]

1. Задача о ранце

Название своё получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен.
...
В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.

Это вообще знаменитая задача!
И имеющая, кроме того, огромное практическое значение (например, на ней построено несколько алгоритмов криптографии).

Опять же, показываю :
- наихудший вариант (даже худший худшего полного перебора! ) ... чтоб был простор для улучшения алгоритма;
- заготовку программы, в которой можно легко заменить сам алгоритм поиска, оставив всю рутину как обрамление (ввод исходных последовательностей, их вывод для диагностики, изменение уровня отладочного вывода и т.д.).

Вот такой вариант (но не советую рассматривать его здесь - скачайте код или весь архив, в архиве тестовые наборы):

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

#include <stdlib.h> 
#include <getopt.h>
#include <iostream>
#include <fstream>
#include <list>
#include <limits>
using namespace std;

// Задача о ранце: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D0%B0%D0%BD%D1%86%D0%B5

int debug_level = 0;                           // уровень отладосного вывода

struct entity {
   bool bGood;
   double cost, weight;                        // стоимость и вес
   entity( double cost = 0, double weight = 0 ) { this->cost = cost; this->weight = weight; }
   inline entity& operator +=( entity& add ) {
      this->cost += add.cost;
      this->weight += add.weight;
      return *this;
   }
   friend inline ostream& operator << ( ostream& stream, entity obj ) {
      return stream << "{" <<  obj.cost << ":" << obj.weight << "}"; 
   };
   friend istream& operator >> ( istream& stream, entity& obj );
};

inline istream& operator >> ( istream& stream, entity& obj ) {
   double c, w;
   string s;
   obj.bGood = false;                          // флаг неправильного ввода 
   if( ( stream >> c ).eof() ) return stream;  // ввод cost
   if( stream.rdstate() & ios::failbit ) {
      cerr << "ошибка ввода!" << endl;
      stream.clear();
      getline( stream, s );
      return stream;
   }
   if( c <= 0 ) {
      cerr << "ошибка ввода: " << c << endl;
      return stream;
   }   
   if( ( stream >> w ).eof() ) return stream;  // ввод weight
   if( stream.rdstate() & ios::failbit ) {
      cerr << "ошибка ввода!" << endl;
      stream.clear();
      getline( stream, s );
      return stream;
   }
   if( w <= 0 ) {
      cerr << "ошибка ввода: " << w << endl;
      return stream;
   }   
   getline( stream, s );
   if( !s.empty() ) {                          // если введено больше 2-значений
      basic_string<char>::iterator i;
      for( i = s.begin(); i != s.end() && *i == ' '; i++ );
      if( i != s.end() ) {                     // если там непробельные символы
         cerr << "ошибка ввода: " << s << endl;
         return stream;
      }
   }
   obj = entity( c, w );
   obj.bGood = true;
   return stream;
};

//---------------------------------- end struct entity ------------------------------

class set : public list<entity> {
private:
   set *result;
   set packlvl( int level, double volume, double& cost, set& globl );
public:
   static ulong counter;
   friend set packlvl( int level, double volume, set& list );
   set( void ) : list<entity>() {};            // пустой список предметов
   set( char *file );                          // ввод писка предметов
   entity summa( void ) {
      entity res;
      for( list<entity>::iterator i = begin(); i != end(); i++ ) 
         res += *i;
      return entity( res );
   }
   set pack( double volume ) { 
      counter = 1;
      set ret;
      double cost = 0;
      packlvl( 0, volume, cost, ret );
      return ret;
   }
   friend ostream& operator <<( ostream& stream, set* obj );
   friend inline ostream& operator <<( ostream& stream, set& obj ) {
      return stream << &obj;
   }
};

ulong set::counter;                            // счётчик перебранных вариантов

set::set( char *file ) {                       // ввод полного набора предметов
   entity data;
   if( file != NULL ) {
      ifstream fin;
      fin.open( file );
      if( !fin ) {
         cerr << "ошибка открытия " << file << endl;
         exit( 1 );
      }
      while( true ) {
         fin >> data;
         if( fin.eof() ) break;
         if( data.bGood ) push_back( data );
      }
      fin.close();
   }
   else {
      cout << "вводите пары чисел (стоимость, вес) через пробел (^D для завершения):" << endl;
      while( true ) {
         cin >> data;
         if( cin.eof() ) break;
         if( data.bGood ) push_back( data );
      }
   }
}

ostream& operator << ( ostream& stream, set* obj ) {
   if( obj->empty() )
      return stream << "{}";
   for( list<entity>::iterator i = obj->begin(); i != obj->end(); i++ ) 
      stream << *i << " ";
   return stream;
}

set set::packlvl( int level, double volume, double& cost, set& globl ) {
   set ret;
   level++;
   if( debug_level > 1 ) {
      for( int i = 0; i < level; i++ ) cout << "----";
      cout << "> " << this << endl;
   }
   for( list<entity>::iterator i = begin(); i != end(); i++ ) {
      set child;
      for( list<entity>::iterator j = begin(); j != end(); j++ ) 
         if( j != i ) child.push_back( *j );
      if( child.empty() ) ret = child;
      else {
         ret = child.packlvl( level, volume, cost, globl );
         counter++;
      }
      ret.push_front( *i );
      entity sum = summa();
      bool next = sum.weight <= volume && sum.cost > cost;
      if( debug_level > 2 ) {
         cout << '<';
         for( int i = 0; i < level; i++ ) cout << "----";
         cout << " " << ret << "| cost=" << cost << " "
              << sum << ( next ? "+"  : "-" ) << endl;
      }
      if( sum.weight <= volume && sum.cost > cost ) {
         cost = sum.cost;
         globl = ret;
      } 
   }
   level--;
   return ret;
}

//------------------------------------ end class set --------------------------------

int main( int argc, char **argv, char **envp ) {
   char c;
   while( -1 != ( c = getopt( argc, argv, "hv" ) ) )
      switch( c ) {
         case 'v':
            debug_level++;
            break;
         case 'h':
         default :
            cerr << "запуск: " << argv[ 0 ] 
                 << " [-v...][-h] <вместительность> [<файл предметов>]" << endl;
            if( c != 'h' ) return( EXIT_FAILURE );
      }
   if( argc - optind < 1 || argc - optind > 2 ) // 1 или 2 параметра
      cerr << "запуск: " << argv[ 0 ] 
           << "[-v...][-h] <вместительность> [<файл предметов>]" << endl,
      exit( EXIT_FAILURE );
   double volume = atof( argv[ optind ] );
   set arr( argc - optind > 1 ? argv[ optind + 1 ] : NULL );
   cout << "набор [" << arr.size() << "]: " << arr
        << "при вместительности " << volume << endl;
   if( debug_level > 0 ) cout << "суммарно весь набор = " << arr.summa() << endl; 
   set res = arr.pack( volume );
   cout << "решение [" << res.size() << "]: " << res 
        << "- результат: " << res.summa() << endl;  
   if( debug_level > 0 ) cout << "число циклов перебора = " << set::counter << endl;
   return 0;
}

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

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

olej@nvidia ~/2015_WORK/in.WORK/NP/backpack $ ./bpack_cc 11 a2.dat
набор [3]: {3:3} {4:4} {5:5} при вместительности 11
решение [2]: {4:4} {5:5} - результат: {9:9}

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

olej@nvidia ~/2015_WORK/in.WORK/NP/backpack $ ./bpack_cc 11 a2.dat -v
набор [3]: {3:3} {4:4} {5:5} при вместительности 11
суммарно весь набор = {12:12}
решение [2]: {4:4} {5:5} - результат: {9:9}
число циклов перебора = 10

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

olej@nvidia ~/2015_WORK/in.WORK/NP/backpack $ ./bpack_cc -vv 11 a2.dat
набор [3]: {3:3} {4:4} {5:5} при вместительности 11
суммарно весь набор = {12:12}
----> {3:3} {4:4} {5:5}
--------> {4:4} {5:5}
------------> {5:5}
------------> {4:4}
--------> {3:3} {5:5}
------------> {5:5}
------------> {3:3}
--------> {3:3} {4:4}
------------> {4:4}
------------> {3:3}
решение [2]: {4:4} {5:5} - результат: {9:9}
число циклов перебора = 10

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

olej@nvidia ~/2015_WORK/in.WORK/NP/backpack $ ./bpack_cc 11 -vvv a2.dat
набор [3]: {3:3} {4:4} {5:5} при вместительности 11
суммарно весь набор = {12:12}
----> {3:3} {4:4} {5:5}
--------> {4:4} {5:5}
------------> {5:5}
<------------ {5:5} | cost=0 {5:5}+
<-------- {4:4} {5:5} | cost=5 {9:9}+
------------> {4:4}
<------------ {4:4} | cost=9 {4:4}-
<-------- {5:5} {4:4} | cost=9 {9:9}-
<---- {3:3} {5:5} {4:4} | cost=9 {12:12}-
--------> {3:3} {5:5}
------------> {5:5}
<------------ {5:5} | cost=9 {5:5}-
<-------- {3:3} {5:5} | cost=9 {8:8}-
------------> {3:3}
<------------ {3:3} | cost=9 {3:3}-
<-------- {5:5} {3:3} | cost=9 {8:8}-
<---- {4:4} {5:5} {3:3} | cost=9 {12:12}-
--------> {3:3} {4:4}
------------> {4:4}
<------------ {4:4} | cost=9 {4:4}-
<-------- {3:3} {4:4} | cost=9 {7:7}-
------------> {3:3}
<------------ {3:3} | cost=9 {3:3}-
<-------- {4:4} {3:3} | cost=9 {7:7}-
<---- {5:5} {4:4} {3:3} | cost=9 {12:12}-
решение [2]: {4:4} {5:5} - результат: {9:9}
число циклов перебора = 10

Как понятно, здесь исходный набор данных берётся из тестового файла a2.dat, а вместительность ранца - 1-м параметром запуска.
При желании, тестовый набор можно вводить и с терминала:

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

olej@nvidia ~/2015_WORK/in.WORK/NP/backpack $ ./bpack_cc 80. -vv
вводите пары чисел (стоимость, вес) через пробел (^D для завершения):
61 21
91 31
101 51
набор [3]: {61:21} {91:31} {101:51} при вместительности 80
суммарно весь набор = {253:103}
----> {61:21} {91:31} {101:51}
--------> {91:31} {101:51}
------------> {101:51}
------------> {91:31}
--------> {61:21} {101:51}
------------> {101:51}
------------> {61:21}
--------> {61:21} {91:31}
------------> {91:31}
------------> {61:21}
решение [2]: {61:21} {101:51} - результат: {162:72}
число циклов перебора = 10

[Olej]

1. Задача о ранце

Название своё получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен.
...
В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.

Это вообще знаменитая задача!
И имеющая, кроме того, огромное практическое значение (например, на ней построено несколько алгоритмов криптографии).

Это вообще замечательная (одна из лучших!) задач для экспериментирования и совершенствования в технике, например, C++ - тем, что кроме множества алгоритмов, существует ещё и множество вариантов формулирования задач:
- Произвольное количество экземпляров каждого предмета из набора можно укладывать в рюкзак;
- Не более заданного числа экземпляров каждого предмета из набора можно укладывать в рюкзак;
и др.