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

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

Модератор: Olej

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

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

Непрочитанное сообщение Olej » 08 дек 2015, 08:07

Вот ещё любопытная задача:
Встретилось задание из раздела о динамическом программировании, которое вызывает у меня трудности. Необходимо построить алгоритм, который по заданному множеству определяет, можно ли его разбить на три части, в которых суммы всех элементов будут равны. Например:
[1, 2, 3, 4, 4, 5, 8] -> {1,8}, {4,5}, {2,3,4}

Очевидно, что если сумма всех элементов не делится на 3, то множество не содержит такого разбиения (самая простая часть:) ). Но как действовать дальше?
Неприятность здесь в том, что формулировка неверная, это не set, а multiset ... который, в свою очередь, создаёт неприятности.
Лучше бы здесь говорить о списке чисел!

Вот рабочее решение ... более-менее:

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

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

ostream& operator <<( ostream& out, const multiset<int>& obj ) {
   out << "{ ";
   for( auto i = obj.begin(); i != obj.end(); i++ ) {
      auto j = i;
      j++;
      out << *i << ( j == obj.end() ? "" : ", " ); 
   }
   return out << " }"; 
}

istream& operator >>( istream& inp, multiset<int>& obj ) {
   obj.clear();
   string e;
   while( true ) {
      getline( inp, e );
      if( inp.rdstate() & ios::eofbit ) break;
      if( 0 == e.length() ) break;
      istringstream ist( e );
      try { 
         double d;   
         while( ist >> d ) 
            obj.insert( d );
      }
      catch( exception const& e ) {
         cout << "ошибка ввода!" << endl;
         exit( 1 ); 
      }
   }
   return inp;
};

multiset<int>& operator +=( multiset<int>& md, const multiset<int>& ms ) {
   for( auto i = ms.begin(); i != ms.end(); i++ ) 
      md.insert( *i );
   return md;
}

multiset<int>& operator -=( multiset<int>& md, const multiset<int>& ms ) {
   for( auto i = ms.begin(); i != ms.end(); i++ ) {
      int n = md.count( *i );
      if( 0 == n ) continue;
      auto j = md.find( *i );
      if( j != md.end() )
         md.erase( *i );
      while( --n > 0 ) md.insert( *i );
   }
   return md;
}

int summa( const multiset<int>& obj ) {
   int ret = 0;
   for( auto i = obj.begin(); i != obj.end(); i++ ) 
      ret += *i;
   return ret;
}

multiset<int> select( multiset<int> from, int sum ) {
   multiset<int> s1;
   for( auto i = from.rbegin(); i != from.rend(); i++ ) {
      if( *i == sum ) {
         s1.insert( *i );
         return s1;
      }
      if( *i < sum ) {
         multiset<int> from1( from );
         auto j = from1.find( *i );
         from1.erase( j );
         multiset<int> s2 = select( from1, sum - *i );
         if( !s2.empty() ) {
            s1.insert( *i );
            s1 += s2;
            return s1;
         }
      }
   }
   return s1;
} 

int main() {
   multiset<int> S;
   cout << "Вводите числа построчно (пустая строка - конец ввода):" << endl;
   cin >> S;
   cout << S << " ->" << endl;
   if( summa( S ) % 3 != 0 )
      cout << "нет требуеого разбиения" << endl; 
   int sum = summa( S ) / 3;
   multiset<int> S1, S2, S3;
   cout << ( S1 = select( S, sum ) ) << endl;
   cout << ( S2 = select( ( S -= S1 ), sum ) ) << endl;
   cout << ( S3 = select( ( S -= S2 ), sum ) ) << endl;
}

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

olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/3set $ ./3set
Вводите числа построчно (пустая строка - конец ввода):
1 2 3 4
4 5 8

{ 1, 2, 3, 4, 4, 5, 8 } ->
{ 1, 8 }
{ 4, 5 }
{ 2, 3, 4 }
Неприятность такого решения в том, что удаление элемента в multiset (в этом случае "4") удаляет все вхождения элемента, поэтому удаление пришлось делать через задницу.
Вложения
3set.cc
(2.46 КБ) 281 скачивание

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

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

Непрочитанное сообщение Olej » 27 дек 2015, 23:41

Прекрасный online справочник под рукой, когда вы пишете код на C++:
Изображение

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

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

Непрочитанное сообщение Olej » 20 фев 2016, 15:24

Вот ещё десятка 2 задач на использование STL / Boost, которая на сегодня (после C++03) является просто составной частью стандарта (стандартной библиотеки) C++ : Начала STL и контейнры C++.
Объяснять не хочется ... кому нужно - посмотрит сам.

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

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

Непрочитанное сообщение Olej » 01 дек 2016, 14:16

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

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

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

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

Непрочитанное сообщение Olej » 01 дек 2016, 14:37

Olej писал(а): Но!
Интересные задачи, поштучно и до помещения их в новые редакции этих текстов, я буду показывать здесь.
Задача:
Определить можно ли представить квадрат некоторого числа N в виде:
N^2 = a1^2 + a2^2 + ... ak^2
С числом слагаемых k >= 2 и a1 != a2 != ... != ak
Если есть такое разложение, то показать эти a1, a2, ... Если такого разложения нет, то сообщить об этом.

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

#include <iostream>
using namespace std;

bool sq( unsigned n2, unsigned beg ) {
   static int lvl = 0;
   lvl++;
   bool ret = false;
   unsigned i;
   for( i = beg; i * i < n2; i++ )
      if( sq( n2 - i * i, i + 1 ) ) {
         cout << '<' << i << '>' << ( 1 == lvl ? "\n" : "" );
         ret = true;
      }
   if( lvl != 1 && i * i == n2 ) {
      cout << '<' << i << '>';
      ret = true;
   }
   lvl--;
   return ret;
}

int main( int argc, char* argv[] ) {
   while( true ) {
      cout << "Число : ";
      unsigned n;
      cin >> n;
      if( !sq( n * n, 1 ) )
         cout << "нет таких чисел!" << endl;
   }
}

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

[olej@dell sum2]$ make
g++     sum2.cc   -o sum2

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

[olej@dell sum2]$ ./sum2 
Число : 4
нет таких чисел!
Число : 5
<4><3>
Число : 6
нет таких чисел!
Число : 7
<6><3><2>
Число : 8
нет таких чисел!
Число : 9
<8><4><1>
<6><5><4><2>
Число : 10
<7><5><4><3><1>
<8><6>
Число : 11
<8><6><10><4><2><1>
<9><6><2>
Число : 12
<9><7><3><2><1>
Число : 13
<9><7><5><3><10><8><2><1>
<8><7><6><10><7><4><2>
<12><4><3>
<12><5>
Число : 14
<9><7><6><4><11><6><5><3><9><7><6><5><2><9><8><5><11><7><4><3><11><7><5><1>
<12><6><4>
Число : 15
<11><7><5><4><3><2><12><8><4><1>
<14><4><3><12><6><5><13><6><4><14><5><11><8><6><11><10><2>
<10><8><6><4><3>
<10><8><6><5>
<12><9>
Число : ^C

Вложения
sum2.cc
(841 байт) 118 скачиваний

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

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

Непрочитанное сообщение Olej » 22 дек 2016, 23:26

Дано N точек, найти точки пересечения прямых проходящих через каждую пару точек.
(не включать в точки пересечения сами N точек, являющиеся пересечением смежных прямых ... исключить из рассмотрения пары параллельных прямых)

Пересечение прямых
Рассмотрим пересечение двух прямых L 1 и L 2 на плоскости, где прямая L1 определена двумя различными точками ( x1 , y1 ) и ( x2 , y2 ), а прямая L2 — различными точками ( x3 , y3 ) и ( x4 , y4 )
Изображение
Если две прямые параллельны или совпадают, знаменатель обращается в нуль:
Изображение
(это чтобы не выводить эти выражения, а взять готовые)

Код:

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

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unistd.h>
using namespace std;

// дано N точек, найти точки пересечения прямых проходящих через каждую пару точек,
// пересечений не совпадающих с самими концевыми точками (смежные прямые)

const double eps = 1E-3;

struct point { 
   double x, y; 
   bool operator==( const point& p ) {
      return ( fabs( p.x - x ) < eps ) && 
             ( fabs( p.y - y ) < eps ); 
   }
};
ostream& operator <<( ostream& out, const point& p ) {
   char s[ 20 ];
   sprintf( s, "<%+.2f,%+.2f>", p.x, p.y );   
   return out << s; 
}

struct line { point b, f; };
vector< line > lines;

bool parallel( line& l1, line& l2 ) {
   double x1 = l1.b.x, x2 = l1.f.x, x3 = l2.b.x, x4 = l2.f.x,
          y1 = l1.b.y, y2 = l1.f.y, y3 = l2.b.y, y4 = l2.f.y;
   return eps > fabs( ( x1 - x2 ) * ( y3 - y4 ) - 
                      ( y1 - y2 ) * ( x3 - x4 ) ); // denominator    
}

point cross( line& l1, line& l2 ) {
   double x1 = l1.b.x, x2 = l1.f.x, x3 = l2.b.x, x4 = l2.f.x,
          y1 = l1.b.y, y2 = l1.f.y, y3 = l2.b.y, y4 = l2.f.y,
          denominator = ( x1 - x2 ) * ( y3 - y4 ) -
                        ( y1 - y2 ) * ( x3 - x4 );
   point ret = {
      ( ( x1 * y2 - y1 * x2 ) * ( x3 - x4 ) - 
        ( x1 - x2 ) * ( x3 * y4 - y3 * x4 ) ) / denominator,
      ( ( x1 * y2 - y1 * x2 ) * ( y3 - y4 ) -
        ( y1 - y2 ) * ( x3 * y4 - y3 * x4 ) ) / denominator 
               };
   return ret;
}

int main( int argc, char **argv ) {
   vector<point> pts;
   int n = 0;
   point p; 
   while( cin ) {
      string s;   
      getline( cin, s );
      if( 0 == s.length() ) break;
      istringstream( s ) >> p.x >> p.y;  
      for( auto &x : pts ) {
         line l = { x, p };
         lines.push_back( l );
      }
      pts.push_back( p );
      n++;
   }
   if( !isatty( 0 ) ) {           // вывод при переадресации <
      for( auto &p : pts )
         cout << p << "  ";
      cout << endl;
   }         
   cout << n << "-угольник, " << lines.size() << " линий, " << endl;   
   int nc = 0, np = 0, nt = 0;
   n = 0;
   const int nline = 5;
   for( auto i = lines.begin(); i < lines.end(); i++ )
      for( auto j = i + 1; j < lines.end(); j++, n++ )
         if( parallel( *i, *j ) )
            np++;
         else {
            point c = cross( *i, *j );
            if( find( pts.begin(), pts.end(), c ) != pts.end() ) 
               nt++;
            else 
               cout << c << ( ++nc % nline ? "\t" : "\n" );
         }    
   cout << ( nc % nline ? "\n" : "" )
        << n << ": пересечений " << nc << " терминальных " 
        << nt  << " параллельных " << np << endl;   
}
Результат:

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

[olej@dell ngon]$ ./ngon
0 0
0 3
2 2
2 1

4-угольник, 6 линий,
<+1.50,+1.50>   <+3.00,+1.50>
15: пересечений 2 терминальных 12 параллельных 1

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

[olej@dell ngon]$ ./ngon <5.dat
<+0.00,+0.00>  <+0.00,+1.00>  <+1.00,+2.00>  <+2.00,+1.00>  <+1.00,+0.00>  
5-угольник, 10 линий, 
<-0.00,+3.00>	<+0.00,-1.00>	<+0.50,+1.00>	<+0.33,+0.67>	<-1.00,-2.00>
<-2.00,-1.00>	<-1.00,-0.00>	<+0.67,+0.33>	<+1.00,+0.50>	<+1.00,+1.00>
<+3.00,-0.00>	
45: пересечений 11 терминальных 30 параллельных 4
[olej@dell ngon]$ cat 5.dat
0 0
0 1
1 2
2 1
1 0

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

[olej@dell ngon]$ ./ngon <6.dat
<+0.00,+2.00>  <+1.00,+1.00>  <+1.00,-1.00>  <+0.00,-2.00>  <-1.00,-1.00>  <-1.00,+1.00>  
6-угольник, 15 линий, 
<+2.00,-0.00>	<+3.00,-1.00>	<-2.00,+4.00>	<-1.00,+3.00>	<+0.67,-0.00>
<+0.50,+0.50>	<+2.00,-4.00>	<+0.33,+1.00>	<-1.00,+5.00>	<+1.00,+5.00>
<+1.00,-3.00>	<+1.00,+3.00>	<+1.00,-5.00>	<+0.00,+0.00>	<-0.00,-1.00>
<+0.00,+1.00>	<+0.00,-0.00>	<+0.33,-1.00>	<+2.00,+4.00>	<+0.50,-0.50>
<-1.00,-5.00>	<-2.00,-4.00>	<+3.00,+1.00>	<-1.00,-3.00>	<-0.33,+1.00>
<-0.50,+0.50>	<-0.67,-0.00>	<-0.00,+0.00>	<-0.50,-0.50>	<-3.00,-1.00>
<-0.33,-1.00>	<-2.00,+0.00>	<-3.00,+1.00>	
105: пересечений 33 терминальных 60 параллельных 12
[olej@dell ngon]$ cat 6.dat
 0  2
 1  1
 1 -1
 0 -2
-1 -1
-1  1
Вложения
ngon.tgz
(2.8 КБ) 117 скачиваний

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

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

Непрочитанное сообщение Olej » 22 дек 2016, 23:29

Имеется N городов, каждый из которых имеет целые координаты.
Расстояние между двумя городами определяется как |x1-x2|+|y1-y2|.
Требуется построить n+1 город и сделать его столицей (координаты должны быть целыми).
Место для столицы выбирается так, чтобы среднее арифметическое расстояний между столицей
и остальными городами было наименьшим и столица не должна стоять на уже построенном городе.
На вход подается N - количество городов (1<=N<=100); пары целых чисел, не превышающих 1000
по абсолютной величине - координаты городов.
На выходе два целых числа X и Y - координаты столицы.

Тут может быть 2 совершенно разных варианта (и >2):

1. Ищем размеры поля:
Xmax = max( x1, x2, ...) + 1
Xmin = min( x1, x2, ...) - 1
Ymax = max( y1, y2, ...) + 1
Ymin = min( y1, y2, ...) - 1
Для всех (Xmin ... Xmax) * (Ymin ... Ymax) точек поля просчитываем сумму расстояний D и фиксируем минимум этой величины D.

2. Ищем начальную позицию внутри поля:
X = sum( xi, i=1, n ) / n
Y = sum( yi, i=1, n ) / n
Из 4-х целочисленных позиций, окружающих вещественную позицию (X,Y) выбираем ближайшую.
Итерационно, в цикле, рассчитываем расстояния до каждой Di точки ... и сдвигаем позицию (X, Y) в направлении той точки, расстояние до которой минимально.

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

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

Непрочитанное сообщение Olej » 22 дек 2016, 23:35

Olej писал(а): 1. Ищем размеры поля:
Xmax = max( x1, x2, ...) + 1
Xmin = min( x1, x2, ...) - 1
Ymax = max( y1, y2, ...) + 1
Ymin = min( y1, y2, ...) - 1
Для всех (Xmin ... Xmax) * (Ymin ... Ymax) точек поля просчитываем сумму расстояний D и фиксируем минимум этой величины D.
capital.h :

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

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

struct town { 
   int x, y;
   town( int x = 0, int y = 0 ) {
      this->x = x; this->y = y;
   }
   town operator +( town shf ) {
      return town( x + shf.x, y + shf.y ); 
   } 
   inline unsigned operator -( const town& t ) {
      return abs( x - t.x ) + abs( y - t.y );
   }
   inline bool operator ==( const town& t ) {
      return x == t.x && y == t.y;
   }
};

ostream& operator <<( ostream& out, const town& t ) {
   char s[ 10 ];
   sprintf( s, "<%+03d,%+03d>", t.x, t.y ); 
   return out << s; 
}

unsigned summa( vector<town>& country, town point ) {
   unsigned ret = 0;
   for( auto &x : country ) ret += ( x - point );    
   return ret;
}
capital1.cc :

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

#include "capital.h"

int main( int argc, char **argv ) {
   vector<town> country;
   int xmin = 9999, xmax = -9999, ymin = 9999, ymax = -9999;
   while( true ) {
      string s;   
      getline( cin, s );
      if( !cin || 0 == s.length() ) break;
      town p; 
      istringstream( s ) >> p.x >> p.y;
      xmin = p.x < xmin ? p.x : xmin;
      xmax = p.x > xmax ? p.x : xmax;
      ymin = p.y < ymin ? p.y : ymin;
      ymax = p.y > ymax ? p.y : ymax; 
      country.push_back( p );
   }
   cout  << "городов " << country.size() << " : ";  
   for( auto &p : country ) cout << p << "  ";
   cout << endl;
   xmin -= 1; xmax += 1; ymin -= 1; ymax += 1;
   cout << "границы поля: [" << xmin << "..." << xmax 
        << ',' << ymin << "..." << ymax << "]" << endl;
   town capital = { xmin, ymin };
   unsigned distanse = summa( country, capital ), m = 0;
   for( int x = xmin; x <= xmax; x++ )
      for( int y = ymin; y <= ymax; y++ ) {
         town point = { x, y };
         if( find( country.begin(), country.end(), point ) != country.end() ) continue;
         unsigned d = summa( country, point );
         if( d < distanse ) {
            distanse = d;
            capital = point;
         }
         m++;
      }
   cout << "столица " << capital << " среднее расстояние " 
        << (float)distanse / country.size() << " число проб " << m << endl;       
}

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

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

Непрочитанное сообщение Olej » 22 дек 2016, 23:36

Olej писал(а): 2. Ищем начальную позицию внутри поля:
X = sum( xi, i=1, n ) / n
Y = sum( yi, i=1, n ) / n
Из 4-х целочисленных позиций, окружающих вещественную позицию (X,Y) выбираем ближайшую.
Итерационно, в цикле, рассчитываем расстояния до каждой Di точки ... и сдвигаем позицию (X, Y) в направлении той точки, расстояние до которой минимально.
capital2.cc :

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

#include "capital.h"

int main( int argc, char **argv ) {
   vector<town> country;
   double xm = 0, ym = 0;
   while( true ) {
      string s;   
      getline( cin, s );
      if( !cin || 0 == s.length() ) break;
      town p; 
      istringstream( s ) >> p.x >> p.y;
      xm += p.x;
      ym += p.y;
      country.push_back( p );
   }    
   cout  << "городов " << country.size() << " : ";  
   for( auto &p : country ) cout << p << "  ";
   cout << endl;
   town cp( xm / country.size(), ym / country.size() );
   unsigned dist = summa( country, cp ), m = 1;
   bool bstp;
   do {
      town neib[] = {
         { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 },
         { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }
      };
      bstp = false;
      town pm; 
      for( auto &p : neib ) {
         town pc = cp + p;
         if( find( country.begin(), country.end(), pc ) != country.end() )
            continue; 
         unsigned d = summa( country, pc ); //  cp + p );
         if( d < dist ) {
            dist = d;
            pm = pc; // cp + p;
            bstp = true;
         }
         m++;
      }
      if( bstp ) cp = pm;
   } while( bstp );    
   cout << "столица " << cp << " среднее расстояние " 
        << (float)dist / country.size() << " число проб " << m << endl;
}

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

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

Непрочитанное сообщение Olej » 22 дек 2016, 23:39

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

[olej@dell capital]$ ./capital1 < country.4
городов 4 : <+00,+03>  <+03,+00>  <+00,-03>  <-03,+00>
границы поля: [-4...4,-4...4]
столица <+00,+00> среднее расстояние 3 число проб 77

[olej@dell capital]$ ./capital2 < country.4
городов 4 : <+00,+03>  <+03,+00>  <+00,-03>  <-03,+00>
столица <+00,+00> среднее расстояние 3 число проб 9

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

[olej@dell capital]$ ./capital1 < country.80
городов 8 : <-20,-20>  <-10,+10>  <+10,+30>  <+30,+40>  <+60,+30>  <+50,+00>  <+30,-10>  <+10,-20>
границы поля: [-21...61,-21...41]
столица <+10,+00> среднее расстояние 42.5 число проб 5221

[olej@dell capital]$ ./capital2 < country.80
городов 8 : <-20,-20>  <-10,+10>  <+10,+30>  <+30,+40>  <+60,+30>  <+50,+00>  <+30,-10>  <+10,-20>
столица <+20,+07> среднее расстояние 42.5 число проб 9

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

[olej@dell capital]$ ./capital1 < country.800
городов 8 : <-200,-200>  <-100,+100>  <+100,+300>  <+300,+400>  <+600,+300>  <+500,+00>  <+300,-100>  <+100,-200>
границы поля: [-201...601,-201...401]
столица <+100,+00> среднее расстояние 425 число проб 484201

[olej@dell capital]$ ./capital2 < country.800
городов 8 : <-200,-200>  <-100,+100>  <+100,+300>  <+300,+400>  <+600,+300>  <+500,+00>  <+300,-100>  <+100,-200>
столица <+200,+75> среднее расстояние 425 число проб 9
Любопытно, что при наличии нескольких оптимальных размещений (как это чаще всего и бывает) 2 подхода находят разные оптимумы, но критерий оптимальности (средняя дистанция) у них одинаковые. Изучите показанные выше результаты...
Вложения
capital.tgz
(3.04 КБ) 108 скачиваний

Ответить

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

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

Сейчас этот форум просматривают: FAST WebCrawler [Crawler] и 8 гостей