Подскажите, как найти количество представлений целого числа в виде суммы целых чисел МЕНЬШЕ 10. Т.е. например 16 = 6+2+8=9+7=4+4+4+4=6+5+5 и т.д. Хотя бы идею

Здравствуйте Xenia, Вы писали:

X>Подскажите, как найти количество представлений целого числа в виде суммы целых чисел МЕНЬШЕ 10. Т.е. например 16 = 6+2+8=9+7=4+4+4+4=6+5+5 и т.д. Хотя бы идею

Если я правильно понял,
то для любого целого A тебе надо найти такие целые числа (ai >= 0) a1, ..., a9,
чтобы выполнялось

a1 * 1 + a2 * 2 + ... + a9 * 9 = A

Смысл этих ai — это сколько раз цифра i учаcтвует в сумме.
(если ai=0 — то не участвует)

Получилось самое обыкновенное линейное уравнение с 9-ю неизвестными.
Методы решения (систем) линейных уравнений известны.
Тебе осталось найти количество решений этого уравнения на множестве целых чисел.

Что в общем пустяки...

В том примере, что ты привела A = 16

одно решение     - a6=1, a2=1 a8=1, остальные ai=0
другое решение   - a9=1, a7=1,      остальные ai=0
ещё одно решение - a6=1, a5=2,      остальные ai=0
и ещё            - a4=4,            остальные ai=0

Здравствуйте Рек, Вы писали:

Рек>a1 * 1 + a2 * 2 + ... + a9 * 9 = A

Рек>Смысл этих ai — это сколько раз цифра i учаcтвует в сумме.
Рек>(если ai=0 — то не участвует)

Круто! Я даже не подумал о таком представлении!

Рек>Получилось самое обыкновенное линейное уравнение с 9-ю неизвестными.
Рек>Методы решения (систем) линейных уравнений известны.
Рек>Тебе осталось найти количество решений этого уравнения на множестве целых чисел.

Вот не знаю, как решать такие уравнения Подскажи, плз

Как развитие метода и способ решения этого уравнения могу предложить следующее:
Ищём, какое максимальное число девяток влезет в наше число: (N div 9) и устанавливаем его в a9. На этом шаге получили остаток (N — a9*9) и пытаемся его записать цифрами от 1 уже до 8. То есть уже выбираем максимальное число восьмёрок... Потом семёрок, и так далее. Вроде получается рекурсия.

Дошли до решения (определили все аi) поднимаемся шагом выше (то есть к выбору а2) и устанавливаем а2 = а2 — 1 и рекурсивно спускаемся дальше.

Так мы обойдём все решения и получим что нужно! Вот...

В продолжение своего ответа с подачи Рек'а привожу код:

#include <deque>
#include <iostream>

using namespace std;

typedef deque < int > ADeque;

int g_counter = 0;

void Print_Buff(ADeque& Buff)
{
    g_counter++;

    int i = 9;
    for(ADeque::iterator it = Buff.begin(); it != Buff.end(); i--, it++)
    {
        if (*it != 0)
            cout << *it << "*" << i << "  + ";
        else
            cout << "       ";
    }
    cout << endl;
};

void Run(int N, int i, ADeque& Buff)
{
    if (1 == i)
    {
        Buff.push_back(N);
        Print_Buff(Buff);
        Buff.pop_back();
        return;
    }
    else if (0 == N)
    {
        Print_Buff(Buff);
        return;
    }
    else if (i > N)
    {
        Buff.push_back(0);
        Run(N, i-1, Buff);
        Buff.pop_back();
        return;
    }
    else
    {
        for(int j = (N/i); j >= 0; j--)
        {
            Buff.push_back(j);
            Run(N - i*j, i-1, Buff);
            Buff.pop_back();
        }
    }
    return;
}

void main()
{
    ADeque Buffer;
    int       N;

    cout << "Input number, please: ";
    cin >> N;

    Run(N, 9, Buffer);

    cout << "Total number of variants is " << g_counter << endl;
}

Только там вывод некрасивый Доработайте, плиз

Здравствуйте Хитрик Денис, Вы писали:

Рек>>Получилось самое обыкновенное линейное уравнение с 9-ю неизвестными.
Рек>>Методы решения (систем) линейных уравнений известны.
Рек>>Тебе осталось найти количество решений этого уравнения на множестве целых чисел.

ХД>Вот не знаю, как решать такие уравнения Подскажи, плз

Например методом Гаусса......
Сама не пробовала, но наш профессор математики утверждал, помнится, что данный метод наиболее легко реализуется программно.
Спасибо за альтернативный совет

Здравствуйте Рек, Вы писали:

Рек>Здравствуйте Xenia, Вы писали:

X>>Подскажите, как найти количество представлений целого числа в виде суммы целых чисел МЕНЬШЕ 10. Т.е. например 16 = 6+2+8=9+7=4+4+4+4=6+5+5 и т.д. Хотя бы идею

Рек>Если я правильно понял,
Рек>то для любого целого A тебе надо найти такие целые числа (ai >= 0) a1, ..., a9,
Рек>чтобы выполнялось

Рек>a1 * 1 + a2 * 2 + ... + a9 * 9 = A

Рек>Смысл этих ai — это сколько раз цифра i учаcтвует в сумме.
Рек>(если ai=0 — то не участвует)

Рек>Получилось самое обыкновенное линейное уравнение с 9-ю неизвестными.
Рек>Методы решения (систем) линейных уравнений известны.
Рек>Тебе осталось найти количество решений этого уравнения на множестве целых чисел.

Рек>Что в общем пустяки...
Спасибо за совет. Вот уж действительно, гениальность в простоте (я серьезно)

Здравствуйте Xenia, Вы писали:

Рек>>>Получилось самое обыкновенное линейное уравнение с 9-ю неизвестными.
Рек>>>Методы решения (систем) линейных уравнений известны.
Рек>>>Тебе осталось найти количество решений этого уравнения на множестве целых чисел.
ХД>>Вот не знаю, как решать такие уравнения Подскажи, плз

X>Например методом Гаусса......
X>Сама не пробовала, но наш профессор математики утверждал, помнится, что данный метод наиболее легко реализуется программно.

Хех! Для систем, имеющих одно решение -- да, всё очень легко и просто. Я имею в виду метод решения системы A*x = b (где A -- матрица NхN, а х и b -- векторы Nх1) приведением матрицы A к диагональному виду.
А у нас задача заведомо имеет не единственное решение, плюс нам же нужно решение в целых числах...

X>Спасибо за альтернативный совет
Спасибо Вам за вопрос! И с праздником наступившей Весны!

Здравствуйте Хитрик Денис, Вы писали:

ХД>Хех! Для систем, имеющих одно решение -- да, всё очень легко и просто. Я имею в виду метод решения системы A*x = b (где A -- матрица NхN, а х и b -- векторы Nх1) приведением матрицы A к диагональному виду.
ХД>А у нас задача заведомо имеет не единственное решение, плюс нам же нужно решение в целых числах...
Во первых, мы вообще о чем говорим? Никакой системы из 9-ти уравнений здесь нет и быть не может, т.к. эти a1 a2 и т.д. будут меняться отуравнения к уравнению. Кроме того система линейных уравнений по теореме Кранекера-Копелли может иметь ОДНО ИЛИ НИ ОДНОГО решения. Вообще, она еще может иметь бесконечное множество решений, которое искать, понятно, смысла нет. Если я не права, поправьте меня, математики.

И с праздником наступившей Весны!
Спасибо за поздравление.

Здравствуйте Xenia, Вы писали:

X>Во первых, мы вообще о чем говорим?
1. Мы про решение уравнения с девятью неизвестными методом Гаусса
Расскажите поподробнее о том, который вы имели в виду, пожалуйста

X>Никакой системы из 9-ти уравнений здесь нет и быть не может
Разумеется. Я привёл описание метода Гаусса, который знаю и см. п.1

Здравствуйте Хитрик Денис, Вы писали:

ХД>Здравствуйте Xenia, Вы писали:

X>>Во первых, мы вообще о чем говорим?
ХД>1. Мы про решение уравнения с девятью неизвестными методом Гаусса
ХД>Расскажите поподробнее о том, который вы имели в виду, пожалуйста

X>>Никакой системы из 9-ти уравнений здесь нет и быть не может
ХД>Разумеется. Я привёл описание метода Гаусса, который знаю и см. п.1
Вот я и говорю, что раз системы уравнений нет, то зачем говорить про метод Гаусса, а если бы система была, то метод Гаусса бы работал

Здравствуйте Xenia, Вы писали:

X>>>Никакой системы из 9-ти уравнений здесь нет и быть не может
ХД>>Разумеется. Я привёл описание метода Гаусса, который знаю и см. п.1
X>Вот я и говорю, что раз системы уравнений нет, то зачем говорить про метод Гаусса, а если бы система была, то метод Гаусса бы работал

Женская логика! Не в обиду

Рек>>>Получилось самое обыкновенное линейное уравнение с 9-ю неизвестными.
Рек>>>Методы решения (систем) линейных уравнений известны.
Рек>>>Тебе осталось найти количество решений этого уравнения на множестве целых чисел.
ХД>>Вот не знаю, как решать такие уравнения Подскажи, плз
X>Например методом Гаусса......

Выше я имел в виду решение уравнения "на множестве целых чисел", а не линейных систем вообще! Потому и не понял, к чему там был метод Гаусса...
Всё, закругляюсь, а то нас с Вами за флейм и переход на личности ещё выгонят

Здравствуйте Хитрик Денис, Вы писали:

ХД>Здравствуйте Xenia, Вы писали:

X>>>>Никакой системы из 9-ти уравнений здесь нет и быть не может
ХД>>>Разумеется. Я привёл описание метода Гаусса, который знаю и см. п.1
X>>Вот я и говорю, что раз системы уравнений нет, то зачем говорить про метод Гаусса, а если бы система была, то метод Гаусса бы работал

ХД>Женская логика! Не в обиду

Рек>>>>Получилось самое обыкновенное линейное уравнение с 9-ю неизвестными.
Рек>>>>Методы решения (систем) линейных уравнений известны.
Рек>>>>Тебе осталось найти количество решений этого уравнения на множестве целых чисел.
ХД>>>Вот не знаю, как решать такие уравнения Подскажи, плз
X>>Например методом Гаусса......

ХД>Выше я имел в виду решение уравнения "на множестве целых чисел", а не линейных систем вообще! Потому и не понял, к чему там был метод Гаусса...
ХД>Всё, закругляюсь, а то нас с Вами за флейм и переход на личности ещё выгонят

Действительно, пора. Спасибо за беседу и спокойной ночи всем.

Здравствуйте Xenia, Вы писали:

X>Подскажите, как найти количество представлений целого числа в виде суммы целых чисел МЕНЬШЕ 10. Т.е. например 16 = 6+2+8=9+7=4+4+4+4=6+5+5 и т.д. Хотя бы идею
Вроде бы даже работает

#include <iostream.h>

void viewsum(int *numbers,int numsym){
    for (int i=0;i<numsym-1;i++){
        cout << numbers[i] << "+";
    }
    cout << numbers[i] << endl;
}

void findsum(int *numbers,int ost,int pos)
{
    for (int i=1;i<10;i++){
        numbers[pos]=i;
        if (ost-i>0){
            findsum(numbers,ost-i,pos+1);
        }
        if (ost-i==0){
            viewsum(numbers,pos+1);
        }
    }
}

void main(void)
{
    int num;
    cin >> num;
    int *numbers=new int[num];
    findsum(numbers,num,0);
    delete [] numbers;
}

Здравствуйте Soulless, Вы писали:

S>Вроде бы даже работает

Не совсем. Например, по-вашему выходит, что варианты 7+9 и 9+7 различны. А это не так...

Здравствуйте Хитрик Денис, Вы писали:

ХД>Здравствуйте Soulless, Вы писали:

S>>Вроде бы даже работает

ХД>Не совсем. Например, по-вашему выходит, что варианты 7+9 и 9+7 различны. А это не так...

Xenia просила, идею, мой алгоритм-это именно идея. Ну если угодно, могу предложить исправленный вариант.

void viewsum(int *numbers,int numsym){
    for (int i=0;i<numsym-1;i++){
        cout << numbers[i] << "+";
    }
    cout << numbers[i] << endl;
}

void findsum(int *numbers,int ost,int pos)
{
    int prev=(pos!=0)?numbers[pos-1]:9;
    for (int i=1;i<=prev;i++){
        numbers[pos]=i;
        if (ost-i>0){
            findsum(numbers,ost-i,pos+1);
        }
        if (ost-i==0){
            viewsum(numbers,pos+1);
        }
    }
}

void main(void)
{
    int num;
    cin >> num;
    int *numbers=new int[num];
    findsum(numbers,num,0);
    delete [] numbers;
}

Изменены 2 первые строки в findsum. Ну теперь, вроде, совсем то, что надо. Ну как? или

Здравствуйте Soulless, Вы писали:

S>Здравствуйте Хитрик Денис, Вы писали:

ХД>>Здравствуйте Soulless, Вы писали:

S>>>Вроде бы даже работает

ХД>>Не совсем. Например, по-вашему выходит, что варианты 7+9 и 9+7 различны. А это не так...

На самом деле как раз и нужно было, чтобы 7+9 и 9+7 считались различными вариантами.

Здравствуйте Soulless, Вы писали:

S>Xenia просила, идею, мой алгоритм-это именно идея. Ну если угодно, могу предложить исправленный вариант.

code skipped

S>Изменены 2 первые строки в findsum. Ну теперь, вроде, совсем то, что надо. Ну как? или

Гм, оказывается и в первый раз было

Здравствуйте Xenia, Вы писали:

X>На самом деле как раз и нужно было, чтобы 7+9 и 9+7 считались различными вариантами.

Тогда у меня неверно...

Здравствуйте Xenia, Вы писали:

ХД>>>Не совсем. Например, по-вашему выходит, что варианты 7+9 и 9+7 различны. А это не так...

X>На самом деле как раз и нужно было, чтобы 7+9 и 9+7 считались различными вариантами.

Очень странно. Без этого условия эта задача выглятит как классическая задача дискретного анализа на размен рубля монетами определенного достоинства. В общем-то, я и не вижу никакого смысла считать такие варианты различными (это попросту противоречит ассоциативности операции +).

Если интересно, то упомянутая мною задача решается через рекурсивные соотношения. Примерно так:
Пусть N(i,S) — число способов разложить S в сумму чисел, не больших i. Нас будет интересовать
N(9,S).
Для N(i,S) можно написать простое рекурсивное соотношение:
N(i,S)=N(i-1,S)+N(i,S-i) (разложение S без числа i и разложение S с числом i).
В качестве начальных условий берем: N(1,S)=1, для любых S>0 N(i,S)=0, если S<1.
Решение задачи получается за i проходов (вычислние i таблиц N(i,S)).