Форум программистов, компьютерный форум CyberForum.ru

рекурсия на расставление знаков между числами - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.73
вандал
126 / 126 / 1
Регистрация: 20.11.2009
Сообщений: 498
20.11.2009, 19:21     рекурсия на расставление знаков между числами #1
Прошу вас помочь мне с рекурсией.
Для заданного набора целых чисел без знака расставить между ними знаки сложения, вычитания и умножения так, чтобы результат полученного арифметического выражения был как можно ближе к заданному числу. Число знаков умножения в этом выражении должно быть равным или на одно меньше чем знаков сложения, а знаков сложения - не менее чем на один больше чем знаков вычитания. В наборе должно быть не менее пяти чисел а в полученном арифметическом выражении должны присутствовать все три арифметических знака.
Помогите хотябы с идеей потому что все мои идеи упирались в тупик.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2009, 19:21     рекурсия на расставление знаков между числами
Посмотрите здесь:

C++ Классы для арифметических операций с большими числами (целые числа более 10 знаков)
C++ Массив, нахождене разности между двумя числами
В списке целых чисел подсчитать количество переменных знаков. Вывести между какими элементами C++
C++ Массив отсортировать по возрастанию,находящегося между 2 введенными числами
Как взять разность по модулю между двумя числами int? C++
C++ Вывод всех чисел, находящихся между двумя заданными числами
Количество цифр между числами C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
manfeese
 Аватар для manfeese
128 / 127 / 16
Регистрация: 04.01.2009
Сообщений: 415
20.11.2009, 19:29     рекурсия на расставление знаков между числами #2
Пример приведи!!!

Добавлено через 1 минуту
Цитата Сообщение от вандал Посмотреть сообщение
чтобы результат полученного арифметического выражения был как можно ближе к заданному числу
Какому именно числу, речь ведь идет о
Цитата Сообщение от вандал Посмотреть сообщение
набора целых чисел без знака
вандал
126 / 126 / 1
Регистрация: 20.11.2009
Сообщений: 498
20.11.2009, 19:50  [ТС]     рекурсия на расставление знаков между числами #3
например даны числа 1 2 3 4 5 расставить между ними знаки + - * таким образом чтобы полученное выражение было как можно ближе например к числу 10
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
20.11.2009, 19:58     рекурсия на расставление знаков между числами #4
хорошая задачка, контрольная?
над такой можно и подумать

числа произвольные положительные? у тебя просто попорядку выстроены, это случайно?
вандал
126 / 126 / 1
Регистрация: 20.11.2009
Сообщений: 498
20.11.2009, 20:00  [ТС]     рекурсия на расставление знаков между числами #5
Цитата Сообщение от TanT Посмотреть сообщение
хорошая задачка, контрольная?
над такой можно и подумать

числа произвольные положительные? у тебя просто попорядку выстроены, это случайно?
случайно получилось) нет не контрольная просто на рекурсию мне сложная досталась)
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
20.11.2009, 21:11     рекурсия на расставление знаков между числами #6
можно решить перебрав все варианты, отсеив лишнее, но там рекурсия не причём вообще будет. да и прога не фига не простая выйдет. где-то реально подвох.
тебе препод не говорил куда рекурсию прикручивать?
manfeese
 Аватар для manfeese
128 / 127 / 16
Регистрация: 04.01.2009
Сообщений: 415
20.11.2009, 21:22     рекурсия на расставление знаков между числами #7
Цитата Сообщение от вандал Посмотреть сообщение
например даны числа 1 2 3 4 5 расставить между ними знаки + - * таким образом чтобы полученное выражение было как можно ближе например к числу 10
Так я понимаю, что число 10 тоже задается отдельно???

Добавлено через 1 минуту
Цитата Сообщение от вандал Посмотреть сообщение
а знаков сложения - не менее чем на один больше чем знаков вычитания
Уточни это выражение, а то некорректно записано!!!
вандал
126 / 126 / 1
Регистрация: 20.11.2009
Сообщений: 498
20.11.2009, 21:35  [ТС]     рекурсия на расставление знаков между числами #8
Цитата Сообщение от TanT Посмотреть сообщение
можно решить перебрав все варианты, отсеив лишнее, но там рекурсия не причём вообще будет. да и прога не фига не простая выйдет. где-то реально подвох.
тебе препод не говорил куда рекурсию прикручивать?
я пытался сделать эту прогу для пяти чисел так:
записал в двусвязный список + - и *
и как бы за счет того что знаков всегда больше чем три возвращался вначало списка и выводил опять плюс в выражение получалось так: 1+2-3*4+5
записывал результат менял в списке первый и следующий элемент и вызывал рекурсию и т.д.

Добавлено через 7 минут
Цитата Сообщение от manfeese Посмотреть сообщение
Так я понимаю, что число 10 тоже задается отдельно???

Добавлено через 1 минуту
Уточни это выражение, а то некорректно записано!!!
да число 10 задается отдельно
кол-во умножений в полученном выражении на один меньше или равно кол-ву плюсов т.е. например
1+2-3*4+5 здесь плюсов 2 а умножений 1 значит условие выполняется а если например
1+2+3*4+5 то условие не выполняется т.к. плюсов на два больше чем умножений
тоже самое и для другого условия
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.11.2009, 15:20     рекурсия на расставление знаков между числами #9
Вот вариант (и даже с рекурсией):
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream.h>
#include <math.h>
#include <windows.h>
bool prov_znak(int *temp_znak, int n)
{
    int kol_1=0, kol_2=0, kol_3=0;
    for(int i=0; i<n; i++)
    {
        if(temp_znak[i]==1 && i!=0)
            kol_1++;
        if(temp_znak[i]==2)
            kol_2++;
        if(temp_znak[i]==3)
            kol_3++;
    }
    if((kol_1-kol_3==0 || kol_1-kol_3==1) && kol_1>kol_2 && kol_1!=0 && kol_2!=0 && kol_3!=0)
        return true;
    else
        return false;
}
 
int znach_vir(int *temp_znak, int *mas, int n)
{
    int temp, rez=0;
    if(temp_znak[0]==2)
        rez=-1*mas[0];
    else
        rez=mas[0];
    for(int i=1; i<n; i++)
    {
        temp=0;
        if(temp_znak[i]==1 && temp_znak[i+1]!=3)
            rez+=mas[i];
        if(temp_znak[i]==2 && temp_znak[i+1]!=3)
            rez-=mas[i];
        if(i==1 && temp_znak[1]==3)
            while(temp_znak[i]==3)
            {
                rez*=mas[i];
                i++;
            }
        if(temp_znak[i+1]==3)
        {
            temp=mas[i];
            if(temp_znak[i]==2)
                temp*=-1;
            while(temp_znak[i+1]==3)
            {
                temp*=mas[i+1];
                i++;
            }
        }
        rez+=temp;      
    }
    return rez;
}
 
void rec_funk(int *mas, int *znak, int *temp_znak , int n, int rez)
{
    int i;
    do
    {
        temp_znak[n-1]++;
        for(i=n-1; i>=0; i--)
            if(temp_znak[i]>3)
            {
                temp_znak[i]=1;
                temp_znak[i-1]+=1;
            }
    }while(!prov_znak(temp_znak, n));
    if(temp_znak[0]!=3)
    {
    if(fabs(znach_vir(temp_znak, mas, n)-rez) < fabs(znach_vir(znak, mas, n)-rez))
        for(i=0; i<n; i++)
            znak[i]=temp_znak[i];
    rec_funk(mas, znak, temp_znak, n, rez);
    }
    
}
 
int main()
{
    int *mas, *znak, *temp_znak , i, n, rez;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout<<"Ââåäèòå êîëè÷åñòâî Г·ГЁГ±ГҐГ« ГЁГ§ Г*Г*áîðГ*"<<endl;
    cin>>n;
    mas=new int[n];
    znak=new int [n];
    temp_znak=new int[n];
    cout<<"Ââåäèòå Г·ГЁГ±Г«Г* Г*Г*áîðГ*"<<endl;
    for(i=0; i<n; i++)
    {
        cout<<i+1<<" ÷èñëî =";
        cin>>mas[i];
        temp_znak[i]=1;
    }
    cout<<"Ââåäèòå Г§Г*Г¤Г*Г*Г*îå ÷èñëî (ðåçóëüòГ*ГІ âûðГ*æåГ*ГЁГї ГЄ êîòîðîìó äîëæåГ* ñòðåìèòüñÿ)"<<endl;
    cin>>rez;
    while(!prov_znak(temp_znak, n))
    {
        temp_znak[n-1]++;
        for(i=n-1; i>=0; i--)
            if(temp_znak[i]>3)
            {
                temp_znak[i]=1;
                temp_znak[i-1]+=1;
            }
    }
    for(i=0; i<n; i++)
        znak[i]=temp_znak[i];
    rec_funk(mas, znak, temp_znak , n, rez);
    for(i=0; i<n; i++)
    {
        if(znak[i]==1)
            cout<<'+';
        if(znak[i]==2)
            cout<<'-';
        if(znak[i]==3)
            cout<<'*';
        cout<<mas[i];
    }
    cout<<endl;
return 0;
}
вандал
126 / 126 / 1
Регистрация: 20.11.2009
Сообщений: 498
21.11.2009, 16:38  [ТС]     рекурсия на расставление знаков между числами #10
Спасибо большое за лабу
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.11.2009, 13:46     рекурсия на расставление знаков между числами
Еще ссылки по теме:

C++ Определить количество вхождений строки из n знаков в строку из k знаков
C++ Знак табуляции между числами
C++ Найти количество различных пар между числами по признаку
Найти разность между неотрицательными числами А и В C++
C++ Символ между двумя числами в scanf

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

Или воспользуйтесь поиском по форуму:
manfeese
 Аватар для manfeese
128 / 127 / 16
Регистрация: 04.01.2009
Сообщений: 415
23.11.2009, 13:46     рекурсия на расставление знаков между числами #11
Упс, опоздал немного, походу прогу уже решили, но все же вот мой вариант и тоже с рекурсией!
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream.h>
#include <math.h>
#include <conio.h>
 
void swap(unsigned a,unsigned b) {a^=a, b^=b, a^=a;}
 
int GetSum(unsigned Xx[],char Yy[],unsigned A_Size)
{
    int SSum=Xx[0];
    for (int i = 1; i < A_Size; i++)
    {
     if (Yy[i]=='*')
     {
      int j = i+1;
      int Pr=Xx[j-1]*Xx[j];
      while (Yy[j]=='*') Pr*=Xx[j],j++;
 
      if (Yy[i-1]=='+') SSum+=Pr;
      else if (Yy[i-1]=='-') SSum-=Pr;
      else if (Yy[i-1]=='*') SSum*=Pr;
      i=j;
     }
     else
        {
        if (Yy[i-1]=='+') SSum+=Xx[i];
        else if (Yy[i-1]=='-') SSum-=Xx[i];
        else if (Yy[i-1]=='*') SSum*=Xx[i];
        }
    }
    return SSum;
}
 
void Generate(unsigned X[],char Y[],char Z[],unsigned A_Size,int Num, unsigned &Min,int k=0)
 {
   if ( k==A_Size-1 )
   {
    int Sum = GetSum(X,Y,A_Size);
 
    if (abs(Num-Sum) < Min)
    {
     Min = abs(Num-Sum);
     for (int i = 0; i < A_Size; i++) Z[i]=Y[i];
    }
   }
   else
   for (int j=k; j < A_Size-1; j++)
   {
    if (j!=k && Y[j]==Y[k]) continue;
    swap(Y[j],Y[k]);
    Generate(X,Y,Z,A_Size,Num,Min,k+1);
    swap(Y[j],Y[k]);
   }
 }
 
int main()
 {
 int K = 10;              // число, которому должна быть равна функция
 unsigned X[] = {1,2,3,4,5};   // Массив чисел
 unsigned N = sizeof(X)/sizeof(int);  // Кол-во элементов массива чисел
 char *Y = new char [N];         // Массив знаков
 char *MinMas = new char [N];    // Оптимальный массив знаков
 
 int p,um,Sum;                  // дополнительные переменные
 unsigned min = ~0;
 
   ((N-1)%3) ? p = (N-1)/3+1 : p = (N-1)/3;
   ((N-1-p)%2) ? um=(N-1-p)/2+1 : um=(N-1-p)/2;
 
   for (int i = 0; i < N-1; i++)
   {
     if (i<p) Y[i]='+';
     else
       if ( (i>=p) && (i<p+um) ) Y[i]='-';
       else Y[i]='*';
 
   Generate(X,Y,MinMas,N,K,min);
 
   Sum = GetSum(X,MinMas,N);
 
   for (int i = 0; i < N; i++)
   {
    cout<<X[i];
    if (i<N-1) cout<<MinMas[i];
   }
   cout<<" = "<<Sum;
 
   getch();
   return 0;
 }
Yandex
Объявления
23.11.2009, 13:46     рекурсия на расставление знаков между числами
Ответ Создать тему
Опции темы

Текущее время: 06:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru