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;
//否则将值减少1，并增加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