极客时间-轻松学习，高效学习-极客邦

2018-12-20

由于暂时无法追加回复，我这里再回复一下网友debugtalk

我看了Python的实现，果然很简介👍
奖金的题目没问题。整数的因子分解有点小瑕疵，少了一些可能。比如，输入8，少了
[1, 2, 2, 2]
[1, 2, 4]
[1, 4, 2]
[2, 1, 2, 2]

展开



 10

杨景胜

2018-12-19

从递归的两个原则到代码实现有点跳跃，想了半天还是没想明白这个代码的逻辑啊~

 2

 17

debugtalk

2018-12-19

Python 实现赏金问题：https://github.com/debugtalk/geektime-notes/blob/master/programmers-mathematics/chapter5.md
Python 实现思考题：https://github.com/debugtalk/geektime-notes/blob/master/programmers-mathematics/chapter5.py

作者回复: 很棒我稍后sync下来看

 1

 9

李尧

2018-12-19

思考题：请大神帮忙看下，输出少了个 [1,8]
输出：[2, 2, 2, 1] [2, 4, 1][4, 2, 1][8, 1]

import java.util.ArrayList;

/**
* @Auther: yli
* @Date: 2018/12/19 17:19
* @Description:
*/
public class Iteration {

    public static void recursion(long total, ArrayList<Long> result){

        if (total == 1){
            result.add(1L);
            System.out.println(result);
            return;
        }else {
            for(long i = 2; i <= total; i ++){
                ArrayList<Long> newList = (ArrayList<Long>)(result.clone());
                newList.add(Long.valueOf(i));
                if(total%i !=0){
                   continue;
                }
                recursion(total/i, newList);
            }
        }
    }

    public static void main(String[] args){
        long total = 8;
        recursion(total, new ArrayList<Long>());
    }
}

展开

作者回复: 循环的时候不能少了1，可以在结果中判断是否已经涵盖1，我稍微修改了一下
public static void recursion(long total, ArrayList<Long> result) {

        if (total == 1) {
            if (!result.contains(1L)) result.add(1L);
            System.out.println(result);
            return;
        } else {
            for (long i = 1; i <= total; i++) {
                if ((i == 1) && result.contains(1L)) continue;
                ArrayList<Long> newList = (ArrayList<Long>) (result.clone());
                newList.add(Long.valueOf(i));
                if (total % i != 0) {
                    continue;
                }
                recursion(total / i, newList);
            }
        }
    }

 2

 7

文刂氵共超

2018-12-19

整数分解 - C++代码
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// 输出函数
void PrintResult(vector<int> &Result)
{
  for (size_t i = 0; i < Result.size(); ++i)
  {
    cout << Result[i] << " ";
  }
  cout << endl;
}

//数组中是否存在某值
bool IsExit(vector<int> &Result, int value)
{
  vector<int>::iterator result = std::find(Result.begin(), Result.end(), value);
  if (result == Result.end())
  {
    return false;
  }
  else
  {
    return true;
  }
}

//整数分解
void RecursionAlgo(int Num, vector<int> &Result)
{
  if (Num == 1)
  {
    PrintResult(Result);
    return;
  }
  for (int i = 1; i <= Num; ++i)
  {
    //判断1是否在解中
    if (IsExit(Result, 1))
    {
      if (i == 1)
      {
        continue;
      }
    }
    if (Num%i == 0)
    {
      vector<int> newResult = Result;
      newResult.push_back(i);

      RecursionAlgo(Num/i, newResult);
    }
  }
}

int _tmain(int argc, _TCHAR* argv[])
{
  int Totalmoney = 10;
  vector<int> Result;

  RecursionAlgo(Totalmoney, Result);
  return 0;
}

展开

作者回复: 回答很棒，下次可以将运行结果也贴出来👍



 7

debugtalk

2018-12-20

感谢 Sean 的指正，之前整数因子分解的解答的确存在问题，没有完整考虑整数 1 在各种位置的情况。
现已更正：https://github.com/debugtalk/geektime-notes/blob/master/programmers-mathematics/chapter5.py



 3

松原

2018-12-19

黄老师，这句“递归和循环其实都是迭代法的实现”我不太理解。
如果递归和循环都属于迭代法，那么就是说递归是从属于迭代法的。而我所理解的迭代法的核心是从1到n的递推，而递归是从n到1的逐步求解的过程，两者应该是并列的关系。希望老师能解答我的这个困惑。

作者回复: 确实两者的递推方向是不一样的，不过递归在计算机的实现中，是使用的函数调用，在满足条件后，函数开始逐级返回，这时候又是正向递推了，所以我觉得这也是从1到n



 3

杨景胜

2018-12-19

//因数分解
public static void getMultiFactors(long multi,ArrayList<Long> result){
        if (multi == 1){
            result.add(multi);
            System.out.println(result);
        }else{
            for (long i = 2; i <= multi; i++) {
                if(multi % i == 0){
                    ArrayList<Long> newResult = (ArrayList<Long>) result.clone();
                    newResult.add(i);
                    getMultiFactors(multi / i,newResult);
                }
            }
        }
    }

展开

作者回复: 如果循环从2开始，可能会漏掉一些情况，请参考为我给另一位网友李尧的回复



 3

Sawyer

2019-03-12

老师好，我实现了一个算法，但是没有打印出来1的情况。
还有个问题就是，如果使用老师的示例输入8，结果既有 2x4，又有 4x2 这不是重复了吗？
static void getFactorization(long product, ArrayList<Long> result) {
    for (int i = 2; i <= product / 2; i++) {
        if (0 == product % i) {
            ArrayList<Long> newResult = (ArrayList<Long>) result.clone();
            newResult.add((long) i);
            getFactorization(product / i, newResult);
            newResult.add(product / i);
            System.out.println(newResult);
        }
    }
}

展开

作者回复: 这里作为教学案例，可以遍历所有情况，包括4x2和2x4。至于1，需要特殊处理一下，你可以思考看看，或者看看之前读者的留言



 2

悬炫

2019-01-28

JavaScript的实现：
赏金问题：
/**
*
* @description 赏金问题
* @param {number} totalReward 奖赏总金额
* @param {array} result 保存当前的解
* @param {array} rewards 可供选择的面额
* @returns void
*/
function get(totalReward, result=[],rewards = [1, 2, 5, 10]) {
    // 当 totalReward = 0 时，证明它是满足条件的解，结束嵌套调用，输出解
    if (totalReward === 0) {
        console.log(result.toString());
        // 当 totalReward < 0 时，证明它不是满足条件的解，不输出
    } else if(totalReward<0) {
        return;
    } else {
        for (let index = 0; index < rewards.length; index++) {
            let newResult =[...result];// 由于有 4 种情况，需要 clone 当前的解并传入被调用的函数
            newResult.push(rewards[index]);// 记录当前的选择，解决一点问题
            get(totalReward - rewards[index], newResult);// 剩下的问题，留给嵌套调用去解决
        }
    }
}

展开



 2

方得始终

2018-12-29

参考老师和其他同学的留言, 下面是Pythoni实现的思考题, 应该是个较为简洁的版本.
import copy

def prod_factors(num, result=[]):
    if num == 1:
        print('x'.join([str(_) for _ in result]))
        if 1 not in result:
            result.append(1)
            print('x'.join([str(_) for _ in result]))
    elif num < 0:
        return
    else:
        for i in range(1, num+1):
            if (i == 1 and i not in result) or (i !=1 and num % i == 0):
                newresult = copy.copy(result)
                newresult.append(i)
                prod_factors(num/i, newresult)

prod_factors(8)
1x2x2x2
1x2x4
1x4x2
1x8
2x1x2x2
2x1x4
2x2x1x2
2x2x2
2x2x2x1
2x4
2x4x1
4x1x2
4x2
4x2x1
8
8x1

展开

作者回复: 同时考虑了1出现和不出现的情况 👍



 2

Youngggg

2018-12-25

import copy
def get(num, result=[]):
    sum = 1
    for index in result:
        sum = sum * index
    if sum == num:
        print(result)
        if 1 not in result:
            result.append(1)
            print(result)
        return
    elif sum > num:
        return
    else:
        i=1
        while i<=num:
            if num%i != 0:
                i = i+1
                continue
            if i == 1 & 1 in result:
                i = i+1
                continue
            new_result = copy.copy(result)
            new_result.append(i)
            i = i+1
            get(num, new_result)

get(8, [])

[1, 2, 2, 2]
[1, 2, 4]
[1, 4, 2]
[1, 8]
[2, 1, 2, 2]
[2, 1, 4]
[2, 2, 1, 2]
[2, 2, 2]
[2, 2, 2, 1]
[2, 4]
[2, 4, 1]
[4, 1, 2]
[4, 2]
[4, 2, 1]
[8]
[8, 1]

展开



 2

icy

2018-12-24

# -*- coding: utf-8 -*-
"""
Created on Mon Dec 24 14:30:38 2018
@author: icytanz
"""

import copy

def get_mul_factor(num,result=[]):
    if(num==1):
        total=copy.copy(result)
        if 1 not in total:
            total.append(1)
        print(total)
        return
    elif(num<1):
        return
    else:
        n=list(range(num+1))
        n.reverse()
        if 1 in result:
            m=range(len(n)-2)
        else:
            m=range(len(n)-1)
        for i in m:
            new_result=copy.copy(result)
            if num%n[i]==0:
                new_result.append(n[i])
                get_mul_factor(num//n[i],new_result)

if __name__=='__main__':
    get_mul_factor(2)
    #[2, 1]
    #[1, 2]

    get_mul_factor(1)
    #[1]

    get_mul_factor(4)
    #[4, 1]
    #[2, 2, 1]
    #[2, 1, 2]
    #[1, 4]
    #[1, 2, 2]

    get_mul_factor(6)
    #[6, 1]
    #[3, 2, 1]
    #[3, 1, 2]
    #[2, 3, 1]
    #[2, 1, 3]
    #[1, 6]
    #[1, 3, 2]
    #[1, 2, 3]

    get_mul_factor(8)
    #[8, 1]
    #[4, 2, 1]
    #[4, 1, 2]
    #[2, 4, 1]
    #[2, 2, 2, 1]
    #[2, 2, 1, 2]
    #[2, 1, 4]
    #[2, 1, 2, 2]
    #[1, 8]
    #[1, 4, 2]
    #[1, 2, 4]
    #[1, 2, 2, 2]

展开



 2

hallon

2018-12-21

思考题，用js实现如下：
function mul(totalReward, result) {
    //i从自身开始循环到1，每次递减1
    for(var i=totalReward; i>0; i--) {
        if(totalReward % i == 0) {//能整除i
            var newResult = result.concat();
            newResult.push(i);
            if(i == totalReward) {//i为自身的情况，结果就是[totalReward，1]
                newResult.push(1);
                console.log(newResult);
            } else if(i == 1) {//i为1的情况，结果就是[1，totalReward]
                newResult.push(totalReward);
                console.log(newResult);
            }else {//除以i之后，继续分解
                 mul(totalReward/i, newResult);
            }
        }
    }
}
测试：数字6和8
var b = [];
mul(6, b);
mul(8, b);
结果如下：
[ 6, 1 ]
[ 3, 2, 1 ]
[ 3, 1, 2 ]
[ 2, 3, 1 ]
[ 2, 1, 3 ]
[ 1, 6 ]

[ 8, 1 ]
[ 4, 2, 1 ]
[ 4, 1, 2 ]
[ 2, 4, 1 ]
[ 2, 2, 2, 1 ]
[ 2, 2, 1, 2 ]
[ 2, 1, 4 ]
[ 1, 8 ]

展开



 2

郑晨Cc

2018-12-20

package 二进制;

import java.util.ArrayList;

public class Lesson5Test {

    public int counter = 0;



    public void chosen(int num,ArrayList list){

            if(null==list){
                list = new ArrayList();
                list.add(1);
                list.add(num);
            }

            if(num==1){ //递归终止
                return;
            }

            for(int i=1;i<=num;i++ ){
                if(i==1){
                    System.out.println(list);
                    counter++;
                    continue;

                }
                if(i==num){
                    list.add(1);
                    list.remove(0);
                    System.out.println(list);
                    counter++;
                    continue;

                }

                if(num%i==0){
                    int a = num/i;
                    ArrayList list2 = new ArrayList(list);
                    list2.remove(list.size()-1);
                    list2.add(i);
                    list2.add(a);
                    chosen(num/i,list2);
                }
            }

    }

    public static void main(String[] args){

        Lesson5Test too = new Lesson5Test();

        too.chosen(8, null);
        System.out.println("总数："+too.counter);

    }

}

控制台输出：
[1, 8]
[1, 2, 4]
[1, 2, 2, 2]
[2, 2, 2, 1]
[2, 4, 1]
[1, 4, 2]
[4, 2, 1]
[8, 1]
总数：8

展开



 2

miracle

2018-12-19

我来答下吧，案例中的n代表已经迭代的次数，在这个案例中，限制了每轮迭代只有四种选择



 2

Genesis_nbq♡

2019-12-22

#include <iostream>
#include <vector>
using namespace std;

const int N = 4;
int coins[N] = {1, 2, 5, 10};
vector<int> closen;

void dfs(int u)
{
    if(u > 10) return;
    if(u == 10)
    {
        for(int i = 0; i < closen.size(); i++)
        {
            if(i > 0) printf(" ");
            printf("%d", closen[i]);
        }
        puts("");
        return;
    }
    for(int i = 0; i < N; i++)
    {
        closen.push_back(coins[i]);
        u += coins[i];
        dfs(u);
        closen.pop_back();
        u -= coins[i];
    }
    return;
}

int main(void)
{
    dfs(0);
    return 0;
}
// 老师这样写对吗

展开

作者回复: 这个是C版本吗？

 1

 1

Geek_zy

2019-04-28

public class RecusionTwo {
    public RecusionTwo(int n){
        this.n =n;
    }
    private static int n;

    public static void get(ArrayList<Integer> result){
        int product =1;
        for(int j=0;j<result.size();j++){
            product*=result.get(j);
        }
        if(product == n){
            System.out.println(result);
            return;
        }else if(product>n){
            return;
        }else {
            for (int i=1; i <= n; i++) {
                int count = 1;
                if(i==1){
                 for(int j=0;j<result.size();j++){
                     if(result.get(j)==1){
                         count++;
                     }
                 }
                }
                if(count>1){
                    continue;
                }
                 ArrayList<Integer> newResult = (ArrayList<Integer>) result.clone();
                 newResult.add(i);
                 get( newResult);

            }
        }
    }

    public static void main(String[] args) {

        RecusionTwo recusionTwo = new RecusionTwo(8);
        get(new ArrayList<>());
    }
}

展开



 1

somenzz

2018-12-20

这里贴代码对Python这种缩进语言来讲很不友好啊，建议可以提交图片或者支持md格式。说下自己的思路：一个整数num 对 num 到 1 之间的整数 i 分别求余，如果余数为0，说明这是一个因子，将 i 添加到结果列表里，然后再让num 对 i 取整，得到 k ，对整数 K 再次递归求解。退出条件，如果 num == 1，那么将 1 添加到结果列表里，并打印结果列表。这里要注意下，如果 i == 1 ,也是退出条件，此时将 num 加入结果列表并打印。因为，一个大于1的数据除以1，永远得不到1 ，也就达不到前面的退出条件。源代码见 https://github.com/somenzz/geekbang/blob/master/mathOfProgramer/chapter05_recursion_1.py

作者回复: 少了一些可能。比如，输入8，少了
[1, 2, 2, 2]
[1, 2, 4]
[1, 4, 2]
[2, 1, 2, 2]



 1

文刂氵共超

2018-12-19

使用C++实现赏金问题
#include <vector>
#include <iostream>

using namespace std;

// totalmoney : 总金额
// select : 钱币面额的选择列表
// Result : 结果列表
void RecursionAlgo(int Totalmoney, vector<int> &Select, vector<int> &Result)
{
    //每次递归需要用总金额减去使用的面额，直到Totalmoney=0，表示找到解
    if (Totalmoney == 0)
    {
        for (size_t i = 0; i < Result.size(); ++i)
        {
            cout << Result[i] << " ";
        }
        cout << endl;
        return;
    }
    //Totalmoney < 0, 不符合标准返回
    else if (Totalmoney < 0)
    {
        return;
    }
    else
    {
        for (size_t i = 0; i < Select.size(); ++i)
        {
            vector<int> newResult = Result;
            newResult.push_back(Select[i]);
            RecursionAlgo(Totalmoney-Select[i], Select, newResult);
        }
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int Totalmoney = 10;

    int ia[] = {1, 2, 5, 10};
    vector<int> Select(ia, ia+4);
    vector<int> Result;

    RecursionAlgo(Totalmoney, Select, Result);
    return 0;
}

展开



 1