自然数の分割 in C DouKaku?

自然数nとm(n>=m>0)が与えられたとき，nをm個の非負の整数の和で表すやり方を全て出力してください．
その際，和の組(x_1, ..., x_m)は大きい順に出力してください．
ここでm = 3の時の「(a, b, c)が(A, B, C)より大きい」とは
(a > A)
(a == A) かつ (b > B)
(a == A) かつ (b == B) かつ (c > C)
のいずれかが成り立つとき(つまりは辞書的順序)とします．

例:n = 5, m = 3が与えられたときは
5, 0, 0,
4, 1, 0,
4, 0, 1,
3, 2, 0,
3, 1, 1,
...
0, 1, 4,
0, 0, 5,
を出力する．

再帰で

#include <stdio.h>

void partNum(char *s, int n, int m) {
    if (m == 1) {
        printf("%s%d\n", s, n);
    } else if (m > 1) {
        int i;
        char *p;
        p = s + strlen(s);
        for (i = 0; i <= n; i++) {
            sprintf(p, "%d, ", n - i);
            partNum(s, i, m - 1);
        }
    }
}

int main(void) {
    char s[256] = "";
    
    partNum(s, 5, 3);
    return 0;
}

直前に出力した組から次の組が計算できそうだな……と思ってやってみました。なんとなく C で。

#include <stdio.h>
#include <malloc.h>

int step (int n, int m, int *p) {
  int i = m - 1, x;

  /* [0, ..., 0, n] だったら終わり */
  if (p[i] == n) return 0;

  /* [..., a+1, 0, ..., 0, x] -> [..., a, x+1, 0, ..., 0] */
  x = p[i], p[i] = 0;
  while (p[--i] == 0);
  p[i]--, p[i+1] = x + 1;

  return 1;
}

int main (int argc, char *argv[]) {
  int m, n, i, *p;

  n = argc==3 ? atoi(argv[1]) : 5;
  m = argc==3 ? atoi(argv[2]) : 3;
  p = (int *)malloc(sizeof(int) * m);

  for (p[0] = n, i = 1; i < m; ++i) p[i] = 0; /* 最初は [n, 0, ..., 0] */

  do {
    for (i = 0; i < m; ++i) printf("%d, ", p[i]);
    putchar('\n');
  } while (step(n, m, p));

  free(p);
  return 0;
}

DouKaku?

自然数の分割

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq