Giảm số xuống 1 trong JavaScript

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript lấy số, num làm đối số duy nhất.

Hàm của chúng ta chỉ có thể thực hiện hai thao tác này trên num:Nếu num là chẵn, chúng ta có thể thay num bằng num / 2
Nếu num là số lẻ, chúng ta có thể thay thế num bằng num + 1 hoặc num - 1.

Chỉ sử dụng kết hợp hai thao tác này, hàm của chúng ta bắt buộc phải tính toán có bao nhiêu thao tác tối thiểu mà nó yêu cầu để đưa num xuống 1. Hàm phải trả về số hoạt động tối thiểu.

Ví dụ:nếu đầu vào của hàm là -

const num = 7;

Sau đó, đầu ra phải là -

const output = 4;

Giải thích đầu ra:

Bởi vì các hoạt động nhỏ nhất có thể là -

7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

Ví dụ

Mã cho điều này sẽ là -

const num = 7;
const downToOne = (num = 1) => {
   let min = Number.POSITIVE_INFINITY;
   let stack = [{ num: num, step: 0 }];
   let set = new Set();
   let next;
   let item;
   while (stack.length) {
      item = stack.shift();
      if (item.num === 1) {
         if (min > item.step) {
            min = item.step;
         }
         continue;
      }
      if (set.has(item.num) || item.step >= min) {
         continue;
      }
      set.add(item.num);
      next = item.step + 1;
      if (item.num % 2 === 0) {
         item.num /= 2;
         stack.push({ num: item.num, step: next });
      } else {
         stack.push({ num: item.num - 1, step: next });
         stack.push({ num: item.num + 1, step: next });
      }
   }
   return min;
};
console.log(downToOne(num));

Đầu ra

Đầu ra trong bảng điều khiển sẽ là -