繼上次采用形式文法來生成混合運算的算式,由于算法中沒有引入控制參數而導緻容易産生形式累贅(多餘的括号等)的算式。本次更新決定采用一種更為簡單有效的生成方式,由給出的一個随機的最終答案S,通過給定的一個基本運算(加減乘除)将數字分解為兩個數a,b,使得這兩個數的運算結果為之前的數S,那麼a,b分别可按同樣的規則進行拆分,如此反複多次便可得到一個混合運算算式。這個過程實際上也是二叉樹的生成過程,也是我們相當熟悉的算法了。當然,為了生成正确的算式還是需要解決一基本些問題的。
問題1:使數S按某一運算拆解,那麼應該如何去拆解?
分析:對數字實作按某運算實作拆解,無疑我們的讨論範圍隻有加減乘除了,那麼隻需對四種情況分别設計相應的算法最終打包即可。注:本次算法僅實作正整數運算拆解。
⑴加法:S=a+b,那麼令 a=rand()%S,b=S-a 即可;特殊地,S=0 時 a=b=0 ;
⑵減法:S=a-b,那麼令 a=S+rand()%N (N>0),b=a-s 即可;特殊地,S=0 時 a=b=C (C是大于零的常數);
⑶除法:S=a/b,那麼令 a=S*(1+rand()%N),b=a/s 即可;特殊地,S=0 時 a=0,b=C1(C1是大于零的常數);
⑷乘法:既然把乘法放到最後,那麼可想而知實作起來是有點麻煩了。
S=a*b,那麼意味着 a,b 都是S的因子,那麼如何随機地獲得一組S的因子呢?
首先,最簡單的方法是我們可以用枚舉法來獲得S的所有因子:
for(i=i;i<S;i++) //枚舉,這個算法會得到重複的因子組合
if(!(S%i)) //能否除盡
cout<<i<<endl; //列印因子
假設已經獲得S的n個因子,那麼我們隻需要等可能地從這n個因子中随機選擇一個a,那麼 b=S/a 即可。
鑒于本人懶╮(╯∇╰)╭,我采用如下算法:
for(i=1;i<S;i++)
if(!(S%i))
if(rand()%2) //這樣做的壞處是對于S的所有因子而言,a取到1的機率最大,嘛~~╮(╯_╰)╭,下個版本再改進吧。
break;
a=i,b=S/i;
特殊地,S=0 時,a or b=0即可。
分裝後的函數:
/* Random split */
void OP_Decompose(Operator OP,int &a,int &b,int num) //分别用 0,1,2,3 來代表加、減、乘、除 typedef unsigned char Operator
{
switch(OP)
{
case 0:// +
{
if(num)
{
a=rand()%(num+1);
b=num-a;
}
else a=b=0;
}break;
case 1:// -
a=num+rand()%100;
b=a-num;
else a=b=rand()%100;
case 2:// *
int i;
for(i=1;i<num;i++)
if(!(num%i))
if(rand()%2)
a=i,b=num/i;
else
if(rand()%2)
a=rand()%100,b=0;
else
b=rand()%100,a=0;
case 3:// /
a=num*(1+rand()%10+rand()%10);
b=a/num;
a=0,b=rand()%100+1;
}
}
}
通過上述讨論,拆解問題就此告一段落了,其實也是整個程式中的核心問題之一吧(,,#゚Д゚)。
問題2:之前說過了是以二叉樹生成的方式來産生算式,那麼如果父節點的運算符優先級高于子節點的運算符,但實際上是先計算子節點的,那麼就需要括号介入了。
分析:如果在生成二叉樹的過程中,以先建立好父節點的所有資料資訊再分别遞歸構造子節點的方式生成,若父節點對子節點有某些要求,那麼隻需要通過參數傳遞來限制子節點的建立。即,當父節點在構造子節點時将自己的運算符告訴子節點,然後子節點通過對比與父節點的運算優先級來決策是否添加括号。而在對比優先級時,我們隻需要考慮父節點的優先級是否高于子節點,無需關心孰高孰低。在上一個問題中,我們定義了加減乘除的代号分别為0,1,2,3 ,觀察發現0,1的二進制數高位為0,而2,3的二進制數高位為1,那麼隻需要對高位進行對比即可。便有如下宏定義:
#define OA 0 //加法
#define OS 1 //減法
#define OM 2 //乘法
#define OD 3 //除法
#define JUD_Priority(OP1,OP2) (((Operator)(OP1)>>1<(Operator)(OP2)>>1)?true:false) //當且僅當OP2優先級高于OP1時傳回1
到這裡,需要面臨的也就是遞歸下降生成的最後問題了。( ̄- ̄)
問題3:形式控制之算符偏好與數量(遞歸深度)。
所謂偏好,就是指在生成的式子裡某種運算出現的頻率高低。而數量就是一道算式裡出現的算符個數。
分析:首先來考慮偏好吧,回顧我們最初的需求是随機地産生混合運算題目,那麼這個随機既代表了算數的随機也代表了算符的随機。基于上述讨論中的按算符拆分原則,每次拆解一個數的時候我們需要随機的選擇一個算符(也就是本節點的算符),即每個節點都會為自己随機産生一個算符,最終的題目在邏輯上是這些節點連成的二叉樹。如果在每次選擇算符的時候引入機率,那麼當生成很多道題目的時候在每種運算出現的頻率上就可以展現出偏好了。以最簡單的情況為例,如果算符選擇的機率是一定的,我們之需要分裝一個函數來實作選擇就可以了。當然,為了讓這個函數能參與更多的子程式編寫,這裡采用不定參數實作:
#include <cstdarg>
/* Random selection */
int PR_Select(unsigned int n=1,...) //實作n個數分别按機率P1,P2...Pn的随機選擇
if(!n) return 0;
va_list ap;
va_start(ap,n);
float p=0.0f,*pn=new float[n];
if(!pn) return -1;
int i,j=0;
for(i=0;i<n;i++)
p+=pn[i]=(float)va_arg(ap,double);
if(p-1>=-1e-5&&p-1<=1e-5)
float pbt=((float)rand())/((float)RAND_MAX); //#define RAND_MAX 0x7fff 包含在stdlib.h
float ff;
for(i=0,ff=0.0f;i<n;ff+=pn[i],i++)
{
if(pbt>=ff&&pbt<ff+pn[i])
{
j=i+1;
break;
}
}
delete [] pn;
return j;
/* Random operator */
inline int OP_Select(float p1,float p2,float p3,float p4) //随機選擇一個算符,機率分别為p1,p2,p3,p4
return PR_Select(4,p1,p2,p3,p4)-1;
最後,為什麼需要考慮算符數量?先來考慮函數的遞歸;終止條件是遞歸函數必須具備的,在遞歸生成算式的時候,遞歸何時終止将直接影響所生成算式的長度。在邏輯上看,算符的數量決定了二叉樹的非葉子節點個數,同時它又影響着葉子節點的個數。直覺地,随着非葉子節點的增加,葉子節點的數量與非葉子節點的數量呈正相關,可見控制非葉子節點的數量即控制了總節點的數量,即算式的長度。假設用一個參數OP_num來表示算式中出現的算符個數,那麼如何引入該參數呢?
分析:
設函數 void func(...) 為遞歸函數,它将實作生成一個算符數量為OP_num并且計算結果為num的算式。那麼我們就确定了它需要OP_num和num作為參數。同時,因為是遞歸調用的,回顧問題2可知還需要一個供括号決策的Operator型參數Parent。
那麼函數聲明為:void func(Operator Parent,int num,OP_num);
顯然參數Parent和num對遞歸深度無影響。
定義:OP_num=0 時,函數将直接列印num并傳回;即表示不需要對num進行任何拆分。
當 OP_num>0 時,首先對num進行了一次拆分獲得a,b,OP_num減一;當OP_num不為0就意味着a,b可以用OP_num(已經減一)個算符去拆分,此時我們可以将OP_num以加法拆分為兩個數n1,n2(問題1所分裝的函數中已表明對0的加法拆分依然是兩個0),那麼對a,b分别遞歸調用就可以了。最終分裝函數如下:
/* probability of operators */
#define PO_A 0.35f
#define PO_S 0.35f
#define PO_M 0.2f
#define PO_D 0.1f
#include <iostream>
/* Output operator */
void OP_print(Operator OP)
case 0: cout<<"+";break;
case 1: cout<<"-";break;
case 2: cout<<"×";break;
case 3: cout<<"÷";break;
/* Produce formula */
void FormulaGenerator(Operator Parent,int num,int OP_num)
if(!OP_num)
cout<<num;
return;
Operator here=OP_Select(PO_A,PO_S,PO_M,PO_D);
int a,b,OP_n1,OP_n2;
OP_num--;
OP_Decompose(here,a,b,num);
OP_Decompose(0,OP_n1,OP_n2,OP_num);
if(JUD_Priority(here,Parent)) //括号決策
cout<<"(";
FormulaGenerator(here,a,OP_n1);
OP_print(here);
FormulaGenerator(here,b,OP_n2);
cout<<")";
else
至此,整個生産算符就實作完畢了,如下是效果圖:
可見這次程式相比上次對算式形式的控制更加精确,目前就這樣吧,更多功能及優化将在後續版本實作。2016/3/14