一、4數種類分析 統計分析 從標有1-10的數字的10個小球中取出1個小球記錄小球的數字,然後將小球放回,如此反覆4次取出4小球的數字組成的序號一共有多少種。註意:1.1.8.9 和1.8.1.9 算是一種。 需要分為一下幾種情況: 四個小球數字都相等情況: 一個有10種 三個小球數字相等: 一共 ...
一、4數種類分析
統計分析
從標有1-10的數字的10個小球中取出1個小球記錄小球的數字,然後將小球放回,如此反覆4次取出4小球的數字組成的序號一共有多少種。註意:1.1.8.9 和1.8.1.9 算是一種。
需要分為一下幾種情況:
- 四個小球數字都相等情況:
一個有10種
- 三個小球數字相等:
一共有10*9種 = 90
- 兩個小球數字相等,另外兩個小球數字不相等
一共有10 * ( 9 * 8 /2 )種 = 360
10表示:10個相等的兩個小球
( 9 * 8 /2 )表示:另外兩個小球不相等的情況。
- 兩個小球數字相等,另外兩個小球也相等。
一共有(10*9)/2 中 = 45
- 四個小球數字都不想等
總數為=10 + 90 + 360 + 45 + 210 = 715
代碼分析
代碼中我們可以直接使用遍歷的方式進行窮舉,
1 . 對比記錄列表中的數據是否存在,如果存在就忽略。
2. 如果不存在就添加到列表中。
遍歷所有的數據。
#define MAXNUM 10 QList<struNum> initList() { QList<struNum> list; for (int i1 = 1;i1 <= MAXNUM; i1++) { for (int i2 = 1;i2 <= MAXNUM; i2++) { for (int i3 = 1;i3 <= MAXNUM; i3++) { for (int i4 = 1;i4 <= MAXNUM; i4++) { struNum num(i1,i2,i3,i4); if(!isInList(num,list)){ list.append(num); } } } } } return list; }
判斷是否存在列表中
typedef struct SNUM{ SNUM(int num1,int num2,int num3,int num4){ this->num1 = num1; this->num2 = num2; this->num3 = num3; this->num4 = num4; } int num1 =0; int num2 =0; int num3 =0; int num4 =0; int c = 0; // 四個數能夠計算24演算法。 }struNum; bool isInList(struNum num, QList<struNum> list) { int numList[4] = {num.num1,num.num2,num.num3,num.num4}; bool result = false; for (int i1 = 0 ; i1 < 4; i1 ++) { for (int i2 = 0 ; i2 < 4; i2 ++){ if(i1 == i2) continue; for (int i3 = 0 ; i3 < 4; i3 ++){ if(i2 == i3 || i1 == i3) continue; for (int i4 = 0 ; i4 < 4; i4 ++){ if(i1 == i4 || i2 == i4 || i3 == i4) continue; foreach(auto item ,list){ if(item.num1 == numList[i1] && item.num2 == numList[i2] && item.num3 == numList[i3] && item.num4 == numList[i4]){ result = true; } } } } } } return result; }
二、四數排列演算法分析
4個數按照順序排列,一共有多少種排列方法。
我們可以使用遍歷方法,將所有的數字進行遍歷,那麼可以得到一下演算法。可以看到以下演算法的步驟需要經過4*4*4*4 次運算。那麼我們通過觀察可以優化代碼演算法。
優化前
4*4*4*4 = 256次運算
int numList[4] = {num1,num2,num3,num4}; for (int i1 = 0 ; i1 < 4; i1 ++) { for (int i2 = 0 ; i2 < 4; i2 ++){ for (int i3 = 0 ; i3 < 4; i3 ++){ for (int i4 = 0 ; i4 < 4; i4 ++){ if(i1 != i2 && i1 != i3 && i1 != i4 && i2 != i3 && i2 != i4 && i3 != i4){ qInfo()<<numList[i1]<<" "<<numList[i2] <<" "<< numList[i3] <<" "<<" "<< numList[i4]; c++; } } } } } 點擊並拖拽以移動
優化後
4*3*2 = 24 次運算。
1 int numList[4] = {num1,num2,num3,num4}; 2 int c =0; 3 for (int i1 = 0 ; i1 < 4; i1 ++) { 4 for (int i2 = 0 ; i2 < 4; i2 ++){ 5 if(i1 == i2) continue; 6 for (int i3 = 0 ; i3 < 4; i3 ++){ 7 if(i2 == i3 || i1 == i3) continue; 8 for (int i4 = 0 ; i4 < 4; i4 ++){ 9 if(i1 == i4 || i2 == i4 || i3 == i4) continue; 10 qInfo()<<numList[i1]<<" "<<numList[i2] <<" "<< numList[i3] <<" "<<" "<< numList[i4]; 11 c++; 12 } 13 } 14 } 15 }
三、分數計算類
由於計算過程中可能會遇到分數計算,因此我們不能使用int類型直接表示數據,或者是數據運算結果,我們定義一個分數類,專門用來計算分數的,加、減、乘、除,這樣可以儘可能保存數據的正確性。
加法
減法
乘法
除法
LNum.h
1 #ifndef LNUM_H 2 #define LNUM_H 3 4 class LNum 5 { 6 7 public: 8 LNum(int Molecule); 9 LNum(int Molecule,int Denominator); 10 int getMolecule(); // 獲取分子 11 int getDenominator(); // 獲取分母 12 void setMolecule(int molecule); // 設置分子 13 void setDenominator(int denominator);// 設置分母 14 double data(); 15 LNum operator + ( LNum p1); 16 LNum operator - ( LNum p1); 17 LNum operator * ( LNum p1); 18 LNum operator / ( LNum p1); 19 bool operator ==( LNum p1) ; 20 private: 21 // 分子 22 int m_iMolecule = 1; 23 // 分母 24 int m_iDenominator = 1; 25 void Equivalency(); // 約分 26 27 }; 28 29 #endif // LNUM_H
LNum.cpp
1 #include "lnum.h" 2 3 4 LNum::LNum(int num) 5 :m_iMolecule(num) 6 ,m_iDenominator(1) 7 { 8 9 } 10 11 LNum::LNum(int Molecule, int Denominator) 12 :m_iMolecule(Molecule) 13 ,m_iDenominator(Denominator) 14 { 15 16 } 17 18 int LNum::getMolecule() 19 { 20 Equivalency(); 21 return m_iMolecule; 22 } 23 24 int LNum::getDenominator() 25 { 26 Equivalency(); 27 return m_iDenominator; 28 } 29 30 void LNum::setMolecule(int molecule) 31 { 32 m_iMolecule = molecule; 33 } 34 35 void LNum::setDenominator(int denominator) 36 { 37 m_iDenominator = denominator; 38 } 39 40 double LNum::data() 41 { 42 Equivalency(); 43 if(m_iDenominator == 1){ 44 return m_iMolecule; 45 } 46 return double(m_iMolecule)/double(m_iDenominator); 47 } 48 49 void LNum::Equivalency() 50 { 51 int num = m_iMolecule> m_iDenominator?m_iDenominator:m_iMolecule; 52 53 for (int i = 2 ; i < num ;i++) { 54 if(m_iDenominator%i == 0 && m_iMolecule%i ==0){ 55 m_iDenominator = m_iDenominator/i; 56 m_iMolecule = m_iMolecule/i; 57 num = m_iMolecule> m_iDenominator?m_iDenominator:m_iMolecule; 58 } 59 } 60 } 61 62 LNum LNum::operator +(LNum p1) 63 { 64 LNum res(getMolecule(),getDenominator()); 65 res.setMolecule(getMolecule()*p1.getDenominator() + getDenominator()*p1.getMolecule()); 66 res.setDenominator(getDenominator()*p1.getDenominator()); 67 return res; 68 } 69 70 LNum LNum::operator -(LNum p1) 71 { 72 LNum res(getMolecule(),getDenominator()); 73 res.setMolecule(getMolecule()*p1.getDenominator() - getDenominator()*p1.getMolecule()); 74 res.setDenominator(getDenominator()*p1.getDenominator()); 75 return res; 76 } 77 78 LNum LNum::operator *(LNum p1) 79 { 80 LNum res(getMolecule(),getDenominator()); 81 res.setMolecule(getMolecule()*p1.getMolecule()); 82 res.setDenominator(getDenominator()*p1.getDenominator()); 83 return res; 84 } 85 86 LNum LNum::operator /(LNum p1) 87 { 88 LNum res(getMolecule(),getDenominator()); 89 res.setMolecule(getMolecule()*p1.getDenominator()); 90 res.setDenominator(getDenominator()*p1.getMolecule()); 91 return res; 92 } 93 94 bool LNum::operator ==(LNum p1) 95 { 96 if (getMolecule() == p1.getMolecule() && getDenominator() == p1.getDenominator()) { 97 return true; 98 } 99 else{ 100 return false; 101 } 102 103 }
四、加減乘除操作符遍歷
第一步將操作符數字化,方便遍歷。可以得到如下公式。x為操作符標識。
1 double jisuan(LNum num1,LNum num2,int x){ 2 switch (x) { 3 case 0: 4 return num1+num2; 5 case 1: 6 return num1-num2 ; 7 case 2: 8 return num1*num2; 9 case 3: 10 return num1/num2 ; 11 } 12 return 0; 13 }
五、探測4個數是否能計算24
迴圈遍歷4個數的不同位置,並且迴圈遍歷演算法。判斷其內容是否為24如果是24那麼表示可以計算成功。
1 int is24OK(LNum num1, LNum num2, LNum num3, LNum num4) 2 { 3 int result = 0; 4 QList<struRecordNum> list; 5 LNum numList[4] = {num1,num2,num3,num4}; 6 // 交換4個數字的順序。 7 for (int i1 = 0 ; i1 < 4; i1 ++) { 8 for (int i2 = 0 ; i2 < 4; i2 ++){ 9 if(i1 == i2) continue; 10 for (int i3 = 0 ; i3 < 4; i3 ++){ 11 if(i2 == i3 || i1 == i3) continue; 12 for (int i4 = 0 ; i4 < 4; i4 ++){ 13 if(i1 == i4 || i2 == i4 || i3 == i4) continue; 14 // qInfo()<<numList[i1]<<" "<<numList[i2] <<" "<< numList[i3] <<" "<<" "<< numList[i4]; 15 int x=suanfatongji(numList[i1],numList[i2],numList[i3],numList[i4],&list); 16 if(x !=0){ 17 qInfo()<<"x:"<<x; 18 result += x; 19 } 20 } 21 } 22 } 23 } 24 return result; 25 } 26 27 int suanfatongji(LNum num1, LNum num2, LNum num3, LNum num4, QList<struRecordNum> *list) 28 { 29 LNum sum = 0; 30 31 int c= 0; 32 for(int i1 = 0 ; i1 < 4; i1 ++){ 33 for(int i2 = 0 ; i2 < 4; i2 ++ ){ 34 for(int i3 = 0 ; i3 < 4; i3 ++){ 35 sum = jisuan(jisuan(jisuan (num1,num2,i1),num3,i2),num4,i3) ; 36 if(24.0 == sum.data()){ 37 // 是否找到相同的演算法,因為有重覆數字可能導致演算法想法和數字相同的情況。 38 bool result = false; 39 for(auto item : *list){ 40 if(item.num1 == static_cast<int>(num1.data()) 41 && item.num2 == static_cast<int>(num2.data()) 42 && item.num3 == static_cast<int>(num3.data()) 43 && item.num4 == static_cast<int>(num4.data()) 44 && item.option1 == i1 45 && item.option2 == i2 46 && item.option3 == i3){ 47 result = true; 48 } 49 } 50 if(!result){ 51 struRecordNum tmpItem; 52 tmpItem.num1 = static_cast<int>(num1.data()); 53 tmpItem.num2 = static_cast<int>(num2.data()); 54 tmpItem.num3 = static_cast<int>(num3.data()); 55 tmpItem.num4 = static_cast<int>(num4.data()); 56 tmpItem.option1 = i1; 57 tmpItem.option2 = i2; 58 tmpItem.option3 = i3; 59 list->append(tmpItem); 60 c++; 61 qInfo()<< "(( "<< num1.data() <<strOption(i1) << num2.data() <<")"<<strOption(i2)<< num3.data()<<")" <<strOption(i3)<< num4.data(); 62 } 63 } 64 } 65 } 66 } 67 return c; 68 }
六、源碼地址