fork download
copy 
  1. //-----------------------------------------------------------------------------
  2. // 数値Nを重複しないN以下の数に分割するプログラム
  3. //-----------------------------------------------------------------------------
  4. // N -> Answer
  5. // 3 -> Q=2 : 3, 2+1
  6. // 4 -> Q=2 : 4, 3+1
  7. // 5 -> Q=3 : 5, 4+1, 3+2
  8. // 6 -> Q=4 : 6, 5+1, 4+2, 3+2+1
  9. //-----------------------------------------------------------------------------
  10. #include <stdio.h>
  11. #include <queue>
  12. #include <stack>
  13.  
  14. #define LOG_ENABLE 0
  15. #define MAXNUMBER  25
  16.  
  17. typedef struct {
  18. 	int sum;
  19. 	int start;
  20. 	int hist[MAXNUMBER + 1];
  21. } PartData;
  22.  
  23. void PartDataPrint(PartData* pd)
  24. {
  25. #if (LOG_ENABLE == 1)
  26. 	int i;
  27. 	for (i = 1; i <= pd->sum; i++) {
  28. 		if (pd->hist[i]) {
  29. 			printf("%d ", pd->hist[i]);
  30. 		}
  31. 	}
  32. 	printf("\n");
  33. #endif
  34. }
  35.  
  36. //-----------------------------------------------------------------------------
  37. // 総当たり実装
  38. //-----------------------------------------------------------------------------
  39. int brute_force(int N)
  40. {
  41. 	int num, i, val;
  42. 	int count = 0;
  43.  
  44. 	for (num = 1; num < (1 << N); num++)
  45. 	{
  46. 		val = 0;
  47. 		for (i = 0; i<MAXNUMBER; i++) {
  48. 			if (num & (1 << i)) {
  49. 				val += (i + 1);
  50. 			}
  51. 		}
  52. 		if (val == N) {
  53. #if (LOG_ENABLE == 1)
  54. 			printf("[%2d] ",count);
  55. 			for (i = 0; i<MAXNUMBER; i++) {
  56. 				if (bitimg & (1 << i)) {
  57. 					printf("%d ", i + 1);
  58. 				}
  59. 			}
  60. 			printf("\n");
  61. #endif
  62. 			count++;
  63. 		}
  64. 	}
  65. 	return count;
  66. }
  67.  
  68.  
  69. //-----------------------------------------------------------------------------
  70. // 再起呼び出し実装
  71. //-----------------------------------------------------------------------------
  72. int recursive(int N, PartData* prev = NULL)
  73. {
  74. 	int n;
  75. 	int num = 0;
  76. 	PartData pd = { 0, 1 };
  77.  
  78. 	if (prev == NULL) { prev = &pd; }
  79.  
  80. 	for (n = prev->start; n <= N; n++)
  81. 	{
  82. 		PartData nd = *prev;
  83. 		nd.sum += n;
  84. 		nd.start = n + 1;
  85. 		nd.hist[n] = n;
  86.  
  87. 		if (nd.sum > N) { return 0; }
  88. 		if (nd.sum == N)
  89. 		{
  90. 			PartDataPrint(&nd);
  91. 			num++;
  92. 			return num;
  93. 		}
  94. 		else
  95. 		{
  96. 			num += recursive(N, &nd);
  97. 		}
  98. 	}
  99. 	return num;
  100. }
  101.  
  102. //-----------------------------------------------------------------------------
  103. // スタック or キューを使った実装
  104. //-----------------------------------------------------------------------------
  105. int stack_or_que(int N, int isStack)
  106. {
  107. 	int i;
  108. 	int num = 0;
  109. 	std::stack<PartData> stk;
  110. 	std::queue<PartData> que;
  111.  
  112. 	// 初期値登録
  113. 	//  合計値       = 0
  114. 	//  ループ開始値 = 1
  115. 	PartData s = { 0, 1 };
  116. 	if (isStack)	stk.push(s);
  117. 	else        que.push(s);
  118.  
  119. 	while ((isStack ? stk.size() : que.size()) > 0)
  120. 	{
  121. 		if (isStack) { s = stk.top();   stk.pop(); } // 値を取り出す
  122. 		else { s = que.front(); que.pop(); } // 値を取り出す
  123.  
  124. 		// 目標値に到達していれば表示して次へ
  125. 		if (s.sum == N)
  126. 		{
  127. 			PartDataPrint(&s);
  128. 			num++;
  129. 			continue;
  130. 		}
  131.  
  132. 		// s を 1 要素分だけ探索
  133. 		// "合計値 <= N" の条件に該当するものを登録
  134. 		for (i = s.start; i <= N; i++)
  135. 		{
  136. 			PartData cp = s;
  137. 			cp.sum += i;
  138. 			cp.start = i + 1;
  139. 			cp.hist[i] = i;
  140.  
  141. 			if (cp.sum > N)
  142. 			{
  143. 				break; // これ以上の探索は無駄なのでbreak
  144. 			}
  145. 			if (isStack) { stk.push(cp); }
  146. 			else { que.push(cp); }
  147. 		}
  148. 	}
  149. 	return num;
  150. }
  151.  
  152. int main(int argc, char** argv)
  153. {
  154. 	int N = 0;
  155.  
  156. 	for (N = 1; N <= MAXNUMBER; N++)
  157. 	{
  158. 		int Q0 = brute_force(N);
  159. 		int Q1 = stack_or_que(N, 1);
  160. 		int Q2 = recursive(N);
  161.  
  162. 		if (Q0 != Q1 || Q0 != Q2) {
  163. 			printf("[%2d] NG %d %d %d \n", N, Q0, Q1, Q2);
  164. 		}
  165. 		else {
  166. 			printf("[%2d] OK %d %d %d \n", N, Q0, Q1, Q2);
  167. 		}
  168. 	}
  169. 	return 0;
  170. }
  171.  
  172.  
Success #stdin #stdout 0.24s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[ 1] OK 1 1 1 
[ 2] OK 1 1 1 
[ 3] OK 2 2 2 
[ 4] OK 2 2 2 
[ 5] OK 3 3 3 
[ 6] OK 4 4 4 
[ 7] OK 5 5 5 
[ 8] OK 6 6 6 
[ 9] OK 8 8 8 
[10] OK 10 10 10 
[11] OK 12 12 12 
[12] OK 15 15 15 
[13] OK 18 18 18 
[14] OK 22 22 22 
[15] OK 27 27 27 
[16] OK 32 32 32 
[17] OK 38 38 38 
[18] OK 46 46 46 
[19] OK 54 54 54 
[20] OK 64 64 64 
[21] OK 76 76 76 
[22] OK 89 89 89 
[23] OK 104 104 104 
[24] OK 122 122 122 
[25] OK 142 142 142
https://ideone.com/abDUD5
language:
C++14 (clang 8.0)
created:
9 years ago
visibility:
secret

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!