Rating@Mail.ru

Форум по операционной системе GNU/Linux и свободному программному обеспечению


Текущее время: 19 июн 2018, 13:33

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу Пред.  1, 2, 3, 4, 5  След.
Автор Сообщение
 Заголовок сообщения: Re: примеры задач при изучении C++
Непрочитанное сообщениеДобавлено: 13 ноя 2015, 03:27 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10806
Откуда: Харьков
Хорошая задача для самых начинающих ;-) ...

Вводится целое число.
Подсчитайте программно сколько раз в его десятичную запись входит некоторая цифра, скажем 3. Вот и всё условие. Например: 123 -> 1; 54321345 -> 2; 3333 -> 4 и т.д.

Задача очень простая … на уровне средней (сельской ;-) ) школы. Но для того, чтобы задачу сделать не совсем уж примитивной – усложним её так:
– предложите несколько (как можно больше) разных способов реализации;
– для каждой реализации сократите запись кода так, чтобы он был, как можно более кратким.

Поехали...

Код:
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
   unsigned long long e;
   unsigned n = 0;
   cout << "Ввод числа: ";
   cin >> e;
   do if( 3 == e % 10 ) n++;
   while( ( e /= 10 ) > 0 );
   cout << "Цифр 3 в числе " << n << " штук" << endl;
}

Здесь всё решение укладывается в один оператор do … while.
Но, обратим внимание на то, что формулировка “вводится целое число” – это ввод всегда строки, представляющей число (здесь подвох в формулировке задачи). Тогда так:
Код:
#include <iostream>
#include <cstring>
using namespace std;

int main() {
   char e[ 80 ], *p = e;
   unsigned n = 0;
   cout << "Ввод числа: ";
   cin >> e;
   while( ( p = strchr( p, '3' ) ) != NULL )
      p++, n++;
   cout << "Цифр 3 в числе " << n << " штук" << endl;
}

Или так:
Код:
#include <iostream>
#include <cstring>
using namespace std;

int main() {
   char e[ 80 ];
   unsigned n = 0, i;
   cout << "Ввод числа: ";
   cin >> e;
   for( i = 0; i < strlen( e ); i++ )
      if( e[ i ] == '3' ) n++;
   cout << "Цифр 3 в числе " << n << " штук" << endl;
}

Или так:
Код:
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
   string e;
   unsigned n = 0;
   cout << "Ввод числа: ";
   cin >> e;
   for( string::iterator i = e.begin() ;; n++, i++ )
      if( ( i = find( i, e.end(), '3' ) ) == e.end() ) break;
   cout << "Цифр 3 в числе " << n << " штук" << endl;
}


Как легко видеть, во всех 4-х вариантах всё решение задачи (без ввода исходных данных и вывода результата) осуществляется 1-м оператором цикла.

P.S. Эта задача является очень хорошей иллюстрацией того основополагающего принципа программирования, что любая поставленная задача может быть решена многими и очень разными способами.


Вложения:
mul3.tgz [909 байт]
Скачиваний: 198
Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: примеры задач при изучении C++
Непрочитанное сообщениеДобавлено: 18 ноя 2015, 02:43 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10806
Откуда: Харьков
Ещё одна очень хорошая задача ... хоть на C, хоть на C++ - здесь без разницы...
Но, поскольку она завязана на потоки, синхронизацию и параллельное выполнение, то я её снесу сюда вот в тему параллельность + синхронизации (примеры).


Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: примеры задач при изучении C++
Непрочитанное сообщениеДобавлено: 24 ноя 2015, 01:57 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10806
Откуда: Харьков
Ещё одна хорошая задача ... может не столько для практического использования, сколько попрактиковаться: реализация матриц.
Известное дело, что в C матрицы (прямогольные) зачастую реализуются как:
Код:
double **M; // имитирует динамически создаваемый массив M[][]

Или так ... что то же самое:
Код:
double M[][5] = {
   { 1, 2, 3, 4, 5 },
   { 2, 3, 4, 5, 6 },
};


Но в C++ матрицу (в любом представлении ... пусть таком как выше) - легко запаковать в класс, который будет представлять тип матриц.

Задача:
- реализовать класс matrix
- представить как можно больше способов внутреннего хранения матрицы
- так, чтобы класс реализовывал, как минимум, возможности: создания, заполнения, 2-мерной индексации, ввод-вывод, присвоения, инициализации ... что там ещё? ;-)
Вот так, чтобы все внутренние реализации класса позволяли делать так:
Код:
class matrix {
   // от вас требуется всего лишь здесь ;-)
}

int main() { // а это тестовая программа
   matrix M( 2, 5 );
   for( int r = 0; r < M.row(); r++ )
      for( int c = 0; c < M.col(); c++ ) M[ r ][ c ] = r + c;
   cout << "матрица M[" << M.row() << "," << M.col() << "]=" << endl << M;
   cout << "Вводите матрицу построчно (Enter - конец ввода):" << endl;
   cin >> M;
   cout << "новая матрица M[" << M.row() << "," << M.col() << "]=" << endl << M;
   cout << "присвоение X = M : ";
   matrix X( 3, 3 );
   X = M;
   cout << "X[" << X.row() << "," << X.col() << "]=" << endl << X;
   cout << "инициализация Y( M ) : ";
   matrix Y( M );
   cout << "Y[" << Y.row() << "," << Y.col() << "]=" << endl << Y;
}


А ... ;-) :-o ну и чтобы ввод матрицы (с терминала, переадресацией из файла данных, ...) сделать по-людски ... не спрашивая так занудно "введите число столбцов ... введите число строк ....", а как-то вот так:
Код:
Вводите матрицу построчно (Enter - конец ввода):
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
       

- 2 последовательных Enter (окончание строки ввода + пустая строка) - это конец матрицы ... а столбцы и строки пусть там сама программа считает ;-)


Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: примеры задач при изучении C++
Непрочитанное сообщениеДобавлено: 24 ноя 2015, 14:41 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10806
Откуда: Харьков
Olej писал(а):
- реализовать класс matrix

Поехали... ;-)

1. matrix = vector< vector<double> > ... и эта таблица является одним из полей (matvio.cc):
Код:
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

typedef vector<double> line;
ostream& operator <<( ostream& out, line& obj ) {
   for( unsigned i = 0; i < obj.size(); i++ )
      out << obj[ i ] << ( i == obj.size() - 1 ? "" : ", " );
   return out;
}

class matrix {
private:
   typedef vector<line> table;
   vector< vector<double> > *data;
   bool ok;
   unsigned rows, // 1-й индекс
            cols; // 2-й индекс
   void clean( void ) {
      for( unsigned r = 0; r < rows; r++ ) (*data)[ r ].clear();
      (*data).clear();
   }
public:
   bool inline good( void ) { return ok; }
   const int col( void ) { return cols; }
   const int row( void ) { return rows; }
   matrix( void ) {
      ok = true;
      cols = rows = 0;
      data = new table();     
   }
   matrix( int rows, int cols ) {
      ok = true;
      this->cols = cols;
      this->rows = rows;
      line l( cols, 0.0 );     
      data = new table( rows, l );     
   }
   matrix( const matrix& m ) {
      if( !( ok = m.ok ) ) return;
      data = new table();     
      cols = m.cols;
      rows = m.rows;
      for( unsigned r = 0; r < rows; r++ )
         data->push_back( (*m.data)[ r ] );
   }
   ~matrix( void ) {
      clean();
      delete data;
   }
   line& operator []( int row ) { return (*data)[ row ]; }
   matrix& operator =( const matrix& m ) {
      if( !( ok = m.ok ) ) return *this;
      clean();
      cols = m.cols;
      rows = m.rows;
      for( unsigned r = 0; r < rows; r++ )
         data->push_back( (*m.data)[ r ] );
      return *this;
   }
   inline void clear( void ) {
      clean();
      cols = rows = 0;
   }
   friend ostream& operator <<( ostream& out, matrix& obj ) {
      if( !obj.ok )
         return out << "разрушенный объект" << endl;
      for( unsigned r = 0; r < obj.rows; r++ )
         out << (*(obj.data))[ r ] << endl;
      return out;
   }
   friend istream& operator >>( istream& inp, matrix& obj );
};

istream& operator >>( istream& inp, matrix& obj ) {
   obj.clear();
   int r = 0;
   while( true ) {
      string e;
      getline( inp, e );
      if( 0 == e.length() ) break;
      istringstream ist( e );
      int n = 0;
      vector<double> l;
      try {
         double d;   
         while( ist >> d ) {
            n++;
            l.push_back( d );
         }
      }
      catch( exception const& e ) {
         obj.ok = false;
         return inp;
      }
      if( 0 == r ) obj.cols = l.size();
      else if( obj.cols != l.size() ) {
         obj.ok = false;
         return inp;
      }
      obj.data->push_back( l );
      r++;
   }
   obj.rows = r;
   obj.ok = true;
   return inp;
};

#include "main.c"


2. matrix = производный класс от vector< vector<double> > (matiio.cc):
Код:
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

typedef vector<double> line;
ostream& operator <<( ostream& out, line& obj ) {
   for( unsigned i = 0; i < obj.size(); i++ )
      out << obj[ i ] << ( i == obj.size() - 1 ? "" : ", " );
   return out;
}

typedef vector<line> table;

class matrix : protected vector< vector<double> > {
private:
   bool ok;
   unsigned rows, // 1-й индекс
            cols; // 2-й индекс
   void clean( void ) {
      for( unsigned r = 0; r < rows; r++ ) (*this)[ r ].clear();
      (*this).clear();
   }
public:
   bool inline good( void ) { return ok; }
   const int col( void ) { return cols; }
   const int row( void ) { return rows; }
   matrix( unsigned rows, unsigned cols ) {
      this->rows = rows;
      this->cols = cols;
      line l( cols, 0.0 );
      for( unsigned r = 0; r < rows; r++ )
         (*this).push_back( l );
   }
   matrix( const matrix& m ) {
      if( !( ok = m.ok ) ) return;
      rows = m.rows;
      cols = m.cols;
      for( unsigned r = 0; r < rows; r++ )
         push_back( ( (table)m )[ r ] );
   }
   ~matrix( void ) { clean(); }
   line& operator []( unsigned row ) { return (*(table*)this)[ row ]; }
   matrix& operator =( const matrix& m ) {
      if( !( ok = m.ok ) ) return *this;
      clean();
      rows = m.rows;
      cols = m.cols;
      for( unsigned r = 0; r < rows; r++ )
         push_back( ( (table)m )[ r ] );
      return *this;
   }
   friend ostream& operator <<( ostream& out, matrix& obj ) {
      for( unsigned r = 0; r < obj.rows; r++ )
         out << ( (table)obj )[ r ] << endl;
      return out;
   }
   friend istream& operator >>( istream& inp, matrix& obj );
};

istream& operator >>( istream& inp, matrix& obj ) {
   obj.clean();
   int r = 0;
   while( true ) {
      string e;
      getline( inp, e );
      if( 0 == e.length() ) break;
      istringstream ist( e );
      int n = 0;
      vector<double> l;
      try {
         double d;
         while( ist >> d ) {
            n++;
            l.push_back( d );
         }
      }
      catch( exception const& e ) {
         obj.ok = false;
         return inp;
      }
      if( 0 == r ) obj.cols = l.size();
      else if( obj.cols != l.size() ) {
         obj.ok = false;
         return inp;
      }
      obj.push_back( l );
      r++;
   }
   obj.rows = r;
   obj.ok = true;
   return inp;
};

#include "main.c"


Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: примеры задач при изучении C++
Непрочитанное сообщениеДобавлено: 24 ноя 2015, 14:47 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10806
Откуда: Харьков
Olej писал(а):
Olej писал(а):
- реализовать класс matrix

Поехали... ;-)


3. matrix = double[] ... одномерное представление (matpio.cc):
Код:
#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

class matrix {
public:
   double *data;  // масив [ rows * cols ]
private:
   bool ok;
   unsigned rows, // 1-й индекс
            cols; // 2-й тндекс
protected:
   void clean( void ) {
      delete [] data;
      cols = rows = 0;
   }
public:
   bool inline good( void ) { return ok; }
   const int col( void ) { return cols; }
   const int row( void ) { return rows; }
   matrix( int rows, int cols ) {
      ok = true;
      this->cols = cols;
      this->rows = rows;
      data = new double[ rows * cols ];
   }
   matrix( const matrix& m ) {
      if( !( ok = m.ok ) ) return;
      data = new double[ ( rows = m.rows ) * ( cols = m.cols ) ];
      for( unsigned long long i = 0; i < rows * cols; i++ )
         data[ i ] = m.data[ i ];
   }
   ~matrix( void ) { clean(); }
   double* operator []( int row ) {
      return data + row * cols;
   }
   matrix& operator =( const matrix& m ) {
      if( !( ok = m.ok ) ) return *this;
      clean();
      data = new double[ ( rows = m.rows ) * ( cols = m.cols ) ];
      for( unsigned long long i = 0; i < rows * cols; i++ )
         data[ i ] = m.data[ i ];
      return *this;
   }
   friend ostream& operator <<( ostream& out, matrix& obj ) {
      if( !obj.ok )
         return out << "разрушенный объект" << endl;
      for( unsigned r = 0; r < obj.rows; r++ )
         for( unsigned c = 0; c < obj.cols; c++ )
            out << obj.data[ r * obj.cols +  c ] << ( c == obj.cols - 1 ? "\n" : ", " );
      return out;
   }
   friend istream& operator >>( istream& inp, matrix& obj );
};

istream& operator >>( istream& inp, matrix& obj ) {
   obj.clean();
   unsigned r = 0;
   vector<double> l;
   while( true ) {
      string e;
      getline( inp, e );
      if( 0 == e.length() ) break;
      istringstream ist( e );
      unsigned n = 0;
      try {
         double d;   
         while( ist >> d ) {
            n++;
            l.push_back( d );
         }
      }
      catch( exception const& e ) {
         obj.ok = false;
         return inp;
      }
      if( 0 == r ) obj.cols = n;
      else if( obj.cols != n ) {
         obj.ok = false;
         return inp;
      }
      r++;
   }
   obj.data = new double[ ( obj.rows = r ) * obj.cols ];
   for( unsigned long long i = 0; i < obj.rows * obj.cols; i++ )
      obj.data[ i ] = l[ i ];
   obj.ok = true;
   return inp;
};

#include "main.c"


4. 3. matrix = double[][] ... - это традиционное представление, идущее от C реализации, и, как оказывается, самое неудобное и громоздкое (mataio.cc):
Код:
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

class matrix {
private:
   double **data;

   bool ok;
   unsigned rows, // 1-й индекс
            cols; // 2-й тндекс
protected:
   void clean( void ) {
      for( unsigned r = 0; r < rows; r++ )
         delete [] data[ r ];
      delete [] data;
      cols = rows = 0;
   }
public:
   bool inline good( void ) { return ok; }
   const int col( void ) { return cols; }
   const int row( void ) { return rows; }
   matrix( unsigned rows, unsigned cols ) {
      ok = true;
      this->cols = cols;
      this->rows = rows;
      data = new double*[ rows ];
      for( unsigned r = 0; r < rows; r++ )
         data[ r ] = new double[ cols ];
   }
   matrix( const matrix& m ) {
      if( !( ok = m.ok ) ) return;
      data = new double*[ rows = m.rows ];
      cols = m.cols;
      for( unsigned r = 0; r < rows; r++ )
         data[ r ] = new double[ cols ];
      for( unsigned r = 0; r < rows; r++ )
         for( unsigned c = 0; c < cols; c++ )
            data[ r ][ c ] = m.data[ r ][ c ];
   }
   ~matrix( void ) { clean(); }
   double* operator []( int row ) { return data[ row ]; }

   matrix& operator =( const matrix& m ) {
      if( !( ok = m.ok ) ) return *this;
      clean();
      data = new double*[ rows = m.rows ];
      cols = m.cols;
      for( unsigned r = 0; r < rows; r++ )
         data[ r ] = new double[ cols ];
      for( unsigned r = 0; r < rows; r++ )
         for( unsigned c = 0; c < cols; c++ )
            data[ r ][ c ] = m.data[ r ][ c ];
      return *this;
   }
   friend ostream& operator <<( ostream& out, matrix& obj ) {
      if( !obj.ok )
         return out << "разрушенный объект" << endl;
      for( unsigned r = 0; r < obj.rows; r++ )
         for( unsigned c = 0; c < obj.cols; c++ )
            out << obj.data[ r ][ c ] << ( c == obj.cols - 1 ? "\n" : ", " );
      return out;
   }
   friend istream& operator >>( istream& inp, matrix& obj );
};

istream& operator >>( istream& inp, matrix& obj ) {
   obj.clean();
   unsigned r = 0;
   vector<double> l;
   while( true ) {
      string e;
      getline( inp, e );
      if( 0 == e.length() ) break;
      istringstream ist( e );
      unsigned n = 0;
      try {
         double d;
         while( ist >> d ) {
            n++;
            l.push_back( d );
         }
      }
      catch( exception const& e ) {
         obj.ok = false;
         return inp;
      }
      if( 0 == r ) obj.cols = n;
      else if( obj.cols != n ) {
         obj.ok = false;
         return inp;
      }
      r++;
   }
   obj.data = new double*[ ( obj.rows = r ) ];
   for( r = 0; r < obj.rows; r++ ) {
      obj.data[ r ] = new double[ obj.cols ];
      for( unsigned c = 0; c < obj.cols; c++ )
      obj.data[ r ][ c ] = l[ r * obj.cols + c ];
   }
   obj.ok = true;
   return inp;
};

#include "main.c"


Вложения:
matrix.tgz [2.72 КБ]
Скачиваний: 221
Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: примеры задач при изучении C++
Непрочитанное сообщениеДобавлено: 24 ноя 2015, 14:50 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10806
Откуда: Харьков
Olej писал(а):
А ... ;-) :-o ну и чтобы ввод матрицы (с терминала, переадресацией из файла данных, ...) сделать по-людски ... не спрашивая так занудно "введите число столбцов ... введите число строк ...."

Код:
olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/matrix $ ./mataio < m1.dat
матрица M[2,5]=
0, 1, 2, 3, 4
1, 2, 3, 4, 5
Вводите матрицу построчно (Enter - конец ввода):
новая матрица M[2,3]=
1, 2, 3
2, 3, 4
присвоение X = M : X[2,3]=
1, 2, 3
2, 3, 4
инициализация Y( M ) : Y[2,3]=
1, 2, 3
2, 3, 4

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/matrix $ ./matiio < m1.dat
матрица M[2,5]=
0, 1, 2, 3, 4
1, 2, 3, 4, 5
Вводите матрицу построчно (Enter - конец ввода):
новая матрица M[2,3]=
1, 2, 3
2, 3, 4
присвоение X = M : X[2,3]=
1, 2, 3
2, 3, 4
инициализация Y( M ) : Y[2,3]=
1, 2, 3
2, 3, 4

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/matrix $ ./matpio < m1.dat
матрица M[2,5]=
0, 1, 2, 3, 4
1, 2, 3, 4, 5
Вводите матрицу построчно (Enter - конец ввода):
новая матрица M[2,3]=
1, 2, 3
2, 3, 4
присвоение X = M : X[2,3]=
1, 2, 3
2, 3, 4
инициализация Y( M ) : Y[2,3]=
1, 2, 3
2, 3, 4

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/matrix $ ./matvio < m1.dat
матрица M[2,5]=
0, 1, 2, 3, 4
1, 2, 3, 4, 5
Вводите матрицу построчно (Enter - конец ввода):
новая матрица M[2,3]=
1, 2, 3
2, 3, 4
присвоение X = M : X[2,3]=
1, 2, 3
2, 3, 4
инициализация Y( M ) : Y[2,3]=
1, 2, 3
2, 3, 4


Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: примеры задач при изучении C++
Непрочитанное сообщениеДобавлено: 04 дек 2015, 17:54 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10806
Откуда: Харьков
Вот подбросили мне задачку...
Она а). и проста по алгоритмике, понятна и б). не так проста в реализации и в). имеет подводные камни и г). использует матрицы, о которых только-что шла речь ...
Формулировка (я её получил на украинском языке, но как-то переведу):
Цитата:
Условие задачи:
Квадратное поле разбито на N полос по N квадратиков. Некоторые квадратики закрашены в жёлтый цвет, среди которых левый верхний квадратик и правый нижний квадратик.
Черепашка, которая находится в левой верхней клетке, мечтает попасть в правую нижнюю.
Определить может ли она переместиться из левого верхнего квадрата в правый нижний, переползая из текущего квадратика только на соседние жёлтые квадратики (квадратики считаются соседними, только если у них одна сторона общая) в каком-либо направлении. Если такие маршруты существуют, то определить длину кратчайшего из них.

Входной файл input.txt содержит:
N – целое число, размер поля, (N<=100);
Таблица розміром N x N с значениями 0 или 1 – структура поля:
1 – закрашенный квадратик; 0 – чистый квадратик.

Выходной файл output.txt содержит одно целое число:
0 – если между указанными квадратиками нет ни единой траектории;
положительное число – минимальное число шагов, если между указанным квадратиками есть хотя бы один маршрут.

Как понятно из формулировки (все вот эти input.txt и output.txt ... для автоматической формальной проверки результата) - это из задач так называемого "спортивного программирования", или олимпиадных задач.

Кроме того, вводить N прежде, как размерность следующей далее матрицы - глупость. Размер матрицы должен извлекаться из её изображения, как делает человек глазами, и как показано в совсем предыдущих сообщениях о матрицах.


Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: примеры задач при изучении C++
Непрочитанное сообщениеДобавлено: 04 дек 2015, 18:00 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10806
Откуда: Харьков
Olej писал(а):
в). имеет подводные камни

Подводные камни (не сразу очевидные) таких задач:
1. Должны обрабатываться тупиковые пути, "отростки"...
2. Должны исключаться повторные обходы (кружение до бесконечности) на циклических путях (нужно отслеживать пройденную траекторию).

Как на примере вот такой матрицы:
Цитата:
1 1 1 0 0
1 0 1 1 1
1 0 1 0 0
1 0 1 1 1
1 1 1 0 1


Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: примеры задач при изучении C++
Непрочитанное сообщениеДобавлено: 04 дек 2015, 18:25 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10806
Откуда: Харьков
Olej писал(а):
проста по алгоритмике, понятна


Всё решение задачи вот:
Код:
int way( matrix& m, int y, int x ) {
   if( y == m.row() - 1 && x == m.col() - 1 ) return 1; // это конечная точка
   matrix m1( m );
   m1[ y ][ x ] = false;                                // отметить как пройдено
   int y1, x1, res = INT_MAX;
   for( int i = 0; i < 4; i++ ) {                       // обойти 4 соседа
      switch( i ) {
         case 0:
            y1 = y; x1 = x + 1; break;
         case 1:
            y1 = y; x1 = x - 1; break;
         case 2:
            y1 = y + 1; x1 = x; break;
         case 3:
            y1 = y - 1; x1 = x; break;
      }
      if( x1 < 0 || x1 >= m.col() ||
          y1 < 0 || y1 >= m.row() ) continue;          // поле за пределами матрицы
      if( !m1[ y1 ][ x1 ] ) continue;                  // недопустиммый шаг
      int ret = way( m1, y1, x1 );
      if( ret > 0 && ret < res )
         res = ret + 1;
   }
   return res == INT_MAX ? 0 : res;
}

А потом где-то в main:
Код:
...
   int w = way( M, 0, 0 );
...

В итоге:
Код:
olej@nvidia ~/2015_WORK/in.WORK/+ForMoney/cherepah $ ./cherepah input5_1.txt
matrix size 5 x 5
matrix M[5,5]=
1, 1, 1, 0, 0
1, 0, 1, 1, 1
1, 0, 1, 0, 0
1, 0, 1, 1, 1
1, 1, 1, 0, 1
trace in 8 steps

Собственно ...
Условия задачи, как они сформулированы - выполнены полностью.
Но вот только для матрицы размером 10х10:
Код:
olej@nvidia ~/2015_WORK/in.WORK/+ForMoney/cherepah $ ./cherepah input10_2.txt
matrix size 10 x 10
matrix M[10,10]=
1, 0, 0, 0, 0, 0, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 0, 0, 1
1, 0, 0, 0, 0, 0, 1, 0, 0, 1
1, 0, 1, 1, 1, 0, 1, 0, 0, 1
1, 0, 1, 0, 0, 0, 1, 0, 0, 1
1, 0, 1, 1, 1, 1, 1, 0, 0, 1
1, 0, 0, 0, 0, 0, 0, 0, 0, 1
1, 0, 0, 0, 0, 0, 0, 0, 0, 1
1, 1, 1, 1, 0, 0, 0, 0, 0, 1
0, 0, 0, 1, 1, 1, 1, 1, 1, 1
trace in 18 steps

Здесь отследить эту трассу (из нескольких) из18 шагов - сложно.
А на матрице 50х50, скажем - просто невозможно!

Следующий этап задачи: не только вычислить минимальную трассу, но и диагностировать её ... что-то типа:
Код:
...
trace in 18 steps
<0,0> <1,0> <2,0> <3,0> <4,0> <5,0> <6,0> <7,0> <8,0> <8,1> <8,2> <8,3> <9,3> <9,4> <9,5> <9,6> <9,7> <9,8> <9,9>

Но для этого задача становится намного сложнее!
(Я так подозреваю, что для какого-то-там спортивного программирования её поэтому и сформулироаали именно так)


Вложения:
cherepah.cc [5.01 КБ]
Скачиваний: 203
Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: примеры задач при изучении C++
Непрочитанное сообщениеДобавлено: 05 дек 2015, 00:25 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10806
Откуда: Харьков
Olej писал(а):
Но для этого задача становится намного сложнее!

Вот такой код могу предложить:
Код:
...
struct coord {
   int y, x;
   coord( int y, int x ) {
      this->y = y;
      this->x = x;
   }
   coord operator +( coord& s ) {
      return coord( y + s.y, x + s.x );
   };
   coord& operator +=( const coord & s ) {
      y += s.y;
      x += s.x;
      return *this;
   };
   friend ostream& operator <<( ostream& out, coord& obj ) {
      return out << '<' << obj.y << ',' << obj.x << '>';
   }
};
...
list<coord> way( matrix& m, coord& p ) {
   list<coord> v;                                              // пустой список
   if( p.y == m.row() - 1 && p.x == m.col() - 1 ) {            // это конечная точка
      v.push_back( p );
      return v;
   }
   matrix m1( m );
   m1[ p.y ][ p.x ] = false;                                   // отметить как пройдено
   unsigned len = INT_MAX;
   static coord neib[] = { coord( 0, 1 ), coord( 0, -1 ),
                           coord( 1, 0 ), coord( -1, 0 ) };    // соседи
   for( unsigned i = 0; i < sizeof( neib ) / sizeof( neib[ 0 ] ); i++ ) {
      coord p1 = p + neib[ i ];
      if( p1.x < 0 || p1.x >= m.col() ||
          p1.y < 0 || p1.y >= m.row() ) continue;              // поле за пределами матрицы
      if( !m1[ p1.y ][ p1.x ] ) continue;                      // недопустиммый шаг
      list<coord> v1 = way( m1, p1 );                          // последующая трасса
      if( v1.size() > 0 && v1.size() < len ) {                 // это одно из решений
         v1.push_front( p );
         len = v1.size();
         v = v1;
      }
   }
   return v;
}
...

Он не намного бъёмнее ... но с ним пришлось повозиться ;-) .

Теперь это выглядит так:
Код:
olej@nvidia ~/2015_WORK/in.WORK/+ForMoney/cherepah $ ./cherepahv input20_1.txt
matrix size 20 x 20
space matrix M[20,20]=
1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1
0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1
0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1
1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1
1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1
1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1
1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1
0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1
1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1
1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1
1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1
0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1
1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1
1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1
1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1
0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0
1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1
0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1
trace in 80 steps
<0,0> <1,0> <1,1> <1,2> <2,2> <2,3> <3,3> <4,3> <4,2> <4,1> <4,0> <5,0> <6,0> <7,0> <8,0> <8,1> <8,2> <8,3> <8,4> <9,4> <10,4> <10,3> <10,2> <10,1> <10,0> <11,0> <12,0> <12,1> <12,2> <12,3> <12,4> <12,5> <13,5> <14,5> <14,4> <14,3> <14,2> <14,1> <14,0> <15,0> <16,0> <16,1> <16,2> <16,3> <16,4> <16,5> <17,5> <18,5> <19,5> <19,6> <19,7> <18,7> <17,7> <16,7> <15,7> <14,7> <13,7> <12,7> <11,7> <10,7> <10,8> <10,9> <11,9> <11,10> <11,11> <12,11> <13,11> <14,11> <15,11> <16,11> <16,12> <16,13> <17,13> <18,13> <19,13> <19,14> <19,15> <19,16> <19,17> <19,18> <19,19>

Но попробуйте в этой матрице, не имея трассы решения, проверить результат, состоящий в том, что есть таки там трасса из 80 шагов!

P.S. В архиве оба варианта + набор тестовых файлов данных.


Вложения:
cherepahv.cc [6.16 КБ]
Скачиваний: 206
cherepah.tgz [4.96 КБ]
Скачиваний: 224
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Часовой пояс: UTC + 3 часа


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

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB
[ Time : 0.400s | 20 Queries | GZIP : On ]