ブルーブリッジカップの小型計算機-分治法思想+簡単な論理判断(c++実現)
42957 ワード
上のリンク:ブルーブリッジカップの合根植物-そして調査集と親子ノードの法則解の簡略化(c++実現)
リソースの制限
時間制限:1.0 sメモリ制限:256.0 MB
問題の説明
アナログプログラム型計算機は、順次命令を入力し、含まれる可能性のある命令は
1.数字:「NUM X」は、大文字と数字のみを含む文字列であり、前進するときの数を表す.演算指令:‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’は,それぞれ加減算,除法取商,除法取余3を表す.進数変換指令:「CHANGE K」は、進数制をK進数(2≦K≦36)4に変換する.出力指令:「EQUAL」は、前進制出力結果5.リセット命令:「CLEAR」、現在の数値をクリア
命令は以下の規則に従って与えられる:数字、演算命令は連続的に与えられず、進数変換命令、出力命令、リセット命令は演算命令を連続的に与えた後に現れた最初の数字であり、演算に参加した数字を表す可能性がある.また、演算命令とその数字との間には、演算命令と出力命令リセット命令との間に現れる最初の数字が現れず、基礎値を表す.リセット命令と最初の数字の間に演算命令と出力命令の進数変換命令はどこにも現れない
演算中の中間変数はいずれも非負の整数であり、2^63未満である.1035を大文字の「A」「Z」で表す
入力フォーマット
1行目:1 n、命令数2...n+1行目を表す:行ごとに1つの命令が与えられる.命令シーケンスは必ず‘CLEAR’を開始とし、命令ルールを満たす
出力フォーマット
「EQUAL」毎に得られた結果を順次与える
サンプル入力
7 CLEAR NUM 1024 CHANGE 2 ADD NUM 100000 CHANGE 8 EQUAL
サンプル出力
2040
このアルゴリズムの私の考え方次の手順を簡略化しました. 1.命令を分類し,対応する関数を確立する.すなわち、機能モジュール化 2.ある進数の計算に対応するプロセスをすべて10進数のプロセスに変換し、最後に結果を出力するときに10進数の結果数を話し、対応する結果数に変換します.そのため、str_を抽象化しました.to_int. 3は、NUM 100000、NUMに分割され、100000の数字が1つの配列に格納されるなどの命令のセットを分割する.関数はsplit .ヒント:データの計算中、進数は常に変化しているため、対応する進数はまず10進数に変換し、計算します.
プライマリコードの表示
アルゴリズムディスプレイ
以下リンク:ブルーブリッジカップの分試験場-深さ優先遍歴(DFS)+単純論理判断簡略化版(c++実現)
リソースの制限
時間制限:1.0 sメモリ制限:256.0 MB
問題の説明
アナログプログラム型計算機は、順次命令を入力し、含まれる可能性のある命令は
1.数字:「NUM X」は、大文字と数字のみを含む文字列であり、前進するときの数を表す.演算指令:‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’は,それぞれ加減算,除法取商,除法取余3を表す.進数変換指令:「CHANGE K」は、進数制をK進数(2≦K≦36)4に変換する.出力指令:「EQUAL」は、前進制出力結果5.リセット命令:「CLEAR」、現在の数値をクリア
命令は以下の規則に従って与えられる:数字、演算命令は連続的に与えられず、進数変換命令、出力命令、リセット命令は演算命令を連続的に与えた後に現れた最初の数字であり、演算に参加した数字を表す可能性がある.また、演算命令とその数字との間には、演算命令と出力命令リセット命令との間に現れる最初の数字が現れず、基礎値を表す.リセット命令と最初の数字の間に演算命令と出力命令の進数変換命令はどこにも現れない
演算中の中間変数はいずれも非負の整数であり、2^63未満である.1035を大文字の「A」「Z」で表す
入力フォーマット
1行目:1 n、命令数2...n+1行目を表す:行ごとに1つの命令が与えられる.命令シーケンスは必ず‘CLEAR’を開始とし、命令ルールを満たす
出力フォーマット
「EQUAL」毎に得られた結果を順次与える
サンプル入力
7 CLEAR NUM 1024 CHANGE 2 ADD NUM 100000 CHANGE 8 EQUAL
サンプル出力
2040
このアルゴリズムの私の考え方
プライマリコードの表示
int main()
{
int n,i,temp,flag=-1; //n ,i ,temp ,flag
string ins[1000];//
string ins_ad[]={"NUM","ADD","SUB","MUL","DIV","MOD","CHANGE","EQUAL","CLEAR"};
cin>>n;
//
for(i=0;i<n;i++)
{
getline(cin,ins[i]);
}
//
i=0;
while(n>i)
{
split(ins[i]);
//
for(int j = 0;j<sizeof(ins_ad)/sizeof(ins_ad[0]);j++)if(splits[0]==ins_ad[j]) temp = j;
switch(temp)
{
case 0:// NUM 。 NUM flag,
if(flag==-1){result = str_to_int(splits[1]);}
if(flag==1){add(splits[1]);flag=-1;}
if(flag==2){sub(splits[1]);flag=-1;}
if(flag==3){mul(splits[1]);flag=-1;}
if(flag==4){div(splits[1]);flag=-1;}
if(flag==5){mod(splits[1]);flag=-1;}
if(flag==8){result = str_to_int(splits[1]);flag=-1;}
break;
case 1:flag=1;break;
case 2:flag=2;break;
case 3:flag=3;break;
case 4:flag=4;break;
case 5:flag=5;break;
case 6:change(splits[1]);break;
case 7:equal();break;
case 8:flag=8;clear();break;
}
i++;
}
アルゴリズムディスプレイ
#include
#include
#include
#include
#include
using namespace std;
long long result=0;//
string splits[2];//
int k = 10;//
//
void split(string result)
{
int split = result.find(" ");
if(split==-1)
{
splits[0] = result;
}
else
{
splits[0]=result.substr(0,split);
splits[1]=result.substr((split+1),result.size());
}
}
//
long long str_to_int(string result)
{
long long ret = 0;
int flag=0;
if(k==10)
{
stringstream sm;
sm<<result;
sm>>ret;
return ret;
}
for(int i = 0;i<result.size();i++)
{
if(result[i]-'0'>=0&&result[i]-'0'<=9)
{
ret += (result[i]-'0')*(long long)pow(k,result.size()-i-1);
flag++;
}else ret += (result[i]-'A'+10)*(long long)pow(k,result.size()-i-1);
}
return ret;
}
//
void add(string beadd){result+=str_to_int(beadd); }
void sub(string besub){result-=str_to_int(besub); }
void mul(string bemul){result*=str_to_int(bemul); }
void div(string bediv){result/=str_to_int(bediv); }
void mod(string bemod){result%=str_to_int(bemod); }
//
void change(string K)
{
stringstream sm;
sm<<K;
sm>>k;
}
//
void equal()
{
string s;
// result k
while(result)
{
s+=(char)(result%k>=0&&result%k<=9)?result%k+'0':result%k-10+'A';
result/=k;
}
// k ,
for(int i = s.size()-1;i>=0;i--)
{
cout<<s[i];
}
cout<<endl;
}
//
void clear(){result = 0;}
int main()
{
int n,i,temp,flag=-1; //n ,i ,temp ,flag
string ins[1000];//
string ins_ad[]={"NUM","ADD","SUB","MUL","DIV","MOD","CHANGE","EQUAL","CLEAR"};
cin>>n;
//
for(i=0;i<n;i++)
{
getline(cin,ins[i]);
}
//
i=0;
while(n>i)
{
split(ins[i]);
//
for(int j = 0;j<sizeof(ins_ad)/sizeof(ins_ad[0]);j++)if(splits[0]==ins_ad[j]) temp = j;
switch(temp)
{
case 0:// NUM 。 NUM flag,
if(flag==-1){result = str_to_int(splits[1]);}
if(flag==1){add(splits[1]);flag=-1;}
if(flag==2){sub(splits[1]);flag=-1;}
if(flag==3){mul(splits[1]);flag=-1;}
if(flag==4){div(splits[1]);flag=-1;}
if(flag==5){mod(splits[1]);flag=-1;}
if(flag==8){result = str_to_int(splits[1]);flag=-1;}
break;
case 1:flag=1;break;
case 2:flag=2;break;
case 3:flag=3;break;
case 4:flag=4;break;
case 5:flag=5;break;
case 6:change(splits[1]);break;
case 7:equal();break;
case 8:flag=8;clear();break;
}
i++;
}
return 0;
}
以下リンク:ブルーブリッジカップの分試験場-深さ優先遍歴(DFS)+単純論理判断簡略化版(c++実現)