找到最小切割数

Question

谁能给我一个提示，如何找到下面这个问题的有效解决方案

亚历克斯带了一个面包卷到厨房，他想和同事们分享。要做到这一点，他想把纸卷切成N等份。当然，这卷纸只能横切。因此，亚历克斯将作出决定− 1用小刀定期切割

咖啡休息回来后，亚历克斯想知道——如果瓦尼亚的刀无限长（换句话说，如果他一次能切出他想要的任意多个伤口，如果这些伤口在一条直线上），是否可以少动几次？据信，切割的位置是事先规划好的，所有切割都精确无误

事实证明你可以。例如，如果Alex想将纸卷分成4部分，他可以做两次切割-首先他将纸卷分成两半，然后将两半合并，同时将两者切成两半。所以我需要找到最小的切割

给定N人

六,

结果

三,

给定N人

五,

结果

三,

我可以和少数人一起做，但如果有100或1000人呢

我的代码如下：

    public class Cake{
        public static void main(String[] args) throws IOException {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            int number = Integer.parseInt(reader.readLine());
            int all = 0;
            if (N % 2 == 0) {
                all = number/ 2;
            } 
            else {
            all = number / 2 + 1;
            }
                
            System.out.println(all);
        }
    }

Answer 1

这确实是一道数学题。两个人的第一次电源需要原木（N，2）切割，额外的人需要一次切割

from math import log

def cutCount(N): return 0 if N<2 else int(log(N-1,2))+1

输出：

for N in range(1,10): print(N,"people, cuts: ",cutCount(N))

1 people, cuts:  0
2 people, cuts:  1
3 people, cuts:  2
4 people, cuts:  2
5 people, cuts:  3
6 people, cuts:  3
7 people, cuts:  3
8 people, cuts:  3
9 people, cuts:  4

要验证是否存在较大的数字，可以模拟切割：

cutCount(50) # 6

1st cut  > 2 pieces
2nd cut  > 4 pieces
3rd cut  > 8 pieces
4th cut  > 16 pieces
5th cut  > 32 pieces
6th cut  > only cut 18 of the 32 pieces  > 50 pieces

假设你每次都有策略地放置这些碎片，那么你需要切割的最后18个碎片正好是总长度的2/50，其他14个碎片是1/50

有几种方法可以实现“战略性”削减。下面是一个例子：

 Number x Lengths (in 1/50th of the total length):
 
 cut #1 : [  -1x32  -][      1x18       -] total 2 pieces
 cut #2 : [  -2x16  -][      2x9        ] total 4 pieces
 cut #3 : [   4x8  -][ -2x4 ][    2x5     ] total 8 pieces
 cut #4 : [   8x4  -][ -4x2 ][ 2x2 ][  2x3  -] total 16 pieces
 cut #5 : [  -16x2  -](   12x1   -)(-2x1-)[-2x2-] total 32 pieces
          (     14x1    )[    18x2     -]
 cut #6 : (     14x1    )(    32x1     -) total 50 pieces
          (          -50x1           )

括号不可缩放。1/50的碎片不会再切割

如果您想要此计算的递归版本，可以在每次将人数除以2时计算1，然后在这些划分中至少有一个奇数结果时添加1：

def cutCount(N,odd=0):
    return odd if N<2 else 1+cutCount(N//2,odd|N%2)

Answer 2

使用递归算法

注：Alain T答案为精确公式

代码

def cuts(n):
    '''
        Recursively decide number of required cuts '
        
        Algorithm:
            Base case: n = 0 or 1:
                no cuts, so answer is 0

             n is even: divide roll into two rolls of n//2 (1 cut).  
                       These two rolls can be cut in parallel in the future
                       so cuts will be 1 + cuts(n//2).

                       Since n is even, n//2 == (n+1)//2, 
                       so this can also be written as 1 + cuts((n+1)//2).
                
                       So answer is: 1 + cuts((n+1)//2)
        
             Odd n: divide roll into two rolls of lengths n//2 and (n+1)//2  (1 cut)
                      One of these is even, the other odd.
                      These two rolls can be cut in parallel successively 
                      until the longer 1 is reduced to length 1.
                    
                      Thus cuts is 1 + cuts(max((n//2), (n+1)//2))

                      For all n: (n+1)//2 >= (n//2), so
                               max((n//2), (n+1)//2) = (n+1)//2

                       So answer is 1 + cuts((n+1)//2)

             So we have:
                if n = 0 or 1: return 0
                otherwise: return 1 + cuts((n+1)//2)
    '''
    return 0 if n < 2 else 1 + cuts((n+1)//2)
        
    for n in list(range(9)) + [20, 50, 100, 1000, 10000]:
        print(f'{n} people, cuts: {cuts(n)}')

输出

0 people, cuts: 0
1 people, cuts: 0
2 people, cuts: 1
3 people, cuts: 2
4 people, cuts: 2
5 people, cuts: 3
6 people, cuts: 3
7 people, cuts: 3
8 people, cuts: 3
20 people, cuts: 5
50 people, cuts: 6
100 people, cuts: 7
1000 people, cuts: 10
10000 people, cuts: 14