找回密码
 欢迎注册
查看: 17004|回复: 13

[讨论] 求解拆分数组成固定组数的拆分方法(函数)

[复制链接]
发表于 2009-7-10 18:41:05 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
一个老问题,但这次没有限制,求全分组。具体如下: 设有1.....30个整数存放入a[1...30]的整数数组中,初始化如下: int a[30]; for (int i=0;i<30;i++) a[i]= i+1; 现要把此30个数分成10个组,每组固定3个数(不管数的顺序,如1,2,3 和 2, 3,1 算一样的一组)。 1)设计一个函数,打印出该30数组拆分为10组的全部可能的分组情况,每行打印一种拆分方法,以||分开各组。如: 1 2 3 ||4 5 6 ||7 8 9 ||10 11 12 ||13 14 15|| 16 17 18|| 19 20 21|| 22 23 24|| 25 26 27|| 28 29 30|| --算一种拆分方法 ..... ..... 2)该函数返回30个数拆分为10个组的所有的可能拆分数(就是返回上面多少行),这个数应该是固定的,具体多少我还没搞懂。 请指教,谢谢。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-10 22:47:00 | 显示全部楼层
2) 取最小的,然后找两个和它一组 f(n)=C(2,n-1)*f(n-3)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-7-10 22:49:58 | 显示全部楼层
没明白版主的意思?能说明白些吗?取最小的是取什么最小的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-7-10 23:08:48 | 显示全部楼层
我自己写了一个函数,理论上可以实现。但是运算时间太太长了。。。。。。。。。不现实。有人给出意见吗?
  1. ============Part 1 - Head.h============================
  2. //head.h
  3. #include<iostream>
  4. #include<bitset>
  5. #include<iomanip>
  6. #include<algorithm>
  7. #include<fstream>
  8. #include<cstdlib>
  9. #include<string>
  10. #include<vector>
  11. #include<set>
  12. #include<map>
  13. #include<utility>
  14. #include<cstdlib>
  15. #include<ctime>
  16. #include <sstream>
  17. #include <cmath>
  18. //一个Group (三个数字)
  19. struct Group {
  20. int r1;
  21. int r2;
  22. int r3;
  23. std::set<int> rSet;
  24. void reset() {
  25. r1 = r2 = r3 = 0;
  26. rSet.clear();
  27. }
  28. void setCodes(int num1,int num2,int num3) {
  29. r1 = num1;
  30. r2 = num2;
  31. r3 = num3;
  32. rSet.clear();
  33. rSet.insert(rSet.end(),r1);
  34. rSet.insert(rSet.end(),r2);
  35. rSet.insert(rSet.end(),r3);
  36. }
  37. Group() {
  38. reset();
  39. }
  40. };
  41. //一种折分方法
  42. struct OneDivided{
  43. Group group[10];
  44. void reset() {
  45. for(int i=0;i<10;i++) {
  46. group[i].reset();
  47. }
  48. }
  49. OneDivided(){
  50. reset();
  51. }
  52. };
  53. //求数组a中的n个数的m组合,组合的结果以整数的集合形式放入codesResult中
  54. int
  55. combineCodes(int a[], int n, int m, std::vector<ThreeCodes>& codesResult) const{
  56. codesResult.clear();
  57. //m should smaller or equal n
  58. m = m > n ? n : m;
  59. int* order = new int[m+1];
  60. for(int i=0; i<=m; i++) {
  61. order[i] = i-1; // 注意这里order[0]=-1用来作为循环判断标识
  62. }
  63. int count = 0;
  64. int k = m;
  65. bool flag = true; // 标志找到一个有效组合
  66. while(order[0] == -1) {
  67. if(flag) {
  68. // 输出符合要求的组合
  69. ThreeCodes item;
  70. item.reset();
  71. for(int i=1; i<=m; i++){
  72. //std::cout << a[order[i]] << " ";
  73. if(i==1) {
  74. item.r1 = a[order[1]];
  75. } else if(i==2){
  76. item.r2 = a[order[2]];
  77. } else if(i==3) {
  78. item.r3 = a[order[3]];
  79. }
  80. }
  81. codesResult.push_back(item);
  82. //std::cout << std::endl;
  83. count++;
  84. flag = false;
  85. }
  86. order[k]++; // 在当前位置选择新的数字
  87. if(order[k] == n) // 当前位置已无数字可选,回溯
  88. {
  89. order[k--] = 0;
  90. continue;
  91. }
  92. if(k < m) // 更新当前位置的下一位置的数字
  93. {
  94. order[++k] = order[k-1];
  95. continue;
  96. }
  97. if(k == m) {
  98. flag = true;
  99. }
  100. }
  101. delete[] order;
  102. return count;
  103. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-7-10 23:12:10 | 显示全部楼层
  1. ============Part2---------main.cpp==============================
  2. #include "head.h"
  3. //求把30个数的数组分解为10个Group的算法
  4. //思量是:先将30个数组合3,一共有4060个3组合。
  5. //然后再在这4060个组合里面依次选出第1个Group,第2个Group....第10个Group
  6. //选择的范围就是在上面组合出来的4060个3组合里面选,选第n+1个Group的时候排除掉和
  7. //第1 - n组合3有重复的3组合(就是只选前面没有出现的Group)来保证各个Group是互相独立的
  8. //没有交集。
  9. long Get30Group10(void) const {
  10. long total = 0;
  11. std::vector<ThreeCodes> threeCodeResult;
  12. int howManyThreeCodeResult = 0;
  13. int a[30];
  14. for(int i=0;i<30;i++) a[i] = i+1;
  15. //howManyThreeCodeResult is 4060
  16. howManyThreeCodeResult = combineCodes(a,30,3,threeCodeResult);
  17. std::set<int> reSet;
  18. std::set<int> tmpSet;
  19. std::set<int>::iterator reIter;
  20. for(int i=0;i<howManyThreeCodeResult;i++){
  21. //求一种分拆方式,分拆的10个Group放入oneDivided中
  22. OneDivided oneDivided;
  23. //选择Group0
  24. oneDivided.group[0].setCodes(threeCodeResult[i].r1,
  25. threeCodeResult[i].r2,
  26. threeCodeResult[i].r3);
  27. for(int j=0;j<howManyThreeCodeResult;j++) {
  28. tmpSet.clear();
  29. tmpSet.insert(tmpSet.begin(),threeCodeResult[j].r1);
  30. tmpSet.insert(tmpSet.begin(),threeCodeResult[j].r2);
  31. tmpSet.insert(tmpSet.begin(),threeCodeResult[j].r3);
  32. reSet.clear();
  33. reIter = reSet.begin();
  34. set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  35. tmpSet.begin(), tmpSet.end(),
  36. inserter(reSet, reIter));
  37. if(reSet.size() > 0) {
  38. //有相同
  39. continue;
  40. }
  41. //选择Group1, 在选择Group1之前,先排除和Group0有重复的元素,下面其他类似
  42. oneDivided.group[1].setCodes(threeCodeResult[j].r1,
  43. threeCodeResult[j].r2,threeCodeResult[j].r3);
  44. for(int k=0;k<howManyThreeCodeResult;k++) {
  45. tmpSet.clear();
  46. tmpSet.insert(tmpSet.begin(),threeCodeResult[k].r1);
  47. tmpSet.insert(tmpSet.begin(),threeCodeResult[k].r2);
  48. tmpSet.insert(tmpSet.begin(),threeCodeResult[k].r3);
  49. reSet.clear();
  50. reIter = reSet.begin();
  51. set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  52. tmpSet.begin(), tmpSet.end(),
  53. inserter(reSet, reIter));
  54. int size0 = reSet.size();
  55. if(size0 > 0) {
  56. continue;
  57. }
  58. reSet.clear();
  59. reIter = reSet.begin();
  60. set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  61. tmpSet.begin(), tmpSet.end(),
  62. inserter(reSet, reIter));
  63. int size1 = reSet.size();
  64. if(size1 > 0) {
  65. //有相同
  66. continue;
  67. }
  68. oneDivided.group[2].setCodes(threeCodeResult[k].r1,
  69. threeCodeResult[k].r2,threeCodeResult[k].r3);
  70. for(int m=0;m<howManyThreeCodeResult;m++) {
  71. tmpSet.clear();
  72. tmpSet.insert(tmpSet.begin(),threeCodeResult[m].r1);
  73. tmpSet.insert(tmpSet.begin(),threeCodeResult[m].r2);
  74. tmpSet.insert(tmpSet.begin(),threeCodeResult[m].r3);
  75. reSet.clear();
  76. reIter = reSet.begin();
  77. set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  78. tmpSet.begin(), tmpSet.end(),
  79. inserter(reSet, reIter));
  80. int size0 = reSet.size();
  81. if(size0 > 0) {
  82. continue;
  83. }
  84. reSet.clear();
  85. reIter = reSet.begin();
  86. set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  87. tmpSet.begin(), tmpSet.end(),
  88. inserter(reSet, reIter));
  89. int size1 = reSet.size();
  90. if(size1 > 0) {
  91. continue;
  92. }
  93. reSet.clear();
  94. reIter = reSet.begin();
  95. set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  96. tmpSet.begin(), tmpSet.end(),
  97. inserter(reSet, reIter));
  98. int size2 = reSet.size();
  99. if(size2 > 0) {
  100. continue;
  101. }
  102. oneDivided.group[3].setCodes(threeCodeResult[m].r1,
  103. threeCodeResult[m].r2,threeCodeResult[m].r3);
  104. for(int n=0;n<howManyThreeCodeResult;n++) {
  105. tmpSet.clear();
  106. tmpSet.insert(tmpSet.begin(),threeCodeResult[n].r1);
  107. tmpSet.insert(tmpSet.begin(),threeCodeResult[n].r2);
  108. tmpSet.insert(tmpSet.begin(),threeCodeResult[n].r3);
  109. reSet.clear();
  110. reIter = reSet.begin();
  111. set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  112. tmpSet.begin(), tmpSet.end(),
  113. inserter(reSet, reIter));
  114. int size0 = reSet.size();
  115. if(size0 > 0) {
  116. continue;
  117. }
  118. reSet.clear();
  119. reIter = reSet.begin();
  120. set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  121. tmpSet.begin(), tmpSet.end(),
  122. inserter(reSet, reIter));
  123. int size1 = reSet.size();
  124. if(size1 > 0) {
  125. continue;
  126. }
  127. reSet.clear();
  128. reIter = reSet.begin();
  129. set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  130. tmpSet.begin(), tmpSet.end(),
  131. inserter(reSet, reIter));
  132. int size2 = reSet.size();
  133. if(size2 > 0) {
  134. continue;
  135. }
  136. reSet.clear();
  137. reIter = reSet.begin();
  138. set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  139. tmpSet.begin(), tmpSet.end(),
  140. inserter(reSet, reIter));
  141. int size3 = reSet.size();
  142. if(size3 > 0) {
  143. continue;
  144. }
  145. oneDivided.group[4].setCodes(threeCodeResult[n].r1,
  146. threeCodeResult[n].r2,threeCodeResult[n].r3);
  147. for(int o=0;o<howManyThreeCodeResult;o++) {
  148. tmpSet.clear();
  149. tmpSet.insert(tmpSet.begin(),threeCodeResult[o].r1);
  150. tmpSet.insert(tmpSet.begin(),threeCodeResult[o].r2);
  151. tmpSet.insert(tmpSet.begin(),threeCodeResult[o].r3);
  152. reSet.clear();
  153. reIter = reSet.begin();
  154. set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  155. tmpSet.begin(), tmpSet.end(),
  156. inserter(reSet, reIter));
  157. int size0 = reSet.size();
  158. if(size0 > 0) {
  159. continue;
  160. }
  161. reSet.clear();
  162. reIter = reSet.begin();
  163. set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  164. tmpSet.begin(), tmpSet.end(),
  165. inserter(reSet, reIter));
  166. int size1 = reSet.size();
  167. if(size1 > 0) {
  168. continue;
  169. }
  170. reSet.clear();
  171. reIter = reSet.begin();
  172. set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  173. tmpSet.begin(), tmpSet.end(),
  174. inserter(reSet, reIter));
  175. int size2 = reSet.size();
  176. if(size2 > 0) {
  177. continue;
  178. }
  179. reSet.clear();
  180. reIter = reSet.begin();
  181. set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  182. tmpSet.begin(), tmpSet.end(),
  183. inserter(reSet, reIter));
  184. int size3 = reSet.size();
  185. if(size3 > 0) {
  186. continue;
  187. }
  188. reSet.clear();
  189. reIter = reSet.begin();
  190. set_intersection(oneDivided.group[4].redSet.begin(),oneDivided.group[4].redSet.end(),
  191. tmpSet.begin(), tmpSet.end(),
  192. inserter(reSet, reIter));
  193. int size4 = reSet.size();
  194. if(size4 > 0) {
  195. continue;
  196. }
  197. oneDivided.group[5].setCodes(threeCodeResult[o].r1,
  198. threeCodeResult[o].r2,threeCodeResult[o].r3);
  199. for(int p=0;p<howManyThreeCodeResult;p++) {
  200. tmpSet.clear();
  201. tmpSet.insert(tmpSet.begin(),threeCodeResult[p].r1);
  202. tmpSet.insert(tmpSet.begin(),threeCodeResult[p].r2);
  203. tmpSet.insert(tmpSet.begin(),threeCodeResult[p].r3);
  204. reSet.clear();
  205. reIter = reSet.begin();
  206. set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  207. tmpSet.begin(), tmpSet.end(),
  208. inserter(reSet, reIter));
  209. int size0 = reSet.size();
  210. if(size0 > 0) {
  211. continue;
  212. }
  213. reSet.clear();
  214. reIter = reSet.begin();
  215. set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  216. tmpSet.begin(), tmpSet.end(),
  217. inserter(reSet, reIter));
  218. int size1 = reSet.size();
  219. if(size1 > 0) {
  220. continue;
  221. }
  222. reSet.clear();
  223. reIter = reSet.begin();
  224. set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  225. tmpSet.begin(), tmpSet.end(),
  226. inserter(reSet, reIter));
  227. int size2 = reSet.size();
  228. if(size2 > 0) {
  229. continue;
  230. }
  231. reSet.clear();
  232. reIter = reSet.begin();
  233. set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  234. tmpSet.begin(), tmpSet.end(),
  235. inserter(reSet, reIter));
  236. int size3 = reSet.size();
  237. if(size3 > 0) {
  238. continue;
  239. }
  240. reSet.clear();
  241. reIter = reSet.begin();
  242. set_intersection(oneDivided.group[4].redSet.begin(),oneDivided.group[4].redSet.end(),
  243. tmpSet.begin(), tmpSet.end(),
  244. inserter(reSet, reIter));
  245. int size4 = reSet.size();
  246. if(size4 > 0) {
  247. continue;
  248. }
  249. reSet.clear();
  250. reIter = reSet.begin();
  251. set_intersection(oneDivided.group[5].redSet.begin(),oneDivided.group[5].redSet.end(),
  252. tmpSet.begin(), tmpSet.end(),
  253. inserter(reSet, reIter));
  254. int size5 = reSet.size();
  255. if(size5 > 0) {
  256. continue;
  257. }
  258. oneDivided.group[6].setCodes(threeCodeResult[p].r1,
  259. threeCodeResult[p].r2,threeCodeResult[p].r3);
  260. for(int s=0;s<howManyThreeCodeResult;s++) {
  261. tmpSet.clear();
  262. tmpSet.insert(tmpSet.begin(),threeCodeResult[s].r1);
  263. tmpSet.insert(tmpSet.begin(),threeCodeResult[s].r2);
  264. tmpSet.insert(tmpSet.begin(),threeCodeResult[s].r3);
  265. reSet.clear();
  266. reIter = reSet.begin();
  267. set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  268. tmpSet.begin(), tmpSet.end(),
  269. inserter(reSet, reIter));
  270. int size0 = reSet.size();
  271. if(size0 > 0) {
  272. continue;
  273. }
  274. reSet.clear();
  275. reIter = reSet.begin();
  276. set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  277. tmpSet.begin(), tmpSet.end(),
  278. inserter(reSet, reIter));
  279. int size1 = reSet.size();
  280. if(size1 > 0) {
  281. continue;
  282. }
  283. reSet.clear();
  284. reIter = reSet.begin();
  285. set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  286. tmpSet.begin(), tmpSet.end(),
  287. inserter(reSet, reIter));
  288. int size2 = reSet.size();
  289. if(size2 > 0) {
  290. continue;
  291. }
  292. reSet.clear();
  293. reIter = reSet.begin();
  294. set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  295. tmpSet.begin(), tmpSet.end(),
  296. inserter(reSet, reIter));
  297. int size3 = reSet.size();
  298. if(size3 > 0) {
  299. continue;
  300. }
  301. //===================================Part 2 End ===============================//
  302. //见下面(由于帖子长度有限制)
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-7-10 23:12:36 | 显示全部楼层
  1. //===================================Part 3 Start ================//
  2. reSet.clear();
  3. reIter = reSet.begin();
  4. set_intersection(oneDivided.group[4].redSet.begin(),oneDivided.group[4].redSet.end(),
  5. tmpSet.begin(), tmpSet.end(),
  6. inserter(reSet, reIter));
  7. int size4 = reSet.size();
  8. if(size4 > 0) {
  9. continue;
  10. }
  11. reSet.clear();
  12. reIter = reSet.begin();
  13. set_intersection(oneDivided.group[5].redSet.begin(),oneDivided.group[5].redSet.end(),
  14. tmpSet.begin(), tmpSet.end(),
  15. inserter(reSet, reIter));
  16. int size5 = reSet.size();
  17. if(size5 > 0) {
  18. continue;
  19. }
  20. reSet.clear();
  21. reIter = reSet.begin();
  22. set_intersection(oneDivided.group[6].redSet.begin(),oneDivided.group[6].redSet.end(),
  23. tmpSet.begin(), tmpSet.end(),
  24. inserter(reSet, reIter));
  25. int size6 = reSet.size();
  26. if(size6 > 0) {
  27. continue;
  28. }
  29. oneDivided.group[7].setCodes(threeCodeResult[s].r1,
  30. threeCodeResult[s].r2,threeCodeResult[s].r3);
  31. for(int t=0;t<howManyThreeCodeResult;t++) {
  32. tmpSet.clear();
  33. tmpSet.insert(tmpSet.begin(),threeCodeResult[t].r1);
  34. tmpSet.insert(tmpSet.begin(),threeCodeResult[t].r2);
  35. tmpSet.insert(tmpSet.begin(),threeCodeResult[t].r3);
  36. reSet.clear();
  37. reIter = reSet.begin();
  38. set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  39. tmpSet.begin(), tmpSet.end(),
  40. inserter(reSet, reIter));
  41. int size0 = reSet.size();
  42. if(size0 > 0) {
  43. continue;
  44. }
  45. reSet.clear();
  46. reIter = reSet.begin();
  47. set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  48. tmpSet.begin(), tmpSet.end(),
  49. inserter(reSet, reIter));
  50. int size1 = reSet.size();
  51. if(size1 > 0) {
  52. continue;
  53. }
  54. reSet.clear();
  55. reIter = reSet.begin();
  56. set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  57. tmpSet.begin(), tmpSet.end(),
  58. inserter(reSet, reIter));
  59. int size2 = reSet.size();
  60. if(size2 > 0) {
  61. continue;
  62. }
  63. reSet.clear();
  64. reIter = reSet.begin();
  65. set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  66. tmpSet.begin(), tmpSet.end(),
  67. inserter(reSet, reIter));
  68. int size3 = reSet.size();
  69. if(size3 > 0) {
  70. continue;
  71. }
  72. reSet.clear();
  73. reIter = reSet.begin();
  74. set_intersection(oneDivided.group[4].redSet.begin(),oneDivided.group[4].redSet.end(),
  75. tmpSet.begin(), tmpSet.end(),
  76. inserter(reSet, reIter));
  77. int size4 = reSet.size();
  78. if(size4 > 0) {
  79. continue;
  80. }
  81. reSet.clear();
  82. reIter = reSet.begin();
  83. set_intersection(oneDivided.group[5].redSet.begin(),oneDivided.group[5].redSet.end(),
  84. tmpSet.begin(), tmpSet.end(),
  85. inserter(reSet, reIter));
  86. int size5 = reSet.size();
  87. if(size5 > 0) {
  88. continue;
  89. }
  90. reSet.clear();
  91. reIter = reSet.begin();
  92. set_intersection(oneDivided.group[6].redSet.begin(),oneDivided.group[6].redSet.end(),
  93. tmpSet.begin(), tmpSet.end(),
  94. inserter(reSet, reIter));
  95. int size6 = reSet.size();
  96. if(size6 > 0) {
  97. continue;
  98. }
  99. reSet.clear();
  100. reIter = reSet.begin();
  101. set_intersection(oneDivided.group[7].redSet.begin(),oneDivided.group[7].redSet.end(),
  102. tmpSet.begin(), tmpSet.end(),
  103. inserter(reSet, reIter));
  104. int size7 = reSet.size();
  105. if(size7 > 0) {
  106. continue;
  107. }
  108. oneDivided.group[8].setCodes(threeCodeResult[t].r1,
  109. threeCodeResult[t].r2,threeCodeResult[t].r3);
  110. for(int u=0;u<howManyThreeCodeResult;u++) {
  111. tmpSet.clear();
  112. tmpSet.insert(tmpSet.begin(),threeCodeResult[u].r1);
  113. tmpSet.insert(tmpSet.begin(),threeCodeResult[u].r2);
  114. tmpSet.insert(tmpSet.begin(),threeCodeResult[u].r3);
  115. reSet.clear();
  116. reIter = reSet.begin();
  117. set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  118. tmpSet.begin(), tmpSet.end(),
  119. inserter(reSet, reIter));
  120. int size0 = reSet.size();
  121. if(size0 > 0) {
  122. continue;
  123. }
  124. reSet.clear();
  125. reIter = reSet.begin();
  126. set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  127. tmpSet.begin(), tmpSet.end(),
  128. inserter(reSet, reIter));
  129. int size1 = reSet.size();
  130. if(size1 > 0) {
  131. continue;
  132. }
  133. reSet.clear();
  134. reIter = reSet.begin();
  135. set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  136. tmpSet.begin(), tmpSet.end(),
  137. inserter(reSet, reIter));
  138. int size2 = reSet.size();
  139. if(size2 > 0) {
  140. continue;
  141. }
  142. reSet.clear();
  143. reIter = reSet.begin();
  144. set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  145. tmpSet.begin(), tmpSet.end(),
  146. inserter(reSet, reIter));
  147. int size3 = reSet.size();
  148. if(size3 > 0) {
  149. continue;
  150. }
  151. reSet.clear();
  152. reIter = reSet.begin();
  153. set_intersection(oneDivided.group[4].redSet.begin(),oneDivided.group[4].redSet.end(),
  154. tmpSet.begin(), tmpSet.end(),
  155. inserter(reSet, reIter));
  156. int size4 = reSet.size();
  157. if(size4 > 0) {
  158. continue;
  159. }
  160. reSet.clear();
  161. reIter = reSet.begin();
  162. set_intersection(oneDivided.group[5].redSet.begin(),oneDivided.group[5].redSet.end(),
  163. tmpSet.begin(), tmpSet.end(),
  164. inserter(reSet, reIter));
  165. int size5 = reSet.size();
  166. if(size5 > 0) {
  167. continue;
  168. }
  169. reSet.clear();
  170. reIter = reSet.begin();
  171. set_intersection(oneDivided.group[6].redSet.begin(),oneDivided.group[6].redSet.end(),
  172. tmpSet.begin(), tmpSet.end(),
  173. inserter(reSet, reIter));
  174. int size6 = reSet.size();
  175. if(size6 > 0) {
  176. continue;
  177. }
  178. reSet.clear();
  179. reIter = reSet.begin();
  180. set_intersection(oneDivided.group[7].redSet.begin(),oneDivided.group[7].redSet.end(),
  181. tmpSet.begin(), tmpSet.end(),
  182. inserter(reSet, reIter));
  183. int size7 = reSet.size();
  184. if(size7 > 0) {
  185. continue;
  186. }
  187. reSet.clear();
  188. reIter = reSet.begin();
  189. set_intersection(oneDivided.group[8].redSet.begin(),oneDivided.group[8].redSet.end(),
  190. tmpSet.begin(), tmpSet.end(),
  191. inserter(reSet, reIter));
  192. int size8 = reSet.size();
  193. if(size8 > 0) {
  194. continue;
  195. }
  196. oneDivided.group[9].setCodes(threeCodeResult[u].r1,
  197. threeCodeResult[u].r2,threeCodeResult[u].r3);
  198. for(int rr=0;rr<10;rr++) {
  199. std::cout << oneDivided.group[rr].r1 << " "
  200. << oneDivided.group[rr].r2 << " "
  201. << oneDivided.group[rr].r3 << " "
  202. << "||";
  203. }
  204. total++;
  205. }//end for(u)
  206. }//end for(t)
  207. }//end for(s)
  208. }//end for(p);
  209. }//end for(o)
  210. }//end for(n)
  211. }//end for(m)
  212. } //end for(k)
  213. }//end for(j)
  214. }//end for (i)
  215. return total;
  216. }
  217. void main(void) {
  218. long total = Get30Group10();
  219. std::cout << "Total: " << total;
  220. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-7-10 23:15:55 | 显示全部楼层
以上程序在gcc+STL下面正确编译并运行。但是发现运算时间太长太长了。。。。。。。。。。。。。。。。 求帮助。。。。。。。。。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-12 10:43:24 | 显示全部楼层
1-30,最小的是1,先将1与某两个元素分为一组,需要从剩下的29个中取两个,故有C(2,29)种方法。 接下来需要将其他的27个分组。 于是f(30)=C(2,29)*f(27)=C(2,29)*C(2,26)*f(24)=...=C(2,29)*C(2,26)*...*C(2,5)*C(2,2)=1208883745669600000 如果你的程序每秒输出1000种的话,你需要大约40万个世纪
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-15 16:29:58 | 显示全部楼层
30!/10!/(3!)^10=1208883745669600000
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-15 17:21:56 | 显示全部楼层
northwolves分析正确,shshsh_0510还需要在结果上除以10!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-24 08:10 , Processed in 0.028097 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表