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

@M1kloFFi · Регистрация: 14.10.2012

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

Добрый день.
Столкнулся с заданием описанным ниже, ломаю голову уже несколько дней. Додумался сделать данное задание с помощью операции перебора(если есть какое то другое решение данной задачи подскажите пожалуйста), но возникли трудности:
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 ;
                    }
                }
 
            }
        }
    }

@Folko · 10.11.2013, 14:51

M1kloFFi, конкретно по замене символа: создаете массив char и там записываете все нужные символы

@salam · 10.11.2013, 19:01

backtrack / перебор с откатом писать умеете?

@M1kloFFi · 10.11.2013, 20:47 **[ТС]**

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

backtrack / перебор с откатом писать умеете?

Нет, не умею.

@lemegeton · 10.11.2013, 21:33

Тут всего 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;
}

@M1kloFFi · 10.11.2013, 21:47 **[ТС]**

Сообщение от 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;
}

Спасибо, помощь!!! Но прога выбивает ошибки, ошибки в скрине

@lemegeton · 10.11.2013, 21:51

На скриншоте другой код. Вы поменяли мой код, не имея представления, что вы делаете? Верните как было.

@Ryuk · 10.11.2013, 21:59

salam, что-то стало интересно, что за перебор такой?

@M1kloFFi · 10.11.2013, 22:03 **[ТС]**

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

На скриншоте другой код. Вы поменяли мой код, не имея представления, что вы делаете? Верните как было.

В данных местах ругается.

@Max Dark · 10.11.2013, 22:12

C++
1
#include <string>

@M1kloFFi · 10.11.2013, 22:56 **[ТС]**

Сообщение от 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); - что означают << и >> ??

@lemegeton · 11.11.2013, 08:44

Сообщение от 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

что означают << и >>

Это битовые операторы сдвига.

@M1kloFFi · 11.11.2013, 17:02 **[ТС]**

Сообщение от 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").

Это битовые операторы сдвига.

Огромное вам спасибо за разъяснение!!! Живите долго и счастливо!!)

Новые блоги и статьи Все статьи Все блоги /
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.

@Folko 267 / 255 / 27 Регистрация: 27.09.2013 Сообщений: 876 Записей в блоге: 1
	10.11.2013, 14:51
	M1kloFFi, конкретно по замене символа: создаете массив char и там записываете все нужные символы 1

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	10.11.2013, 19:01
	backtrack / перебор с откатом писать умеете? 0

@lemegeton 4903 / 2696 / 921 Регистрация: 29.11.2010 Сообщений: 5,783
	10.11.2013, 21:51
	На скриншоте другой код. Вы поменяли мой код, не имея представления, что вы делаете? Верните как было. 1

@Ryuk 183 / 182 / 56 Регистрация: 10.06.2011 Сообщений: 871
	10.11.2013, 21:59
	salam, что-то стало интересно, что за перебор такой? 0