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

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

Восстановить пароль Регистрация
 
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 23
10.11.2013, 14:36     Подскажите пожалуйста как написать реализацию алгоритма #1
Добрый день.
Столкнулся с заданием описанным ниже, ломаю голову уже несколько дней. Додумался сделать данное задание с помощью операции перебора(если есть какое то другое решение данной задачи подскажите пожалуйста), но возникли трудности:
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 ;
                    }
                }
 
            }
        }
    }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2013, 14:36     Подскажите пожалуйста как написать реализацию алгоритма
Посмотрите здесь:

Выкладываю реализацию алгоритма Дейкстры на С++ C++
Подскажите ,пожалуйста,как отобразить схему алгоритма оператора свитч в с++? нигде не могу найти корректного ответа( C++
C++ пытаюсь сделать реализацию через считывание из файла кол-ва чисел, i,но незнаю как сделать реализацию из файла в массив и сортировки.
C++ Подскажите пожалуйста как написать программу, которая считывает текст
Подскажите реализацию умножения многочлена на моном C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Folko
 Аватар для Folko
265 / 253 / 7
Регистрация: 27.09.2013
Сообщений: 877
Записей в блоге: 1
10.11.2013, 14:51     Подскажите пожалуйста как написать реализацию алгоритма #2
M1kloFFi, конкретно по замене символа: создаете массив char и там записываете все нужные символы
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
10.11.2013, 19:01     Подскажите пожалуйста как написать реализацию алгоритма #3
backtrack / перебор с откатом писать умеете?
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 23
10.11.2013, 20:47  [ТС]     Подскажите пожалуйста как написать реализацию алгоритма #4
Цитата Сообщение от salam Посмотреть сообщение
backtrack / перебор с откатом писать умеете?
Нет, не умею.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
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;
}
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 23
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;
}
Спасибо, помощь!!! Но прога выбивает ошибки, ошибки в скрине
Миниатюры
Подскажите пожалуйста как написать реализацию алгоритма  
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
10.11.2013, 21:51     Подскажите пожалуйста как написать реализацию алгоритма #7
На скриншоте другой код. Вы поменяли мой код, не имея представления, что вы делаете? Верните как было.
Ryuk
 Аватар для Ryuk
179 / 177 / 33
Регистрация: 10.06.2011
Сообщений: 869
10.11.2013, 21:59     Подскажите пожалуйста как написать реализацию алгоритма #8
salam, что-то стало интересно, что за перебор такой?
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 23
10.11.2013, 22:03  [ТС]     Подскажите пожалуйста как написать реализацию алгоритма #9
Цитата Сообщение от lemegeton Посмотреть сообщение
На скриншоте другой код. Вы поменяли мой код, не имея представления, что вы делаете? Верните как было.
В данных местах ругается.
Миниатюры
Подскажите пожалуйста как написать реализацию алгоритма   Подскажите пожалуйста как написать реализацию алгоритма  
Max Dark
В поиске работы
 Аватар для Max Dark
1546 / 1399 / 501
Регистрация: 09.10.2013
Сообщений: 3,185
Записей в блоге: 8
Завершенные тесты: 2
10.11.2013, 22:12     Подскажите пожалуйста как написать реализацию алгоритма #10
C++
1
#include <string>
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 23
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); - что означают << и >> ??
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
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 Посмотреть сообщение
что означают << и >>
Это битовые операторы сдвига.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2013, 17:02     Подскажите пожалуйста как написать реализацию алгоритма
Еще ссылки по теме:

C++ Проверьте пожалуйста реализацию кода [Мини-скрипт язык]
C++ Подскажите пожалуйста как написать консольное приложение win32, которое принимает на вход путь к папке
C++ Подскажите реализацию конструктора копирования

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

Или воспользуйтесь поиском по форуму:
M1kloFFi
0 / 0 / 0
Регистрация: 14.10.2012
Сообщений: 23
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").


Это битовые операторы сдвига.
Огромное вам спасибо за разъяснение!!! Живите долго и счастливо!!)
Yandex
Объявления
11.11.2013, 17:02     Подскажите пожалуйста как написать реализацию алгоритма
Ответ Создать тему
Опции темы

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