Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/25: Рейтинг темы: голосов - 25, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 04.10.2014
Сообщений: 12
1

Перечислить все разбиения натурального числа на натуральные слагаемые

28.10.2014, 22:04. Показов 4802. Ответов 13
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
у меня есть код, но он работает неправильно. Я так понимаю, что где-то надо сделать рекурсию, помогите пожалуйста, разобраться.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
int main() {
    int i, n, k, sum, s;
    int x[1000];
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        x[i] = 1;
    }
    k = n;
    s = k - 1;
    while((x[s] ==1)||(x[s-1]>x[s])) {
        s = s-1;
        x[s] = x[s] + 1;
        sum = 0;
    }
        for (i=s+1; i<k; i++) {
            sum = sum + x[i];
        }
            for (i=1; i<sum-1; i++) {
                x[s+1]= 1;
            }
 
                k= s+sum-1;
 
 
 
    for (i=1; i<n; i++){
        printf("%d", x[i]);
 
    }
    return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.10.2014, 22:04
Ответы с готовыми решениями:

Перечислить все разбиения целого положительного числа на слагаемые
Ребята, в общем хотел обратиться за помощью, сижу ломаю голову, но не могу догадаться как...

Перечислить все разбиения целого положительного числа N на целые положительные слагаемые
Перечислить все разбиения целого положительного числа N на целые положительные слагаемые...

Перечислить все натуральные числа, не превосходящие заданного N
Перечислить все натуральные числа, не превосходящие заданного N, в двоичном представлении которых...

Перечислить все натуральные числа не превосходящие заданного N
Перечислить все натуральные числа не превосходящие заданного N, в двоичном представлении которых...

13
61 / 61 / 24
Регистрация: 28.09.2012
Сообщений: 378
28.10.2014, 22:14 2
daniel33,
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int main() {
    int i=2, n;
    scanf("%d", &n);
    while (n != 1)
    {
        if (!(n%i))
        {
            n /= i;
            printf("%i ", i);
            i = 2;
            continue;
        }
        i++;
    }
    return 0;
}
0
0 / 0 / 0
Регистрация: 04.10.2014
Сообщений: 12
28.10.2014, 22:18  [ТС] 3
код не работает.
у меня задача: вводится число, например, 4. На выходе должно получиться: 1 1 1 1, 1 1 2, 1 3, 2 2, 4
ну или в другом порядке
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
28.10.2014, 23:22 4
kiff20072008, Это вы решаете совсем другую задачу. Факторизации. (Разбиения на делители) И строчка 11 в вашем коде совершенно излишняя.
0
61 / 61 / 24
Регистрация: 28.09.2012
Сообщений: 378
28.10.2014, 23:26 5
Байт, это я уже понял
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
28.10.2014, 23:32 6
Вот что-то в этом роде
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
F(int k, int n)  // Разбиение числа n на к слагаемых
{ int i;
  if (k==1) {
   printf("%d\n", n);
   return;
 }
  for(i=1; i<n-k; i++) {
   printf("%d ", j);
   F(k-1, n-i);
  }
}
main()
{ int i, N;
   // Ввод N
   for(i=N; i>0; i--)
     F(i, N);
}
Состряпал на коленке. Не проверял.
0
0 / 0 / 0
Регистрация: 04.10.2014
Сообщений: 12
28.10.2014, 23:43  [ТС] 7
она зациклена и выдает 2686924, по всей видимости, просто мусор какой-то
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
29.10.2014, 00:03 8
Цитата Сообщение от daniel33 Посмотреть сообщение
она зациклена и выдает 2686924, по всей видимости, просто мусор какой-то
в строчке 8 моя ошибка. Надо
C
1
printf("%d ", i);
Но идея понятна? Пройдись дебагером, поставь отладочные выдачи промежуточных результатов, копайся. Мы все так живем.

Добавлено через 11 минут
Заметил, что прожка моя не хороша. Даже если код соответствует моим мыслям, она должна выдать и 1 1 2 и 2 1 1, что, видимо, не то, что хотелось бы. Надо бы, чтоб выполнялось еще условие не убывания слагаемых. Но тут ты что-то должен сделать и сам.
0
0 / 0 / 0
Регистрация: 04.10.2014
Сообщений: 12
29.10.2014, 11:37  [ТС] 9
программа не работает для 3, то есть выдает 3. Для 4 выдает 1+3 и 4.
для 5: 1+1+3, 1+4, 2+3, 5
то есть нет разбиения на единицы и на 1 + 2
начинается с 3

Добавлено через 23 минуты
я сделал вручную через while для 1 и для 2

Добавлено через 9 минут
до 6 включительно работает верно,начиная с 7 пишет в разбиении, в частности, 2+3, 2+1+3, что является разложением 6
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
30.10.2014, 04:51 10
Лучший ответ Сообщение было отмечено Байт как решение

Решение

Рекурсия - страшная сила. После безуспешных попыток написать хоть что-то на функциональных языках, подобные вещи на С пишутся гораздо легче
C
1
2
3
4
5
6
7
8
9
10
11
12
void find(unsigned int k, unsigned int m, char *p, char *ps)
{
    sprintf(p, "%d\n", k); printf(ps);
    for (unsigned int i=m; i<=k/2; i++) find(k-i, i, p+sprintf(p, "%d+", i), ps);
}
int _tmain(int argc, _TCHAR* argv[]) 
{
    char r[100];
    find(15, 1, r, r);
    system("pause");
    return 0;
}
1
Байт
30.10.2014, 22:36
  #11

Не по теме:

daniel33, _Ivana, Вы меня раздразнили. Завтра поговорим.

0
_Ivana
30.10.2014, 22:45
  #12

Не по теме:

Конечно поговорим :) У меня до завтра чуть больше часа осталось, но я планирую сидеть в инете как обычно до 3 ночи :)

0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
01.11.2014, 00:50 13
Байт, разговор получился кратким - сухое спасибо как признание моего кода Но я предлагаю продолжить общение - например, приглашаю вас в эту мою тему: Победить модификацию Фарроу для оптимизации расчета коэффициентов полинома Смею надеяться, что вам это может показаться интересным
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
01.11.2014, 08:15 14
Цитата Сообщение от _Ivana Посмотреть сообщение
разговор получился кратким
Увы! Я все пытался обойтись без накапливающей вывод строки, но никак не получалось, видимо, не с той лапы стал. По поводу вашего кода -
И все мои попытки упирались в нечто, напоминающее ваш код. Так что я это дело бросил и занялся текущими делами.
0
01.11.2014, 08:15
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.11.2014, 08:15
Помогаю со студенческими работами здесь

Перечислить все натуральные числа, не превосходящие заданного N
Перечислить все натуральные числа, не превосходящие заданного N, в двоичном представлении которых...

Перечислить все натуральные числа, не превосходящие заданного N
Перечислить все натуральные числа, не превосходящие заданного N, в двоичном представлении которых...

Перечислить все натуральные числа, не превосходящие заданного N
Перечислить все натуральные числа, не превосходящие заданного N, в двоичном представлении которых...

Вывести все "интересные" разбиения числа на слагаемые
Недавно на кружке математики Дезидерий узнал о разбиении на слагаемые. Разбивкой числа n на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru