📄 separatenumber.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>数字拆解</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 数字拆解</a></h1>
<h2>说明</h2>
这个题目来自于 <a href="http://www.jsptw.com/jute/post/view?bid=5&id=8317&sty=1&tpg=1&age=0">数字拆解</a>，我将之改为C语言的版本，并加上说明。<br>
<br>
题目是这样的：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">3 = 2+1 = 1+1+1 所以3有三种拆法</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五种</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1</span><br>
</div>
<br>
共七种<br>
<br>
依此类推，请问一个指定数字NUM的拆解方法个数有多少个？<br>
<h2>解法</h2>
我们以上例中最后一个数字5的拆解为例，假设f( n )为数字n的可拆解方式个数，而f(x, y)为使用y以下的数字来拆解x的方法个数，则观察：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1</span><br>
</div>
<br>
使用函式来表示的话：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,4) + f(0,5)</span><br>
</div>
<br>
其中f(1, 4) = f(1, 3) + f(1, 2) + f(1, 1)，但是使用大于1的数字来拆解1没有意义，所以f(1, 4) = f(1, 1)，而同样的，f(0, 5)会等于f(0, 0)，所以：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,1) + f(0,0)</span><br>
</div>
<br>
依照以上的说明，使用动态程式规画（Dynamic programming）来进行求解，其中f(4,1)其实就是f(5-1,
min(5-1,1))，f(x, y)就等于f(n-y, min(n-x, y))，其中n为要拆解的数字，而min()表示取两者中较小的数。<br>
<br>
使用一个二维阵列表格table[x][y]来表示f(x, y)，刚开始时，将每列的索引0与索引1元素值设定为1，因为任何数以0以下的数拆解必只有1种，而任何数以1以下的数拆解也必只有1种：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">for(i = 0; i < NUM +1; i++){ </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> table[i][0] = 1; // 任何数以0以下的数拆解必只有1种 </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> table[i][1] = 1; // 任何数以1以下的数拆解必只有1种 </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">}</span><br>
</div>
<br>
<br>
接下来就开始一个一个进行拆解了，如果数字为NUM，则我们的阵列维度大小必须为NUM x (NUM/2+1)，以数字10为例，其维度为10 x 6我们的表格将会如下所示：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 0 0 0 0</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 0 0 0 0</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 2 0 0 0</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 2 3 0 0</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 3 4 5 0</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 3 5 6 7</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 4 7 9 0</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 4 8 0 0</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 5 0 0 0</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 0 0 0 0 </span><br>
</div>
<br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br>#define NUM 10 // 要拆解的数字 <br>#define DEBUG 0 <br><br>int main(void) { <br> int table[NUM][NUM/2+1] = {0}; // 动态规画表格 <br> int count = 0; <br> int result = 0; <br> int i, j, k; <br><br> printf("数字拆解\n"); <br> printf("3 = 2+1 = 1+1+1 所以3有三种拆法\n"); <br> printf("4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1"); <br> printf("共五种\n"); <br> printf("5 = 4 + 1 = 3 + 2 = 3 + 1 + 1");<br> printf(" = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1");<br> printf("共七种\n"); <br> printf("依此类推，求 %d 有几种拆法？", NUM); <br><br> // 初始化 <br> for(i = 0; i < NUM; i++){ <br> table[i][0] = 1; // 任何数以0以下的数拆解必只有1种 <br> table[i][1] = 1; // 任何数以1以下的数拆解必只有1种 <br> } <br><br> // 动态规划 <br> for(i = 2; i <= NUM; i++){ <br> for(j = 2; j <= i; j++){ <br> if(i + j > NUM) // 大于 NUM <br> continue; <br> <br> count = 0; <br> for(k = 1 ; k <= j; k++){ <br> count += table[i-k][(i-k >= k) ? k : i-k]; <br> } <br> table[i][j] = count; <br> } <br> } <br><br> // 计算并显示结果 <br> for(k = 1 ; k <= NUM; k++) <br> result += table[NUM-k][(NUM-k >= k) ? k : NUM-k]; <br> printf("\n\nresult: %d\n", result); <br><br> if(DEBUG) { <br> printf("\n除错资讯\n"); <br> for(i = 0; i < NUM; i++) { <br> for(j = 0; j < NUM/2+1; j++) <br> printf("%2d", table[i][j]); <br> printf("\n"); <br> } <br> } <br><br> return 0; <br>}</pre>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -