Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 27
#1

Подскажите пожалуйста как написать реализацию алгоритма - C++

10.11.2013, 14:36. Просмотров 839. Ответов 12
Метки нет (Все метки)

Добрый день.
Столкнулся с заданием описанным ниже, ломаю голову уже несколько дней. Додумался сделать данное задание с помощью операции перебора(если есть какое то другое решение данной задачи подскажите пожалуйста), но возникли трудности:
1) как заменить '?' на +, –, *, /?
2)как сделать что бы было вот так вот result = 1 z[a] 2 z[b] 3 z[c] 4 z[d] 5 z[e] 6 ; что бы знак арифметической операции брались из массива z, или как по другому делать выбор операции?

Кликните здесь для просмотра всего текста

Написать реализацию алгоритма для выполнения следующего:
В выражении ((((1 ? 2) ? 3) ? 4) ? 5) ? 6 вместо каждого знака ? вставить знак одной из 4 арифметических операций +, –, *, / так, чтобы результат вычислений равнялся заданному целому числу N (при делении дробная часть отбрасывается).
Результатом выполнения алгоритма является число, показывающее количество различных решений задачи. Если решений нет, вернуть 0.
По желанию пользователя данного алгоритма все верные последовательности операций (верные выражения) выводить на консоль.
Крайне желательно использование автоматического юнит-тестирования для данного задания.

Пример:
Вход Выход Дополнительно
21 4 ((((1+2)+3)+4)+5)+6
((((1*2)+3)*4)-5)+6
((((1*2)-3)+4)*5)+6
((((1*2)*3)+4)+5)+6
28 0 решений нет


Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
char z[] = {'+', '-', '*', '/'};
    
    int result;
    
    srand(time(NULL));
    
    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 d=0; d<3; d++)
                    {
                     result = 1 + znak[rand()%4] + 2 ;
                    }
                }
 
            }
        }
    }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2013, 14:36
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Подскажите пожалуйста как написать реализацию алгоритма (C++):

Подскажите ,пожалуйста,как отобразить схему алгоритма оператора свитч в с++? нигде не могу найти корректного ответа( - C++
вот например есть у меня программка: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;cstring&gt; using...

Подскажите пожалуйста как написать консольное приложение win32, которое принимает на вход путь к папке - C++
Нужно написать консольное приложение win32, которое принимает на вход путь к папке

Выкладываю реализацию алгоритма Дейкстры на С++ - C++
Дпанная программа выполняет поиск по заданной матрице весов. Далее указываем начальную точку в графе и программа расчитывает все кратчайшие...

Выполнить программную реализацию алгоритма ГОСТ 28147 - C++
Товарищи программисты,помогите с заданием! Выполнить программную реализацию алгоритма ГОСТ 28147.Записать свои Фамилию, Имя и Отчество без...

Подскажите реализацию конструктора копирования - C++
Подскажите пожалуйста как реализовать конструктор копирования. #include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;math.h&gt; using...

Подскажите реализацию умножения многочлена на моном - C++
Умножение многочлена на x^k Подскажите реализацию.

12
Folko
265 / 253 / 7
Регистрация: 27.09.2013
Сообщений: 877
Записей в блоге: 1
10.11.2013, 14:51 #2
M1kloFFi, конкретно по замене символа: создаете массив char и там записываете все нужные символы
1
salam
173 / 154 / 17
Регистрация: 10.07.2012
Сообщений: 759
10.11.2013, 19:01 #3
backtrack / перебор с откатом писать умеете?
0
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 27
10.11.2013, 20:47  [ТС] #4
Цитата Сообщение от salam Посмотреть сообщение
backtrack / перебор с откатом писать умеете?
Нет, не умею.
0
lemegeton
2931 / 1360 / 136
Регистрация: 29.11.2010
Сообщений: 2,725
10.11.2013, 21:33 #5
Тут всего 1024 варианта прямого перебора хватит.
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
#include <iostream>
#include <iomanip>
#include <cmath>
 
double operate(double a, double b, int operation) {
  switch (operation) {
    case 0: return a + b;
    case 1: return a - b;
    case 2: return a * b;
    case 3: return a / b;
  }
  return 0;
}
 
int getOperation(long permutation, int position) {
  return (permutation & (3 << (position * 2))) >> (position * 2);
}
 
double calculate(long permutation) {
    return operate(
    operate(
    operate(
    operate(
    operate(
    1,
    2, getOperation(permutation, 0)),
    3, getOperation(permutation, 1)),
    4, getOperation(permutation, 2)),
    5, getOperation(permutation, 3)),
    6, getOperation(permutation, 4));
}
 
std::string formulate(long permutation) {
  const static char symbols[] = {'+', '-', '*', '/'};
  std::string result = std::string("1 ") +
    symbols[getOperation(permutation, 0)] +
    " 2 " + symbols[getOperation(permutation, 1)] +
    " 3 " + symbols[getOperation(permutation, 2)] +
    " 4 " + symbols[getOperation(permutation, 3)] +
    " 5 " + symbols[getOperation(permutation, 4)] +
    " 6";
  return result;
}
 
int main(int, char**) {
  for (int i = 0; i < 1024; ++i) {
    double value = calculate(i);
    if (fabs(value - int(value)) < 0.000000001) {
      std::cout << formulate(i) << " = " << value << std::endl;
    }
  }
 
  return 0;
}
1
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 27
10.11.2013, 21:47  [ТС] #6
Цитата Сообщение от lemegeton Посмотреть сообщение
Тут всего 1024 варианта прямого перебора хватит.
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
#include <iostream>
#include <iomanip>
#include <cmath>
 
double operate(double a, double b, int operation) {
  switch (operation) {
    case 0: return a + b;
    case 1: return a - b;
    case 2: return a * b;
    case 3: return a / b;
  }
  return 0;
}
 
int getOperation(long permutation, int position) {
  return (permutation & (3 << (position * 2))) >> (position * 2);
}
 
double calculate(long permutation) {
    return operate(
    operate(
    operate(
    operate(
    operate(
    1,
    2, getOperation(permutation, 0)),
    3, getOperation(permutation, 1)),
    4, getOperation(permutation, 2)),
    5, getOperation(permutation, 3)),
    6, getOperation(permutation, 4));
}
 
std::string formulate(long permutation) {
  const static char symbols[] = {'+', '-', '*', '/'};
  std::string result = std::string("1 ") +
    symbols[getOperation(permutation, 0)] +
    " 2 " + symbols[getOperation(permutation, 1)] +
    " 3 " + symbols[getOperation(permutation, 2)] +
    " 4 " + symbols[getOperation(permutation, 3)] +
    " 5 " + symbols[getOperation(permutation, 4)] +
    " 6";
  return result;
}
 
int main(int, char**) {
  for (int i = 0; i < 1024; ++i) {
    double value = calculate(i);
    if (fabs(value - int(value)) < 0.000000001) {
      std::cout << formulate(i) << " = " << value << std::endl;
    }
  }
 
  return 0;
}
Спасибо, помощь!!! Но прога выбивает ошибки, ошибки в скрине
0
Миниатюры
Подскажите пожалуйста как написать реализацию алгоритма  
lemegeton
2931 / 1360 / 136
Регистрация: 29.11.2010
Сообщений: 2,725
10.11.2013, 21:51 #7
На скриншоте другой код. Вы поменяли мой код, не имея представления, что вы делаете? Верните как было.
1
Ryuk
179 / 177 / 33
Регистрация: 10.06.2011
Сообщений: 871
10.11.2013, 21:59 #8
salam, что-то стало интересно, что за перебор такой?
0
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 27
10.11.2013, 22:03  [ТС] #9
Цитата Сообщение от lemegeton Посмотреть сообщение
На скриншоте другой код. Вы поменяли мой код, не имея представления, что вы делаете? Верните как было.
В данных местах ругается.
0
Миниатюры
Подскажите пожалуйста как написать реализацию алгоритма   Подскажите пожалуйста как написать реализацию алгоритма  
Max Dark
шКодер самоучка
1855 / 1655 / 603
Регистрация: 09.10.2013
Сообщений: 3,689
Записей в блоге: 6
Завершенные тесты: 2
10.11.2013, 22:12 #10
C++
1
#include <string>
2
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 27
10.11.2013, 22:56  [ТС] #11
Цитата Сообщение от lemegeton Посмотреть сообщение
Тут всего 1024 варианта прямого перебора хватит.
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
#include <iostream>
#include <iomanip>
#include <cmath>
 
double operate(double a, double b, int operation) {
  switch (operation) {
    case 0: return a + b;
    case 1: return a - b;
    case 2: return a * b;
    case 3: return a / b;
  }
  return 0;
}
 
int getOperation(long permutation, int position) {
  return (permutation & (3 << (position * 2))) >> (position * 2);
}
 
double calculate(long permutation) {
    return operate(
    operate(
    operate(
    operate(
    operate(
    1,
    2, getOperation(permutation, 0)),
    3, getOperation(permutation, 1)),
    4, getOperation(permutation, 2)),
    5, getOperation(permutation, 3)),
    6, getOperation(permutation, 4));
}
 
std::string formulate(long permutation) {
  const static char symbols[] = {'+', '-', '*', '/'};
  std::string result = std::string("1 ") +
    symbols[getOperation(permutation, 0)] +
    " 2 " + symbols[getOperation(permutation, 1)] +
    " 3 " + symbols[getOperation(permutation, 2)] +
    " 4 " + symbols[getOperation(permutation, 3)] +
    " 5 " + symbols[getOperation(permutation, 4)] +
    " 6";
  return result;
}
 
int main(int, char**) {
  for (int i = 0; i < 1024; ++i) {
    double value = calculate(i);
    if (fabs(value - int(value)) < 0.000000001) {
      std::cout << formulate(i) << " = " << value << std::endl;
    }
  }
 
  return 0;
}
Огромное спасибо за помощь!!! Теперь буду разбираться)

Добавлено через 26 минут
Цитата Сообщение от lemegeton Посмотреть сообщение
Тут всего 1024 варианта прямого перебора хватит.
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
#include <iostream>
#include <iomanip>
#include <cmath>
 
double operate(double a, double b, int operation) {
  switch (operation) {
    case 0: return a + b;
    case 1: return a - b;
    case 2: return a * b;
    case 3: return a / b;
  }
  return 0;
}
 
int getOperation(long permutation, int position) {
  return (permutation & (3 << (position * 2))) >> (position * 2);
}
 
double calculate(long permutation) {
    return operate(
    operate(
    operate(
    operate(
    operate(
    1,
    2, getOperation(permutation, 0)),
    3, getOperation(permutation, 1)),
    4, getOperation(permutation, 2)),
    5, getOperation(permutation, 3)),
    6, getOperation(permutation, 4));
}
 
std::string formulate(long permutation) {
  const static char symbols[] = {'+', '-', '*', '/'};
  std::string result = std::string("1 ") +
    symbols[getOperation(permutation, 0)] +
    " 2 " + symbols[getOperation(permutation, 1)] +
    " 3 " + symbols[getOperation(permutation, 2)] +
    " 4 " + symbols[getOperation(permutation, 3)] +
    " 5 " + symbols[getOperation(permutation, 4)] +
    " 6";
  return result;
}
 
int main(int, char**) {
  for (int i = 0; i < 1024; ++i) {
    double value = calculate(i);
    if (fabs(value - int(value)) < 0.000000001) {
      std::cout << formulate(i) << " = " << value << std::endl;
    }
  }
 
  return 0;
}
Не могли бы вы мне объяснить как функция int getOperation(long permutation, int position) выбирает знак?
Что такое permutation ??
return (permutation & (3 << (position * 2))) >> (position * 2); - что означают << и >> ??
0
lemegeton
2931 / 1360 / 136
Регистрация: 29.11.2010
Сообщений: 2,725
11.11.2013, 08:44 #12
Цитата Сообщение от M1kloFFi Посмотреть сообщение
Не могли бы вы мне объяснить как функция int getOperation(long permutation, int position) выбирает знак?
Так как знаков всего четыре, то для выражения каждого знака необходимо и достаточно ровно 2-х бит, а для хранения пяти знаков потребуется ровно 10 бит. Это очень хорошо, так как позволит легко и непринужденно перебрать все варианты расстановки знаков с помощью чисел от нуля до 1024 (5 в степени 4), где каждое число означает уникальный вариант перестановки. Переменная permutation (перестановка) и хранит вариант перестановки знаков.

Например, 0 в бинарном виде будет "00 00 00 00 00", что даст нам "++++"; 1 в бинарном виде "00 00 00 00 01" это "+++-", 2 -- "00 00 00 00 10" -- "+++\" и так далее до 1024 -- "11 11 11 11 11" -- "*****".

Цитата Сообщение от M1kloFFi Посмотреть сообщение
как функция int getOperation(long permutation, int position) выбирает знак?
Функция выбирает знак на позиции position из перестановки (permutation) путем вычленения пары бит на позиции position и position + 1.

Делает это она так.
Например, у нас перестановка (permutation) "11 01 10 10 00" ("*-\\+") и мы хотим взять третий знак (premutation = 2).
Создается пара бит на этой позиции с помощью сдвига двух бит влево
(3 << (position * 2)) == "00 00 11 00 00"
Затем применяется битовая операция "И" с перестановкой и полученным выше числом, отсекая ненужные биты:
"11 01 10 10 00" & "00 00 11 00 00" == "00 00 10 00 00"
Затем полученное сдвигается вправо на position * 2 бит, чтобы получить число от нуля до трех:
"00 00 10 00 00" >> (position * 2) == "00 00 00 00 10" (число "2").

Цитата Сообщение от M1kloFFi Посмотреть сообщение
что означают << и >>
Это битовые операторы сдвига.
1
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 27
11.11.2013, 17:02  [ТС] #13
Цитата Сообщение от lemegeton Посмотреть сообщение
Так как знаков всего четыре, то для выражения каждого знака необходимо и достаточно ровно 2-х бит, а для хранения пяти знаков потребуется ровно 10 бит. Это очень хорошо, так как позволит легко и непринужденно перебрать все варианты расстановки знаков с помощью чисел от нуля до 1024 (5 в степени 4), где каждое число означает уникальный вариант перестановки. Переменная permutation (перестановка) и хранит вариант перестановки знаков.

Например, 0 в бинарном виде будет "00 00 00 00 00", что даст нам "++++"; 1 в бинарном виде "00 00 00 00 01" это "+++-", 2 -- "00 00 00 00 10" -- "+++\" и так далее до 1024 -- "11 11 11 11 11" -- "*****".


Функция выбирает знак на позиции position из перестановки (permutation) путем вычленения пары бит на позиции position и position + 1.

Делает это она так.
Например, у нас перестановка (permutation) "11 01 10 10 00" ("*-\\+") и мы хотим взять третий знак (premutation = 2).
Создается пара бит на этой позиции с помощью сдвига двух бит влево
(3 << (position * 2)) == "00 00 11 00 00"
Затем применяется битовая операция "И" с перестановкой и полученным выше числом, отсекая ненужные биты:
"11 01 10 10 00" & "00 00 11 00 00" == "00 00 10 00 00"
Затем полученное сдвигается вправо на position * 2 бит, чтобы получить число от нуля до трех:
"00 00 10 00 00" >> (position * 2) == "00 00 00 00 10" (число "2").


Это битовые операторы сдвига.
Огромное вам спасибо за разъяснение!!! Живите долго и счастливо!!)
0
11.11.2013, 17:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2013, 17:02
Привет! Вот еще темы с ответами:

Проверьте пожалуйста реализацию кода [Мини-скрипт язык] - C++
Встала задача создать структурный язык на подобие xml, для передачи и приёма данных в моём протоколе.. Собственно что должно получится: ...

пытаюсь сделать реализацию через считывание из файла кол-ва чисел, i,но незнаю как сделать реализацию из файла в массив и сортировки. - C++
В файле input.txt находится неизвестное количество вещественных чисел в интервале . Выцапарать их оттуда, отсортировать по убыванию модуля...

Написать свою реализацию deque - C++
Всем привет, требуется написать свою реализацию deque. Я до этого никогда не сталкивался с распределением памяти, аллокаторами и другими...

Написать реализацию перегруженных функций - C++
Написать реализацию перегруженных функций: double func (int * arr, int length); double func (double * arr, int length); Функция...


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

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

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