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

Оптимизация решения. - C++

Восстановить пароль Регистрация
 
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
27.07.2011, 10:08     Оптимизация решения. #1
всем привет.
решил задачу -
Даны N целых чисел X1, X2, ..., XN. Расставить между ними знаки "+" и "-" так, чтобы значение получившегося выражения было равно заданному целому S.
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 <iostream>
#include <fstream>
 
void print (const int *MAS, const char *, const int, const int); //функция печати найденного выражения.
void func (const int *, const int, const int, int, int, char *); // рекурсивная функция поиска решения.
 
bool flag = false; // true - решение найдено.
 
int main() {
    std::ifstream ifs ("input.txt");
    std::ofstream ofs ("output.txt");
    //
    int size, rezult;
    std::cin >> size >> rezult;
    int *MAS = new int [size];
    char *SIGNS= new char [size - 1];
 
    for (int i = 0; i < size; i++)
        std::cin >> MAS[i];
    //
    --size; // т.к. в будущем приходится работать со знаками,
            // а у нас их size - 1.
    func (MAS, rezult, size, MAS[0], 0, SIGNS);
    if (!(flag)) 
        std::cout << "No solution";
    //
    delete []MAS;
    delete []SIGNS;
    ifs.close();
    ofs.close();
    return 0;
}
 
void print (const int *MAS,  char *SIGNS, const int size, const int rez)
{
    for (int i = 0; i < size; i++) {
        std::cout << MAS[i] << " ";
        std::cout << SIGNS[i] << " ";
    }
    std::cout << MAS[size] << " = " << rez;
}
 
void func (const int *MAS, const int rez, const int size, int sum,
           int idxSIGN, char *SIGNS)
           // MAS - массив чисел, rez - нужный результат, size - кол-во знаков,
           // sum - набранная сумма, idxSIGN - индекс знака, с которым будем работать
           // SIGNS - массив знаков.
{
    if (idxSIGN < size) {
        SIGNS[idxSIGN] = '+';
        func (MAS, rez, size, sum + MAS[idxSIGN + 1], idxSIGN + 1, SIGNS);
        SIGNS[idxSIGN] = '-';
        func (MAS, rez, size, sum - MAS[idxSIGN + 1], idxSIGN + 1, SIGNS);
    }
 
    if ((sum == rez) && (idxSIGN == size) && ((!flag))) {
        print (MAS, SIGNS, size, rez);
        flag = true;
        return;
    }
}
дело в том, что мне самому не нравится свое решение, не красиво как - то.
смущает большое кол-во параметров в функции, можно сделать большую часть из них глобальными, но тогда прийдется отказаться от динамического выделения памяти, и брать все по макс. ограничениям, + я не люблю глобальные переменные. да и с этим флагом заморочка какая - то ..
может есть какие замечания / предложения?

входные данные:
3 6
1 2 3
выходные данные:
1 + 2 + 3 = 6
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.07.2011, 10:25     Оптимизация решения. #2
Тут есть пара вариантов =)
Оптимизация в каком смысле? Смущает только быдлокод, или по времени не проходит?
Ну и 2е место в лучших попытках: (это сжатый вариант решения при помощи двоичной системы, полный по ссылке выше есть)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <fstream>
int q[24], w[24], n, s, i, x;
int main(){
    std::fstream v("input.txt");
    std::ofstream o("output.txt");
    for (v >> n >> s; v >> w[i++];);
    while ( !*q ){
        for (x = *w, i = 0; ++i < n ; )
            x  += q[i] ?  w[i] : -w[i];
        if (x == s){
            for (i = 0; i < n - 1;   )
                o << w[i-1] << (q[++i] ? '+' : '-');            
            o << w[i] << '=' << s;
            return 0;
        }
        for ( ++q[n-1], i = n; --i && q[i] > 1; ++q[i-1])
            q[i] = 0;
    }
    o << "No solution";
}
P.S. тоже очень не нравилось глобальные переменные использовать, однако как минимум флаг тут вполне оправдан. Зачем они вообще нужны, если их не использовать? >_< В данном случае код без глобальной переменной получится менее читаемым.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
27.07.2011, 10:30  [ТС]     Оптимизация решения. #3
да, меня мой быдлокод смущает)
спасибо
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.07.2011, 10:45     Оптимизация решения. #4
Цитата Сообщение от neske Посмотреть сообщение
смущает большое кол-во параметров в функции
Чтобы из мейна было комфортнее вызывать, можно сделать как-то так.
C++
1
2
void func (const int *MAS, const int rez, const int size, int sum,
           char *SIGNS, int idxSIGN = 0)
Тогда в мейне на 1 параметр меньше указывать придется =)

Цитата Сообщение от neske Посмотреть сообщение
можно сделать большую часть из них глобальными, но тогда прийдется отказаться от динамического выделения памяти
Можно ведь глобально только указатели объявлять, а память уже в мейне выделять.
Вроде такого
C++
1
2
3
4
5
6
7
8
int * arr;
int main(){
  int N;
  std::cin >> N;
  arr = new int [N];
  //...
  delete[] N;
}
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
27.07.2011, 11:45  [ТС]     Оптимизация решения. #5
во блин, действительно) спасибо

Добавлено через 20 минут
Так получилось.
Не знаю, как и писать, с глобальными или без )

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
#include <iostream>
#include <fstream>
 
void print ();
void func (int, int);
 
int *MAS, size, rezult;
char *SIGNS;
bool flag = false;
 
int main() {
    std::ifstream ifs ("input.txt");
    std::ofstream ofs ("output.txt");
    //
    std::cin >> size >> rezult;
    MAS = new int [size];
    SIGNS= new char [size - 1];
 
    for (int i = 0; i < size; i++)
        std::cin >> MAS[i];
    //
    --size; // т.к. в будущем приходится работать со знаками,
            // а у нас их size - 1.
    func (MAS[0], 0);
    if (!(flag)) std::cout << "No solution";
    //
    delete []MAS;
    delete []SIGNS;
    ifs.close();
    ofs.close();
    return 0;
}
 
void print ()
{
    for (int i = 0; i < size; i++) {
        std::cout << MAS[i] << " ";
        std::cout << SIGNS[i] << " ";
    }
    std::cout << MAS[size] << " = " << rezult;
}
 
void func (int sum, int idxSIGN)
{
    if (idxSIGN < size) {
        SIGNS[idxSIGN] = '+';
        func (sum + MAS[idxSIGN + 1], idxSIGN + 1);
        SIGNS[idxSIGN] = '-';
        func (sum - MAS[idxSIGN + 1], idxSIGN + 1);
    }
 
    if ((sum == rezult) && (idxSIGN == size) && ((!flag))) {
        print ();
        flag = true;
        return;
    }
}
Добавлено через 23 минуты
Воо, теперь мне нравится.

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
#include <iostream>
#include <fstream>
 
void print (const int *, const int, const int, const char *); //функция печати найденного выражения.
bool func (const int *, const int, const int, int, int, char *); // рекурсивная функция поиска решения.
 
int main() {
    std::ifstream ifs ("input.txt");
    std::ofstream ofs ("output.txt");
    //
    int size, rezult;
    std::cin >> size >> rezult;
    int *MAS = new int [size];
    char *SIGNS= new char [size - 1];
 
    for (int i = 0; i < size; i++)
        std::cin >> MAS[i];
    --size;
    //
    if (func (MAS, rezult, size, MAS[0], 0, SIGNS))
        print (MAS, rezult, size, SIGNS);
    else
        std::cout << "No solution";
    //
    delete []MAS;
    delete []SIGNS;
    ifs.close();
    ofs.close();
    return 0;
}
 
void print (const int *MAS,  const int rezult, const int size, const char *SIGNS)
{
    for (int i = 0; i < size; i++) {
        std::cout << MAS[i] << " ";
        std::cout << SIGNS[i] << " ";
    }
    std::cout << MAS[size] << " = " << rezult;
}
 
bool func (const int *MAS, const int rez, const int size, int sum,
           int idxSIGN, char *SIGNS)
{
    if (idxSIGN < size) {
        SIGNS[idxSIGN] = '+';
        if (func (MAS, rez, size, sum + MAS[idxSIGN + 1], idxSIGN + 1, SIGNS))
            return true;
        SIGNS[idxSIGN] = '-';
        if (func (MAS, rez, size, sum - MAS[idxSIGN + 1], idxSIGN + 1, SIGNS))
            return true;
    }
    if ((sum == rez) && (idxSIGN == size))
        return true;
 
    return false;
}
Yandex
Объявления
27.07.2011, 11:45     Оптимизация решения.
Ответ Создать тему
Опции темы

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