Rayn Miller
  • 2021年 12月04日
  • 0 阅读

Rust·算法基础·暴力递归

 

本文简介

本文简介

暴力递归

  • 尝试
    • 把问题转化为规模更小的同类子问题
    • 有明确的不需要继续进行递归的条件：base case
    • 有得到子问题结果之后的决策过程
    • 不记录每个子问题的解

汉诺塔问题

在一根柱子上从下往上按照大小顺序摞着多个黄金圆盘，把圆盘从下面开始按大小顺序重新摆放在另一根柱子上

fn hanoi(n: usize) {
    hanoi_recurrence(n, "A", "C", "B");
}

fn hanoi_recurrence(n: usize, from:&str, to:&str, mid: &str) {
    if n == 0 {return;}

    hanoi_recurrence(n-1, from, mid, to);
    println!("盘[{}]: {} -> {}", n, from, to);
    hanoi_recurrence(n-1, mid, to, from);
}

打印字符串的子序列

  • 打印一个字符串的所有子序列，包括空串
  • 算法
    • 从左到右依次对每一个字符尝试有和无两种情况
    • 当到达最后一个字符之外，打印这整个字符串

  • 算法实现

    pub fn print_all_sub_sequence(s: &str) {
  let mut ss: Vec<char> = s.to_string().chars().collect();
  sub_sequence(&mut ss, 0);
  println!("");
}

fn sub_sequence(s: &mut Vec<char>, idx: usize) {
    if idx == s.len() {
        let mut x = String::from_iter(s.iter());
        x.retain(|c| c != ' ');
        print!("{:?}, ", x);
        return;
    }

    sub_sequence(s, idx+1);
    let tmp = s[idx];
    s[idx] = ' ';
    sub_sequence(s, idx+1);
    s[idx] = tmp;
}

获取一个字符串的全排列

  • 算法
    • 从左到右全排列

  • 算法实现

    fn permutation(s: &mut Vec<char>, idx: usize, res: &mut Vec<String>) {
  if idx == s.len() {
      res.push(String::from_iter(s.iter()));
      return;
  }

  let mut visit = vec![false;26];
  for j in idx..s.len() {
      if  !visit[s[j] as usize - 'a' as usize] {
          visit[s[j] as usize - 'a' as usize] = true;
          s.swap(idx, j);
          permutation(s, idx+1, res);
          s.swap(idx, j);
      }
  }
}

pub fn print_permutation(s: &str) {
    println!("字符串: {}的全排序为：", s);
    let mut res: Vec<String> = vec![];
    let mut s:Vec<char> = s.to_string().chars().collect();
    permutation(&mut s, 0, &mut res);
    println!("{:?}", res);
}

纸牌

  • 题目
    • 给定一个整形数组，代表数值不同的纸牌排成一条线
    • 玩家A、B依次拿走纸牌
    • 规定A先拿B后拿
    • 每个玩家只能拿走最左或最右的牌
    • 假定A、B都绝顶聪明
    • 返回最后获胜者的分数
  • 举例
    • arr = [1, 2, 100, 3]
    • A先拿1 -> B拿2 -> A拿100

  • 算法实现

    fn frist(card: &Vec<u32>, l: usize, r:usize) -> u32 {
    if l == r { return card[l]; }

    std::cmp::max(
        frist(card, l, l) + second(card, l+1, r), 
        frist(card, r, r) + second(card, l, r-1))
}

fn second(card: &Vec<u32>, l:usize, r:usize) -> u32 {
    if l==r { return 0; }

    std::cmp::min(
        frist(card, l+1, r),
        frist(card, l, r-1))
}

逆序一个栈

  • 不能用额外数据结构，用递归实现
  • 实现一个取出栈底元素的函数stack_bottom

  • 算法实现

    fn stack_bottom(stack: &mut Vec<i32>)-> i32 {
    let res = stack.pop().unwrap();
    if stack.is_empty() {
        return res;
    }else{
        let last = stack_bottom(stack);
        stack.push(res);
        return last;
    }
}

fn reverse_stack(stack: &mut Vec<i32>) {
    if stack.is_empty() {return;}
    let bottom = stack_bottom(stack);
    reverse_stack(stack);
    stack.push(bottom);
}

转换字符

  • 题目
    • 规则
      • 1:A, 2:B, ...
      • 1个数字对应一个字符
      • 111可以是AAA, KA, AK
    • 给定一个数字字符串，返回多种结果
  • 算法
    • 从左到右依次转换
    • 对遇到的数字进行拆分
      • 数字为0
        • 不能转换，有问题
      • 数字为1
        • 可以是A
        • 可以和后面的数字组合
      • 数字为2
        • 可以是B
        • 后面数字是[0:6]，可以组合
        • 后面数字是[7:9]，不可以组合
      • 数字为[3:9]
        • 直接转换为字母
    • 假设trans_methods(str, i)表示
      • str[..i-1]的转换已经完成
      • str[i..]有多少种转换

  • 算法实现

    // [0..i-1]如何转化已经做过决定
// [i..]有多少种转化结果
fn trans_methods(s: &Vec<char>, i:usize) ->i32 {
    let slen = s.len();
    if slen == i {return 1;}
    match s[i] {
        // 进入无效状态，虽然a[..i-1]转化有效，所以整体是0种
      '0' => return 0,
      '1' => {
          // s[i]独立转化，后续a[i+1..]有多少种
          let mut res = trans_methods(s, i+1);
          // s[i]和s[i+1]组合，后续a[i+2..]有多少种
            if i+1 < slen { res += trans_methods(s, i+2); }
            return res;
        },
        '2' => {
            let mut res = trans_methods(s, i+1);
            if i+1 < slen && '0' <= s[i+1] && s[i+1] <= '6' {
                res += trans_methods(s, i+2);
            }
            return res;
        }
        _ => { return trans_methods(s, i+1); }
    }
}

装袋

  • 给定长度为N的数组：weights, values
  • 给定正数bag，表示载重bag的袋子
  • 问能装下最多的价值是多少？

  • 算法实现

    fn max_value(weight: &mut Vec<i32>, values: &mut Vec<i32>,
          i: usize, alread_weight: i32, bag: i32) -> i32 {
    // 如果超重了，直接返回0
    if alread_weight > bag {return 0;}
    // 没货了，要的货超过了货物数目
    if i == weight.len() {return 0;}
    std::cmp::max(
        // 不选第i件
        max_value(weight, values, i+1, alread_weight, bag),
        // 选第i件
        values[i] + max_value(weight, values, i+1, alread_weight+weight[i], bag)
    )
}
搜索