資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時髦研究
法律研究C++ 程式以所有可能的方式執行整數的分割槽
這是一個 C++ 程式，獲取特定整數的所有唯一分割槽，這樣分割槽加起來得到整數。這個程式給出一個正整數 n，然後生成 n 的所有可能唯一表示方式，即正整數之和。
演算法
Begin function displayAllUniqueParts(int m): Declare an array to store a partition p[m]. Set Index of last element k in a partition to 0 Initialize first partition as number itself, p[k]=m Create a while loop which first prints current partition, then generates next partition. The loop stops when the current partition has all 1s. Display current partition as displayArray(p, k + 1); Generate next partition: Initialize val=0. Find the rightmost non-one value in p[]. Also, update the val so that we know how much value can be accommodated. If k < 0, all the values are 1 so there are no more partitions Decrease the p[k] found above and adjust the val. If val is more, then the sorted order is violeted. Divide val in different values of size p[k] and copy these values at different positions after p[k]. Copy val to next position and increment position. End
範例程式碼
#include<iostream>
using namespace std;
void printArr(int p[], int m) {
for (int i = 0; i < m; i++)
cout << p[i] << " ";
cout << endl;
}
void printAllUniqueParts(int m) {
int p[m];
int k = 0;
p[k] = m;
while (true) {
printArr(p, k + 1);
int rem_val = 0;
while (k >= 0 && p[k] == 1) {
rem_val += p[k];
k--;
}
if (k < 0)
return;
p[k]--;
rem_val++;
while (rem_val > p[k]) {
p[k + 1] = p[k];
rem_val = rem_val - p[k];
k++;
}
p[k + 1] = rem_val;
k++;
}
}
int main() {
cout << "All Unique Partitions of 3\n";
printAllUniqueParts(3);
cout << "\nAll Unique Partitions of 4\n";
printAllUniqueParts(4);
cout << "\nAll Unique Partitions of 5\n";
printAllUniqueParts(5);
return 0;
}輸出
All Unique Partitions of 3 3 2 1 1 1 1 All Unique Partitions of 4 4 3 1 2 2 2 1 1 1 1 1 1 All Unique Partitions of 5 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
更新於： 30-7-2019
750 次瀏覽
廣告