数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究找到把一个数字表示为小于它的数字之和的方法数的 C++ 程序
在这个程序中，我们将计算一个数字可以用小于它的数字之和来表示的方法数。此程序将计算给定数字的划分。我们取一个数字 n 作为输入，然后从一个数字开始，每次去掉 1 来分解它。如果生成了新划分，则增加计数器。
算法
partitionCount(n)
输入：数字 n
输出：划分数
Begin Create array p of size n k := 0 count := -1 put n as the first element of array p Repeat the following steps, do increase count by 1 rem := 0 while k >= 0 and p[k] = 1, do rem := rem + p[k] decrease k by 1 done if k < 0, then return count p[k] := p[k] – 1 rem := rem + 1 while rem >= p[k], do p[k+1] := p[k] rem := rem - p[k] increase k by 1 done p[k+1] := rem increase k by 1 done End
示例代码
#include<iostream>
using namespace std;
int partitionCount(int n){ //used to count all possible partitions
int p[n], k = 0, count = -1;
p[k] = n; //add n as the first element of array
while(true) { //repeat untill all elements are turned to 1
count++;
int rem = 0;
while (k >= 0 && p[k] == 1){ // Move the pointer to the correct index where p[k] > 1.
rem += p[k];
k--;
}
if (k < 0) // If k < 0 then the all the element are broken down to 1.
return count;
//otherwise decrease the value by 1, and increase rem
p[k]--;
rem++;
while (rem > p[k]) { // repeat until the number of 1's are greater than the value at k index.
p[k+1] = p[k];
rem -= p[k]; // Decrease the rem_val value.
k++;
}
p[k+1] = rem; // Assign remaining value to the index next to k.
k++;
}
}
main() {
int n, c;
cout<<"Enter number for partition counting: ";
cin>>n;
if (n <= 0) { //n must be greater than or equal to 1
cout<<"Invalid value of n";
exit(1);
}
c = partitionCount(n);
cout<<"The number of partitions: "<<c;
}输出
Enter number for partition counting: 7 The number of partitions: 14
更新于： 2019-07-30
206 次浏览
广告