扔鸡蛋(Egg dropping)

  1. /// # Egg Dropping Puzzle
  3. /// `egg_drop(eggs, floors)` returns the least number of egg droppings
  4. ///     required to determine the highest floor from which an egg will not
  5. ///     break upon dropping
  6. ///
  7. /// Assumptions: n > 0
  8. pub fn egg_drop(eggs: u32, floors: u32) -> u32 {
  9.     assert!(eggs > 0);
  11.     // Explicity handle edge cases (optional)
  12.     if eggs == 1 || floors == 0 || floors == 1 {
  13.         return floors;
  14.     }
  16.     let eggs_index = eggs as usize;
  17.     let floors_index = floors as usize;
  19.     // Store solutions to subproblems in 2D Vec,
  20.     // where egg_drops[i][j] represents the solution to the egg dropping
  21.     // problem with i eggs and j floors
  22.     let mut egg_drops: Vec<Vec<u32>> = vec![vec![0; floors_index + 1]; eggs_index + 1];
  24.     // Assign solutions for egg_drop(n, 0) = 0, egg_drop(n, 1) = 1
  25.     for egg_drop in egg_drops.iter_mut().skip(1) {
  26.         egg_drop[0] = 0;
  27.         egg_drop[1] = 1;
  28.     }
  30.     // Assign solutions to egg_drop(1, k) = k
  31.     for j in 1..=floors_index {
  32.         egg_drops[1][j] = j as u32;
  33.     }
  35.     // Complete solutions vector using optimal substructure property
  36.     for i in 2..=eggs_index {
  37.         for j in 2..=floors_index {
  38.             egg_drops[i][j] = std::u32::MAX;
  40.             for k in 1..=j {
  41.                 let res = 1 + std::cmp::max(egg_drops[i - 1][k - 1], egg_drops[i][j - k]);
  43.                 if res < egg_drops[i][j] {
  44.                     egg_drops[i][j] = res;
  45.                 }
  46.             }
  47.         }
  48.     }
  50.     egg_drops[eggs_index][floors_index]
  51. }
  53. #[cfg(test)]
  54. mod tests {
  55.     use super::egg_drop;
  57.     #[test]
  58.     fn zero_floors() {
  59.         assert_eq!(egg_drop(5, 0), 0);
  60.     }
  62.     #[test]
  63.     fn one_egg() {
  64.         assert_eq!(egg_drop(1, 8), 8);
  65.     }
  67.     #[test]
  68.     fn eggs2_floors2() {
  69.         assert_eq!(egg_drop(2, 2), 2);
  70.     }
  72.     #[test]
  73.     fn eggs3_floors5() {
  74.         assert_eq!(egg_drop(3, 5), 3);
  75.     }
  77.     #[test]
  78.     fn eggs2_floors10() {
  79.         assert_eq!(egg_drop(2, 10), 4);
  80.     }
  82.     #[test]
  83.     fn eggs2_floors36() {
  84.         assert_eq!(egg_drop(2, 36), 8);
  85.     }
  87.     #[test]
  88.     fn large_floors() {
  89.         assert_eq!(egg_drop(2, 100), 14);
  90.     }
  91. }