C语言实现正整数划分计数

#include <stdio.h>

int partition(int n, int m) { if (n == 1 || m == 1) { // 只有1个数或只能选1时，只有一种情况 return 1; } if (n < m) { // n比m小，不能选比n更大的数，退化为n的划分数 return partition(n, n); } if (n == m) { // n等于m，包含只选1的情况 return partition(n, m - 1) + 1; } return partition(n, m - 1) + partition(n - m, m); }

int main() { int n; while (scanf("%d", &n) == 1) { printf("%d\n", partition(n, n)); } return 0; }