Ideone.com

download

copy

#include <iostream>
using namespace std;
 
class
DividePatternGeneratorException
	{
	}
	;
 
class
DividePatternGenerator
	{
	private: /* private fields */
 
		int *
		_list
			;
 
		int
		_size
			;
 
		int
		_division
			;
 
		int
		_min
			;
 
		int
		_max
			;
 
		int
		_count
			;
 
	private: /* private constructors */
 
		DividePatternGenerator
			(
			)
			;
 
	private: /* private methods */
 
		void
		init
			(
			)
			{
				if
					(	_size < 2
					||	_division < 2
					||	_size < _division
					||	_size < _min * _division
					||	_max < _min
					||	_size < _max + _min * (_division - 1 )
					)
					{
						throw DividePatternGeneratorException();		
					}
				_list = new int[_division];
				for
					(	int i = 0
					;	i < _division
					;	i++
					)
					{
						_list[i] = 0;
					}
			}
 
	public: /* public constructors */
 
		DividePatternGenerator
			(	int size
			,	int division
			,	int minsize
			,	int maxsize
			)
			:	_size(size)
			,	_division(division)
			,	_min(minsize)
			,	_max(maxsize)
			,	_count(0)
			{
				init();
			}
 
		DividePatternGenerator
			(	int size
			,	int division
			)
			:	_size(size)
			,	_division(division)
			,	_min(1)
			,	_max(size - division + 1)
			,	_count(0)
			{
				init();
			}
 
		DividePatternGenerator
			(	int size
			)
			:	_size(size)
			,	_division(2)
			,	_min(size / 2)
			,	_max(size - 1)
			,	_count(0)
			{
				init();
			}
 
	public: /* public destructor */
 
		~DividePatternGenerator
			(
			)
			{
				delete [] _list;
			}
 
	public: /* public methods */
 
		int
		length
			(
			)
			const
			{
				return _division;
			}
 
		int
		size
			(
			)
			const
			{
				return _size;
			}
 
		int
		count
			(
			)
			const
			{
				return _count;
			}
 
		const int *
		list
			(
			)
			const
			{
				return _list;
			}
 
		const int *
		next
			(
			)
			{
				int n, d, p;
				bool f;
 
				if
					(	_count == 0
					)
					{
						_list[0] = _min;
						p = 1;
						d = _division - 1;
						n = _size - _min;
						f = false;
					}
				else
					{
						p = _division - 2;
						d = 2;
						n = _list[p] + _list[p + 1];
						f = true;
					}
 
				for
					(
					;
					;
					)
					{
						if
							(	d == 1
							)
							{
								if
									(	n <= _max
									)
									{
										_list[p] = n;
										n = 0;
										d = 0;
										_count++;
										break;
										// OK
										// exit loop
									}
								else
									{
										d++;
										p--;
										n += _list[p];
										f = true;
									}
							}
						else
							{
								int m;
								if
									(	f == true
									)
									{
										m = _list[p] + 1;
										f = false;
									}
								else
									{
										m = _list[p - 1];
									}
								if
									(	m * d > n
									)
									{
										if
											(	p == 0
											)
											{
												_count = 0;
												_list[0] = _min;
												p = 1;
												d = _division - 1;
												n = _size - _min;
												// all pattern had gone
												// reset pattern
											}
										else
											{
												d++;
												p--;
												n += _list[p];
												f = true;
											}
									}
								else
									{
										_list[p] = m;
										n -= m;
										d--;
										p++;
									}
							}
					}
				return _list;
			}
	}
	;
 
 
int
main
	(
	)
	{
		try
			{
				DividePatternGenerator gen(10, 5);
 
				cout << "10個を5分割するパターンのリストを作る" << endl;
 
				cout << "size: " << gen.size() << endl;
 
				for
					(	int j = 0
					;	j < 10
					;	j++
					)
					{
						const int* list = gen.next();
						cout << "[" << gen.count() << "] ";
						for
							(	int i = 0
							;	i < gen.length()
							;	i++
							)
							{
								cout << list[i] << " ";
							}
						cout << endl;
					}
 
				cout << "* * * * * * * * * * * * * *" << endl;
 
				DividePatternGenerator gen2(10, 3);
 
				cout << "10個を3分割するパターンのリストを作る" << endl;
 
				cout << "size: " << gen2.size() << endl;
 
				for
					(	int j = 0
					;	j < 10
					;	j++
					)
					{
						const int* list = gen2.next();
						cout << "[" << gen2.count() << "] ";
						for
							(	int i = 0
							;	i < gen2.length()
							;	i++
							)
							{
								cout << list[i] << " ";
							}
						cout << endl;
					}
			}
		catch
			(	DividePatternGeneratorException& ex
			)
			{
				cout << "Exception" << endl;
			}
 
		return 0;
	}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MKRGl2aWRlUGF0dGVybkdlbmVyYXRvckV4Y2VwdGlvbgoJewoJfQoJOwoKY2xhc3MKRGl2aWRlUGF0dGVybkdlbmVyYXRvcgoJewoJcHJpdmF0ZTogLyogcHJpdmF0ZSBmaWVsZHMgKi8KCQkKCQlpbnQgKgoJCV9saXN0CgkJCTsKCQkKCQlpbnQKCQlfc2l6ZQoJCQk7CgkJCgkJaW50CgkJX2RpdmlzaW9uCgkJCTsKCQkKCQlpbnQKCQlfbWluCgkJCTsKCQkKCQlpbnQKCQlfbWF4CgkJCTsKCQkKCQlpbnQKCQlfY291bnQKCQkJOwoJCglwcml2YXRlOiAvKiBwcml2YXRlIGNvbnN0cnVjdG9ycyAqLwoJCgkJRGl2aWRlUGF0dGVybkdlbmVyYXRvcgoJCQkoCgkJCSkKCQkJOwoJCQoJcHJpdmF0ZTogLyogcHJpdmF0ZSBtZXRob2RzICovCgkKCQl2b2lkCgkJaW5pdAoJCQkoCgkJCSkKCQkJewoJCQkJaWYKCQkJCQkoCV9zaXplIDwgMgoJCQkJCXx8CV9kaXZpc2lvbiA8IDIKCQkJCQl8fAlfc2l6ZSA8IF9kaXZpc2lvbgoJCQkJCXx8CV9zaXplIDwgX21pbiAqIF9kaXZpc2lvbgoJCQkJCXx8CV9tYXggPCBfbWluCgkJCQkJfHwJX3NpemUgPCBfbWF4ICsgX21pbiAqIChfZGl2aXNpb24gLSAxICkKCQkJCQkpCgkJCQkJewoJCQkJCQl0aHJvdyBEaXZpZGVQYXR0ZXJuR2VuZXJhdG9yRXhjZXB0aW9uKCk7CQkKCQkJCQl9CgkJCQlfbGlzdCA9IG5ldyBpbnRbX2RpdmlzaW9uXTsKCQkJCWZvcgoJCQkJCSgJaW50IGkgPSAwCgkJCQkJOwlpIDwgX2RpdmlzaW9uCgkJCQkJOwlpKysKCQkJCQkpCgkJCQkJewoJCQkJCQlfbGlzdFtpXSA9IDA7CgkJCQkJfQoJCQl9CgkJCglwdWJsaWM6IC8qIHB1YmxpYyBjb25zdHJ1Y3RvcnMgKi8KCQkKCQlEaXZpZGVQYXR0ZXJuR2VuZXJhdG9yCgkJCSgJaW50IHNpemUKCQkJLAlpbnQgZGl2aXNpb24KCQkJLAlpbnQgbWluc2l6ZQoJCQksCWludCBtYXhzaXplCgkJCSkKCQkJOglfc2l6ZShzaXplKQoJCQksCV9kaXZpc2lvbihkaXZpc2lvbikKCQkJLAlfbWluKG1pbnNpemUpCgkJCSwJX21heChtYXhzaXplKQoJCQksCV9jb3VudCgwKQoJCQl7CgkJCQlpbml0KCk7CgkJCX0KCgkJRGl2aWRlUGF0dGVybkdlbmVyYXRvcgoJCQkoCWludCBzaXplCgkJCSwJaW50IGRpdmlzaW9uCgkJCSkKCQkJOglfc2l6ZShzaXplKQoJCQksCV9kaXZpc2lvbihkaXZpc2lvbikKCQkJLAlfbWluKDEpCgkJCSwJX21heChzaXplIC0gZGl2aXNpb24gKyAxKQoJCQksCV9jb3VudCgwKQoJCQl7CgkJCQlpbml0KCk7CgkJCX0KCQoJCURpdmlkZVBhdHRlcm5HZW5lcmF0b3IKCQkJKAlpbnQgc2l6ZQoJCQkpCgkJCToJX3NpemUoc2l6ZSkKCQkJLAlfZGl2aXNpb24oMikKCQkJLAlfbWluKHNpemUgLyAyKQoJCQksCV9tYXgoc2l6ZSAtIDEpCgkJCSwJX2NvdW50KDApCgkJCXsKCQkJCWluaXQoKTsKCQkJfQoJCglwdWJsaWM6IC8qIHB1YmxpYyBkZXN0cnVjdG9yICovCgkKCQl+RGl2aWRlUGF0dGVybkdlbmVyYXRvcgoJCQkoCgkJCSkKCQkJewoJCQkJZGVsZXRlIFtdIF9saXN0OwoJCQl9CgkKCXB1YmxpYzogLyogcHVibGljIG1ldGhvZHMgKi8KCQkKCQlpbnQKCQlsZW5ndGgKCQkJKAoJCQkpCgkJCWNvbnN0CgkJCXsKCQkJCXJldHVybiBfZGl2aXNpb247CgkJCX0KCQkKCQlpbnQKCQlzaXplCgkJCSgKCQkJKQoJCQljb25zdAoJCQl7CgkJCQlyZXR1cm4gX3NpemU7CgkJCX0KCQkKCQlpbnQKCQljb3VudAoJCQkoCgkJCSkKCQkJY29uc3QKCQkJewoJCQkJcmV0dXJuIF9jb3VudDsKCQkJfQoJCQoJCWNvbnN0IGludCAqCgkJbGlzdAoJCQkoCgkJCSkKCQkJY29uc3QKCQkJewoJCQkJcmV0dXJuIF9saXN0OwoJCQl9CgkJCgkJY29uc3QgaW50ICoKCQluZXh0CgkJCSgKCQkJKQoJCQl7CgkJCQlpbnQgbiwgZCwgcDsKCQkJCWJvb2wgZjsKCQkJCQoJCQkJaWYKCQkJCQkoCV9jb3VudCA9PSAwCgkJCQkJKQoJCQkJCXsKCQkJCQkJX2xpc3RbMF0gPSBfbWluOwoJCQkJCQlwID0gMTsKCQkJCQkJZCA9IF9kaXZpc2lvbiAtIDE7CgkJCQkJCW4gPSBfc2l6ZSAtIF9taW47CgkJCQkJCWYgPSBmYWxzZTsKCQkJCQl9CgkJCQllbHNlCgkJCQkJewoJCQkJCQlwID0gX2RpdmlzaW9uIC0gMjsKCQkJCQkJZCA9IDI7CgkJCQkJCW4gPSBfbGlzdFtwXSArIF9saXN0W3AgKyAxXTsKCQkJCQkJZiA9IHRydWU7CgkJCQkJfQoJCQkJCgkJCQlmb3IKCQkJCQkoCgkJCQkJOwoJCQkJCTsKCQkJCQkpCgkJCQkJewoJCQkJCQlpZgoJCQkJCQkJKAlkID09IDEKCQkJCQkJCSkKCQkJCQkJCXsKCQkJCQkJCQlpZgoJCQkJCQkJCQkoCW4gPD0gX21heAoJCQkJCQkJCQkpCgkJCQkJCQkJCXsKCQkJCQkJCQkJCV9saXN0W3BdID0gbjsKCQkJCQkJCQkJCW4gPSAwOwoJCQkJCQkJCQkJZCA9IDA7CgkJCQkJCQkJCQlfY291bnQrKzsKCQkJCQkJCQkJCWJyZWFrOwoJCQkJCQkJCQkJLy8gT0sKCQkJCQkJCQkJCS8vIGV4aXQgbG9vcAoJCQkJCQkJCQl9CgkJCQkJCQkJZWxzZQoJCQkJCQkJCQl7CgkJCQkJCQkJCQlkKys7CgkJCQkJCQkJCQlwLS07CgkJCQkJCQkJCQluICs9IF9saXN0W3BdOwoJCQkJCQkJCQkJZiA9IHRydWU7CgkJCQkJCQkJCX0KCQkJCQkJCX0KCQkJCQkJZWxzZQoJCQkJCQkJewoJCQkJCQkJCWludCBtOwoJCQkJCQkJCWlmCgkJCQkJCQkJCSgJZiA9PSB0cnVlCgkJCQkJCQkJCSkKCQkJCQkJCQkJewoJCQkJCQkJCQkJbSA9IF9saXN0W3BdICsgMTsKCQkJCQkJCQkJCWYgPSBmYWxzZTsKCQkJCQkJCQkJfQoJCQkJCQkJCWVsc2UKCQkJCQkJCQkJewoJCQkJCQkJCQkJbSA9IF9saXN0W3AgLSAxXTsKCQkJCQkJCQkJfQoJCQkJCQkJCWlmCgkJCQkJCQkJCSgJbSAqIGQgPiBuCgkJCQkJCQkJCSkKCQkJCQkJCQkJewoJCQkJCQkJCQkJaWYKCQkJCQkJCQkJCQkoCXAgPT0gMAoJCQkJCQkJCQkJCSkKCQkJCQkJCQkJCQl7CgkJCQkJCQkJCQkJCV9jb3VudCA9IDA7CgkJCQkJCQkJCQkJCV9saXN0WzBdID0gX21pbjsKCQkJCQkJCQkJCQkJcCA9IDE7CgkJCQkJCQkJCQkJCWQgPSBfZGl2aXNpb24gLSAxOwoJCQkJCQkJCQkJCQluID0gX3NpemUgLSBfbWluOwoJCQkJCQkJCQkJCQkvLyBhbGwgcGF0dGVybiBoYWQgZ29uZQoJCQkJCQkJCQkJCQkvLyByZXNldCBwYXR0ZXJuCgkJCQkJCQkJCQkJfQoJCQkJCQkJCQkJZWxzZQoJCQkJCQkJCQkJCXsKCQkJCQkJCQkJCQkJZCsrOwoJCQkJCQkJCQkJCQlwLS07CgkJCQkJCQkJCQkJCW4gKz0gX2xpc3RbcF07CgkJCQkJCQkJCQkJCWYgPSB0cnVlOwoJCQkJCQkJCQkJCX0KCQkJCQkJCQkJfQoJCQkJCQkJCWVsc2UKCQkJCQkJCQkJewoJCQkJCQkJCQkJX2xpc3RbcF0gPSBtOwoJCQkJCQkJCQkJbiAtPSBtOwoJCQkJCQkJCQkJZC0tOwoJCQkJCQkJCQkJcCsrOwoJCQkJCQkJCQl9CgkJCQkJCQl9CgkJCQkJfQoJCQkJcmV0dXJuIF9saXN0OwoJCQl9Cgl9Cgk7CgoKaW50Cm1haW4KCSgKCSkKCXsKCQl0cnkKCQkJewoJCQkJRGl2aWRlUGF0dGVybkdlbmVyYXRvciBnZW4oMTAsIDUpOwoJCQkJCgkJCQljb3V0IDw8ICIxMOWAi+OCkjXliIblibLjgZnjgovjg5Hjgr/jg7zjg7Pjga7jg6rjgrnjg4jjgpLkvZzjgosiIDw8IGVuZGw7CgkJCQkKCQkJCWNvdXQgPDwgInNpemU6ICIgPDwgZ2VuLnNpemUoKSA8PCBlbmRsOwoJCQkJCgkJCQlmb3IKCQkJCQkoCWludCBqID0gMAoJCQkJCTsJaiA8IDEwCgkJCQkJOwlqKysKCQkJCQkpCgkJCQkJewoJCQkJCQljb25zdCBpbnQqIGxpc3QgPSBnZW4ubmV4dCgpOwoJCQkJCQljb3V0IDw8ICJbIiA8PCBnZW4uY291bnQoKSA8PCAiXSAiOwoJCQkJCQlmb3IKCQkJCQkJCSgJaW50IGkgPSAwCgkJCQkJCQk7CWkgPCBnZW4ubGVuZ3RoKCkKCQkJCQkJCTsJaSsrCgkJCQkJCQkpCgkJCQkJCQl7CgkJCQkJCQkJY291dCA8PCBsaXN0W2ldIDw8ICIgIjsKCQkJCQkJCX0KCQkJCQkJY291dCA8PCBlbmRsOwoJCQkJCX0KCQkJCQkKCQkJCWNvdXQgPDwgIiogKiAqICogKiAqICogKiAqICogKiAqICogKiIgPDwgZW5kbDsKCgkJCQlEaXZpZGVQYXR0ZXJuR2VuZXJhdG9yIGdlbjIoMTAsIDMpOwoJCQkJCgkJCQljb3V0IDw8ICIxMOWAi+OCkjPliIblibLjgZnjgovjg5Hjgr/jg7zjg7Pjga7jg6rjgrnjg4jjgpLkvZzjgosiIDw8IGVuZGw7CgkJCQkKCQkJCWNvdXQgPDwgInNpemU6ICIgPDwgZ2VuMi5zaXplKCkgPDwgZW5kbDsKCQkJCQoJCQkJZm9yCgkJCQkJKAlpbnQgaiA9IDAKCQkJCQk7CWogPCAxMAoJCQkJCTsJaisrCgkJCQkJKQoJCQkJCXsKCQkJCQkJY29uc3QgaW50KiBsaXN0ID0gZ2VuMi5uZXh0KCk7CgkJCQkJCWNvdXQgPDwgIlsiIDw8IGdlbjIuY291bnQoKSA8PCAiXSAiOwoJCQkJCQlmb3IKCQkJCQkJCSgJaW50IGkgPSAwCgkJCQkJCQk7CWkgPCBnZW4yLmxlbmd0aCgpCgkJCQkJCQk7CWkrKwoJCQkJCQkJKQoJCQkJCQkJewoJCQkJCQkJCWNvdXQgPDwgbGlzdFtpXSA8PCAiICI7CgkJCQkJCQl9CgkJCQkJCWNvdXQgPDwgZW5kbDsKCQkJCQl9CgkJCX0KCQljYXRjaAoJCQkoCURpdmlkZVBhdHRlcm5HZW5lcmF0b3JFeGNlcHRpb24mIGV4CgkJCSkKCQkJewoJCQkJY291dCA8PCAiRXhjZXB0aW9uIiA8PCBlbmRsOwoJCQl9CgkJCgkJcmV0dXJuIDA7Cgl9CgoKCg==

Success #stdin #stdout 0s 3432KB

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/8UGdHv

language:

C++ (gcc 8.3)

created:

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language