Как решить задачу на c?

Question

[iayjull]

int main()
{
    int x, i;
    scanf("%d", &x);
    int a[0]*x;
    for (i = 1; i = x; i++)
        if i+1<=x: a[i+1]+=a[i];
        if i*2<=x: a[i*2]+=a[i];
        if i*3<=x: a[i*3]+=a[i];
    printf("%d\n", a[x]);
}

решала такие задачи на питоне, но не знаю, как правильно перенести на синтаксис с

Comments

[RabraBabr]

Элементарная задачка на комбинаторику. Надо подсчитать все варианты. Так как n ограничено 30 можно использовать рекурсию (шансы скрашить стэк минимальны). Если предположить, что int у нас 4 байтовый, то выглядеть это будет как то так.

#include <stdio.h>

typedef enum { false, true } bool;
const int MIN_X=1;
const int MAX_X=30;

int n=MIN_X+1;
int path_num=0;

void path_counter(int current_x)
{
    if (current_x<n)
    {
        path_counter(current_x+1);
        path_counter(current_x+2);
        path_counter(current_x+3);
    }else
    if (current_x==n)
    {
        path_num++;
    }
};

int main()
{
    int x=MIN_X;
    
    bool done=false;
    while (!done)
    {
        scanf("%d", &n);
        if ((n>MIN_X)&&(n<=MAX_X))done=true;
        else printf("%s\n", "error: out of range");
    }
    
    path_counter(x);
    
    printf("%d\n", path_num);

    return 0;
}

По времени правда не знаю пройдет или нет.

Answer 1

[GavriKos]

Ну если выше ваша попытка перенести на си, то:

if i+1<=x:

это так не работает, условие должно быть в круглых скобках (if это оператор), двоеточие не нужно:
if (i+1<=x)

int a[0]*x;

Вот это я вообще не понял и 99% что это не будет работать. Просто почитайте в гугле как в си инициализировать массив переменной длины.

И да - в тегах c++, в вопросе c - вы определитесь

P.S. Логику не проверял вообще, чисто синтаксис. Кстати в цикле тоже ошибка - и тоже просто советую загуглить цикл for

Answer 2

[mayton2019]

Задача похожа на knapsack problem. Ее можно переформулировать как укладка вещей в рюкзаке с полным заполнением и с сохранением порядка вещей. Или еще как поиск всех сумм целых чисел 1,2,3 равных в сумме n.

Если представить тернарное дерево где childs - это соотвественно длины прыжков (веса) - тогда задача сводится к генерации всех возможных путей в тернарном дереве где длина пути равна n. У этого дерева будет много лишних ветвей которые можно сразу отбросить на этапе обхода если частичная сумма уже больше чем n.

Вобщем DFS.