fork download
copy 
  1.  
  2.  
  3.  
  4.  
  5.  
  6. #include <iostream>
  7.  
  8. class DividePatternGeneratorException {};
  9.  
  10. class DividePatternGenerator
  11. {
  12. private: /* private fields */
  13.  
  14.   int* _list;
  15.   int _size;
  16.   int _division;
  17.   int _min;
  18.   int _max;
  19.   int _count;
  20.  
  21. private: /* private constructors */
  22.  
  23.   DividePatternGenerator();
  24.  
  25. private: /* private methods */
  26.  
  27.   void init()
  28.   {
  29.     if(
  30.       _size < 2 ||
  31.       _division < 2 ||
  32.       _size < _division ||
  33.       _size < _min * _division ||
  34.       _max < _min ||
  35.       _size < _max + _min * ( _division - 1 ) )
  36.     {
  37.       throw DividePatternGeneratorException();
  38.     }
  39.     _list = new int[_division];
  40.     for( int i = 0; i < _division; i++ )
  41.     {
  42.       _list[i] = 0;
  43.     }
  44.   }
  45.  
  46. public: /* public constructors */
  47.  
  48.   DividePatternGenerator( int size, int division, int minsize, int maxsize )
  49.     : _size( size ), _division( division ), _min( minsize ), _max( maxsize ), _count( 0 )
  50.   {
  51.     init();
  52.   }
  53.  
  54.   DividePatternGenerator( int size, int division )
  55.     : _size( size ), _division( division ), _min( 1 ), _max( size - division + 1 ), _count( 0 )
  56.   {
  57.     init();
  58.   }
  59.  
  60.   DividePatternGenerator( int size )
  61.     : _size( size ), _division( 2 ), _min( size / 2 ), _max( size - 1 ), _count( 0 )
  62.   {
  63.     init();
  64.   }
  65.  
  66. public: /* public destructor */
  67.  
  68.   ~DividePatternGenerator()
  69.   {
  70.     delete[] _list;
  71.   }
  72.  
  73. public: /* public methods */
  74.  
  75.   int length() const
  76.   {
  77.     return _division;
  78.   }
  79.  
  80.   int size() const
  81.   {
  82.     return _size;
  83.   }
  84.  
  85.   int count() const
  86.   {
  87.     return _count;
  88.   }
  89.  
  90.   const int* list() const
  91.   {
  92.     return _list;
  93.   }
  94.  
  95.   const int* next()
  96.   {
  97.     int n, d, p;
  98.     bool f;
  99.  
  100.     if( !_count )
  101.     {
  102.       _list[0] = _min;
  103.       p = 1;
  104.       d = _division - 1;
  105.       n = _size - _min;
  106.       f = false;
  107.     }
  108.     else
  109.     {
  110.       p = _division - 2;
  111.       d = 2;
  112.       n = _list[p] + _list[p + 1];
  113.       f = true;
  114.     }
  115.  
  116.     for( ;; )
  117.     {
  118.       if( d == 1 )
  119.       {
  120.         if( n <= _max )
  121.         {
  122.           _list[p] = n;
  123.           n = 0;
  124.           d = 0;
  125.           _count++;
  126.           break;
  127.           // OK
  128.           // exit loop
  129.         }
  130.         else
  131.         {
  132.           d++;
  133.           p--;
  134.           n += _list[p];
  135.           f = true;
  136.         }
  137.       }
  138.       else
  139.       {
  140.         int m;
  141.         if( f )
  142.         {
  143.           m = _list[p] + 1;
  144.           f = false;
  145.         }
  146.         else
  147.         {
  148.           m = _list[p - 1];
  149.         }
  150.         if( m * d > n )
  151.         {
  152.           if( !p )
  153.           {
  154.             _count = 0;
  155.             _list[0] = _min;
  156.             p = 1;
  157.             d = _division - 1;
  158.             n = _size - _min;
  159.             // all pattern had gone
  160.             // reset pattern
  161.           }
  162.           else
  163.           {
  164.             d++;
  165.             p--;
  166.             n += _list[p];
  167.             f = true;
  168.           }
  169.         }
  170.         else
  171.         {
  172.           _list[p] = m;
  173.           n -= m;
  174.           d--;
  175.           p++;
  176.         }
  177.       }
  178.     }
  179.     return _list;
  180.   }
  181. };
  182.  
  183.  
  184. int main()
  185. {
  186.   try
  187.   {
  188.     DividePatternGenerator gen( 10, 5 );
  189.  
  190.     std::cout << "10個を5分割するパターンのリストを作る" << std::endl;
  191.  
  192.     std::cout << "size: " << gen.size() << std::endl;
  193.  
  194.     for( int j = 0; j < 10; j++ )
  195.     {
  196.       const int* list = gen.next();
  197.       std::cout << "[" << gen.count() << "] ";
  198.       for( int i = 0; i < gen.length(); i++ )
  199.       {
  200.         std::cout << list[i] << " ";
  201.       }
  202.       std::cout << std::endl;
  203.     }
  204.  
  205.     std::cout << "* * * * * * * * * * * * * *" << std::endl;
  206.  
  207.     DividePatternGenerator gen2( 10, 3 );
  208.  
  209.     std::cout << "10個を3分割するパターンのリストを作る" << std::endl;
  210.  
  211.     std::cout << "size: " << gen2.size() << std::endl;
  212.  
  213.     for( int j = 0; j < 10; j++ )
  214.     {
  215.       const int* list = gen2.next();
  216.       std::cout << "[" << gen2.count() << "] ";
  217.       for( int i = 0; i < gen2.length(); i++ )
  218.       {
  219.         std::cout << list[i] << " ";
  220.       }
  221.       std::cout << std::endl;
  222.     }
  223.   }
  224.   catch( DividePatternGeneratorException& ex )
  225.   {
  226.     std::cout << "Exception" << std::endl;
  227.   }
  228.  
  229.   return 0;
  230. }
  231.  
  232.  
  233.  
  234.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10個を5分割するパターンのリストを作る
size: 10
[1] 1 1 1 1 6 
[2] 1 1 1 2 5 
[3] 1 1 1 3 4 
[4] 1 1 2 2 4 
[5] 1 1 2 3 3 
[6] 1 2 2 2 3 
[7] 2 2 2 2 2 
[1] 1 1 1 1 6 
[2] 1 1 1 2 5 
[3] 1 1 1 3 4 
* * * * * * * * * * * * * *
10個を3分割するパターンのリストを作る
size: 10
[1] 1 1 8 
[2] 1 2 7 
[3] 1 3 6 
[4] 1 4 5 
[5] 2 2 6 
[6] 2 3 5 
[7] 2 4 4 
[8] 3 3 4 
[1] 1 1 8 
[2] 1 2 7
https://ideone.com/Q8pLau
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!