E卷-分糖果(100分)

分糖果

问题描述

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

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

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

输入格式

一个正整数 （），表示小明抓取的糖果数。

输出格式

一个整数，表示最少分至一颗糖果的次数。

样例输入

15

样例输出

5

样例解释

15+1=16;16/2=8;8/2=4;4/2=2;2/2=1;

数据范围

题解

由于每次会 / 2，时间复杂度是 级别的，可以接受

1. 如果当前糖果数是奇数，就 +1 或 -1 使其变为偶数。
2. 将偶数除以 2。
3. 重复上述步骤，直到糖果数变为 1。

参考代码

• Python

import sys

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

def dfs(candy, steps, min_steps):
    """
    深度优先搜索函数
    
    参数:
    candy: 当前的糖果数量
    steps: 当前的操作步数
    min_steps: 存储最小操作步数的列表
    """
    # 基本情况：如果糖果数量为1，更新最小操作步数
    if candy == 1:
        min_steps[0] = min(min_steps[0], steps)
        return

    # 如果糖果数量是偶数，直接除以2
    if candy % 2 == 0:
        dfs(candy // 2, steps + 1, min_steps)
    else:
        # 如果是奇数，有两种选择：加1或减1
        dfs(candy + 1, steps + 1, min_steps)
        dfs(candy - 1, steps + 1, min_steps)

def solve():
    """
    解题函数，初始化并调用DFS，返回最终结果
    """
    min_steps = [sys.maxsize]  # 使用列表存储最小步数，便于在递归中修改
    dfs(n, 0, min_steps)
    return min_steps[0]

# 输出结果
print(solve())

• C

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

// DFS函数声明
void dfs(long long candy, int steps, int *min_steps);

int main() {
    long long n;
    int min_steps = INT_MAX;
    
    // 读取输入
    scanf("%lld", &n);
    
    // 调用DFS函数
    dfs(n, 0, &min_steps);
    
    // 输出结果
    printf("%d\n", min_steps);
    
    return 0;
}

// DFS函数定义
void dfs(long long candy, int steps, int *min_steps) {
    // 基本情况：如果糖果数量为1，更新最小操作步数
    if (candy == 1) {
        if (steps < *min_steps) {
            *min_steps = steps;
        }
        return;
    }
    
    // 如果糖果数量是偶数，直接除以2
    if (candy % 2 == 0) {
        dfs(candy / 2, steps + 1, min_steps);
    } else {
        // 如果是奇数，有两种选择：加1或减1
        dfs(candy + 1, steps + 1, min_st