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

Вопросы написания собственного программного кода (на любых языках)

Модератор: Olej

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 18 сен 2015, 11:07

Возвращаясь чуть назад ...
Olej писал(а): А теперь оригинал задачи, предложенный из Израиля:
Simplify the implementation below as much as you can.
Even better if you can also improve performance as part of the simplification!
FYI: This code is over 35 lines and over 300 tokens, but it can be written in 5 lines and in less than 60 tokens.
Так вот ...
Наши израильские друзья считают такое решение неверным – они мечтали о чём-то более кошерном :lol:
Хотя, с другой стороны, я, напротив, считаю, что они просто не умеют точно формулировать свои мечты о кошерности ... не умеют строго формализовать условие того, что они хотят.

Тестирование показывает полную эквивалентность func1() и func2().
А как говорили когда-то ;-) классики марксизма-ленинизма: "Практика - критерий истины".

Но как бы там ни было, этот инцидент подсказывает, что задача может иметь несколько интересных вариантов решения.
Предлагаю всем желающим активно заняться их поисками!

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 28 сен 2015, 10:59

Ещё одна очень интересная тема - это типы и преобразования типов.
Здесь в C++ может быть очень много классных примеров и с очень неожиданными результатами.

Мы тут даже повздорили по этой теме с одним ... преподавателем C++ для начинающих ;-) :-(

Но прежде чем писать и показывать примеры нужно выписать основные принципы типизации C++ ... чтоб со знанием дела рассуждать о преобразованиях...

1. В C++ типизация именная, в отличие от других языков, где типизация может быть структурная.
При структурной типизации переменные разных типов но описанных идентичными структурами - совместимы по присвоению.
В C++ если полностью идентичные классы названы разными именами, то переменные таких типов не совместимы по присвоению.

2. Тип переменной определяет набор (множество) тех операций и их смысл, которые можно применять к любым переменным данного типа.
Преобразование типа меняет набор допустимых операций.
Объекты данных (класса) идентичны существительным в разговорном языке, а тип этих данных определяет действия, которые можно применять к таким объектам.
Тип - яблоко: его можно кусать, резать, сушить и др.
Тип - мяч: любым объектом типа мяч можно играть ... но его нельзя кусать.

3. Если не предусмотрены специальные процедуры преобразования типов (классов), то при статическом преобразовании типа ( static_cast<...>() что мы часто делаем как префикс (type) ) структура объекта данных не меняется.
Примером преобразования данных встроенными типами (пожалуй единственным и очень неудачным) является преобразование между целыми и вещественными значениями ... да ещё и выполняющиеся неявно!
Целое 4 преобразованное в вещественное 4.0 получит совершенно иное (floating point) внутреннее представление.

4. Преобразование типов (классов) можно определить явно в коде класса. При этом преобразование может уже проделывать любые трансформации внутреннего представления объектов классов.

5. Классы C++ вообще являются продолжением и расширением понятия тип. Классы C++ не наследуются от какого-то предопределённого класса object (как в Java или Python), поэтому описание класса C++ это просто и ест описание нового типа. Естественное продолжение и ясность это нашло в языке Go, который является прямым наследником C и отчасти C++.

Этих правил достаточно, для того чтобы понимать схему типизации и преобразования типов в C++.

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

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 28 сен 2015, 12:20

Olej писал(а): 1. В C++ типизация именная, в отличие от других языков, где типизация может быть структурная.
При структурной типизации переменные разных типов но описанных идентичными структурами - совместимы по присвоению.
В C++ если полностью идентичные классы названы разными именами, то переменные таких типов не совместимы по присвоению.

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

class double1 {
   float data;
public:
   double1( double d ) { data =  d; }
};

class double2 : public double1 {
public:
   double2( double d ) : double1( d ) {};
};

class double3 : public double1 {
public:
   double3( double d ) : double1( d ) {};
};

int main() {
   double2 d2( 2. );
   double3 d3( 3. );
   d2 = d3;
   return 0;
}
Как вы видите, типы double2 и double2 совершенно идентичные, отличаются только именем.
И вот вам результат:

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

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/cast $ make
g++ -Wall     name.cc   -o name
name.cc: In function ‘int main()’:
name.cc:27:7: error: no match for ‘operator=’ (operand types are ‘double2’ and ‘double3’)
    d2 = d3;
       ^
name.cc:27:7: note: candidate is:
name.cc:14:7: note: double2& double2::operator=(const double2&)
 class double2 : public double1 {
       ^
name.cc:14:7: note:   no known conversion for argument 1 from ‘double3’ to ‘const double2&’
make: *** [name] Ошибка 1
Но:

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

class double2 {
   float data;
public:
   double2( double d ) { data =  d; }
};

typedef double2 double3;

int main() {
   double2 d2( 2. );
   double3 d3( 3. );
   d2 = d3;
   return 0;
}

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

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/cast $ g++ -Wall     name2.cc   -o name2
Потому что typedef вводит только синоним.

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 28 сен 2015, 13:04

Olej писал(а): Но прежде чем писать и показывать примеры нужно выписать основные принципы типизации C++ ... чтоб со знанием дела рассуждать о преобразованиях...
По всем остальным пунктам, начиная п.2:

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

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

class Complex : public complex<double> {
public:
   Complex( double re, double im ) : complex<double>( re, im ) {};
   operator string();
   operator double();
};

Complex::operator string() {
   char c[ 30 ];
   sprintf( c, "<%f;i*%f>", real(), imag() );
   return string( c );
}

Complex::operator double() {
   double mod = real() * real() + imag() * imag();
   return sqrt( mod );
}

int main() {
   long long e = 0x1234;
   printf( "%llx | %p | %p | %p | %p | %p \n",
           e,
           (char*)e + 1,
           (short*)e + 1,
           (int*)e + 1,
           (long long*)e + 1,
           (long double*)e + 1
         );
   long long f = 1234;
   printf( "%f | %f \n", (double)f, *(double*)&f );
   float g = 1234.;
   printf( "%ld | %ld \n", (long)g, *(long*)&g );
   int n = -1;
   cout << n << " | " << (unsigned)n << endl;
   Complex data( 3, 1 );
   cout << data << " | " << (string)data << " | " << (double)data << endl;
   return 0;
}
И вот что это даёт:

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

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/cast $ ./cast 
1234 | 0x1235 | 0x1236 | 0x1238 | 0x123c | 0x1240 
1234.000000 | 0.000000 
1234 | 1150964261 
-1 | 4294967295
(3,1) | <3.000000;i*1.000000> | 3.16228
В этом выводе:

1-я строка - если преобразовать значение к типу "указатель на ..." то смысл простейшей операции инкремента (+ 1) будет отличаться каждый раз в зависимости от того, указатель на что.
2.-я строка - как преобразовывается целое в вещественное + как это выглядело бы при неизменном содержании переменной, без действий по преобразованию формата хранения.
3-я строка - наоборот, как вещественное преобразуется типом (!) в целое, как изменяется значение (потеря дробной части), и как выглядит это вещественное без преобразования формата его хранения.
4-я строка - как выглядит одно и то же значение, но если его преобразовывать между знаковым и беззнаковым типом.
5-я строка - как определять свои преобразования типа для любых классов с любыми самыми замысловатыми операциями по преобразованию:
(3,1) - так выглядит вывод в поток типа complex<double> - его дефаултное представление;
<3.000000;i*1.000000> - так выглядит преобразование переменных класса в C++ тип string;
3.16228 - так выглядит преобразование переменных класса во встроенный тип double (это модуль комплексного числа, длина вектора ... делать так - это не лучшая идея, но как пример синтаксиса - убедительно).

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 02 окт 2015, 10:30

Olej писал(а):Задачи.
Это лучший способ освоить любой язык программирования - не читать описания, а брать и писать решение задач на нём.
Вот ещё одна славная задача попрактиковаться - возведение в степень ;-)
Как будто: да что там возводить? :-o

Но в вот такой формулировке:
- в примитивном виде, возведение в степень e**n - это последовательные n-1 умножений, в цикле...
- но умножение - дорогая, трудоёмкая операция...
- написать возведение в степень, используя минимальное число умножений!

Кажется, если я не ошибаюсь, задача эта принадлежит Хоару.
Проницательный читатель уже догадывается, что я подталкиваю его к рекурсии... И он прав! ;-)

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

#include <assert.h>
#include <iostream>

using namespace std;

double power( double a, int n, int& m ) {
   assert( n > 0 || ( a != 0.0 || n != 0 ) );
   switch( n ) {
      case 0:
         return 1;
      case 1:
         return a;
      default : {
         double a2 = power( a, n / 2, m );
         if( n & 1 ) {
            m += 2;
            return a * a2 * a2;
         }
         else {
            m++;
            return a2 * a2;                     
         }                                      
      }
   }
}

int main() {
   double e, r;
   int n, m;
   while( true ) {
      cout << "что возводить? : ";
      cin >> e;
      cout << "в какую степень? : ";
      cin >> n;
      m = 0;
      r = power( e, n, m );
      cout << e << "**" << n << "=" << r << ", число умножений " << m << endl;
   }
   return 0;
}

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

 $ ./power 
что возводить? : 2
в какую степень? : 2
2**2=4, число умножений 1
что возводить? : 2
в какую степень? : 10
2**10=1024, число умножений 4
что возводить? : 2   
в какую степень? : 1000
2**1000=1.07151e+301, число умножений 14
что возводить? : 2       
в какую степень? : 5000
2**5000=inf, число умножений 16
что возводить? : ^C
Эта очень простая задача очень понятна и убедительно показывает в чём сила рекурсии.
Попробуйте сделать такую задачу итерационно, через цикл... ... а ещё убедительнее - после того как вы это сделаете, попробуйте кому-нибудь объяснить внятно как это работает. :lol:
Вложения
power.tgz
(884 байт) 298 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 15 окт 2015, 13:25

Вот хорошая задача - имеющая большую практическую ценность: для последовательности вводимых чисел вычислить среднее и дисперсию (или СКО, средне-квадратичное отклонение, если кому так хочется ;-) ) ... но так, чтобы не хранить последовательность, за один проход.

Напомню для тех, кто не любит математику:
- для последовательности N чисел a1, a2, ... aN
- среднее значение вычисляем как M = 1/N * SUM( i=1, N, ai )
- дисперсию вычисляем как D = 1 / N * SUM( i=1, N, ( ai - M ) ** 2 )
- СКО вычисляем как S = SQRT( D )

Это классические определения... но в чём здесь загвоздка? В том, что для вычислений D нужно прежде вычислить M по всей последовательности. Но если последовательность состоит из 10000 или 100000 и т.д. значений, то хранить все их для 2-го прохода - это неразумно и нереально.
Но это можно сделать в потоке, за один проход...
Как?

Это очень частая задача в обработке данных или цифровой обработке сигналов (DSP), потому как дисперсия - это мощность сигнала.

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 15 окт 2015, 15:51

Olej писал(а): Но это можно сделать в потоке, за один проход...
Как?
Нужно просто раскрыть и преобразовать выражение под суммой для вычисления дисперсии:
D = 1 / N * SUM( i=1, N, ( ai - M ) ** 2 ) =
1 / N * SUM( i=1, N, ai ** 2 ) - 2 * M / N * SUM( i=1, N, ai ) + M ** 2 =
1 / N * SUM( i=1, N, ai ** 2 ) - M ** 2
Это нужно один раз проделать, а после запомнить навсегда ;-)

А теперь всё то же в коде:

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

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

int main() {
   string e;
   int n; // счётчик чисел
   double d, s1, s2;
   while( true ) {
      s1 = s2 = 0.0;
      n = 0;
      cout << "Вводите послдовательность чисел: ";
      getline( cin, e );
      istringstream ist( e );
      while( ist >> d ) {
        n++;
        s1 += d;
        s2 += d * d;
      }
      s1 /= n;
      s2 = s2 / n - s1 * s1;
      cout << "Введено чисел " << n << ", среднее=" << s1
           << ", дисперсия=" << s2 << endl;
   }
}
(здесь исключена обработка ошибочного ввода ... и многие другие полезные вещи)
Теперь каждое очередное число после первичного накопления сумм нам уже больше не нужно, может быть потеряно, уничтожено. Так можно обрабатывать последовательности из миллионов отсчётов ... просто перенаправлением потока ввода данных (эксперимента) из файла в командной строке запуска.
И вот что из этого получается:

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

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/sko $ ./sko
Вводите послдовательность чисел: 3 4 5
Введено чисел 3, среднее=4, дисперсия=0.666667
Вводите послдовательность чисел: 1 2 3 4 5 6 7 8 9
Введено чисел 9, среднее=5, дисперсия=6.66667
Вводите послдовательность чисел: 5 4 3 2 1 -1 -2 -3 -4 -5
Введено чисел 10, среднее=0, дисперсия=11
Вводите послдовательность чисел: ^C
Вложения
sko.tgz
(769 байт) 329 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 13 ноя 2015, 14:54

Вышла книга:
Изображение

Доусон М, "Изучаем C++ через программирование игр", ISBN: 978-5-496-01629-2, 352 страницы, август 2015, "Питер"

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 15 ноя 2015, 16:45

Одно из лучших упражнений в C++ для начинающих ... да и не только: взять самую простейшую задачу и поставить условием записать для её решения как можно больше вариантов решения ... с разными структурами данных, алгоритмами и т.д.

Как пример, вот такая элементарнейшая из элементарных задач:
Есть какое-то слово, например "home".
Необходимо заполнить этим словом (последовательно буквами этого слова) строку за определённое
количество итераций.
Т.е. для rep=19 в примере выше результатом должны быть строка "homehomehomehomehom".
Эту задачу я реально стырил с Хабрахабра (или их Тостера), где их студенты затруднялись просто вообще решить задачу хоть как...
Словесная формулировка - бездарная ... но, надеюсь, что понятно что нужно сделать.
А вот числом вариантов как это можно сделать - задача хорошая...

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 15 ноя 2015, 19:25

Olej писал(а): Словесная формулировка - бездарная ... но, надеюсь, что понятно что нужно сделать.
А вот числом вариантов как это можно сделать - задача хорошая...

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

#include <iostream>
using namespace std;

string rep1( const string& base, uint rep ) {
   string ret = "";
   for( uint i = 0; i < rep; i++ )
      ret += base[ i % base.length() ];
   return ret;
}

string rep2( const string& base, uint rep ) {
   string ret = "";
   for( uint i = 0; i < rep; i += base.length() )
      ret += rep - i > base.length() ?
             base : base.substr( 0, rep - i );
   return ret;
}

string rep3( const string& base, uint rep ) {
   string ret = "";
   for( uint i = 0; i < rep / base.length(); i++ )
      ret += base;
   return ret + base.substr( 0, rep % base.length() );
}

int main() {
   string ( *tests[] )( const string& base, uint rep ) = { // последовательность тестов
      rep1, rep2, rep3,
   };
   while( true ) {
      cout << "базовая строка?: ";
      string word;
      cin >> word;
      uint rep;
      cout << "длина результата?: ";
      cin >> rep;
      for( uint i = 0; i < sizeof( tests ) / sizeof( tests[ 0 ] ); i++ )
         cout << tests[ i ]( word, rep )<< endl;
   }
   return 0;
}

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

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/repch $ ./repch
базовая строка?: asdf
длина результата?: 23
asdfasdfasdfasdfasdfasd
asdfasdfasdfasdfasdfasd
asdfasdfasdfasdfasdfasd
базовая строка?: 1234567890
длина результата?: 5
12345
12345
12345
базовая строка?: ^C
Вложения
repch.tgz
(1 КБ) 354 скачивания
repch.cc
(1.1 КБ) 267 скачиваний

Ответить

Вернуться в «Программирование»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 11 гостей