一道趣味算术题

题目地址：http://club.excelhome.net/thread-175411-1-1.html

先看几个数：312132,231213,41312432,23421314

可以看到以上字串有以下特点： 2个1 之间有1个数，2个2 之间有2个数，2个3之间有3个数...
试找出由(1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8) 16个数组成的字符串满足上述条件的所有组合,即2个1 之间有1个数，2个2 之间有2个数，2个3之间有3个数...2个8之间有8个数.

1,1,2,2,3,3,...N,N共2N个数排成一行,2个1 之间有1个数，2个2 之间有2个数，...2个N之间有N个数...

设 1 放在A(1) ,A(1) + 2
2 放在A(2) ,A(2) + 3
3 放在A(3) ,A(3) + 4
....
N 放在A(N) ,A(N)+N+1

则A(1), A(1)+2, A(2), A(2)+3,...,A(N) + N + 1 为1,2,3,4,..2N的一个全排列

故 1 + 2 + 3 + ... + 2N = 2[A(1) + A(2) + ... + A(N)] + [2 + 3 + ... + (N+1)]

2N(2N+1)/2 = 2[A(1) + A(2) + ... + A(N)] + (N+1)(N+2)/2 - 1

4[A(1) + A(2) + ... + A(N)] = 2N(2N+1) - (N+1)(N+2) + 2


A(1) + A(2) + ... + A(N) = N(3N-1)/4


所以 N 只能是 4K,4K+3 的形式.

N=1,2,5,6,9时无解
N=3: 312132,231213
N=4: 41312432,23421314
N=7; 52个解
N=8: 300个解

方法1（qee用提供）

1. PrivateMaxAsLong,mycountAsLong
2. PrivateSubCommand1_Click()
3. DimW()'每位的数字
4. DimNum(1To8)AsBoolean'标识数字使用否
6. DimpAsLong'指针作用
7. DimFillLeftAsLong'填数剩余名额
9. ForMax=6To16Step2
10. ReDimW(1ToMax)
11. FillLeft=Max/2
12. p=1
13. CallBody(W,Num,p,FillLeft)
14. EraseW
15. Next
16. EndSub
18. PrivateSubBody(ByRefW(),ByRefNum()AsBoolean,_
19. ByRefpAsLong,ByRefFillLeftAsLong)
20. DimtAsLong
21. '往前移到空位
22. CallMoveP(W,p)
23. '该位最大可能的值
24. t=Max-p-1
25. Ift>8Thent=8
27. Do
28. '跳过已经使用过的值
29. t=GetMaxUnuse(Num,t)
30. Ift>0Then
31. '尝试成对插入
32. IfBeTwins(Num,W,t,p)=TrueThen
33. FillLeft=FillLeft-1
34. IfFillLeft=0Then
35. '显示结果
36. IfUBound(W)=16Then
37. mycount=mycount+1
38. CallShowResult(W)
39. EndIf
40. Else
41. '递归调用
42. CallBody(W,Num,p,FillLeft)
43. EndIf
44. '成对弹出
45. DoWhileBackTwins(Num,W,p)=False
46. p=p-1
47. Loop
48. FillLeft=FillLeft+1
50. EndIf
51. t=t-1
52. EndIf
53. LoopUntilt=0
55. EndSub
57. PrivateSubMoveP(ByRefW(),ByRefpAsLong)
58. DoWhileW(p)>0
59. p=p+1
60. Loop
61. EndSub
63. PrivateFunctionGetMaxUnuse(ByRefNum()AsBoolean,ByValMaxNumAsLong)AsLong
64. DimtAsLong
65. Fort=MaxNumTo1Step-1
66. IfNum(t)=FalseThen
67. GetMaxUnuse=t
68. ExitFor
69. EndIf
70. Next
71. EndFunction
73. PrivateFunctionBeTwins(ByRefNum()AsBoolean,ByRefW(),_
74. ByValNumberAsLong,ByValpAsLong)AsBoolean
75. DimpMirAsLong
76. BeTwins=False
77. '数字已经用过
78. IfNum(Number)=TrueThenExitFunction
79. '此位已经有数字
80. IfW(p)>0ThenExitFunction
81. '计算对应位置
82. pMir=p+Number+1
83. '对应位置超出范围
84. IfpMir>MaxThenExitFunction
85. '对应位置已经有数字
86. IfW(pMir)>0ThenExitFunction
87. '一切正常
88. Num(Number)=True
89. W(p)=Number
90. W(pMir)=Number
91. BeTwins=True
92. EndFunction
94. PrivateFunctionBackTwins(ByRefNum()AsBoolean,ByRefW(),_
95. ByValpAsLong)AsBoolean
96. DimpMirAsLong
97. BackTwins=False
98. '此位没有数字
99. IfW(p)=0ThenExitFunction
100. '计算对应位置
101. pMir=p+W(p)+1
102. '对应位置超出范围
103. IfpMir>MaxThenExitFunction
104. '对应位置没有数字，或数字不一致
105. IfW(pMir)=0ThenExitFunction
106. IfW(pMir)<>W(p)ThenExitFunction
107. '一切正常
108. Num(W(p))=False
109. W(p)=0
110. W(pMir)=0
111. BackTwins=True
112. EndFunction
114. PrivateSubShowResult(ByRefW())
115. Debug.Printmycount&vbTab&Join(W,"")
116. EndSub

n=7 时,有52个解:
1 74151643752362
2 73625324765141
3 73161345726425
4 72632453764151
5 72462354736151
6 72452634753161
7 71416354732652
8 71316435724625
9 62742356437151
10 61517346532472
11 57416154372632
12 57263254376141
13 57236253471614
14 57141653472362
15 56171354632742
16 53672352461714
17 53647352462171
18 52732653417164
19 52642753461317
20 52472654131763
21 52462754316137
22 51716254237643
23 46357432652171
24 46171452632753
25 46171435623725
26 45671415362732
27 41716425327635
28 41617435263275
29 37463254276151
30 36713145627425
31 35743625427161
32 35723625417164
33 34673245261715
34 34573641512762
35 27423564371516
36 26721514637543
37 26327435614175
38 26325734615147
39 25623745361417
40 24723645317165
41 23726351417654
42 23627345161475
43 17126425374635
44 17125623475364
45 16172452634753
46 16135743625427
47 15173465324726
48 15167245236473
49 15163745326427
50 15146735423627
51 14167345236275
52 14156742352637

n=8 时,有300个解:
1 8642752468357131
2 8642572468531713
3 8631713568427524
4 8613175368425724
5 8527326538471614
6 8514167548236273
7 8457264258376131
8 8456274258631713
9 8451714658237263
10 8427524638573161
11 8426724358637151
12 8416174358632752
13 8372632458764151
14 8357236258471614
15 8352732658417164
16 8316135748625427
17 8273264358746151
18 8271216458734653
19 8271215648735463
20 8253267358416174
21 8247263458376151
22 8246257438653171
23 8237243568471516
24 8236253748651417
25 8141673458362752
26 8131743568427526
27 8131573468524726
28 8131563748526427
29 8121726358437654
30 8121724568347536
31 8121627538463574
32 8121625748365437
33 7831613574862542
34 7823625374865141
35 7813156374852642
36 7812162574836543
37 7582462574386131
38 7581416574382632
39 7562842576431813
40 7561814576342832
41 7536483574612182
42 7528623574368141
43 7518136573428624
44 7516184573642382
45 7485264275386131
46 7481514673582362
47 7468254276358131
48 7463584376512182
49 7426824375631815
50 7425824675131863
51 7416184572632583
52 7386235274685141
53 7386131574682542
54 7385236275481614
55 7368131576428524
56 7345638475261218
57 7318134675248265
58 7283246375481615
59 7281216475384635
60 7281215673485364
61 7263285376415184
62 7246258473651318
63 7245286475131683
64 7245268475316138
65 7238243675418165
66 7236283475614185
67 7141863475326825
68 7141586472532683
69 7141568473526328
70 7131853672452864
71 7131683572462584
72 7131683475264285
73 6852472654831713
74 6831713645827425
75 6827325634875141
76 6814157643852372
77 6752842657431813
78 6751814657342832
79 6734583647512182
80 6714185647235283
81 6485724625387131
82 6475824625731813
83 6475384635712182
84 6471814652732853
85 6471814635723825
86 6418174625328735
87 6417184635273285
88 6384537642582171
89 6378131645728425
90 6357832652471814
91 6357438654271218
92 6285247635483171
93 6284273645381715
94 6278234653748151
95 6275284635743181
96 6274258643751318
97 6258237653418174
98 6257248653471318
99 6238273651418754
100 6237283645171485
101 6181537643582472
102 6181473654382752
103 6171834653742852
104 6171825624735843
105 6151847652432873
106 6151748653427328
107 5864275246831713
108 5841715463827326
109 5827425634873161
110 5824625743861317
111 5823725364817146
112 5817135643872462
113 5814175642832763
114 5814165743826327
115 5784265247386131
116 5748625427368131
117 5746825427631813
118 5746385437612182
119 5728325637418164
120 5724825647131863
121 5716185347632482
122 5673485364712182
123 5671815364732842
124 5628425764318137
125 5618175264238743
126 5618145763428327
127 5378435624728161
128 5378235264718146
129 5374835641712862
130 5364835746121827
131 5286235743681417
132 5283275364181746
133 5248275461318736
134 5247285463171386
135 5181725623487364
136 5181375632482764
137 5181365734286247
138 5171835463724826
139 5161845736423827
140 5161785246237483
141 4862742356837151
142 4857141653872362
143 4853647352862171
144 4852642753861317
145 4835743625827161
146 4815146735823627
147 4782542637583161
148 4758141657238263
149 4753648357261218
150 4752842657131863
151 4738643257268151
152 4738543627528161
153 4718146257238653
154 4718143567328526
155 4716148537623528
156 4683547362582171
157 4682542763581317
158 4672842365731815
159 4637843265271815
160 4635843765121827
161 4618147365238275
162 4617148562372538
163 4586347532682171
164 4578141563728326
165 4567841516372832
166 4567348536271218
167 4278246151738653
168 4275248635713168
169 4268247516138573
170 4268243756318157
171 4258246751318637
172 4257248653171368
173 4181742562387536
174 4161845726325837
175 4161748526327538
176 4161748356237258
177 3862352746851417
178 3861315746825427
179 3857316154872642
180 3852362754816147
181 3847362452876151
182 3847326425871615
183 3845367425826171
184 3825327465814176
185 3782342567481516
186 3758316157428624
187 3746385427625181
188 3726328457614158
189 3681317562482574
190 3681317465284275
191 3681315764285247
192 3672382465714185
193 3645378465121728
194 3628327561418574
195 3627328564171548
196 3586371514682742
197 3582372564181746
198 3574386541712682
199 3568371516428724
200 3568347526428171
201 3568327526418174
202 3564378546121728
203 3486374151682752
204 3485374615182762
205 3485374265281716
206 3478324625718165
207 3467384516172582
208 3456384752612187
209 3181375264285746
210 3181367245286475
211 3181347562482576
212 3181346752482657
213 3171386425724685
214 3171384562742586
215 3171368524726548
216 3171358642752468
217 2862357436854171
218 2862171456834753
219 2852734653847161
220 2852716154837643
221 2852637453864171
222 2852467354836171
223 2842367435816175
224 2832463754816157
225 2812175364835746
226 2812174635843765
227 2812167345836475
228 2812164753846357
229 2812157463854376
230 2812156734853647
231 2782345637485161
232 2752683457364181
233 2742853467351816
234 2732583467514186
235 2682537463584171
236 2682171465384735
237 2672815164735843
238 2672485364735181
239 2642783465317185
240 2632853764151847
241 2632783561417584
242 2582473564381716
243 2572861514736843
244 2572834563741816
245 2572638543761418
246 2572368534716148
247 2482374635181765
248 2472864151736853
249 2462784516137583
250 2462584736513187
251 2452864751316837
252 2452684753161387
253 2382736151487654
254 2382437564181576
255 2382436754181657
256 2362834756141857
257 1815374635842762
258 1815267245836473
259 1814637543862572
260 1813475364825726
261 1718246257438653
262 1716384537642582
263 1716285247635483
264 1714853647352862
265 1714683547362582
266 1714586347532682
267 1713845367425826
268 1713568347526428
269 1712862357436854
270 1712852637453864
271 1712852467354836
272 1712682537463584
273 1618274265348735
274 1618257263458374
275 1617483564372582
276 1617285263475384
277 1615847365432872
278 1613857362452874
279 1613784365247285
280 1613758364257248
281 1518627523468374
282 1518473564328726
283 1517386532472684
284 1517368534276248
285 1516782542637483
286 1516738543627428
287 1516478534623728
288 1514678542362738
289 1418634753268257
290 1415864725326837
291 1415784365237286
292 1415684735263287
293 1318637245268475
294 1318536724528647
295 1317835264275846
296 1317538642572468
297 1316837425624875
298 1316835724625847
299 1316834752642857
300 1316738524627548

方法2（lg_cai提供）

1. Dima(1To16),j,s
2. Subcai()
3. Forj=1To8
4. s=0
5. czj
6. Nextj
7. EndSub
8. Subcz(zz)
9. Fori=zz+2To2*j
10. Ifa(i)=0Anda(i-zz-1)=0Then
11. a(i)=zz
12. a(i-zz-1)=zz
13. Ifzz>1Then
14. czzz-1
15. Else
16. Fork=1To2*j
17. ls=ls&a(k)
18. Nextk
19. s=s+1
20. Debug.Print"'"&ls
21. EndIf
22. a(i)=0
23. a(i-zz-1)=0
24. EndIf
25. Next
26. EndSub

C++ 代码（zhc6211026 提供）

1. #include<iostream>
3. usingnamespacestd;
5. int*numarr;
6. bool*numused;
8. voidDoubleN(intn,inti,intc=0);
9. voidprintnum(int*arr,intn);
10. intmain()
11. {
12. intn,i;
13. cin>>n;
14. numarr=newint[2*n];
15. numused=newbool[2*n];
16. for(i=0;i<2*n;i++)
17. {
18. numarr[i]=0;
19. numused[i]=false;
20. }
21. DoubleN(n,1);
23. return0;
24. }
26. voidDoubleN(intn,inti,intc)
27. {
28. intk=0;
29. for(k=0;k<2*n-i;k++)
30. {
31. if(!numused[k]&&!numused[k+i+1])
32. {
33. numused[k]=numused[k+i+1]=true;
34. numarr[k]=numarr[k+i+1]=i;
35. if(i==n)
36. {
37. printnum(numarr,n);
38. }
39. else
40. {
41. DoubleN(n,i+1);
42. }
43. numused[k]=numused[k+i+1]=false;
44. numarr[k]=numarr[k+i+1]=0;
45. }
46. }
47. }
49. voidprintnum(int*arr,intn)
50. {
51. for(inti=0;i<2*n;i++)
52. {
53. cout<<arr[i];
54. }
55. cout<<endl;
56. }

lg_cai还提供了将1,2,3,...N共3N个数排成一行,3个1 之间各有1个数，3个2 之间各有2个数，...3个N之间各有N个数...的递归方法

1. Dima(1To27),j,s
2. Subcai()
3. Forj=1To9
4. s=0
5. czj
6. Nextj
7. EndSub
8. Subcz(zz)
9. Fori=2*(zz+1)+1To3*j
10. Ifa(i)=0Anda(i-zz-1)=0Anda(i-2*(zz+1))=0Then
11. a(i)=zz
12. a(i-zz-1)=zz
13. a(i-2*(zz+1))=zz
14. Ifzz>1Then
15. czzz-1
16. Else
17. Fork=1To3*j
18. ls=ls&a(k)
19. Nextk
20. s=s+1
21. Cells(s,j*2)="'"&ls
22. EndIf
23. a(i)=0
24. a(i-zz-1)=0
25. a(i-2*(zz+1))=0
26. EndIf
27. Nexti
28. EndSub

代码返回：

191618257269258476354938743

191218246279458634753968357

181915267285296475384639743

347936483574692582762519181

753869357436854972642812191

347839453674852962752816191