练习题 - 数字拆分(数理逻辑)

前言

时隔差不多一个周之后的续更。这段时间更新的比较稀疏,主要有两方面的原因:其一是临近毕业,诸如找房之类的事情比较需要费心;其二是写了一段时间以后,以前的算法练习存货已经不多。

题目

问题描述

一般而言,一个正整数可以写成比其小的几个正整数的和。现要求通过程序实现,讲一个正整数拆分为其他多个正整数的和的形式,并输出所有可能拆分。

输入示例

6

输出示例

6=1+1+1+1+1+1
6=1+1+1+1+2
6=1+1+1+3
6=1+1+2+2
6=1+1+4
6=1+2+3
6=1+5
6=2+2+2
6=2+4
6=3+3

解答

具体代码实现如下。

#include <stdio.h>

int n, answer[100], zuo = 1, total;

void caifen(int k, int min) {
  int mid = k / 2, i, j;
  for (i = min; i <= mid; i++) {
    answer[zuo++] = i;
    if (k - i > i)
      caifen(k - i, i);
    zuo--;

    printf("%d=", n);
    for (j = 1; j <= zuo; j++)
      printf("%d+", answer[j]);
    printf("%d", k - i);
    printf("\n");
  }
}

int main() {
  scanf("%d", &n);
  caifen(n, 1);
  system("pause");

  return 0;
}

以上算法为数据结构中队列的一个运用,也采用了递归的思想进行求解。


* cached version, generated at 2018-12-06 03:11:28 UTC.

Subscribe by RSS