おはようございます。フジワラです。
今日は、123456789の数字の間に+,-をいれて、計算結果が100になるようにするプログラムをc++で書いてみようと思います。
具体例としては、
123+45-678+9
みたいな形です。
いわゆる、小町算というやつです。小町数と混同しないでください
今回は、×、÷、数字の並べ替えは考えないでやりたいと思います。
考え方
123456789の間に+,-を入れるか入れないということは、それぞれの数字の間に3通りの状態(+,-もしくはどちらもいれない)があることになります。
つまり、123456789の間に+,-を入れる方法は、\(3^8\)通りあるということになります。
で、これを3進数8桁で表します。(0の時は間に何も入れない、1の時は間に+を入れる、2の時は間に-を入れる処理として考えます。)
とりあえず、コード
</pre>
#include<iostream>
#include<math.h>
using namespace std;
void plus3(int* a, int n){
a[n]=a[n]+1;
if(a[n]==3){
a[n]=a[n]%3;
plus3(a, n+1);
}
}
int main(void){
int a[9]={0};
int komati[9]={1,2,3,4,5,6,7,8,9};
int buf[10]={0};
while(1){
int x=0;
int n=0;
int y=0;
for(int i=0;i<10;i++){
buf[i]=0;
};
plus3(a, 0);
buf[0]=komati[0];
if(a[8]==1){
break;
}
for(int i=0;i<=7;i++){
if(a[i]==0){
buf[n]=buf[n]*10+komati[x+1];
x=x+1;
}else{
n=n+1;
buf[n]=komati[x+1];
x=x+1;
}
if(x==8){
break;
}
}
y=buf[0];
n=0;
for(int i=0;i<=7;i++){
if(a[i]==1){
y=y+buf[n+1];
n=n+1;
}else if(a[i]==2){
y=y-buf[n+1];
n=n+1;
}
}
if(y==100){
cout<<"komatisuuha "<<1;
for(int i=0;i<=7;i++){
if(a[i]==0){
cout<<i+2;
}
else if(a[i]==1){
cout<<"+";
cout<<i+2;
}else if(a[i]==2){
cout<<"-";
cout<<i+2;
}
}cout<<endl;
}
}
return 0;
}
<pre>
コードの解説
まず、main関数内でint型の配列のa[9]とkomati[9]とbuf[10]を宣言しています。
a[9]は「+,-,何も入れない」の123456789の間の+-の有無の状態を表す3進数8桁を表すものです。一番最初の状態が{0,0,0,0,0,0,0,0,0}で1を足し続けた最終の状態は{2,2,2,2,2,2,2,2,2}です。
komati[9]は、それぞれに{1,2,3,4,5,6,7,8,9}をぶち込んで、123456789を表しています。
buf[10]は、例えば、123+45-6-789としたときに、配列bufにそれぞれ、123、45、6、789をぶち込んで後で計算するために使うものです。
void plus3関数は、3進数の数字に、1を足す処理をするための関数で、第一引数に、1を足したい3進数、第二引数に、1を足す場所(3進数の計算で繰り上がりの処理のためにつけてるだけです。他にもいい方法があると思います。)
一回この関数を呼び出すと、引数として与えられた3進数に1を足した結果を新たに、引数として与えられた3進数を上書きします。つまり、与えた3進数に1を足した結果が得られるものです。
余談：plusで関数を定義すると、c++の標準の関数にもplusがあるので、オーバーロードしないと使えません.
今回は、3進数8桁で+,-の組み合わせを考えているので、8桁目が繰り上がって9桁めが1になったら、\(3^8\)通りの組み合わせはすべて出ていることになるので終了します。
if(a[8]==1){ break; }
while内の処理
while(1){
int x=0;
int n=0;
int y=0;
for(int i=0;i<10;i++){
buf[i]=0; //bufの初期化
};
plus3(a, 0); //3進数に1を足す処理
buf[0]=komati[0];
if(a[8]==1){
break;
}
//bufにそれぞれの値を代入する
for(int i=0;i<=7;i++){
if(a[i]==0){ //+-を間に入れないときは隣り合う数字を結合する
buf[n]=buf[n]*10+komati[x+1];
x=x+1;
}else{
n=n+1;
buf[n]=komati[x+1];
x=x+1;
}
if(x==8){//komatiの最後の項9まで行ったら処理終了
break;
}
}
y=buf[0];
//buf同士の計算
n=0;
for(int i=0;i<=7;i++){
if(a[i]==1){
y=y+buf[n+1];
n=n+1;
}else if(a[i]==2){
y=y-buf[n+1];
n=n+1;
}
}
if(y==100){//結果が100となるときに表示
cout<<"komatisuuha "<<1;
for(int i=0;i<=7;i++){
if(a[i]==0){
cout<<i+2;
}
else if(a[i]==1){
cout<<"+";
cout<<i+2;
}else if(a[i]==2){
cout<<"-";
cout<<i+2;
}
}cout<<endl;
}
}
実行結果
実行結果は、
komatisuuha 123-45-67+89
komatisuuha 12-3-4+5-6+7+89
komatisuuha 12+3+4+5-6-7+89
komatisuuha 123+4-5+67-89
komatisuuha 1+2+3-4+5+6+78+9
komatisuuha 12+3-4+5+67+8+9
komatisuuha 1+23-4+56+7+8+9
komatisuuha 1+2+34-5+67-8+9
komatisuuha 1+23-4+5+6+78-9
komatisuuha 123+45-67+8-9
komatisuuha 123-4-5-6-7+8-9
となります。確かに全部100になってますね。