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

(新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("%d\n", 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); } }