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

Расставить арифметические знаки в выражении - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
NanoBreaker
 Аватар для NanoBreaker
23 / 23 / 7
Регистрация: 11.07.2013
Сообщений: 82
02.02.2014, 19:01     Расставить арифметические знаки в выражении #1
Здравствуйте, хочу представить вашему внимаю одну задачу из олимпиадной работы. У меня самого котелок еще не доварил как её решить, поэтому хочу предоставить эту возможность вам!)

Не уделяйте внимание на то как оформлено условие, Молдавская олимпиада( переводилась с румынского языка, да и люди которые составляли условие к задачи, большим интеллектом по всей видимости не отличались) : D

Файл с условием задачи прикреплен к теме.

P.S. Если есть желание увидеть всю олимпиаду целиком, пишите.
Миниатюры
Расставить арифметические знаки в выражении  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2014, 19:01     Расставить арифметические знаки в выражении
Посмотрите здесь:

C++ Расставить знаки арифметических операций так, чтобы сошелся результат
Переместить арифметические знаки вконец C++
Нужно расставить между числами знаки + или - таким образом, чтобы получилось выражение, значение которого равно s и вывести его на экран C++
C++ Заменить в файле все знаки "+" на знаки "-", а знаки "-" на знаки "+"
В выражении расставить знаки так, чтобы результат вычислений был равен 35 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NanoBreaker
 Аватар для NanoBreaker
23 / 23 / 7
Регистрация: 11.07.2013
Сообщений: 82
02.02.2014, 19:44  [ТС]     Расставить арифметические знаки в выражении #2
Извиняюсь за это, сейчас всё переделаю.

Добавлено через 27 минут
------------------------------------------------------------------------------------------------------------
Условие: Пусть дано N - натуральных последовательных чисел, расположенных один за другим, начиная с 1 и заканчивая N, то есть имеется последовательность(конечная) 1,2,3, . . . , N. Напишите программу, которая устанавливает знаки +, - или * перед каждым (и перед первым тоже) числом так, что результат выражения равен 0. Существует одно исключение: перед первым элементом можно поставить только знаки + и -. Порядок выполнения операций соответствует правилам арифметики.

Input: Натуральное число N вводится с клавиатуры.

Output: Выходной файл semne.out содержит последовательность знаков, которые будут размещены перед каждым числом, если есть такая последовательность, иначе написать слово NU.

Ограничения:

Пример:
N = 5
содержание semne.out: -*++-
и чтоб вы лучше понимали, вот так вот это выглядит: -1*2+3+4-5 = 0
------------------------------------------------------------------------------------------------------------

Не заметил что вы переименовали тему, поэтому создал новую, думая что вы удалили старую.
mf909
96 / 12 / 3
Регистрация: 10.01.2014
Сообщений: 29
03.02.2014, 23:44     Расставить арифметические знаки в выражении #3
А почему не сделать прямым перебором всех возможных вариантов?
Alkenso
5 / 4 / 4
Регистрация: 30.01.2014
Сообщений: 27
04.02.2014, 01:27     Расставить арифметические знаки в выражении #4
Сделал таким образом, если есть корректировки или критика - просьба отписаться

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
int _tmain(int argc, _TCHAR* argv[])
{
    int i, res = 0;
    ofstream fout("semne.out", ios::out);
    vector <int> v; // вектор всех возможных элементов
    vector <char> vch; // вектор символов
    for (i = SIZE ; i > 0 ; i--) // заполняем вектор последовательностью
        v.push_back(i);
 
    vch.push_back('+'); // первый символ со знаком +, текущий результат того же знака
    res = v[i];
 
    for (i = 1 ; i < SIZE - 2 ; i++) // перебор кроме последних двух значений
    {
        if (abs(res + v[i]) > 2)
        {
            vch.push_back('-');
            res -= v[i];
        }
        else
        {
            vch.push_back('+');
            res += v[i];
        }
    }
    vch.push_back('+');
    vch.push_back('*');
    if (res > 0) // и последний символ
    {
        vch.push_back('-');
        res -= 2;
    }
    else
    {
        vch.push_back('+');
        res += 2;
    }
 
    if (res)
        fout << "NU";
    else
        copy(vch.rbegin(), vch.rend(), ostream_iterator <char> (fout)); // выводим в файл
    fout.close();
    return 0;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.02.2014, 22:05     Расставить арифметические знаки в выражении #5
Цитата Сообщение от Alkenso Посмотреть сообщение
если есть корректировки или критика - просьба отписаться
да пожалуйста, проверьте SIZE равное 3, 4, 5, 6 и т.д.
Во-первых, ответы почти всегда NU
Во-вторых, например при 5, выдает ответ: +*+--+ (количество знаков не равно 5)
Подсказка: ответ есть всегда кроме N равном 1 и 2.
Alkenso
5 / 4 / 4
Регистрация: 30.01.2014
Сообщений: 27
04.02.2014, 23:30     Расставить арифметические знаки в выражении #6
ну все правильно, количество знаков при N = 5 не будет равно 5, т.к. кроме знака (+/-) числа есть еще и операция умножения (доп. знак)

Добавлено через 19 минут
а по поводу других ответов разбираюсь (хотя для 4 даже на листочке не нашёл решения)
NanoBreaker
 Аватар для NanoBreaker
23 / 23 / 7
Регистрация: 11.07.2013
Сообщений: 82
06.02.2014, 00:28  [ТС]     Расставить арифметические знаки в выражении #7
Если что, я наблюдаю над темой, если у кого то есть свежие идеи то милости просим. ) До сих пор без понятия как реализовать эту программу, а метод перебора не думаю что подойдет. Спасибо также за ответы выше!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2014, 06:07     Расставить арифметические знаки в выражении
Еще ссылки по теме:

Расставить знаки между числами от 1 до 9, чтобы получить заданное число C++
Расставить среди цифр знаки арифметических операций и скобки, чтобы получить необходимый результат C++
C++ Сколько существует способов расставить между цифр знаки "+" и "-"

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.02.2014, 06:07     Расставить арифметические знаки в выражении #8
Цитата Сообщение от Alkenso Посмотреть сообщение
хотя для 4 даже на листочке не нашёл решения
Очень тяжелый тест ) . Вот ответ для N=4
-++-

это выглядит: -1+2+3-4 = 0

Добавлено через 17 минут
Цитата Сообщение от NanoBreaker Посмотреть сообщение
Если что, я наблюдаю над темой, если у кого то есть свежие идеи то милости просим. ) До сих пор без понятия как реализовать эту программу, а метод перебора не думаю что подойдет.
лучше приступайте к поиску решения. Вот подсказки:
Всего вариантов будет 4:
1. Когда N%2==0 и N%4==0 (можно это условие описать просто N%4==0).
2. Когда N%2==0 и N%4!=0. Учтите что сумма всех чисел от 1 до N в этом случае - нечетное число. Поэтому для этого случая предлагаю делать всегда так начало: 1*2. Вам останется придумать как распределить оставшиеся числа: 2 3 4 5 6
3. Когда N%2!=0 и (N+1)%4==0.
4. Когда N%2!=0 и (N+1)%4!=0. Здесь сумма всех чисел тоже нечетное число. Поэтому начало как во втором варианте.
Yandex
Объявления
06.02.2014, 06:07     Расставить арифметические знаки в выражении
Ответ Создать тему
Опции темы

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