?? 無優先級運算問題.cpp
字號:
#include <iostream>
using namespace std;
#include <string>
#include <cstring>
#include <fstream>
#include <vector>
int *x,*s; // 讀入數據 s是表示各個數的狀態,stats簡稱
int n,m,k; // k = n
int *a;
char *b;
int res=1000000; // 輸出結果
int isModify = 0;
int record = 0; // ·記錄第一次所取數的下標
void ReadData();
void process();
void output();
void backTrack(int time,int *no,char *sn,double result);
int main(int argc, char* argv[])
{
ReadData(); // 讀取數據
process(); // 對數據處理
output(); // 輸出結果
return 0;
}
void process()
{
int *no; // 記錄排列時需要記錄的數
char *sn; // 記錄排列時需要記錄的符號
no = new int[k+1];
sn = new char[k+1];
a = new int[k+1];
b = new char[k+1];
res = 4 ; // ·增量式搜索,回溯,即剪枝的策略三
int i =0;
while(true){
i++;
res +=2; // ·增量式搜索,回溯,即剪枝的策略三
for(int i =1;i<=k;i++) // 從第一層開始,即從n個數開始記數
{
record = i;
no[1] = x[i]; // 記錄第1個數
s[i] = 1; // 表明剛才記錄的數的狀態是已經記錄的
backTrack(1,no,sn,x[i]); // 回溯開始了
s[i] = 0; // 現場恢復
}
if ((isModify == 1)||(res>n)) return;
}
}
void ReadData()
{
ifstream inStream;
inStream.open("input.txt");
if(!inStream )
{
cerr << "Error open file.\n";
return;
}
inStream>>n;
inStream>>m;
k = n;
x=new int[2*n+1];
s=new int[n+1];
for(int i =1;i<=n;i++)
{
inStream>>x[i];
}
for(i = 1;i<=n;i++)
{
s[i] =0;
}
for(i=1;i<=n;i++)
{
x[n+i]=x[i];
}
}
void output()
{
ofstream outStream;
outStream.open("output.txt");
if(!outStream)
{
cerr << "Error open file.\n";
return;
}
for(int i =1;i<k;i++)
{
if(x[i]==m)
{
outStream<<0<<endl;
outStream<<x[i];
return;
}
}
if (isModify==0) {outStream<<"NO SOLUTION";return;}
outStream<<res<<endl;
outStream<<a[1];
for( i=1;i<=res;i++)
outStream<<b[i]<<a[i+1];
cout<<res<<endl;
cout<<a[1];
for( i=1;i<=res;i++)
cout<<b[i]<<a[i+1];
cout<<endl;
}
void backTrack(int time,int *no,char *sn,double result)
{ // time:層數,no:記錄數, sn:記錄符號,result:上次計算的結果
int i = 1;
if ( time >= k ) return; // 1.回溯返回的條件
if (time>=res) return;
for(i=1;i<=k;i++) // 2.對所有的數再進行操作
{
if ((s[i]==0)) // 2.1第一個判斷其狀態是否已經記錄過,
{
if (result+x[i] !=m)
{
if (!((time==1)&&(record>i))){ // ·對應剪枝的策略二
if (!((isModify==1)&&(time>=res-1))) // ·對應剪枝的策略一
{
no[time+1] = x[i]; //2.2.1 不等m,就記錄該樹及符號,繼續往下找,層次加1
sn[time] = '+';
s[i] = 1;
backTrack(time+1,no,sn,result+x[i]);
}
}
}else{
if (time<res) //2.2.2 等于m,判斷其層次是否最短,最短就記錄該數及符號,
{ // 再把記錄的數及符號使用a,b保留起來
res = time; // 以下其他操作類似
no[time+1] = x[i];
isModify = 1;
sn[time] = '+';
a[1] = no[1];
for(int j =1;j<=time;j++)
{
a[j+1] = no[j+1];
b[j] = sn[j];
}
return;
}
}
s[i] = 0; //2.3 現場恢復
if (result-x[i] !=m)
{
if(!((isModify==1)&&(time>=res-1))){
no[time+1] = x[i];
sn[time] = '-';
s[i] = 1;
backTrack(time+1,no,sn,result-x[i]);
}
}else{
if (time<res)
{
res = time;
no[time+1] = x[i];
sn[time] = '-';
isModify = 1;
a[1] = no[1];
for(int j =1;j<=time;j++)
{
a[j+1] = no[j+1];
b[j] = sn[j];
}
return;
}
}
s[i] = 0;
if (result*x[i] !=m)
{
if (!((time==1)&&(record>i))){
if(!((isModify==1)&&(time>=res-1))){
no[time+1] = x[i];
sn[time] = '*';
s[i] = 1;
backTrack(time+1,no,sn,result*x[i]);
}
}
}else{
if (time<res)
{
res = time;
no[time+1] = x[i];
sn[time] = '*';
isModify = 1;
a[1] = no[1];
for(int j =1;j<=time;j++)
{
a[j+1] = no[j+1];
b[j] = sn[j];
}
return;
}
}
s[i] = 0;
if (result/x[i] !=m)
{
if(!((isModify==1)&&(time>=res-1))){
no[time+1] = x[i];
sn[time] = '/';
s[i] = 1;
backTrack(time+1,no,sn,result/x[i]);
}
}else{
if (time<res)
{
res = time;
no[time+1] = x[i];
sn[time] = '/';
isModify = 1;
a[1] = no[1];
for(int j =1;j<=time;j++)
{
a[j+1] = no[j+1];
b[j] = sn[j];
}
return;
}
}
s[i] = 0;
}
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -