1

Нужно подсчитать количество разложений числа на не повторяющиеся слагаемые, то есть для числа 5 количество таких разложений 3: 1+4, 2+3, 5+0. Сами разложения генерировать не нужно, использовать рекурсию запретили. Делала так:

#include <iostream>
#include <conio.h>

using namespace std;

int main(){
    int n;
    cin >> n;

    int a[n][n];
    int i, j, k;
    a[0][0] = 1;

    for (i = 0; i < n; i++)
    for (j = i; j < n; j++)
    if (i == j) (a[i][j] = 1);
       else  a[i][j] = 0;

    for (i = 1; i < n; i++) 
    a[i][0] = 0;

    for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
    a[i][j] = a[i][j - 1] + a[i - j][j - 1];

    cout << "\n";
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++)
        cout << a[i][j] << ' ';
    cout << "\n"    ;
}

    getch();
    return 0;
}

Но формула, судя по всему, не верная, потому что он не находит некоторых разложений: для 3 например, не считает 1+2, а для 5 2+3. За помощь буду очень благодарна.

7
  • укажите источник на вашу формулу. пока видно только выход за границы при j=0 в a[i][j-1] и a[i-j][j-1] - будет что попало. Commented 27 янв. 2014 в 12:39
  • Нужны разложения ровно на 2 слагаемых или на любое возможное количество, например 6 = 1+2+3 учитывается или только 6 = 6+0 = 5+1 = 4+2? UPD: уже увидел ниже, все комбинации надо.
    – paulgri
    Commented 27 янв. 2014 в 14:13
  • @Yura Ivanov, формулу пыталась вывести сама, по-видимому, неудачно
    – akisha
    Commented 27 янв. 2014 в 15:11
  • @akisha, судя по всему формулу надо брать такую Q(n,k) = P(n-C(k,2),k), где P вычисляется по похожей на вашу формуле, P(n,k)=P(n-1,k-1)+P(n-k,k), а C(k,2) - биномиальные коэффициенты. Вполне возможно, что эта формула также сворачивается в формулу на подобии вашей, но я такую не нашел (поэтому про источник и спрашивал)... Commented 27 янв. 2014 в 15:23
  • @Yura Ivanov, как искать эти биномиальные коэффициенты? Если честно, мало чего поняла из этих формул
    – akisha
    Commented 27 янв. 2014 в 15:53

6 ответов 6

1

@akisha, модифицировал ваш алгоритм. Если функция та самая (ну может у кого-то сомнения остались), то будет так:

int b[n][n];
...
for (i = 1; i < n; i++)
    for (j = 1; j <= i; j++){
        a[i][j] = a[i-1][j-1] + a[i-j][j];  // P(n,k) == a[i][j]
        ck2=j*(j-1)/2;                      // C(k,2) 
        ck2=i-ck2;                          // param for Q(n,k) == P(n-C(k,2),k)
        if(ck2>=0 && ck2<n){
            b[i][j]=a[ck2][j];              // Q(n,k) for positive 
                                            // and less than n integers
        } else {
            b[i][j]=0;                      // Q(n,k) otherwise
        }
    }
...

http://ideone.com/sDHp66

1

Оно, конечно, дорога ложка к обеду, но раз уж попалось на глаза...

Это количество описывается в OEIS как последовательность #9, рекурсивно решается вообще в полпинка -

int S(int n, int m = 1)
{
    if (n == 0) return 1;
    if (n < m)  return 0;
    if (n == m) return n%2;

    int sum = 0;
    for(int k = m; k <= n/2; ++k)
        sum += (k%2)*S(n-k,k);
    return sum + n%2;
}

Ну, а с запрещенной рекурсией - предвычислением массива (применение подхода динамического программирования):

const int N = 100;

int s[N][N];

void makeS()
{
    for(int k = 0; k < N; ++k) s[0][k] = 1;
    for(int k = 0; k < N; ++k) s[k][k] = k%2;
    for(int n = 1; n < N; ++n)
        for(int m = 0; m < N; ++m)
        {
            int sum = 0;
            for(int k = m; k <= n/2; ++k)
                sum += (k%2)*s[n-k][k];
            s[n][m] = sum + n%2;
        }
}


int S(int n, int m = 1)
{
    if (n == 0) return 1;
    if (n < m)  return 0;
    if (n == m) return n%2;

    int sum = 0;
    for(int k = m; k <= n/2; ++k)
        sum += (k%2)*S(n-k,k);
    return sum + n%2;
}

int main(int argc, const char * argv[])
{
    makeS();
    for(int n = 1; n < 20; ++n)
        cout << setw(2) << n << ":  "
            << setw(10) << S(n,1) << "   "
            << setw(10) << s[n][1] << endl;
}
0

Может так?

#include <iostream>
#include <stack>
#include <utility>
using namespace std;
int main() {
    int n, count = 0;
    cin >> n;
    stack<pair<int, int> > st;
    st.push(make_pair(1, 1));
    while(!st.empty()) {
        if(st.top().first < n) {
            int i = st.top().second;
            st.push(make_pair(st.top().first+i+1, i+1));
        } else {
            if(st.top().first == n) {
                count ++;
            }
            st.pop();
            if(!st.empty()) {
                st.top().first++;
                st.top().second++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

Если нужны сами комбинации, то придётся хитрить, поскольку stack в stl не позволяет заглядывать внутрь:

#include <iostream>
#include <stack>
#include <utility>
using namespace std;
int main() {
    int n;
    cin >> n;
    stack<pair<int, int> > st;
    st.push(make_pair(1, 1));
    while(!st.empty()) {
        if(st.top().first < n) {
            int i = st.top().second;
            st.push(make_pair(st.top().first+i+1, i+1));
        } else {
            if(st.top().first == n) {
                // печатать
                stack<pair<int, int> > st1;
                while(!st.empty()) {
                    st1.push(st.top());
                    st.pop();
                }
                while(!st1.empty()) {
                    cout << st1.top().second << ' ';
                    st.push(st1.top());
                    st1.pop();
                }
                cout << endl;
            }
            st.pop();
            if(!st.empty()) {
                st.top().first++;
                st.top().second++;
            }
        }
    }
    return 0;
}
2
  • @alexlz, так эти комбинации же могут быть не только из двух чисел, например, для 6: 1+5, 2+4, 1+2+3, 6+0
    – akisha
    Commented 27 янв. 2014 в 12:01
  • @akisha ./a.out 6 4 не понял проблемы
    – alexlz
    Commented 28 янв. 2014 в 0:35
0

Может, что-то вроде такого алгоритма:

  1. Получаем число и загоняем в массив все значения от 1 до полученного числа - 1, то есть для 6 - 5,4,3,2,1.
  2. Далее делаем цикл, который суммирует эти значения сначала в виде двух слагаемых, потом 3х\4х\итд и сравниваем сумму с полученным числом. Если сумма совпадает с числом, то увеличиваем счётчик разбиений на 1 (так как любое число представляется в виде число + 0, то счётчик разбиений изначально должен быть равен 1).

Конечно, этот цикл будет выполнять кучу ненужных проходов по массиву, но ничего умнее в голову не приходит :-)

4
  • @Agressorr, Я так уже делала, преподаватель забраковал, сказал, что слишком долго и сказал придумать формулу
    – akisha
    Commented 27 янв. 2014 в 13:39
  • С формулой все просто, если слагаемых ровно 2, тогда целая_часть((n+1)/2)
    – paulgri
    Commented 27 янв. 2014 в 14:33
  • @paulgri, слагаемых может быть сколько угодно, главное, чтобы они не повторялись
    – akisha
    Commented 27 янв. 2014 в 15:15
  • @akisha, не формулу, но простой алгоритм предложил в ответе
    – paulgri
    Commented 27 янв. 2014 в 16:27
0

Мой вариант (Выводит промежуточные результаты, что бы было удобнее проверять). Формула:

R(x) = СУММ(R(i)), (i = 0 .. x / 2) для нечетных
R(x) = СУММ(R(i)) - 1, (i = 0 .. x / 2) для четных

Запустить на Ideone

0

Тогда так:

#include <iostream>
#include <conio.h>

using namespace std;

int main()
{
  int n;
  cout << "Enter number: ";
  cin >> n;
  int * a = new int[n / 2 + 1];
  // корректно было бы выразить N (размер массива) из отношения N*(N-1)/2 = n,
  // а приведено упрощенное, оно не меньше
  if (!a)
    return 1;

  int count = 0;
  a[0] = 1;
  for (int i = 0, sum = 0; i >= 0; a[i]++)
  {
    if (sum + a[i] < n)
      sum += a[i], i++, a[i] = a[i-1]; // PUSH
    else
    {
      if (sum + a[i] == n)
        count++; // здесь можно напечатать слагаемые a[0]..a[i]
      sum -= a[--i]; // POP, если (sum + a[i] >= n)
    }
  }  
  cout << "Count of sums: " << count << endl;

  getch();
  return 0;
}

Вывод каждой комбинации можно сделать так: вместо строки count++; будет

      {
        count++; // печатаем слагаемые a[0]..a[i]
        for (int j = 0; j <= i; j++)
          cout << a[j] << (j == i ? '\n' : ' ');
      }

Массив 'a' является стеком, 'i' указывает на вершину стека.

Комбинации, в которых присутствует 0 в явном виде, особого смысла не имеют и специально не учитываются, т.к. 2+4 = 0+2+4, поэтому 6+0 это просто 6.

UPD: конечно, можете переписать и на stack<int>, если преподаватель не против ;)

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.