Population

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?

C.The idea of program

    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.

    D.The major functions

    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

    กก

กก

กก