Считая без приоритета...

Скину в качестве памятки, нужен будет подобный пример рекурсии.

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

Арифметические действия выполняются слева направо без учёта обычного приоритета операций.

Вот листинг консольной программы (Visual Studio):

#include <iostream>
#include <vector>
#include <string>
#include <windows.h>
 
using namespace std;

string str(int n){ //цифра n строкой
 string a = "0";
 a[0] = (char)n;
 return a;
}
 
int eval(vector<int> arr, string expr, int v){ //основной метод
 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.erase(p.begin()); total += eval(p, expr + string("+") + str('0' + sp), v);
  m[1] = m[0] - m[1]; m.erase(m.begin()); total += eval(m, expr + string("-") + str('0' + sm), v);
  mp[1]*=mp[0]; mp.erase(mp.begin()); total+=eval(mp, expr + string("*") + str('0' + smp), v);
 } 
 else {
  if ((arr[0] - arr[1]) == v) { total++; cout<<expr<<"-"<<arr[1]<<endl;}
  if ((arr[0] + arr[1]) == v) { total++; cout<<expr<<"+"<<arr[1]<<endl;}
  if ((arr[0] * arr[1]) == v) { total++; cout<<expr<<"*"<<arr[1]<<endl;}
 }
 return total;
}
 
int main(){
 vector <int> arr; 
 for (int i = 1; i < 10; i++) arr.push_back(i); //массив 1,2,...,9
 string expr = "1";
 int total = eval(arr, expr, 100);
 cout << "total=" << total << endl;
 system("pause");
 return 0;
}

25.06.2015, 18:42 [6690 просмотров]