Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Just_Guest
0 / 0 / 0
Регистрация: 09.03.2019
Сообщений: 1
1

Задачка на рекурсию (студент 1 курса)

09.03.2019, 21:19. Просмотров 230. Ответов 4

Задание на рекурсию. Язык программирования - СИ.

Между цифрами от 1 до 9 расставить знаки операций +, -, *, / так, чтобы получилось заданное число.

Напишите функцию, которая решает данное задание через рекурсию. Задача может быть решена не для всех цифр (если очень сложно). Можно немного упростить задачу и вывести лишь строку со знаками.

Бьюсь над задачкой уже много времени. Решил попытаться перебором сделать, т.е. функция вызывает внутри себя ещё 4 таких же, но знак операции (+, -. *. /) определяется ещё в параметре. Так как всего 9 цифр, то в итоге максимум 9^4 = 65619 вариантов, но 9 уровней вложенности. Помогите, пожалуйста.

Примечание: Знаки должны стоят между всеми цифрами.


(вот мой говнокод, ничего не решающий пока что, я не знаю, как реализовать приоритетность:
например 2 + 3 * 4 - 5... Каким образом можно сравнить умноженное число со следующим в рекурсии?
Да, я задаю очень дибильные вопросы, но я просто вообще не представляю, как решать. Помогите.)

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#define COUNT_DIGITS 3
 
int IsExit = 0;
void setOperations(int number, int digit, int sum, char operation)
{
    if (IsExit)
    {
        printf("%c ", operation);
        return;
    }
    if (digit >= COUNT_DIGITS)
    {
        if (sum == number && digit == COUNT_DIGITS)
        {
            printf("%c ", operation);
            IsExit = 1;
        }
        return;
    }
 
    int thisDigit = digit + 1;
    setOperations(number, thisDigit, sum+thisDigit, '+');
    if (IsExit)
    {
        printf("%c ", operation);
        return;
    }
    setOperations(number, thisDigit, sum-thisDigit, '-');
    if (IsExit)
    {
        printf("%c ", operation);
        return;
    }
    setOperations(number, thisDigit, sum*thisDigit, '*');
    if (IsExit)
    {
        printf("%c ", operation);
        return;
    }
    setOperations(number, thisDigit, sum/thisDigit, '/');
    if (IsExit)
    {
        printf("%c ", operation);
        return;
    }
    if (sum == number && digit == COUNT_DIGITS)
    {
        printf("%c ", operation);
        return;
    }
}   
 
void main()
{
    int number = 0;
    printf("Enter the number: ");
    //scanf("%d", &number);
    number = 0;
    setOperations(number, 1, 1, "");
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.03.2019, 21:19
Ответы с готовыми решениями:

Ужасная задачка для второго курса
Здравствуйте, уважаемые! Дело в том, что мы только стали изучать язык СИ и сразу же такая задача....

студент поступает в универ. У него уникальное ID, имя. Студент может переходить с курса на курс.
Я недавно начал изучать Java. Не все пока получается. Помогите с кодом для задачки студент...

Студент 1 курса
Учусь в техническом вузе, 1 курс, С/C++. Компании берут студентов 1 курсов на лето на стажировку...

Запись Студент - Определить список студентов заданного курса
Структура элемента массива студент: фамилия, имя, отчество, пол, возраст, № курса. Определить:...

Java. Студент 3 курса ищет стажировку на лето, желательно с последующий трудоустройством
Учусь по специальности &quot;Компьютерная математика и программирование&quot;. Хочу найти стажировку на...

4
easybudda
Модератор
Эксперт JavaЭксперт CЭксперт С++
10297 / 6179 / 1555
Регистрация: 25.07.2009
Сообщений: 11,762
10.03.2019, 03:35 2
Обязательно использовать все 9 цифр?
0
CoderPC
239 / 159 / 74
Регистрация: 12.02.2019
Сообщений: 521
10.03.2019, 07:36 3
если цифры местами не менять
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void calc(int *a,int n,int r)
{
    int i,sz,b[17];
    int s[]={'+','-','*','/'};
    if(n<8)
        for(i=0; i<4; i++)
        {
            a[n*2+1]=i;
            calc(a,n+1,r);
        }
    else
    {
        sz=17;
        memmove(b,a,sz*sizeof(int));
        for(i=1; i<sz; i+=2)
            if(b[i]>1)
            {
                b[i-1]=b[i]==2?b[i-1]*b[i+1]:b[i-1]/b[i+1];
                sz-=2;
                memmove(b+i,b+i+2,(sz-i)*sizeof(int));
                i-=2;
            }
        while(sz>1)
        {
            *b=b[1]?*b-b[2]:*b+b[2];
            sz-=2;
            memmove(b+1,b+3,(sz-1)*sizeof(int));
        }
        if(*b==r)
        {
            for(i=0; i<17; i++)
                if(i%2) printf("%c",s[a[i]]);
                else printf("%d",a[i]);
            printf("=%d\n",r);
        }
    }
}
int main(int argc , char * argv[])
{
    int i,a[17];
    for(i=0; i<17; i+=2)
        a[i]=i/2+1;
    calc(a,0,1673);
    system("pause");
    return 0;
}
1
Catstail
Модератор
24392 / 12331 / 2241
Регистрация: 12.02.2012
Сообщений: 20,036
10.03.2019, 12:34 4
А приоритет операций учитывать?
0
Байт
Эксперт C
20451 / 12981 / 2728
Регистрация: 24.12.2010
Сообщений: 27,163
11.03.2019, 15:49 5
Если я правильно понял задачу, то перебор можно устроить так. Есть 8 мест, куда можно что-то поставить и 5 претендентов - 4 знака операции и "ничто" Итого получается 58 = 309625 вариантов. Число посильное.
Не знаю совпадает ли этот подход с кодом уважаемого CoderPC, просто не смотрел.
А вот откуда ТС взял 9^4 = 65619 - непонятно. Хотя я мог задачу понять неправильно

Добавлено через 2 минуты

Не по теме:

Цитата Сообщение от Just_Guest Посмотреть сообщение
Да, я задаю очень дебильные вопросы,
Не волнуйтесь. Не самые дебильные. Нормальные вопросы.:)

0
11.03.2019, 15:49
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.03.2019, 15:49

Задачка на рекурсию...
в общем нужно сделать прогу чтоб выводила дерево файлов и папок указанной директории.... Сделать...

Задачка на рекурсию
Всем доброго времени суток! Нужна помощь в написании функции на рекурсию. Нужно подсчитать...

Занесите в отдельный файл записи из файла Студент о студентах 5-го курса, упорядочив их по убыванию сумм балло
Помогите пожалуйста Создайте файл Студент. Занесите в отдельный файл записи из файла Студент о...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru