一个递归问题，请教大家

[gongbao]

卡壳了，一个递归问题怎么也想不出来，请前辈们指点迷津，谢谢啊！

说一个投币机，屏幕开始显示1.

A。投入10元硬币，屏幕显示数字乘以3；
B。 投入5元硬币，屏幕显示数字加4.

要求写一个程序，计算一共需要多少个硬币达到目标数字，其中最小面值的解决方案是多少？
例： “请输入目标面值： ” 109
“达到目标面值需要： ” 45元

用递归编程啊

 

[tototo]

懒得想

 

[dennistan2009]

109开始往下拆，

1. 能被3整除 ---> 除3
---> 减4

2. 不能被3整除 ---> 减4

递归至1.

取最优解。

 

[gongbao]

懒得想

自杀去吧

 

[gongbao]

109开始往下拆，

1. 能被3整除 ---> 除3
---> 减4

2. 不能被3整除 ---> 减4

递归至1.

取最优解。

没看明白，什么道理呢？

 

[gongbao]

109开始往下拆，

1. 能被3整除 ---> 除3
---> 减4

2. 不能被3整除 ---> 减4

递归至1.

取最优解。

给来几行java代码吧

 

[gongbao]

109开始往下拆，

1. 能被3整除 ---> 除3
---> 减4

2. 不能被3整除 ---> 减4

递归至1.

取最优解。

看起来不像是recursive，好像是iterative啊？

 

[dennistan2009]

不要问我为什么，答成这样已经是我的极限了，哈。

 

[gongbao]

不要问我为什么，答成这样已经是我的极限了，哈。

我的感觉，好像您的方案不对啊

 

[gongbao]

@woodenwang 有空帮忙看看啊

 

[月盈亏]

n=0
remainder = x%3
If remainder==0;
x= x/3
n=10+n
else x= x-4
n=5+n

就会这么多

 

[asdfg12345678]

这好像不是递归问题，是动态规划或者贪心算法的问题。

 

[gongbao]

这好像不是递归问题，是动态规划或者贪心算法的问题。

也行啊，给来两行呗

 

[加拿大松鼠]

卡壳了，一个递归问题怎么也想不出来，请前辈们指点迷津，谢谢啊！

说一个投币机，屏幕开始显示1.

A。投入10元硬币，屏幕显示数字乘以3；
B。 投入5元硬币，屏幕显示数字加4.

要求写一个程序，计算一共需要多少个硬币达到目标数字，其中最小面值的解决方案是多少？
例： “请输入目标面值： ” 109
“达到目标面值需要： ” 45元

用递归编程啊

这问题有啥实际用途

 

[woodenwang]

109 的最小解不应该是55吗？怎么会是45?

 

[gongbao]

109 的最小解不应该是55吗？怎么会是45?

老师给的pdf里面写的就是45，我自己在纸上画了一通，也没弄出45啊

 

[woodenwang]

1 投10 变 3
3 投 10 变 9
9 投 10 变 27
27 投 5 变 31
31 投 5 变 35
35 投 10 变105
105 投 5 变109
我写了个程序跑了下也是55, 是不是我理解错了？

 

[gongbao]

这问题有啥实际用途

这是算法，计算机技术的灵魂

 

[加拿大松鼠]

这是算法，计算机技术的灵魂

你在读什么Program？

 

[gongbao]

1 投10 变 3
3 投 10 变 9
9 投 10 变 27
27 投 5 变 31
31 投 5 变 35
35 投 10 变105
105 投 5 变109
我写了个程序跑了下也是55, 是不是我理解错了？

没错，就是这个意思。
题目是瑞典语的，我翻译了一下