Counting Machine---Breadth First Search
A.First Edition
This is the first edition of a counting model which use breadth-first-search and I made it a class. Actually
it originated from assignment of discrete mathematics. I want to verify the answer of a counting problem.
B.The problem
How many positive integers less than 1,000,000 have exactly one digit equal to 9 and have a sum of digits equal
to 13?
No matter how complicated a problem may become, we can divide and conquer it by counting! And breadth-first-search
is one of the simplest way to do it.
1. virtual bool validateOption(int sonData);
This is the place where user-defined methods are implemented to determine if the data (integer) will be verified
to be able to be added.
2. virtual void doGenerate();
This is user-defined way that cases are generated. Method validateOptions will be combined with it to determine
which cases should be added.
3. void CountTree::traverse();
This method allows you to traverse all leaf points.
4. virtual void onVisit();
This is user-defined method like outputing all outcomes.
กก
#include <iostream>
using namespace std;
const int MaxSonCount =8;
int options[7] = {-1,0,1,2,3,4,9};
class CountTree
{
private:
static CountTree root;
static int level;
int depth;
CountTree* parent;
CountTree* sonArray[MaxSonCount];
int data;
int sonCount;
int sonIndex;
void addSon(int sonData);
CountTree* findBrother();
CountTree* findUncle();
bool hasBrother();
CountTree* nextBrother();
CountTree* diving();
void initialize();
bool touchDown();
bool canDive();
bool generate();
void traverse();
protected:
virtual bool lastChance();
virtual void doGenerate();
virtual bool validateOption(int sonData);
virtual void onVisit();
virtual bool lastlast();
public:
void beginCount();
};
int CountTree::level = 0;
CountTree CountTree::root;
int main()
{
CountTree R;
R.beginCount();
return 0;
}
bool CountTree::lastlast()
{
return level==4;
}
//it is a pity there is no stack in C which is my favorite in assembly
void CountTree::onVisit()
{
int temp[6] = {-1};
int counter=0;
CountTree* ptr=this;
while(ptr->parent!=NULL)
{
temp[ptr->depth-1]=ptr->data;
ptr=ptr->parent;
counter++;
}
cout<<"The number is: ";
for (int i=0; i<counter; i++)
{
cout<<temp[i];
}
cout<<endl;
}
void CountTree::traverse()
{
int counter=0;
CountTree* ptr= &root;
while (ptr!=NULL)
{
while(ptr->canDive())
{
ptr= ptr->sonArray[0];
}
cout<<"now it is:"<<++counter;
ptr->onVisit();
if (ptr->hasBrother())
{
ptr= ptr->nextBrother();
}
else
{
ptr=ptr->findUncle();
}
}
cout<<"The total number is :"<<counter<<endl;
}
void CountTree::doGenerate()
{
for (int i=0; i<7; i++)
{
if (validateOption(options[i]))
{
addSon(options[i]);
}
}
}
bool CountTree::validateOption(int sonData)
{
int result =0;
bool found9=false;
CountTree* ptr=this;
if (depth==0&&sonData<=0)//starting digit cannot be 0 or -1
{
return false;
}
while(ptr->parent!=NULL)
{
if (ptr->data==-1)//already ended last level
{
return false;
}
if(ptr->data==9)
{
found9 = true;
}
result+= ptr->data;
ptr = ptr->parent;
}
if (sonData!=-1)
{
if (result+sonData>13)
{
return false;
}
if (lastlast()&&!found9&&sonData!=9)
{
if (result+sonData!=4)
{
return false;
}
}
if (!found9&&sonData!=9)
{
if (result+sonData>4)
{
return false;
}
}
}
else
{
if (result!=13)
{
return false;
}
}
if (result==13&&sonData>0)
{
return false;
}
if (lastChance())
{
if (sonData!=-1&&result+sonData!= 13)//last chance must equal 13
{
return false;
}
}
else
{
if (sonData==-1&&result!= 13)
{
return false;
}
}
return true;
}
bool CountTree::lastChance()
{
return level==5;
}
void CountTree::beginCount()
{
initialize();
while (generate())
{
if (!lastChance()) //true to keep go on
{
level++;
}
else
{
break;
}
}
traverse();
}
bool CountTree::generate()
{
CountTree* ptr= this;
ptr = root.diving();
if (ptr==NULL)
{
return false;
}
while (ptr!=NULL)
{
ptr->doGenerate();
ptr = ptr->findBrother();
}
return true;
}
bool CountTree::touchDown()
{
return depth ==level;
}
bool CountTree::canDive()
{
return sonCount>0;
}
void CountTree::initialize()
{
root.depth = 0;
root.sonCount = 0;
root.sonIndex = -1;
root.parent = NULL;
root.data = 0;
level = 0;
}
//NULL only when there is no more brother
CountTree* CountTree::diving()
{
CountTree* ptr = this;
while (!ptr->touchDown())
{
if (ptr->canDive())
{
ptr = ptr->sonArray[0];
}
else
{
if (ptr->hasBrother())
{
ptr = ptr->nextBrother();
}
else
{
ptr = ptr->findUncle();
}
}
if (ptr==NULL)
{
break; //no more way to dive
}
}
return ptr;
}
bool CountTree::hasBrother()
{
if (parent!=NULL)
{
if (parent->sonCount > sonIndex+1)//has little brother
{
return true;
}
}
return false;
}
CountTree* CountTree::nextBrother()
{
if (parent!=NULL)
{
if (parent->sonCount > sonIndex+1)//has little brother
{
return parent->sonArray[sonIndex+1]; //next little brother
}
}
return NULL;
}
CountTree* CountTree::findUncle()
{
CountTree* ptr= this;
while (!(ptr->hasBrother()))
{
ptr = ptr->parent;
if (ptr==NULL)
{
return NULL;
}
}
return ptr->nextBrother();
}
CountTree* CountTree::findBrother()
{
CountTree* ptr = this;
if (ptr->hasBrother())
{
return ptr->nextBrother();
}
else
{
ptr = ptr->findUncle();
if (ptr==NULL)
{
return NULL;
}
else
{
return ptr->diving();
}
}
}
void CountTree::addSon(int sonData)
{
if (sonCount+1<MaxSonCount)
{
CountTree* ptr = new CountTree;
ptr->data = sonData;
ptr->sonCount = 0;
ptr->parent = this;
ptr->depth = level+1;
sonArray[sonCount] = ptr;
ptr->sonIndex = sonCount;
sonCount++;
}
else
{
cout<<"Exceed max of sons!";
}
}
The following is result of program:
now it is:1The number is: 100039 now it is:2The number is: 100093 now it is:3The number is: 100129 now it is:4The number is: 100192 now it is:5The number is: 100219 now it is:6The number is: 100291 now it is:7The number is: 100309 now it is:8The number is: 10039-1 now it is:9The number is: 100390 now it is:10The number is: 100903 now it is:11The number is: 100912 now it is:12The number is: 100921 now it is:13The number is: 10093-1 now it is:14The number is: 100930 now it is:15The number is: 101029 now it is:16The number is: 101092 now it is:17The number is: 101119 now it is:18The number is: 101191 now it is:19The number is: 101209 now it is:20The number is: 10129-1 now it is:21The number is: 101290 now it is:22The number is: 101902 now it is:23The number is: 101911 now it is:24The number is: 10192-1 now it is:25The number is: 101920 now it is:26The number is: 102019 now it is:27The number is: 102091 now it is:28The number is: 102109 now it is:29The number is: 10219-1 now it is:30The number is: 102190 now it is:31The number is: 102901 now it is:32The number is: 10291-1 now it is:33The number is: 102910 now it is:34The number is: 103009 now it is:35The number is: 10309-1 now it is:36The number is: 103090 now it is:37The number is: 1039-1 now it is:38The number is: 10390-1 now it is:39The number is: 103900 now it is:40The number is: 109003 now it is:41The number is: 109012 now it is:42The number is: 109021 now it is:43The number is: 10903-1 now it is:44The number is: 109030 now it is:45The number is: 109102 now it is:46The number is: 109111 now it is:47The number is: 10912-1 now it is:48The number is: 109120 now it is:49The number is: 109201 now it is:50The number is: 10921-1 now it is:51The number is: 109210 now it is:52The number is: 1093-1 now it is:53The number is: 10930-1 now it is:54The number is: 109300 now it is:55The number is: 110029 now it is:56The number is: 110092 now it is:57The number is: 110119 now it is:58The number is: 110191 now it is:59The number is: 110209 now it is:60The number is: 11029-1 now it is:61The number is: 110290 now it is:62The number is: 110902 now it is:63The number is: 110911 now it is:64The number is: 11092-1 now it is:65The number is: 110920 now it is:66The number is: 111019 now it is:67The number is: 111091 now it is:68The number is: 111109 now it is:69The number is: 11119-1 now it is:70The number is: 111190 now it is:71The number is: 111901 now it is:72The number is: 11191-1 now it is:73The number is: 111910 now it is:74The number is: 112009 now it is:75The number is: 11209-1 now it is:76The number is: 112090 now it is:77The number is: 1129-1 now it is:78The number is: 11290-1 now it is:79The number is: 112900 now it is:80The number is: 119002 now it is:81The number is: 119011 now it is:82The number is: 11902-1 now it is:83The number is: 119020 now it is:84The number is: 119101 now it is:85The number is: 11911-1 now it is:86The number is: 119110 now it is:87The number is: 1192-1 now it is:88The number is: 11920-1 now it is:89The number is: 119200 now it is:90The number is: 120019 now it is:91The number is: 120091 now it is:92The number is: 120109 now it is:93The number is: 12019-1 now it is:94The number is: 120190 now it is:95The number is: 120901 now it is:96The number is: 12091-1 now it is:97The number is: 120910 now it is:98The number is: 121009 now it is:99The number is: 12109-1 now it is:100The number is: 121090 now it is:101The number is: 1219-1 now it is:102The number is: 12190-1 now it is:103The number is: 121900 now it is:104The number is: 129001 now it is:105The number is: 12901-1 now it is:106The number is: 129010 now it is:107The number is: 1291-1 now it is:108The number is: 12910-1 now it is:109The number is: 129100 now it is:110The number is: 130009 now it is:111The number is: 13009-1 now it is:112The number is: 130090 now it is:113The number is: 1309-1 now it is:114The number is: 13090-1 now it is:115The number is: 130900 now it is:116The number is: 139-1 now it is:117The number is: 1390-1 now it is:118The number is: 13900-1 now it is:119The number is: 139000 now it is:120The number is: 190003 now it is:121The number is: 190012 now it is:122The number is: 190021 now it is:123The number is: 19003-1 now it is:124The number is: 190030 now it is:125The number is: 190102 now it is:126The number is: 190111 now it is:127The number is: 19012-1 now it is:128The number is: 190120 now it is:129The number is: 190201 now it is:130The number is: 19021-1 now it is:131The number is: 190210 now it is:132The number is: 1903-1 now it is:133The number is: 19030-1 now it is:134The number is: 190300 now it is:135The number is: 191002 now it is:136The number is: 191011 now it is:137The number is: 19102-1 now it is:138The number is: 191020 now it is:139The number is: 191101 now it is:140The number is: 19111-1 now it is:141The number is: 191110 now it is:142The number is: 1912-1 now it is:143The number is: 19120-1 now it is:144The number is: 191200 now it is:145The number is: 192001 now it is:146The number is: 19201-1 now it is:147The number is: 192010 now it is:148The number is: 1921-1 now it is:149The number is: 19210-1 now it is:150The number is: 192100 now it is:151The number is: 193-1 now it is:152The number is: 1930-1 now it is:153The number is: 19300-1 now it is:154The number is: 193000 now it is:155The number is: 200029 now it is:156The number is: 200092 now it is:157The number is: 200119 now it is:158The number is: 200191 now it is:159The number is: 200209 now it is:160The number is: 20029-1 now it is:161The number is: 200290 now it is:162The number is: 200902 now it is:163The number is: 200911 now it is:164The number is: 20092-1 now it is:165The number is: 200920 now it is:166The number is: 201019 now it is:167The number is: 201091 now it is:168The number is: 201109 now it is:169The number is: 20119-1 now it is:170The number is: 201190 now it is:171The number is: 201901 now it is:172The number is: 20191-1 now it is:173The number is: 201910 now it is:174The number is: 202009 now it is:175The number is: 20209-1 now it is:176The number is: 202090 now it is:177The number is: 2029-1 now it is:178The number is: 20290-1 now it is:179The number is: 202900 now it is:180The number is: 209002 now it is:181The number is: 209011 now it is:182The number is: 20902-1 now it is:183The number is: 209020 now it is:184The number is: 209101 now it is:185The number is: 20911-1 now it is:186The number is: 209110 now it is:187The number is: 2092-1 now it is:188The number is: 20920-1 now it is:189The number is: 209200 now it is:190The number is: 210019 now it is:191The number is: 210091 now it is:192The number is: 210109 now it is:193The number is: 21019-1 now it is:194The number is: 210190 now it is:195The number is: 210901 now it is:196The number is: 21091-1 now it is:197The number is: 210910 now it is:198The number is: 211009 now it is:199The number is: 21109-1 now it is:200The number is: 211090 now it is:201The number is: 2119-1 now it is:202The number is: 21190-1 now it is:203The number is: 211900 now it is:204The number is: 219001 now it is:205The number is: 21901-1 now it is:206The number is: 219010 now it is:207The number is: 2191-1 now it is:208The number is: 21910-1 now it is:209The number is: 219100 now it is:210The number is: 220009 now it is:211The number is: 22009-1 now it is:212The number is: 220090 now it is:213The number is: 2209-1 now it is:214The number is: 22090-1 now it is:215The number is: 220900 now it is:216The number is: 229-1 now it is:217The number is: 2290-1 now it is:218The number is: 22900-1 now it is:219The number is: 229000 now it is:220The number is: 290002 now it is:221The number is: 290011 now it is:222The number is: 29002-1 now it is:223The number is: 290020 now it is:224The number is: 290101 now it is:225The number is: 29011-1 now it is:226The number is: 290110 now it is:227The number is: 2902-1 now it is:228The number is: 29020-1 now it is:229The number is: 290200 now it is:230The number is: 291001 now it is:231The number is: 29101-1 now it is:232The number is: 291010 now it is:233The number is: 2911-1 now it is:234The number is: 29110-1 now it is:235The number is: 291100 now it is:236The number is: 292-1 now it is:237The number is: 2920-1 now it is:238The number is: 29200-1 now it is:239The number is: 292000 now it is:240The number is: 300019 now it is:241The number is: 300091 now it is:242The number is: 300109 now it is:243The number is: 30019-1 now it is:244The number is: 300190 now it is:245The number is: 300901 now it is:246The number is: 30091-1 now it is:247The number is: 300910 now it is:248The number is: 301009 now it is:249The number is: 30109-1 now it is:250The number is: 301090 now it is:251The number is: 3019-1 now it is:252The number is: 30190-1 now it is:253The number is: 301900 now it is:254The number is: 309001 now it is:255The number is: 30901-1 now it is:256The number is: 309010 now it is:257The number is: 3091-1 now it is:258The number is: 30910-1 now it is:259The number is: 309100 now it is:260The number is: 310009 now it is:261The number is: 31009-1 now it is:262The number is: 310090 now it is:263The number is: 3109-1 now it is:264The number is: 31090-1 now it is:265The number is: 310900 now it is:266The number is: 319-1 now it is:267The number is: 3190-1 now it is:268The number is: 31900-1 now it is:269The number is: 319000 now it is:270The number is: 390001 now it is:271The number is: 39001-1 now it is:272The number is: 390010 now it is:273The number is: 3901-1 now it is:274The number is: 39010-1 now it is:275The number is: 390100 now it is:276The number is: 391-1 now it is:277The number is: 3910-1 now it is:278The number is: 39100-1 now it is:279The number is: 391000 now it is:280The number is: 400009 now it is:281The number is: 40009-1 now it is:282The number is: 400090 now it is:283The number is: 4009-1 now it is:284The number is: 40090-1 now it is:285The number is: 400900 now it is:286The number is: 409-1 now it is:287The number is: 4090-1 now it is:288The number is: 40900-1 now it is:289The number is: 409000 now it is:290The number is: 49-1 now it is:291The number is: 490-1 now it is:292The number is: 4900-1 now it is:293The number is: 49000-1 now it is:294The number is: 490000 now it is:295The number is: 900004 now it is:296The number is: 900013 now it is:297The number is: 900022 now it is:298The number is: 900031 now it is:299The number is: 90004-1 now it is:300The number is: 900040 now it is:301The number is: 900103 now it is:302The number is: 900112 now it is:303The number is: 900121 now it is:304The number is: 90013-1 now it is:305The number is: 900130 now it is:306The number is: 900202 now it is:307The number is: 900211 now it is:308The number is: 90022-1 now it is:309The number is: 900220 now it is:310The number is: 900301 now it is:311The number is: 90031-1 now it is:312The number is: 900310 now it is:313The number is: 9004-1 now it is:314The number is: 90040-1 now it is:315The number is: 900400 now it is:316The number is: 901003 now it is:317The number is: 901012 now it is:318The number is: 901021 now it is:319The number is: 90103-1 now it is:320The number is: 901030 now it is:321The number is: 901102 now it is:322The number is: 901111 now it is:323The number is: 90112-1 now it is:324The number is: 901120 now it is:325The number is: 901201 now it is:326The number is: 90121-1 now it is:327The number is: 901210 now it is:328The number is: 9013-1 now it is:329The number is: 90130-1 now it is:330The number is: 901300 now it is:331The number is: 902002 now it is:332The number is: 902011 now it is:333The number is: 90202-1 now it is:334The number is: 902020 now it is:335The number is: 902101 now it is:336The number is: 90211-1 now it is:337The number is: 902110 now it is:338The number is: 9022-1 now it is:339The number is: 90220-1 now it is:340The number is: 902200 now it is:341The number is: 903001 now it is:342The number is: 90301-1 now it is:343The number is: 903010 now it is:344The number is: 9031-1 now it is:345The number is: 90310-1 now it is:346The number is: 903100 now it is:347The number is: 904-1 now it is:348The number is: 9040-1 now it is:349The number is: 90400-1 now it is:350The number is: 904000 now it is:351The number is: 910003 now it is:352The number is: 910012 now it is:353The number is: 910021 now it is:354The number is: 91003-1 now it is:355The number is: 910030 now it is:356The number is: 910102 now it is:357The number is: 910111 now it is:358The number is: 91012-1 now it is:359The number is: 910120 now it is:360The number is: 910201 now it is:361The number is: 91021-1 now it is:362The number is: 910210 now it is:363The number is: 9103-1 now it is:364The number is: 91030-1 now it is:365The number is: 910300 now it is:366The number is: 911002 now it is:367The number is: 911011 now it is:368The number is: 91102-1 now it is:369The number is: 911020 now it is:370The number is: 911101 now it is:371The number is: 91111-1 now it is:372The number is: 911110 now it is:373The number is: 9112-1 now it is:374The number is: 91120-1 now it is:375The number is: 911200 now it is:376The number is: 912001 now it is:377The number is: 91201-1 now it is:378The number is: 912010 now it is:379The number is: 9121-1 now it is:380The number is: 91210-1 now it is:381The number is: 912100 now it is:382The number is: 913-1 now it is:383The number is: 9130-1 now it is:384The number is: 91300-1 now it is:385The number is: 913000 now it is:386The number is: 920002 now it is:387The number is: 920011 now it is:388The number is: 92002-1 now it is:389The number is: 920020 now it is:390The number is: 920101 now it is:391The number is: 92011-1 now it is:392The number is: 920110 now it is:393The number is: 9202-1 now it is:394The number is: 92020-1 now it is:395The number is: 920200 now it is:396The number is: 921001 now it is:397The number is: 92101-1 now it is:398The number is: 921010 now it is:399The number is: 9211-1 now it is:400The number is: 92110-1 now it is:401The number is: 921100 now it is:402The number is: 922-1 now it is:403The number is: 9220-1 now it is:404The number is: 92200-1 now it is:405The number is: 922000 now it is:406The number is: 930001 now it is:407The number is: 93001-1 now it is:408The number is: 930010 now it is:409The number is: 9301-1 now it is:410The number is: 93010-1 now it is:411The number is: 930100 now it is:412The number is: 931-1 now it is:413The number is: 9310-1 now it is:414The number is: 93100-1 now it is:415The number is: 931000 now it is:416The number is: 94-1 now it is:417The number is: 940-1 now it is:418The number is: 9400-1 now it is:419The number is: 94000-1 now it is:420The number is: 940000 The total number is :420
กก
กก
กก