[问题] 重复组合递回算法

楼主: alfadick (悟道修行者)   2014-09-02 15:27:24
不是作业,是解 project euler problem 31 时遇到的
https://projecteuler.net/problem=31
我感觉是重复组合的问题。
我想强迫自己用递回写,来练习递回的思考方式,但写到卡住..。
小弟不是资工系的,所以这方面训练颇薄弱,
如果把问题简化成 x1 + x2 + x3 + x4 = 20 这种
我的算法是:
先用变量 flag 纪录目前 run 到哪个位置
(一开始flag = 4
有个四个参数的函数f)
x1 x2 x3 x4
0 0 0 0
0 0 0 1 -> 呼叫 f(0,0,0,0+1) (第几个参数变动,用flag来判定)
0 0 0 2
...
0 0 0 20 -> 是一个解, 纪录起来
0 0 0 21 -> 爆掉
0 0 1 0 -> flag-=1, 最后一个重设为0
0 0 1 1 -> flag 重设为4,
扼.. 反正最后两行有点问题
我也是在追踪flag这里卡住, 想不下去
我感觉用递回似乎可以不用flag来记录执行状态
有什么SOP吗这种题目...
作者: cutekid (可爱小孩子)   2014-09-02 16:10:00
作者: jackace (inevitable......)   2014-09-02 16:37:00
SOP就是把所有的state用参数丢给下一层当然 什么state是必要的什么是不必要的就自己推敲了
楼主: alfadick (悟道修行者)   2014-09-02 17:29:00
我也是有当参数丢下一层 但是在推敲算法时感觉怪怪的简单来讲是大脑烧坏了
作者: bigpigbigpig (To littlepig with love)   2014-09-06 18:32:00

Links booklink

Contact Us: admin [ a t ] ucptt.com