Java 中的蛋糕数

2025年3月17日 | 阅读 7 分钟

在本节中，我们将学习如何在 Java 中找到蛋糕数。蛋糕数 CK_n表示用 n 个平面切割将蛋糕分割成最多份数。饼干数的三个维度版本就是蛋糕数。

一般来说，

CK_n= (n³ + 5 *n + 6) / 6 其中 n >= 0

因此，

对于 n = 0，

CK₀= (0³+ 5 * 0 + 6) / 6 = (6) / 6 = 6 / 6 = 1

对于 n = 1，

CK₁= (1³+ 5 * 1 + 6) / 6 = (1 + 5 + 6) / 6 = 12 / 6 = 2

对于 n = 2，

CK₂= (2³+ 5 * 2 + 6) / 6 = (8 + 10 + 6) / 6 = 24 / 6 = 4

对于 n = 3，

CK₃= (3³+ 5 * 3 + 6) / 6 = (27 + 15 + 6) / 6 = 48 / 6 = 8

对于 n = 4，

CK₄= (4³+ 5 * 4 + 6) / 6 = (64 + 20 + 6) / 6 = 90 / 6 = 15

对于 a = 5，

CK₅= (5³+ 5 * 5 + 6) / 6 = (125 + 25 + 6) / 6 = 156 / 6 = 26

实施

让我们看看如何实现上述数学公式。请注意以下示例。

文件名： CakeNumberExample1.java

public class CakeNumberExample1
{
// a method that finds the value of b ^ e
int pow(int b, int e)
{
// anything whose power is 0 is 1
if(e == 0)
{
return 1;
}

// it will store the result
int ans = 1;
while(true)
{

if(e % 2 == 1)
{
e = e - 1;
ans = ans * b;
if(e == 0)
{
return ans;
}
}
b = b * b;
e = e / 2;
}
}
public int findCakeNo(int n)
{
// finding n ^ 3
int x = pow(n, 3);
// finding 5 * n
int y = 5 * n;
// finding the cake number
// computing (n ^ 3 + 5 * n + 6) / 6
int no = (x + y + 6) / 6;
return no;
}
// main method
public static void main(String argvs[])
{
// creating an object of the class CakeNumberExample1
CakeNumberExample1 obj = new CakeNumberExample1();
System.out.println("The first 30 cake numbers are: ");
for(int i = 0; i < 30; i++)
{
// invoking the method findCakeNo()
int num = obj. findCakeNo(i);
System.out.print(num + " ");
}
}
}

输出

The first 30 cake numbers are: 
1 2 4 8 15 26 42 64 93 130 176 232 299 378 470 576 697 834 988 1160 1351 1562 1794 2048 2325 2626 2952 3304 3683 4090

使用递归

蛋糕数也可以使用递归找到。但是，要通过递归找到蛋糕数，我们必须知道它的递归公式。

CK₀= 1，当 n = 0 时

CK₁= 2，当 n = 1 时

CK_n = ^{n + 1}C₃ + n + 1，当 n >= 2 时

因此，

对于 n = 2

实施

让我们看看如何实现上述数学公式。请注意以下示例。

文件名： CakeNumberExample2.java

public class CakeNumberExample2
{
public int findCakeNo(int n, int r)
{
// handling the base case nC0 = 1
if(r == 0)
{
    return 1;
}
// handling the base case nC1 = n
else if(r == 1)
{
    return n;
}
// handling the base case nCn = 1
else if( n == r )
{
    return 1;
}
// nCr = ( n / r ) * (n - 1)C(r - 1)
int ans = findCakeNo(n - 1, r - 1);
ans = (ans * n) / r;
return ans;

}
// main method
public static void main(String argvs[])
{
// creating an object of the class CakeNumberExample2
CakeNumberExample2 obj = new CakeNumberExample2();
System.out.println("The first 30 cake numbers are: ");

for(int i = 0; i < 30; i++)
{
int num = 1;
// first cake number
if(i == 0)
{
num = 1;    
}
// second cake number
else if(i == 1)
{
num = 2;
}
// invoking the method findCakeNo()
num = obj. findCakeNo(i + 1, 3) + i + 1;
System.out.print(num + " ");
}
}
}

输出

The first 30 cake numbers are: 
1 2 4 8 15 26 42 64 93 130 176 232 299 378 470 576 697 834 988 1160 1351 1562 1794 2048 2325 2626 2952 3304 3683 4090

使用迭代

蛋糕数也可以通过迭代找到。我们将使用循环借助二维数组来找到蛋糕数。请注意以下程序。

文件名： CakeNumberExample3.java

public class CakeNumberExample3
{

// main method
public static void main(String argvs[])
{
// array for storing combinations of 
// numbers
int arr[][] = new int[31][4];

// nCr, for r = 0 is always 1
for(int i = 0; i < 31; i++)
{
arr[i][0] = 1;
}


// for finding nCr where r != 0
for(int i = 1; i < 31; i++)
{
for(int j = 1; j <= 3 && j <= i; j++)
{
if(i == j)
{
arr[i][j] = 1;
}
else
{
// nCr = (n - 1)C(r - 1) + (n - 1)Cr
arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
}
}
}

System.out.println("The first 30 cake numbers are: ");

for(int i = 0; i < 30; i++)
{
int num = 1;

// first cake number
if(i == 0)
{
num = 1;    
}

// second cake number
else if(i == 1)
{
num = 2;
}

// finding the remaining cake numbers using the
// combinations result stored in the array arr[][]

// computing (n + 1)C3 + n + 1 
num = arr[i + 1][3] + i + 1;
    
System.out.print(num + " ");
}
}
}

输出

The first 30 cake numbers are: 
1 2 4 8 15 26 42 64 93 130 176 232 299 378 470 576 697 834 988 1160 1351 1562 1794 2048 2325 2626 2952 3304 3683 4090

另一种方法

除了上述讨论的方法外，还有一种使用组合计算蛋糕数的方法。请注意以下数学陈述。

CK₀= 1，当

CK₁= 2，当

CK₂= 4，当

CK_n = ⁿC₃ + ⁿC₂ + ⁿC₁ + ⁿC₀，当 n >= 3 时

因此，

对于 n = 3，

实施

让我们在下面的代码中看看上述公式的递归和迭代实现，以找到蛋糕数。

文件名： CakeNumberExample4.java

public class CakeNumberExample4
{

int arr[][] = new int[31][4];

public void fill()
{
    
// nCr, for r = 0 is always 1
for(int i = 0; i < 31; i++)
{
arr[i][0] = 1;
}


// for finding nCr where r != 0
for(int i = 1; i < 31; i++)
{
for(int j = 1; j <= 3 && j <= i; j++)
{
if(i == j)
{
arr[i][j] = 1;
}
else
{
// nCr = (n - 1)C(r - 1) + (n - 1)Cr
arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
}
}
}

}

// finding xCy
public int findCakeNumRecursive(int x, int y)
{

// xCy = 1, for y = x
if(x == y)
{
return 1;
}

// xCy = 1, for y = 0
else if(y == 0)
{
return 1;
}

else
{
int ans = findCakeNumRecursive(x - 1, y - 1);
ans = (ans * x) / y;
return ans;
}

}


// finding xCy iteratively
public int findCakeNumIterative(int x, int y)
{

// xCy = 1, for y = x
if(x == y)
{
return 1;
}

// xCy = 1, for y = 0
else if(y == 0)
{
return 1;
}

else
{
int ans = arr[x][y];
return ans;
}

}


// main method
public static void main(String argvs[])
{
    
// creating an object of the class CakeNumberExample4
CakeNumberExample4 obj = new CakeNumberExample4();

System.out.println("The first 30 cake numbers are: ");

for(int i = 0; i < 30; i++)
{
int num = 1;

// first cake number
if(i == 0)
{
num = 1;    
}

// second cake number
else if(i == 1)
{
num = 2;
}
else if(i == 2)
{
    num = 4;
}
else
{
// recursively finding iC3, iC2, iC1, iC0
num = obj.findCakeNumRecursive(i, 3) +
            obj.findCakeNumRecursive(i, 2) +
            obj.findCakeNumRecursive(i, 1) +
            obj.findCakeNumRecursive(i, 0);
       
}

System.out.print(num + " ");

}

System.out.println("\n ");

obj.fill();


System.out.println("The first 30 cake numbers are: ");

for(int i = 0; i < 30; i++)
{
int num = 1;

// first cake number
if(i == 0)
{
num = 1;    
}

// second cake number
else if(i == 1)
{
num = 2;
}

else
{
// iteratively finding iC3, iC2, iC1, iC0
num = obj.findCakeNumIterative(i, 3) +
            obj.findCakeNumIterative(i, 2) +
            obj.findCakeNumIterative(i, 1) +
            obj.findCakeNumIterative(i, 0);  
}

System.out.print(num + " ");

}
}
}

输出

The first 30 cake numbers are: 
1 2 4 8 15 26 42 64 93 130 176 232 299 378 470 576 697 834 988 1160 1351 1562 1794 2048 2325 2626 2952 3304 3683 4090 

The first 30 cake numbers are: 
1 2 4 8 15 26 42 64 93 130 176 232 299 378 470 576 697 834 988 1160 1351 1562 1794 2048 2325 2626 2952 3304 3683 4090

下一主题Java 中的时间比较

Java 中的蛋糕数

实施

使用递归

实施

使用迭代

另一种方法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的蛋糕数

实施

使用递归

实施

使用迭代

另一种方法

实施

相关帖子

LINQ 是什么

Java UTF

Java 中的动态初始化

DecimalFormat getMaximumIntegerDigits() method in Java

Load Factor in HashMap

如何在 Java 中重写 tostring() 方法

如何在 Java 中从日期获取星期几

Java 程序查找数组元素之间的最小距离

Visitor Design Pattern Java

如何在 Java 中将 double 和 float 四舍五入到两位小数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器