※ 引述《alfadick (悟道修行者)》之铭言：
: 不是作业，是解 project euler problem 31 时遇到的
: https://projecteuler.net/problem=31
: 我感觉是重复组合的问题。
: 我想强迫自己用递回写，来练习递回的思考方式，但写到卡住..。
: 我感觉用递回似乎可以不用flag来记录执行状态
: 有什么SOP吗这种题目...
像这样的题目,
可以说是找出怎样data的组合为解,
每一个data组合,我们可以视为一个state,
简单说就是找出那一个state或那一些state为解.
刚起步练习的时候,可以试着用纸笔列出每一个state,
如果state太多无法全部列举,可以试着列某一个范围就好,
目的在于观察找出规律.
找规律有几个要件,
首是分析如何从某一个state转移到另一个state,
然后是找起点和边界.
再来是如何走过每一个state.
举例一个题目:
1到1000之间,有几个质数?
我们从小到大的经验来看,
1到1000之间可以想都不用想就知到总共有1000个不同的state,
如果题目稍变化一下,
1到1000之间是指9进位,或13进位这种不常见的命题,
总共有几个state那可能要想一下了.
话说回来,
首先来看如何从某一个state跳到另一个state,
直觉上来看也很简单,直接值加上1就好,
透过不断加1,就可以走过从1到1000之间的所有state,
其实方法不见得只有一条路,
例如说0010透过加10来跳到0020,
换句话说0010跟0020之间有一条路可以一步转移,
不用经过11,12,...,19.
所以可以想像成
在某一个空间分布著有许许多多state,
而这些state之间各自就像网络相连,
而我们就像是在这网络中走访来找出解.
至于怎么找,有些就是学问了,比如说还有效率高低问题.
其实某些很多算法就是介绍不同的走访方式来针对题目求解.
而原po的题目算是比较好分析的,
比如说起点是 0, 0, 0, 0, 0, 0, 0 七个coin,
然后边界是
0, 0, 0, 0, 0, 0, 200
0, 0, 0, 0, 0, 100, 0
...
1, 0, 0, 0, 0, 0, 0
然后走访方式如果可以的话
从 0, 0, 0, 0, 0, 0, 0 开始
我想用"+1"这个方法走访每一个state,
如果可以的话这个方法再多加几个判断式
让我可以
0, 0, 0, 0, 0, 0, 200 跳到 0, 0, 0, 0, 0, 1, 0
而且
0, 0, 0, 0, 0, 100, 200 跳到 0, 0, 0, 0, 1, 0, 0 ..
...以此类推
假设找到这方法,
那就可以像1到1000一样用一个loop就可解决了.
假设找不到这条路,
那也可以考虑用7层loop也能解.
recursive也是走访的选择之一,
只是与loop特性不太相同,
有些情况会比loop好写, 也有些情况比loop吃效能,
看自己取舍.
在这题
概念上我举例其中一种纯recursive走法:
find ( a, b, c, d, e, f, g )
{
如果全部总和 刚好 200
记录并离开
如果全部总和 超过 200
离开
find ( a+1, b, c, d, e, f, g );
find ( a, b+1, c, d, e, f, g );
find ( a, b, c+1, d, e, f, g );
find ( a, b, c, d+1, e, f, g );
find ( a, b, c, d, e+1, f, g );
find ( a, b, c, d, e, f+1, g );
find ( a, b, c, d, e, f, g+1 );
}
main()
{
find( 0, 0, 0, 0, 0, 0 ,0 );
}
像这样就是起点为 0, 0, 0, 0, 0, 0 ,0
边界判断是每到一个state都会做的事.
不是边界的话就继续走,
然后每一个state因为有7种硬币所以有7条路出去,
recursive特性就是其中1条路走完会"回到这个state",
简而言之就是一种浑然天成的state记录法,
(现在大多数程式语言的原理背后都符合某种state记录)
接着下一行也是一条recursive方法,
但是用不同的参数转移方式来走到另一个state.
然后根据每个人的分析能力和角度不同,
也有可能loop跟recursive混用.
看个人取舍,重点在于能否找到路.
如果是某段树状的分布,
意思是说走到某个地方没有路必须"倒退噜"才能走别条路的,
就会建议用recursive.
(不用recursive的写法话就可用自制的stack来记录state,只是可能比较麻烦)
另外一个议题就是走访效率,
其中一个方法就是"少走冤枉路",
有种说法就是state修剪,
例如:
如果全部总和 刚好 200
记录"并离开"
后面的"并离开"可以不写,也会正确找到解.
只是会多走7个state.
再一个修剪的例子:
find ( a, b, c, d, e, f )
{
如果全部总和 刚好 200
记录并离开
如果全部总和 超过 200
离开
用 g(1p) 把不足 200 的部分补齐, 并记录
find ( a+1, b, c, d, e, f );
find ( a, b+1, c, d, e, f );
find ( a, b, c+1, d, e, f );
find ( a, b, c, d+1, e, f );
find ( a, b, c, d, e+1, f );
find ( a, b, c, d, e, f+1 );
}
这样就可以少走很多路.
总之方法掌握在个人,
不做任何修剪也可以说是暴力法,
但解题不见得要求效率, 总之是先求有再求好,
个人是建议有了基本解题能力再慢慢去累积各种算法例子.