(B卷,100分)- 分糖果（Java & JS & Python & C）

题目描述

小明从糖果盒中随意抓一把糖果，每次小明会取出一半的糖果分给同学们。

当糖果不能平均分配时，小明可以选择从糖果盒中（假设盒中糖果足够）取出一个糖果或放回一个糖果。

小明最少需要多少次（取出、放回和平均分配均记一次），能将手中糖果分至只剩一颗。

输入描述

抓取的糖果数（<10000000000）：15

输出描述

最少分至一颗糖果的次数：5

用例

题目分析

本题由于是每次折半，因此本题数量级即便很大，也不怕超时。

没有了超时的后顾之忧，本题，直接可以暴力逻辑求解，假设输入的是num，分配次数count初始为0，那么：

• 如果num % 2 == 0，则可以直接折半，此时分配次数count++， num /= 2
• 如果num % 2 !=0，则不可以直接折半，此时需要开两个分支：

1. 取出一个糖，即num += 1，然后分配次数count++，之后继续前面折半逻辑
2. 放回一个糖，即num -= 1，然后分配次数count++，之后继续前面折半逻辑

最终我们只需要在众多分支中，取最少的count即可。

上面逻辑可以基于递归实现。具体实现请看代码。

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.nextLong()));
  }

  public static long getResult(long num) {
    int[] ans = {Integer.MAX_VALUE};
    recursive(num, 0, ans);
    return ans[0];
  }

  public static void recursive(long num, int count, int[] ans) {
    if (num == 1) {
      ans[0] = Math.min(ans[0], count);
      return;
    }

    if (num % 2 == 0) {
      recursive(num / 2, count + 1, ans);
    } else {
      recursive(num + 1, count + 1, ans);
      recursive(num - 1, count + 1, ans);
    }
  }
}

JS算法实现

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(Number(line)));
});

function getResult(num) {
  ans = [Infinity];
  recursive(num, 0, ans);
  return ans[0];
}

function recursive(num, count, ans) {
  if (num == 1) {
    ans[0] = Math.min(ans[0], count);
    return;
  }

  if (num % 2 == 0) {
    recursive(num / 2, count + 1, ans);
  } else {
    recursive(num + 1, count + 1, ans);
    recursive(num - 1, count + 1, ans);
  }
}

Python算法源码

import sys

# 输入获取
num = int(input())


def recursive(num, count, ans):
    if num == 1:
        ans[0] = min(ans[0], count)
        return

    if num % 2 == 0:
        recursive(num // 2, count + 1, ans)
    else:
        recursive(num + 1, count + 1, ans)
        recursive(num - 1, count + 1, ans)


# 算法入口
def getResult():
    ans = [sys.maxsize]
    recursive(num, 0, ans)
    return ans[0]


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <limits.h>

#define MIN(a,b) (a) < (b) ? (a) : (b)

void recursive(long long num, int count);

int ans = INT_MAX;

int main() {
    long long num;
    scanf("%lld", &num);

    recursive(num, 0);

    printf("%dn", ans);

    return 0;
}

void recursive(long long num, int count) {
    if(num == 1) {
        ans = MIN(ans, count);
        return;
    }

    if(num % 2 == 0) {
        recursive(num / 2, count + 1);
    } else {
        recursive(num + 1, count + 1);
        recursive(num - 1, count + 1);
    }
}