dfs

对于目前糖果数分为两种情况$\\$ 1.是偶数，直接选择分配，也就是ans=dfs(n>>1)$\\$ 2.是奇数但不是1则考虑+1和-1操作再分配ans=max(dfs((n+1)>>1),(n-1)>>1,ans)$\\$ 3.是1直接反回ans$\\$ 考虑dfs递归出所有情况最小值即可

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int dfs(int x,int sum){
	int res=100;
	if(x==1){
		return sum;
	}
//	cout<<x<<' '<<sum<<'\n';
	if(x%2==0){
		res=min(dfs(x>>1,sum+1),res);
	}
	else{
		res=min(dfs((x+1)>>1,sum+2),res);
		res=min(dfs((x-1)>>1,sum+2),res);
	}
	return res;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	cout<<dfs(n,0);
	return 0;
}

python

def dfs(x, sum_val):
    res = 100
    if x == 1:
        return sum_val
    if x % 2 == 0:
        res = min(dfs(x // 2, sum_val + 1), res)
    else:
        res = min(dfs((x + 1) // 2, sum_val + 2), res)
        res = min(dfs((x - 1) // 2, sum_val + 2), res)
    return res

n = int(input())
print(dfs(n, 0))

java

import java.util.Scanner;

public class Main {
    public static int dfs(int x, int sum) {
        int res = 100;
        if (x == 1) {
            return sum;
        }
        if (x % 2 == 0) {
            res = Math.min(dfs(x / 2, sum + 1), res);
        } else {
            res = Math.min(dfs((x + 1) / 2, sum + 2), res);
            res = Math.min(dfs((x - 1) / 2, sum + 2), res);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(dfs(n, 0));
        sc.close();
    }
}

题目描述

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

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

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

输入描述

抓取的糖果数<1000000000

输出描述

最少分至一颗糖果的次数

样例1

输入

15

输出

5

说明

$15+1=16$;

$16/2=8$;

$8/2=4$;

$4/2=2$;

$2/2=1$;