X星球要派出一个5人组成的观察团前往W星。
其中：
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
….
那么最终派往W星的观察团会有多少种国别的不同组合呢？
下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为：
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
….
(以下省略，总共101行)
给出代码，请你填空：
|
1 |
<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string"><stdio.h></span></span> <span class="token macro property">#<span class="token directive keyword">define</span> N 6</span> <span class="token macro property">#<span class="token directive keyword">define</span> M 5</span> <span class="token macro property">#<span class="token directive keyword">define</span> BUF 1024</span> <span class="token keyword">void</span> <span class="token function">f</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> k<span class="token punctuation">,</span> <span class="token keyword">int</span> m<span class="token punctuation">,</span> <span class="token keyword">char</span> b<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">int</span> i<span class="token punctuation">,</span>j<span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token operator">==</span>N<span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span> b<span class="token punctuation">[</span>M<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>m<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%s\n"</span><span class="token punctuation">,</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator"><=</span>a<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span> <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator"><</span>i<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> b<span class="token punctuation">[</span>M<span class="token operator">-</span>m<span class="token operator">+</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> k<span class="token operator">+</span><span class="token string">'A'</span><span class="token punctuation">;</span> ________________<span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">int</span> a<span class="token punctuation">[</span>N<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{<!-- --></span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">}</span><span class="token punctuation">;</span> <span class="token keyword">char</span> b<span class="token punctuation">[</span>BUF<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token function">f</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span>M<span class="token punctuation">,</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
思路：
很少做这种填空的，但是递归的话，会有遵循一定的技巧
可以看到递归的首次调用：
|
1 |
<span class="token function">f</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span>M<span class="token punctuation">,</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span> |
a, b数组肯定是不变的参数了，关键是如何确定中间的参数
通过题意理解，中间的参数应该是：
|
1 |
<span class="token keyword">void</span> <span class="token function">f</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> k<span class="token punctuation">,</span> <span class="token keyword">int</span> m<span class="token punctuation">,</span> <span class="token keyword">char</span> b<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> |
关键是看递归中是如何实现的：
k的判断：
|
1 |
<span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token operator">==</span>N<span class="token punctuation">)</span> |
终止条件是k==N，那么应该是k逐渐递增的，这也符合逻辑：各个国家按顺序，派遣人员，逐渐填满下标，所以大概率是填：k+1
m的判断：
|
1 |
<span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator"><=</span>a<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span> <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator"><</span>i<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> b<span class="token punctuation">[</span>M<span class="token operator">-</span>m<span class="token operator">+</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> k<span class="token operator">+</span><span class="token string">'A'</span><span class="token punctuation">;</span> ______________________<span class="token punctuation">;</span> <span class="token punctuation">}</span> |
- 观察这个循环，
a[k]是第k个国家可以派遣的人员的最大数量，从0到a[k]说明是在穷举第k个国家派出人员的情况 - 而内循环则是：第
k个国家派遣了i人，循环填掉i个位置（m越少，M-m越大，空位起始的下标逐渐靠后，也是合理的）
那么递归就很清晰了：
第k个国家出了i个人，剩下m-i个空位，留给k+1 ~ N个国家，于是m大概率填 m-i，因为循环结束，i==j，填m-j也可以
答案：
|
1 |
<span class="token function">f</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> k<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> m<span class="token operator">-</span>i<span class="token punctuation">,</span> b<span class="token punctuation">)</span><span class="token punctuation">;</span> |
完整代码
|
1 |
<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string"><stdio.h></span></span> <span class="token macro property">#<span class="token directive keyword">define</span> N 6</span> <span class="token macro property">#<span class="token directive keyword">define</span> M 5</span> <span class="token macro property">#<span class="token directive keyword">define</span> BUF 1024</span> <span class="token keyword">void</span> <span class="token function">f</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> k<span class="token punctuation">,</span> <span class="token keyword">int</span> m<span class="token punctuation">,</span> <span class="token keyword">char</span> b<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">int</span> i<span class="token punctuation">,</span>j<span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>k<span class="token operator">==</span>N<span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span> b<span class="token punctuation">[</span>M<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>m<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%s\n"</span><span class="token punctuation">,</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator"><=</span>a<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span> <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator"><</span>i<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> b<span class="token punctuation">[</span>M<span class="token operator">-</span>m<span class="token operator">+</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> k<span class="token operator">+</span><span class="token string">'A'</span><span class="token punctuation">;</span> <span class="token function">f</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> k<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> m<span class="token operator">-</span>i<span class="token punctuation">,</span> b<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">int</span> a<span class="token punctuation">[</span>N<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{<!-- --></span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">}</span><span class="token punctuation">;</span> <span class="token keyword">char</span> b<span class="token punctuation">[</span>BUF<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token function">f</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span>M<span class="token punctuation">,</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
微信扫一扫打赏
支付宝扫一扫打赏
