История изменений

Исправление satanic-mechanic, 25.11.13 16:30 (текущая версия) :

Хотя что-то не так, с повторениями вышло меньше, чем без повторений. :-\

Море решение для случая с повторениями (с учетом досадной ошибки использования купюры 1024):

#include <stdio.h>
#include <math.h>

static unsigned long
dec_c(int n)
{
  static unsigned long C[1025];
  int i, j;

  C[0] = 1;

  for (i = 1; i <= n; ++i)
    for (j = 1; j <= i && j <= 512; j <<= 1)
      C[i] += C[i - j];

  return C[n];
}

int
main(int argc, char *argv[])
{
  int n = 1024;
  if (argc > 1)
    n = atoi(argv[1]);

  printf("%lu\n", dec_c(n));

  return 0;
}

Выдает 12183728273700989960, что больше решения без повторений. Закономерно больше.

P.S. На переполнение не проверял.

Исходная версия satanic-mechanic, 25.11.13 16:29:

Море решение для случая с повторениями (с учетом досадной ошибки использования купюры 1024):

#include <stdio.h>
#include <math.h>

static unsigned long
dec_c(int n)
{
  static unsigned long C[1025];
  int i, j;

  C[0] = 1;

  for (i = 1; i <= n; ++i)
    for (j = 1; j <= i && j <= 512; j <<= 1)
      C[i] += C[i - j];

  return C[n];
}

int
main(int argc, char *argv[])
{
  int n = 1024;
  if (argc > 1)
    n = atoi(argv[1]);

  printf("%lu\n", dec_c(n));

  return 0;
}