java - 找到最小切割数

问题描述

谁能给我一个提示如何为以下问题找到有效的解决方案？

亚历克斯带了一卷到厨房，他想和他的同事们分享。为此，他想将卷切成 N 等份。当然，卷筒只能横切。因此，Alex 将定期用刀切割 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);
        }
    }

标签： javapython

解决方案

这确实是一道数学题。您将需要对 2 人的第一次幂进行 log(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)

java - 找到最小切割数

问题描述

解决方案

推荐阅读