資料結構
網路
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 次瀏覽
廣告