本文概述
- C ++
- Java
- Python3
- C#
- PHP
例子：
Input:n = 2
Output: Number of ways = 2
Explanation: Let the set be {1, 2}
{ {1}, {2} }
{ {1, 2} }Input:n = 3
Output: Number of ways = 5
Explanation: Let the set be {1, 2, 3}
{ {1}, {2}, {3} }
{ {1}, {2, 3} }
{ {2}, {1, 3} }
{ {3}, {1, 2} }
{ {1, 2, 3} }.解决上述问题的方法是响铃号码.
什么是响铃号码？
【bell数（对集合进行分区的方式数量）】让
S(n, k)
是将n个元素划分为k个集合的总数。对于k = 1到n, 第n个贝尔号的值是S(n, k)的和。
文章图片
S(n, k)的值可以递归定义为S(n + 1, k)= k * S(n, k)+ S(n, k-1)
上述递归公式如何工作？
当我们将第(n + 1)个元素添加到k个分区时, 有两种可能性。
1)将其作为单个元素集添加到现有分区, 即S(n, k-1)
2)将其添加到每个分区的所有集合中, 即k * S(n, k)
S(n, k)被称为第二类斯特林数
前几个贝尔编号是1、1、2、5、15、52、203, ...。
一种简单方法要计算第n个贝尔数, 则将k = 1到n的计算S(n, k)一对一并返回所有计算值的总和。参考这个用于计算S(n, k)。
一种更好的方法用于钟形三角形。以下是前几个贝尔编号的示例贝尔三角形。
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52使用以下公式构造三角形。
// If this is first column of current row 'i'
If j == 0
// Then copy last entry of previous row
// Note that i'th row has i entries
Bell(i, j) = Bell(i-1, i-1) // If this is not first column of current row
Else
// Then this element is sum of previous element
// in current row and the element just above the
// previous element
Bell(i, j) = Bell(i-1, j-1) + Bell(i, j-1)解释
然后Bell(n, k)计算集合{1, 2??, …, n + 1}的分区数, 其中元素k +1是该集合中可以单独存在的最大元素。
例如, Bell(3, 2)是3, 它是{1, 2, 3, 4}的分区数的计数, 其中3是最大的单例元素。有三个这样的分区：
{1}, {2, 4}, {3}
{1, 4}, {2}, {3}
{1, 2, 4}, {3}.下面是上述递归公式的基于动态编程的实现。
C ++
// A C++ program to find n'th Bell number
#include<
iostream>
using namespace std;
int bellNumber( int n)
{
int bell[n+1][n+1];
bell[0][0] = 1;
for ( int i=1;
i<
=n;
i++)
{
// Explicitly fill for j = 0
bell[i][0] = bell[i-1][i-1];
// Fill for remaining values of j
for ( int j=1;
j<
=i;
j++)
bell[i][j] = bell[i-1][j-1] + bell[i][j-1];
}
return bell[n][0];
}// Driver program
int main()
{
for ( int n=0;
n<
=5;
n++)
cout <
<
"Bell Number " <
<
n <
<
" is "
<
<
bellNumber(n) <
<
endl;
return 0;
}Java
// Java program to find n'th Bell number
import java.io.*;
class GFG
{
// Function to find n'th Bell Number
static int bellNumber( int n)
{
int [][] bell = new int [n+ 1 ][n+ 1 ];
bell[ 0 ][ 0 ] = 1 ;
for ( int i= 1 ;
i<
=n;
i++)
{
// Explicitly fill for j = 0
bell[i][ 0 ] = bell[i- 1 ][i- 1 ];
// Fill for remaining values of j
for ( int j= 1 ;
j<
=i;
j++)
bell[i][j] = bell[i- 1 ][j- 1 ] + bell[i][j- 1 ];
}return bell[n][ 0 ];
}// Driver program
public static void main (String[] args)
{
for ( int n= 0 ;
n<
= 5 ;
n++)
System.out.println( "Bell Number " + n +
" is " +bellNumber(n));
}
}// This code is contributed by Pramod KumarPython3
# A Python program to find n'th Bell numberdef bellNumber(n):bell = [[ 0 for i in range (n + 1 )] for j in range (n + 1 )]
bell[ 0 ][ 0 ] = 1
for i in range ( 1 , n + 1 ):# Explicitly fill for j = 0
bell[i][ 0 ] = bell[i - 1 ][i - 1 ]# Fill for remaining values of j
for j in range ( 1 , i + 1 ):
bell[i][j] = bell[i - 1 ][j - 1 ] + bell[i][j - 1 ]return bell[n][ 0 ]# Driver program
for n in range ( 6 ):
print ( 'Bell Number' , n, 'is' , bellNumber(n))# This code is contributed by Soumen GhoshC#
// C# program to find n'th Bell number
using System;
class GFG {// Function to find n'th
// Bell Number
static int bellNumber( int n)
{
int [, ] bell = new int [n + 1, n + 1];
bell[0, 0] = 1;
for ( int i = 1;
i <
= n;
i++)
{// Explicitly fill for j = 0
bell[i, 0] = bell[i - 1, i - 1];
// Fill for remaining values of j
for ( int j = 1;
j <
= i;
j++)
bell[i, j] = bell[i - 1, j - 1] +
bell[i, j - 1];
}return bell[n, 0];
}// Driver Code
public static void Main ()
{
for ( int n = 0;
n <
= 5;
n++)
Console.WriteLine( "Bell Number " + n +
" is " +bellNumber(n));
}
}// This code is contributed by nitin mittal.PHP
<
?php
// A PHP program to find
// n'th Bell number// function that returns
// n'th bell number
function bellNumber( $n )
{$bell [0][0] = 1;
for ( $i = 1;
$i <
= $n ;
$i ++)
{// Explicitly fill for j = 0
$bell [ $i ][0] = $bell [ $i - 1]
[ $i - 1];
// Fill for remaining
// values of j
for ( $j = 1;
$j <
= $i ;
$j ++)
$bell [ $i ][ $j ] = $bell [ $i - 1][ $j - 1] +
$bell [ $i ][ $j - 1];
}
return $bell [ $n ][0];
}// Driver Code
for ( $n = 0;
$n <
= 5;
$n ++)
echo ( "Bell Number " . $n . " is "
. bellNumber( $n ) . "\n" );
// This code is contributed by Ajit.
?>
输出如下：
Bell Number 0 is 1
Bell Number 1 is 1
Bell Number 2 is 2
Bell Number 3 is 5
Bell Number 4 is 15
Bell Number 5 is 52上述解决方案的时间复杂度为O(n2)。我们很快将讨论计算贝尔数的其他更有效的方法。
贝尔数字可以解决的另一个问题
.
一个数字是
无平方
如果不能用除1以外的完美平方整除, 例如6是无平方数, 但不能用12除以4。
给定无平方数x, 找到x的不同乘法分区的数量。乘法分区的数量是Bell(n), 其中n是x的素数的数量。例如x = 30, 有3个素数分别为2、3和5。因此答案是Bell(3), 即5。5个分区是1 x 30、2 x15、3 x 10、5 x 6和2 3 x 5
行使：
上面的实现导致n的较大值发生算术溢出。扩展上面的程序, 以便以模1000000007计算结果, 以避免溢出。
参考：
https://en.wikipedia.org/wiki/Bell_number
https://en.wikipedia.org/wiki/Bell_triangle
本文作者：拉杰夫·阿格劳瓦尔(Rajeev Agrawal)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- 如何使用PHP在网络浏览器中打开PDF文件（）
- Python中的双端队列详解
- Golang指向指针的指针（双指针）介绍
- Perl中的软件包详细指南
- DetailView –基于类的视图Django
- 计算机网络简明教程（四）（网络性能指标分析详解）
- 10道Vue.js精简经典面试题及答案——面试必备
- 计算机网络简明教程（三）（网络分类详解）
- 7个vue前端ui框架——前端程序员必须掌握