Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100

@rayJIB · Регистрация: 27.06.2014

Author24 — интернет-сервис помощи студентам

Составить программу, которая бы нашла все варианты размещения знаков арифметических операций +,-,* на месте вопросительных знаков в выражении 1?2?3?4?5?6?7?8?9, что значение этого выражения равнялось бы 100. Арифметические действия выполняются слева направо, а не по обычному приоритету.

@Sonance · 27.06.2014, 16:29

На каждой позиции возможны 3 варианта действий, при условии что приоритет выполнения действий не важен и все действия выполняются слева направо:

C++

#include <iostream>
 
 
int mass[9]={1,2,3,4,5,6,7,8,9}, Sf, Ss;
 
 
int Do(int znak, int a, int b, int &S){
    if(znak == 0){
        S=a-b;
    }
    if(znak == 1){
        S=a+b;
    }
    if(znak == 2){
        S=a*b;
    }
    return 0;
}
char Znak(int i){
    char Znak;
    if(i == 0){
        Znak='-';
    }
    if(i == 1){
        Znak='+';
    }
    if(i == 2){
        Znak='*';
    }
    return Znak;
}
void main(){
    int count(0);
    std::cout<<"Varianti podstanovki znakov pri kotorom virazhenie ravno 100:"<<"\n";
    for(int a(0); a<3; a++){
        for(int b(0); b<3; b++){
            for(int c(0); c<3; c++){
                for(int d(0); d<3; d++){
                    for(int e(0); e<3; e++){
                        for(int f(0); f<3; f++){
                            for(int g(0); g<3; g++){
                                for(int h(0); h<3; h++){
                                    Do(e, mass[0], mass[1], Sf);
                                    Ss=0;
                                    Do(b, Sf, mass[2], Ss);
                                    Sf=0;
                                    Do(c, Ss, mass[3], Sf);
                                    Ss=0;
                                    Do(d, Sf, mass[4], Ss);
                                    Sf=0;
                                    Do(e, Ss, mass[5], Sf);
                                    Ss=0;
                                    Do(f, Sf, mass[6], Ss);
                                    Sf=0;
                                    Do(g, Ss, mass[7], Sf);
                                    Ss=0;
                                    Do(h, Sf, mass[8], Ss);
                                    Sf=0;
                                    if(Ss == 100){
 
                                        std::cout<<"1"<<Znak(a)<<"2"<<Znak(b)<<"3"<<Znak(c)<<"4"<<Znak(d)<<"5"<<Znak(e)<<"6"<<Znak(f)<<"7"<<Znak(g)<<"8"<<Znak(h)<<"9"<<" = 100"<<"\n";
                                        count++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
std::cout<<"Kol-vo variantov podstanovki znakov pri kotorom virazhenie ravno 100"<<"\t"<<count<<"\n";
system("pause");
 
}

@rayJIB · 27.06.2014, 16:47 **[ТС]**

Спасибо огромное,а можно описание методов реализации данной программы,в частности к вот этой части:

C++

      Do(e, mass[0], mass[1], Sf);
                                    Ss=0;
                                    Do(b, Sf, mass[2], Ss);
                                    Sf=0;
                                    Do(c, Ss, mass[3], Sf);
                                    Ss=0;
                                    Do(d, Sf, mass[4], Ss);
                                    Sf=0;
                                    Do(e, Ss, mass[5], Sf);
                                    Ss=0;
                                    Do(f, Sf, mass[6], Ss);
                                    Sf=0;
                                    Do(g, Ss, mass[7], Sf);
                                    Ss=0;
                                    Do(h, Sf, mass[8], Ss);
                                    Sf=0;
                                    if(Ss == 100)

@Eva Rosalene · 27.06.2014, 17:04

Рекурсией:

C++

#include <iostream>
#include <vector>
 
using namespace std;
 
int eval(vector<int> arr){
    int total = 0;
    vector<int> p = arr, m = arr, mp = arr;
    if (arr.size() > 2){
        p[1] = p[0] + p[1]; p.erase(p.begin()); total += eval(p);
        m[1] = m[0] - m[1]; m.erase(m.begin()); total += eval(m);
        mp[1]=mp[0] *mp[1];mp.erase(mp.begin()); total+=eval(mp);
    } else {
        if ((arr[0] - arr[1]) == 100) total++;
        if ((arr[0] + arr[1]) == 100) total++;
        if ((arr[0] * arr[1]) == 100) total++;
    }
    return total;
}
 
int main(){
    vector<int> arr; for (int i = 1; i < 10; i++) arr.push_back(i);
    cout<<eval(arr);
}

Добавлено через 16 секунд
Но находит только количество.

@rayJIB · 27.06.2014, 17:05 **[ТС]**

спасибо,разобрался!

@Eva Rosalene · 27.06.2014, 17:15

Полное решение:

C++

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
string str(int n);
 
int eval(vector<int> arr, string expr){
    int total = 0;
    vector<int> p = arr, m = arr, mp = arr;
    int sp = p[1], sm = m[1], smp = mp[1];
    if (arr.size() > 2){
        p[1] = p[0] + p[1]; p.erase(p.begin()); total += eval(p, expr + string("+") + str('0' + sp));
        m[1] = m[0] - m[1]; m.erase(m.begin()); total += eval(m, expr + string("-") + str('0' + sm));
        mp[1]=mp[0] *mp[1];mp.erase(mp.begin()); total+=eval(mp, expr + string("*") + str('0' + smp));
    } else {
        if ((arr[0] - arr[1]) == 100) {total++; cout<<expr<<"-"<<arr[1]<<endl;}
        if ((arr[0] + arr[1]) == 100) {total++; cout<<expr<<"+"<<arr[1]<<endl;}
        if ((arr[0] * arr[1]) == 100) {total++; cout<<expr<<"*"<<arr[1]<<endl;}
    }
    return total;
}
 
string str(int n){
    string a = "0";
    a[0] = (char) n;
    return a;
}
 
int main(){
    string expr = "1";
    vector<int> arr; for (int i = 1; i < 10; i++) arr.push_back(i);
    eval(arr, expr);
}

@rayJIB · 27.06.2014, 17:41 **[ТС]**

Sonance,приоритет выполнения действий не важен и все действия выполняются слева направо,а в данной программе действия выполняются по приоритету.

Добавлено через 1 минуту
FraidZZ, я только учусь и данного не изучал,мне ближе первый вариант,но там приоритет действий есть.

@SlavaSSU · 27.06.2014, 17:50

ответ 7?

C++ (Qt)

#include <iostream>
 
using namespace std;
 
int ans = 0;
 
void rec(int val, int cur)
{
    if(val == 9)
    {
        if(cur == 100)
        {
            ans++;
        }
 
        return;
    }
 
 
    int ncur = cur + (val + 1);
    rec(val + 1, ncur);
    ncur = cur - (val + 1);
    rec(val + 1, ncur);
    ncur = cur * (val + 1);
    rec(val + 1, ncur);
}
 
int main()
{
    rec(1, 1);
    cout << ans << endl;
    return 0;
}

@rayJIB · 27.06.2014, 18:10 **[ТС]**

SlavaSSU, да, 7

Добавлено через 5 минут
FraidZZ, а можно описание методов реализации данной программы?

@Eva Rosalene · 27.06.2014, 18:28

rayJIB, да все просто) Создается вектор (считай это массивом, просто вектор удобнее и передается из функции в функцию). Так же создается строка, в которую потом записывается выражение. И затем просто функция до тех пор пока у нее больше двух чисел в векторе рекурсивно подбирает знаки. Если же ответ сошелся, она его выводит)

@rayJIB · 27.06.2014, 18:59 **[ТС]**

FraidZZ, а можно проделать подобное используя массив?

@Eva Rosalene · 27.06.2014, 19:27

rayJIB, придется пилить очень много костылей.

@Sonance · 27.06.2014, 21:27

Где вы тут приоритет увидели, все считается по порядку с лева направо, функция do() принимает аргументы 1- действие, 2-3-числа с которыми нужно проделать действие, 4- куда записать результат

C++

Do(a, mass[0], mass[1], Sf);//тут опечатка была 1 аргумент "a" а не "e"
Ss=0;
Do(b, Sf, mass[2], Ss);
Sf=0;
Do(c, Ss, mass[3], Sf);
Ss=0;
Do(d, Sf, mass[4], Ss);
Sf=0;
Do(e, Ss, mass[5], Sf);
Ss=0;
Do(f, Sf, mass[6], Ss);
Sf=0;
Do(g, Ss, mass[7], Sf);
Ss=0;
Do(h, Sf, mass[8], Ss);
Sf=0;
if(Ss == 100)

Из-за опечатки выдавало 9 ответов что не верно, вот так все работает, надеюсь теперь все понятно, если нет пишите завтра время будет опишу каждую строку.

@Mr.X · 29.06.2014, 11:18

C++

/////////////////////////////////////////////////////////////////////////////////////////
//Составить программу, которая бы нашла все варианты размещения знаков арифметических операций 
//+,-,* на месте вопросительных знаков в выражении 1?2?3?4?5?6?7?8?9, что значение этого выражения 
//равнялось бы 100. Арифметические действия выполняются слева направо, а не по обычному приоритету.
/////////////////////////////////////////////////////////////////////////////////////////
#include <deque>
#include <iostream>
#include <sstream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string         T_str;
typedef std::deque<int>     T_operands;
/////////////////////////////////////////////////////////////////////////////////////////
T_str   num_to_str( int  num )
{
    std::ostringstream  sout;
    sout    <<  num;
    return  sout.str();
}
/////////////////////////////////////////////////////////////////////////////////////////
void    print_variants_for_add_subtr_mult
    (
        T_operands      operands,
        int             result_target,
        int             result_cur      =   0,
        T_str           str_result      =   T_str()
    )
{
    if  (
            operands.empty()
        )
    {
        if( result_cur == result_target )
        {
            str_result  +=  " = ";
            str_result  +=  num_to_str( result_target );
 
            std::cout   <<  str_result
                        <<  std::endl;
        }
        return;
    }//if
 
    int     operand     =   operands.front();
    operands.pop_front();
 
    if  (
            str_result.empty()
        )
    {
        print_variants_for_add_subtr_mult
            (
                operands,
                result_target,
                operand,
                num_to_str( operand )
            );
    }
    else
    {
        print_variants_for_add_subtr_mult
            (
                operands,
                result_target,
                result_cur + operand,
                str_result + " + " + num_to_str( operand )
            );
 
        print_variants_for_add_subtr_mult
            (
                operands,
                result_target,
                result_cur - operand,
                str_result + " - " + num_to_str( operand )
            );
 
        print_variants_for_add_subtr_mult
            (
                operands,
                result_target,
                result_cur * operand,
                str_result + " * " + num_to_str( operand )
            );
    }//else
}
/////////////////////////////////////////////////////////////////////////////////////////
int  main()
{
    int         operands_arr[]  =   {1, 2, 3, 4, 5, 6, 7, 8, 9};
 
    T_operands  operands
        (
            operands_arr,
            operands_arr + sizeof( operands_arr ) / sizeof( operands_arr[0] )
        );
 
    int     result_target   =   100;
 
    print_variants_for_add_subtr_mult
        (
            operands,
            result_target
        );
 
    system( "pause" );
}

Добавлено через 6 часов 2 минуты
А в этой программе с консоли вводятся операнды и желаемый результат:

C++

/////////////////////////////////////////////////////////////////////////////////////////
//Составить программу, которая бы нашла все варианты размещения знаков арифметических операций 
//+,-,* на месте вопросительных знаков в выражении 1?2?3?4?5?6?7?8?9, что значение этого выражения 
//равнялось бы 100. Арифметические действия выполняются слева направо, а не по обычному приоритету.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <deque>
#include <iostream>
#include <iterator>
#include <set>
#include <sstream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string             T_str;
typedef std::set    < T_str >   T_strings;
typedef std::deque  < int   >   T_operands;
/////////////////////////////////////////////////////////////////////////////////////////
T_str   num_to_str( int  num )
{
    std::ostringstream  sout;
    sout    <<  num;
    return  sout.str();
}
/////////////////////////////////////////////////////////////////////////////////////////
void    set_variants_strings_for_add_subtr_mult
    (
        T_operands      operands,
        int             result_target,
        T_strings   &   variants_strings,
        int             result_cur      =   0,
        T_str           str_result      =   T_str()
    )
{
    if  (
            operands.empty()
        )
    {
        if( result_cur == result_target )
        {
            str_result  +=  " = ";
            str_result  +=  num_to_str( result_target );
 
            variants_strings.insert( str_result );
        }
    }
    else
    {
        int     operand     =   operands.front();
        operands.pop_front();
 
        if  (
                str_result.empty()
            )
        {
            set_variants_strings_for_add_subtr_mult
                (
                    operands,
                    result_target,
                    variants_strings,
                    operand,
                    num_to_str( operand )
                );
        }
        else
        {
            set_variants_strings_for_add_subtr_mult
                (
                    operands,
                    result_target,
                    variants_strings,
                    result_cur + operand,
                    str_result + " + " + num_to_str( operand )
                );
 
            set_variants_strings_for_add_subtr_mult
                (
                    operands,
                    result_target,
                    variants_strings,
                    result_cur - operand,
                    str_result + " - " + num_to_str( operand )
                );
 
            set_variants_strings_for_add_subtr_mult
                (
                    operands,
                    result_target,
                    variants_strings,
                    result_cur * operand,
                    str_result + " * " + num_to_str( operand )
                );
        }//else
    }//else
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_prompt_and_input_val
    (
        T_str   const   &   prompt,
        int             &   val
    )
{
    std::cout   <<  prompt;
    std::cin    >>  val;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_prompt_and_input_val_not_less_than
    (
        T_str   const   &   prompt,
        int             &   val,
        int                 left_bound
    )
{
    do
    {
        print_prompt_and_input_val
            (
                prompt,
                val
            );
    }
    while( val < left_bound );
}
/////////////////////////////////////////////////////////////////////////////////////////
int  main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        int     operands_count  =   0;
 
        print_prompt_and_input_val_not_less_than
            (
                "Введите количество операндов: ",
                operands_count,
                1
            );
 
        std::cout   <<  "Введите "
                    <<  operands_count
                    <<  " операндов:"
                    <<  std::endl;
 
        T_operands  operands;
 
        for( int  i = 0; i < operands_count; ++i )
 
        {
            int     operand_cur     =   0;
 
            print_prompt_and_input_val
                (
                    "#" + num_to_str( i + 1 ) + "\t: ",
                    operand_cur
                );
 
            operands.push_back( operand_cur );
        }
 
        int     result_target   =   0;
 
        print_prompt_and_input_val
            (
                "\nВведите желаемый результат: ",
                result_target
            );
 
        std::cout   <<  std::endl;
        T_strings   variants_strings;
 
        set_variants_strings_for_add_subtr_mult
            (
                operands,
                result_target,
                variants_strings
            );
 
        std::copy
            (
                variants_strings.begin          (),
                variants_strings.end            (),
                std::ostream_iterator<T_str>    ( std::cout, "\n" )
            );
 
        int     variants_total  =   variants_strings.size();
 
        std::cout   <<  (
                            variants_total == 0
                                ?   "Нет решений."
                                :   "Всего " + num_to_str( variants_total ) + " решений."
                        )
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }//for
}

@Sonance · 29.06.2014, 11:40

Mr.X, а можно комментарии к первому коду, что то я не могу разобраться, как он работает

Объясните пожалуйста функцию print_variants_for_add_subtr_mult()

@Mr.X · 29.06.2014, 13:42

Сообщение от Sonance

Объясните пожалуйста функцию print_variants_for_add_subtr_mult()

Она рекурсивная, накапливает в своих аргументах числовой и строковый результаты. Если в конце числовой результат равен желаемому, то печатает строковый.

@Sonance · 29.06.2014, 15:56

Сообщение от Mr.X

Она рекурсивная, накапливает в своих аргументах числовой и строковый результаты. Если в конце числовой результат равен желаемому, то печатает строковый.

Спасибо, посмотрел что такое рекурсия, нашел факториал с её помощью. В случае с факториалом все просто, можно сказать интуитивно понятно, но в данном случае все как то путается, объясните пожалуйста ход мыслей при разработке программы для данной задачи.

@Mr.X · 29.06.2014, 17:41

Сообщение от Sonance

объясните пожалуйста ход мыслей при разработке программы для данной задачи

Каждая функция вызывает три (по числу возможных различных операторов в каждой позиции), т.е. получаем троичное дерево вызовов высотой 8 (по числу операторов в выражении). Каждая ветвь дерева соответствует одному из вариантов расстановки операторов.

@Sonance · 29.06.2014, 18:34

Верно я понял?
Контейнер deque - это стек;
при каждом вызове функции - из стека достается 1 элемент, размер стека уменьшается на 1, и функция вызывает сама себя 3 раза(для каждой операции), уже с меньшим стеком и так пока стек не опустеет

И еще вопрос: есть ли какие-то преимущества у этого способа, перед алгоритмами не использующими рекурсию. В консоли алгоритм с рекурсией работает заметно медленнее, чем без неё.

P.s. Возможно глупые вопросы задаю, но хотелось бы разобраться. Просто я рекурсивный алгоритм впервые вижу. Интересный способ.

@Eva Rosalene Модератор 5235 / 2109 / 415 Регистрация: 06.01.2013 Сообщений: 4,839
	27.06.2014, 19:27	12
	rayJIB, придется пилить очень много костылей. 0

Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100

Решение

Решение

@rayJIB 0 / 0 / 0 Регистрация: 27.06.2014 Сообщений: 9
		1
	Найти все варианты размещения знаков операций +,-,* на месте вопросов в выражении 1?2?3?4?5?6?7?8?9=100 27.06.2014, 15:03. Показов 2589. Ответов 18 Метки нет (Все метки) Составить программу, которая бы нашла все варианты размещения знаков арифметических операций +,-,* на месте вопросительных знаков в выражении 1?2?3?4?5?6?7?8?9, что значение этого выражения равнялось бы 100. Арифметические действия выполняются слева направо, а не по обычному приоритету. 0

@rayJIB 0 / 0 / 0 Регистрация: 27.06.2014 Сообщений: 9
	27.06.2014, 17:05 [ТС]	5
	спасибо,разобрался! 0

@rayJIB 0 / 0 / 0 Регистрация: 27.06.2014 Сообщений: 9
	27.06.2014, 17:41 [ТС]	7
	Sonance,приоритет выполнения действий не важен и все действия выполняются слева направо,а в данной программе действия выполняются по приоритету. Добавлено через 1 минуту FraidZZ, я только учусь и данного не изучал,мне ближе первый вариант,но там приоритет действий есть. 0

@rayJIB 0 / 0 / 0 Регистрация: 27.06.2014 Сообщений: 9
	27.06.2014, 18:10 [ТС]	9
	SlavaSSU, да, 7 Добавлено через 5 минут FraidZZ, а можно описание методов реализации данной программы? 0

@Eva Rosalene Модератор 5235 / 2109 / 415 Регистрация: 06.01.2013 Сообщений: 4,839
	27.06.2014, 18:28	10
	rayJIB, да все просто) Создается вектор (считай это массивом, просто вектор удобнее и передается из функции в функцию). Так же создается строка, в которую потом записывается выражение. И затем просто функция до тех пор пока у нее больше двух чисел в векторе рекурсивно подбирает знаки. Если же ответ сошелся, она его выводит) 0

@rayJIB 0 / 0 / 0 Регистрация: 27.06.2014 Сообщений: 9
	27.06.2014, 18:59 [ТС]	11
	FraidZZ, а можно проделать подобное используя массив? 0

@Sonance 6 / 6 / 5 Регистрация: 15.02.2013 Сообщений: 56
	29.06.2014, 11:40	15
	Mr.X, а можно комментарии к первому коду, что то я не могу разобраться, как он работает Объясните пожалуйста функцию print_variants_for_add_subtr_mult() 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	29.06.2014, 13:42	16
	Сообщение от Sonance Объясните пожалуйста функцию print_variants_for_add_subtr_mult() Она рекурсивная, накапливает в своих аргументах числовой и строковый результаты. Если в конце числовой результат равен желаемому, то печатает строковый. 0

@Sonance 6 / 6 / 5 Регистрация: 15.02.2013 Сообщений: 56
	29.06.2014, 15:56	17
	Сообщение от Mr.X Она рекурсивная, накапливает в своих аргументах числовой и строковый результаты. Если в конце числовой результат равен желаемому, то печатает строковый. Спасибо, посмотрел что такое рекурсия, нашел факториал с её помощью. В случае с факториалом все просто, можно сказать интуитивно понятно, но в данном случае все как то путается, объясните пожалуйста ход мыслей при разработке программы для данной задачи. 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	29.06.2014, 17:41	18
	Сообщение от Sonance объясните пожалуйста ход мыслей при разработке программы для данной задачи Каждая функция вызывает три (по числу возможных различных операторов в каждой позиции), т.е. получаем троичное дерево вызовов высотой 8 (по числу операторов в выражении). Каждая ветвь дерева соответствует одному из вариантов расстановки операторов. 2

@Sonance 6 / 6 / 5 Регистрация: 15.02.2013 Сообщений: 56
	29.06.2014, 18:34	19
	Верно я понял? Контейнер deque - это стек; при каждом вызове функции - из стека достается 1 элемент, размер стека уменьшается на 1, и функция вызывает сама себя 3 раза(для каждой операции), уже с меньшим стеком и так пока стек не опустеет И еще вопрос: есть ли какие-то преимущества у этого способа, перед алгоритмами не использующими рекурсию. В консоли алгоритм с рекурсией работает заметно медленнее, чем без неё. P.s. Возможно глупые вопросы задаю, но хотелось бы разобраться. Просто я рекурсивный алгоритм впервые вижу. Интересный способ. 0