一个简单的证明

今天上概率课，有一个简单的问题，老师没有在课堂上证明，只是用venn diagram来说明。

P[(A∩B')∪(A'∩B)] == P(A) + P(B) - 2P(A∩B)

如图：所要求得概率就是两个圆扣除相交部分。

我的证明：

left hand = P(A∩B')+ P(A'∩B)             as (A∩B')and (A'∩B) are mutually exclusive events as (A∩B')belongs to A;

                                   (A'∩B)belongs to A', and A and A' are mutually exclusive events, so use Postulate3

= P(Ф∪(A∩B'))+ P(Ф∪(A'∩B))                       Identity Law

= P((A∩A')∪(A∩B'))+ P((B∩B')∪(A'∩B))              Negation Law

= P(A∩(A'∪B')) + P((B∩(A'∪B'))                     Distributive Law

= P(A∩(A∩B)') + P(B∩(A∩B)')                       De Morgan's Law

= 1 - P((A∩(A∩B)')') + 1- P((B∩(A∩B)')')          Theorem 2.3

= 1 - P(A'∪(A∩B)) + 1 - P(B'∪(A∩B))              De Morgan's Law

= 1 - (P(A') + P(A∩B) - P(A'∩(A∩B))) + 1 -(P(B') + P(A∩B) - P(B'∩(A∩B)))  Theorem 2.7

= (1- P(A')) + (1 - P(B')) - 2P(A∩B) + P(Ф∩B) + P(Ф∩A)       Associative Law & Negation Law

= P(A) + P(B) - 2P(A∩B) + 2P(Ф)                       Theorem 2.3 and Domination Law

= P(A) + P(B) - 2P(A∩B) = right hand                Theorem 2.4

proved!

　C++的小错误

To: Professor Ms. Leila Kosseim

Dear Madam Kosseim,

I am your student in course COMP248 and I found out there is a  small mistake in your class.

In class you use 

    cout<<setf(ios::showpoint);

    cout<<setf(ios::fixed);

    cout<<precision(2);

In fact, it is wrong, you should use cout's member function setf(), instead of operator "<<" as followoing:

    cout.setf(ios::showpoint);

    cout.setf(ios::fixed);

    cout.precision(2);

or if you really prefer to using the parameterized manipulator, you have to include "iomanip" and like this:

    cout<<setiosflags(ios::showpoint|ios::fixed);

    cout<<setprecision(3);

Thank you for your time in advance.

B.Rgds

Qingzhe Huang

Here is the reply from Madam:

yes.  I verified it and you are right. I mixed up setf and setiosflags. I will correct the mistake in class Friday.

thanks for telling me.

LK

Is it still correct for your suggested expression of theorem?

Hi Doctor,

In today's class you clarified some points about "logically equivalence", and I checked with my notes and found out that in previous class you gave an expression of theorem as following:

(p≡q) ≡ (p←→q ≡ T)

However, you erased it later and said it was not correct. After your clarification about "equivalence", I wonder if it IS INDEED CORRECT after all. The following is the truth table I made, I am not sure if it is right or not. Can you check it? 

p       q           p≡q    p←→q      p←→q≡T

T    T      T         T            T

T    F      F         F            F

F    T      F         F            F

F    F      T         T            T

As "T" is itself a proposition with truth value that is always true, right? Therefore according to definition of "equivalence" that only when the two proposition "p←→q" and "T" have the same truth value, they are equivalence. So, only when proposition "p←→q" is true, compound proposition (p←→q ≡ T) has true value or in other words that it is true that p←→q is equivalent to proposition TRUE. So, we observe that proposition (p≡q) has same truth table as proposition (p←→q ≡ T). Then they are logically equivalent or (p≡q) ≡ (p←→q ≡ T) is true.

Is above correct?

Thank you for your time and patience.

B.Rgds,

Qingzhe Huang

　            A small doubt about 2's complement...

Dear Professor Hina,

I am a student in your section NN and I have a small question about 2's complement.

After 2's complement, a negative number will be tranformed into its positive counter-part, so does the positive. But how about the lowest negative one?

For example of 4bit, the lowest negative is 1000 which is equal to -8. However, after 2's complement, it becomes 1000 again! Does it suggest that the lowest negative one is an exception of 2's complement rule? Or when we encounter the lowest of negative number and want to find out its positive counterpart, how should we do?

Thank you for your time,

QingZhe Huang

        My assignment here...

//****************************************************//
// First Assignment for Comp248						  //	
// Program Title: Ice Cream Experiment				  //	
// Author: Qingzhe Huang							  //
// Section: X                                         //
// Student ID: 5037735                                //
//****************************************************//

#include <iostream>

using namespace std;

const double SweetPerLiter = 0.35;  //sweetner weight per liter of ice cream

void display(double, double, double);

int main()
{
	double mouse, dieter, lethal;
	char choice[10];  //to store user's input choice to decide if repeat inputting

	//set up a menu to ask user if repeat input is desired
	cout<<"\nInput or Quit?(quit)\n";
	cin>>choice;
	while (strcmp(choice, "quit")!=0)//use 'quit' to determine if quit
	{
		cout<<"\nEnter the weight of the mouse in grams: ";
		cin>>mouse;
		cout<<"\nEnter the lethal dose for the mouse in grams: ";
		cin>>lethal;
		cout<<"\nEnter the desired weight of the dieter, in Kilograms: ";
		cin>>dieter;

		//a display subroutine to make easy reading
		display(mouse, lethal, dieter);

		//ask user if repeat input is desired
		cout<<"\nInput or Quit?(quit)\n";
		cin>>choice;
	}

	return 0;
}

//a routine for display of result with 3 parameters of input data

void display(double mouse, double lethal, double dieter)
{
	double temp;  //temperarily store the lethal dose in order to calculate icecream liter
	long preFlag; //previous display format should be saved and restored after display

	temp = dieter / mouse * lethal;  //the lethal weight for dieter

	cout<<"\nFor these parameters:\n";
	cout<<"\tmouse weight: "<<mouse<<" grams\n";
	cout<<"\tlethal dose for the mouse: "<<lethal<<" grams\n";
	cout<<"\tdesired dieter weight: "<<dieter<<" kilograms\n";

	//set up display format to make precision of 3 and fixed format;
	preFlag = cout.setf(ios::fixed);
	prePrec = cout.precision(3);
	cout<<"The lethal dose for sweetener is "<<temp<<"kilograms\n";
	cout<<"The leathal quantity of ice cream is "<< temp* SweetPerLiter<<" kiloliters\n";

	//restore previous display format flag and precision
	cout.flags(preFlag);
}

　 Here it is asked...

    Here it is answered...

Hi,

> I am student from your class of COEN244.
> Just to clear the little doubt of declaration of pointer in your class,
> see following is from your slides:
>
> int number=10, int* pNumber = &number;
>
> Actually the second "int" after comma is unneccessary, after
> compilation the warning of VC++
> "warning C4518: 'int ' : storage-class or type specifier(s) unexpected
> here; ignored"
>


Thank you for the clarification.  I will correct myself next class.


> Sorry for my fussy on details as I am Computer Science student with
> "Software System" option and I treat this course very seriously. I feel
> a bit sad that most students in class are from "Hardware" options which
> probably means that programming is only an option for them.


Actually, in engineering it is a mandatory course.  The way I teach this
course will not differ due the students background.  They will have to
learn how program using OO methodology.


> The unexpected "EARLY" termination of first lecture worries me a lot. I do
> hope you understand that very few software-optioned students do treat
> your lectures very seriously.


Don't worry about the "EARLY" termination.  I had that planned before I
got in there... I have to "EASE" people (including myself) into a summer
course :)


> Here is my answer to your question in class: "What do you expect to get
> after this course?"
> I run into many doubts and confusions in programming from time to time,
> and it is expected that this course can systematically show me the
> answer.

That is exactly my plan!  My lectures are to guide and inspire you
to practice programming.  Learning to program well is really up to the
individual.  But we will look into some "systematic" ways to solve
programming problems.

Regards,
Chris
　

　 Here it is asked...

On Tue, 8 Jul 2003, Hotmail wrote:

> Hi sir,
>
> Thank you so much for your reply.
> As I was doing assignment 1, once again I spent a fruitless afternoon to
> solve my old, long-term painful problem:
>
> I was supposed to ask user to input a number (int , float or whatever). The
> usual way is to use cin>>aVariable;
> But suppose the naughty user key in a character, say 'q' or whatever. The
> program crash.
>  I searched MSDN for ways to "peek" the character before assign value to the
> "aVariable". However, there is no way to "assign" value. I AM able to check
> character by character by using cin.get() or peek(). But it seems that I
> need to re-implement "char"-to-"int" or "char"-to-"float" which I don't want
> to.
>
> I run into this problem from time to time, and cannot find a proper way to
> handle. Can you give me some suggestion?
>
> Thank you for your patience,
>
> B.Regards,
>
> Nick Huang
　

    Here it is answered...

Ok!  I've come up with this solution:

================================================================
#include <iostream>

using std::cin ;
using std::cout ;
using std::endl ;

void main() {

int variable ;

cin >> variable ;

// Check the failbit error flag
if ( ! cin.fail() )
cout << "This is the integer " << variable << endl ;
else {
cout << "This is NOT an integer!" << endl ;
// Clear error flags
cin.clear() ;
// Empty input buffer
cin.get() ;
}
}
========================================================================

Hope this helps!

Best Regards,
Chris Taillefer
　

　    here goes the unexpected result...

           Can you tell who is who?

class MyClass
{
	friend MyClass& operator<<(MyClass& , int );
public:
	MyClass& operator<<(int);
};

int main()
{
	MyClass M;
	M<<45;
	return 0;
}

MyClass& operator<<(MyClass& dummy, int number)
{
	cout<<"this is friend!";
	return dummy;
}

MyClass& MyClass::operator <<(int number)
{
	cout<<"this is members";
	return *this;
}

	The explanation...

This code is ambiguous because when you call the function similar to

MyClass aClass ;
aClass << 5 ;

the operator<< function that is call must have the "signature" of a
MyClass object on the LHS and an int on the RHS.  Both function have the
same signature.  So the compiler does not know which one to use.

	So private member function is indeed accessible

> Hi sir,
>
> Maybe I didn't express myself clearly in class because I asked you the question that is it possible for "friend" function to access member functions of class?
> Because when you mentioned that a friend function to a class is accessable to the private MEMBERS of the class, I arbitarily regarded MEMBER FUNCTIONS are also
> part of MEMBERS. And your answer is positive, if my memory is correct, though I am not sure.
> So, can you confirm me about this issue? Because the error message of compiler shows that there is no way to access PRIVATE MEMBER FUNCTIONS OF A CLASS BY FRIEND FUNCTIONS.
>

Private member functions and data are accessable to friend functions.  You
must have done something else wrong.  Here is a peice of code I used to
test your claim...


class Test {
        friend void foo(Test&) ;
private:
        char* foobar() { return "This is a test!"  ; }
} ;

void foo(Test& tmp) {
        cout << tmp.foobar() ;
}

void main() {

        Test object ;
        foo( object ) ;

}

Hi Nick.  You were right about your previous example, but only on windows.
I compiled on Unix and it gave me a warning but still worked anyway.

I believe that this particular mechanism is operating system dependent.
Hence it is not good way to program.  I will give more in class on Monday.

Best Regards,
Chris Taillefer
P/T Faculty
　

Your tutorial is great! And I just want to say thank you for your great job!

		A little tip about "conversion constructor"

We all know that C++ will automatically try to convert a function call with closest argument, for example, when we overloaded

the operator= of member function of class String. When we call String = "a char string"; compiler will try to convert "a char 

string" into an object of String, see below:

#include <iostream>

using namespace std;

class String
{
private:
	char* sPtr;
	int length;
public:
	String(const char * =" " );
	char* getStr() const;
	~String();
	const String & operator=(const String&);
	void print(){cout<<sPtr<<endl;}
};

int main()
{
	String S("string S");
	S.print();
	S = "change to this!";
	S.print();
	return 0;
}

char* String::getStr() const
{
	 return sPtr;
}


const String& String::operator =(const String& right)
{
	delete [] sPtr;
	length = strlen(right.getStr());
	sPtr = new char[length+1];
	strcpy(sPtr, right.getStr());
	return *this;
}



String::~String()
{
	delete []sPtr;
	length = -1;
}

String::String(const char* str)
{
	length= strlen(str);
	sPtr = new char[length+1];
	strcpy(sPtr, str);
}

The result is like following:

string S
change to this!
Press any key to continue

But keep in mind that it will not always succeed in conversion unless you define your overloaded function properly. That is

it works only if you define the parameter of operator = as const. Otherwise it won't work.

for composition object, initialization is only optional!

Can you confirm this?

> > 2.  See your lecture slides in class2(COEN244Class2.pdf) of compostion
> > example, the Date class has a composition object Time class time, in the
> > constructor, you simply call the object time.setTime(sec, min, hour);
>
> This is a set method, NOT A CONSTRUCTOR CALL. There were no set methods
> provided to you in the prototype!

Even there is no set method provided in prototype, an overloaded assign
operator = is provided in prototype. So, it can be regarded as an set method
plus we use conversion constructor:

msg = data;   //operator= is used and data is converted to be temperary
object by conversion constructor

Of course, as I said in my mai, this is not efficient way since object msg
is initialized first to be empty string, then assigned secondly. But I think
it works. Can you confirm this?

Thank you for your time,

Nick Huang/Qingzhe Huang

it would work, albeit inefficient!

Hi Nick, it would work, albeit inefficient!

Chris

Is conversion constructor involved here? I doubt it...

Hi,

1.  As promised in tutorial, I tried to test to see if conversion constructor is playing any role in following:

class Shape
{
protected:
 double data;
public:
 Shape(double d=1):data(d){cout<<"shape constructor\n";}
};


class Square: public Shape
{
private:
 double side;
public:
 Square(double side=3):side(side), Shape(side){cout<<"square constructor\n";}
};

int main()
{
 Shape aShape;
 aShape =Square(7);

 return 0;
}

2.  The running result is like following:
shape constructor
shape constructor
square constructor
Press any key to continue

3. The first line obviously belongs to aShape construction, and 2nd, 3rd line is due to Square(7). But I am still not sure about whether conversion constructor is involved here. So, I change the main function a little bit:

int main()
{
 Shape aShape;
 aShape =7;

 return 0;
}

4. The new running result is like following: and it is a REAL CONVERSION CONSTRUCTOR HERE. 

shape constructor
shape constructor
Press any key to continue

5. So, it seems to me that the code "aShape =Square(7);" is only doing member-wise copy and no conversion constructor is playing any role here. Though I am not quite sure about this, what do you think?

Thank you for your time,

Nick Huang/Qingzhe Huang

		Do we lose the file pointer?

As simple as following code, what would you expect? Does file "test2.txt" was created? And what is written in file "test1.txt"?

The answer is that "test2.txt" was not created and nothing was written into "test1.txt". Do you believe?

	int main()

	{

		ofstream f;
		f.open("test1.txt");
	
		f.open("test2.txt");
		f<<5;

		return 0;

	}

	My question for final

#include <iostream>

using namespace std;

template<class T, class X>
class Base
{
public:
		virtual X pubTest(T t);
};

template<class X, class T>
class Derived: public Base<T, X>
{
public:
		virtual X pubTest(T t);
};

int main()
{
	Base<int, char> *pB = new Derived<char, int>;
	try
	{
		pB->pubTest('A');
	}
	catch(int i)
	{
		cout<<"catch int "<<i<<endl;
	}
	catch(char c)
	{
		cout<<"catch char "<<c<<endl;
	}
	return 0;
}

template<class T, class X>
X Base<T, X>::pubTest(T t)
{
	throw t;
	return t;
}

template<class X, class T>
X Derived<X, T>::pubTest(T t)
{
	X x = 'A';
	try
	{
		Base<T, X>::pubTest('A');
	}
	catch(T)
	{
		throw x;
	}
	catch(X)
	{
		throw t;
	}
	return x;
}

A const demo

#include <iostream>

using namespace std;

class Demo
{
private:
	int data;
	//the "ptr" pointing to "data"
	int* ptr;

	//const data member is nothing but const values, so, they must be 
	//initialized by initializer BEFORE constructor
	const int constData;

public:
	//even reference is given you still cannot change "data"
	const int& constValueRef(){ return data;} 
	//you have the pointer by its reference, and similarly you cannot change data,
	//but you can change the pointer---"ptr"
	const int*& constValuePtr() { return ptr;}
	//the pointer itselft---ptr--cannot be changed, but the data
	//which pointed to can be changed. In this case, you can change "data"
	//but not "ptr"
	int*  const& constPtr() { return ptr;}

	//even you have the access to constant data by reference, you
	//still cannot change it. What's more, compiler force you to declare 
	//return value as "const int"
	const int& getConstData(){	return constData;}

	//a const member function only for const object to be called
	int getData() const { cout<<"this is const function, should be called by a const"
		<<" object"<<endl; return data;} 

	//it is an overloading to the const version of "getData"
	int getData(){cout<<"this is not const version, so, when const object call"
		<<"getData(), it won't be called\n"; return data;}

	//you cannot overload a function only by different type of "return value"
//	const int getData() {return data;} //error, cannot overload

	void test();

	Demo();

};

//a test function with const object as parameter
void testConst(const Demo& D);

//a wild test 
void testWild(Demo& D);


int global = 100;

int main()
{
	Demo D;
	D.test();
	testConst(D);
	testWild(D);
	return 0;
}

//const data should be initialized before constructor
Demo::Demo() : constData(global)
{
	data = 10;
	ptr = &data;
}

void Demo::test()
{
//	constValueRef() = 12; //Error, try to modify const value
//	*(constValuePtr()) = 13;// Error,try to modify const value
	constValuePtr() = &global; //OK, only change pointer, not data;
//	constPtr() = &global; //Error, try to modify pointer
	*constPtr() = global; //OK, only change the data

//	getConstData() = 11;//Error, you cannot change a const

}


void testConst(const Demo& D)
{
	//can you guess which version of getData() is called here?
	D.getData();
	//obviously, the const version is called, even you don't specify which one.
}

void testWild(Demo& D)
{
	//can you guess which version of getData() is called here?
	D.getData();
	//originally I expect the sequence of function declared may have effect.
	//but it turned out that non-const object call non-const member functions.

	//if you do want to call the const version of "getData()":
	//then change the object to be type of "const object"
	((const Demo)(D)).getData();
	
}

Re: I am not asking for something,

but I do want to make it clear that I finished assignment 6 early last week...

The friend function of a template class can only be defined in formate of inline function, right?

This is really ridiculous! I understand that there might be some difficulty in designing compiler, but there should be some ways!

	Is it a bug with VC++???

See following, it is as simple as an overloading of operator by friend function of a simple class. But compiler continually gives

a strange error: 

fatal error C1001: INTERNAL COMPILER ERROR
(compiler file 'msc1.cpp', line 1786) 

I tried all my way and cannot solve it. It seems a strange error with friend function, since when I changed the friend function 

with no operator overloading, there is no error again. 

#include <iostream>

using namespace std;

class  MyClass
{
	friend int operator +(int i, const MyClass& M);
private:
	int data;
public:
};


int main()
{
	return 0;
}

int operator +(int i, const MyClass& M)
{
	return i+M.data;
}

No operator overload:

class  MyClass
{
	friend int add(int i, const MyClass& M);
private:
	int data;
public:
	MyClass(int i=10): data(i) {;}
};


int main()
{
	MyClass M;
	cout<<add(5, M);
	return 0;
}

int add(int i, const MyClass& M)
{
	return i+M.data;
}

I think there must be some mistakes in question 8...

> Regarding the assignment 1, I think there are quite a few mistakes.

I announced the mistakes in class and put a corrected version of the 
assignment on the course website.

> 1.  Taking question 8 as an example, the integrate formular is obviously 
> incorrect. As the correct one should be 1/2[f(a)+f(b)]*(b-a), instead of 
> 1/2[f(a)+f(b)]/(b-a).  Because the dividing makes really no senses, right?

Yes.

> 2. Secondly "trapezoidal rule" works well if the function f in  interval 
> [a,b] is linear. This implies that we should compare the "SLOPE" of  two 
> half interval  of functions, that is,  if [f(b) - f(m)]/(m-a) is close 
> to [f(b) - f(m)]/(b-m), is it right?

The trapezoidal rule assumes that the function is linear.  However, 
computing the slope is not a good way of finding out whether it is accurate.

> So, my solution is like following:
>  
> --this trape function is the integrate formular, corrected from "divide" 
> to "multiply"
> trape f a b = (f a + f b)*(b-a)*0.5

Yes.

> --this slope function calculate the function f's "slope" at interval [a,b]
> slope f a b = (f b - f a)/(b-a)

Not needed: compare the results of integrating the whole interval [a,b] 
with the sum of the integrals of the half intervals [a,m] and [m,b].

> --if the slope of two interval is close within a tolerance e=0.001, we 
> return one of the integrate formular, of course it should
> --multiply by 2. If not, recursively call integrate function again.

This might work; I am not sure.

> integrate f a b =  if abs (slope f a (half a b) - slope f (half a b) b) <e
>    then (trape f a (half a b))*2
>    else integrate f a (half a b) + integrate f (half a b) b  where e =0.001
> --the result is like following which is quite close to your test:
>  
> A1> integrate sin 0 pi
> 2.0

If you can get answers as close as that, go for it.

Peter

So it is mentioned in class...

Hi,

Actually our prof. corrected this mistake in Q8 in the
class, together with 2 other mistakes in Q1 and Q2. 
You can get the corrected version of assignment from
his web.
I use a slightly different algorithm with yours: my
first approximation simply uses the trapeziodal rule;
second(better) approximation is to split the interval
into two equal parts, then apply trapeziodal rule to
both and then take their summation -- I don't mutiply
the result of one half by 2 and take it as result --
that's the difference from yours.  The rest of the
algorithm is same.  In case of e=0.001, I got the same
result also.

Cheers,
Linda   

The declaration of an object should not add parentheses after constructor

#include <iostream>

using namespace std;

struct Node
{
	Node* next;
	int data;
};

int dataArray[10] = {1, 3, 2, 9, 4, 5, 8, 7, 0, 6};

Node* initialize(int array[], int size);
void print(Node* head);
void deleteKey(Node* head, int K);

int main()
{
	Node* head;
	head = initialize(dataArray, 10);
	print(head);
	cout<<"now delete key=3:\n";
	deleteKey(head, 3);
	print(head);
	cout<<"now delete key=2:\n";
	deleteKey(head, 2);
	print(head);
	cout<<"can we actually delete the head of which the key=1?\n";
	deleteKey(head, 1);
	print(head);//is head still OK?
	return 0;
}

//establish a link list and assign value by input int array to each node
Node* initialize(int array[], int size)
{
	Node* head=NULL, * ptr;
	
	for (int i=0; i<size; i++)
	{
		//first item
		if (head ==NULL)
		{
			head = new Node;
			ptr = head;
			ptr->data = array[i];
			ptr->next = NULL;
		}
		else
		{
			//all other node is the next one.
			ptr->next = new Node;
			ptr = ptr->next;
			ptr->data = array[i];
			ptr->next = NULL;
		}
	}
	return head;
}

void print(Node* head)
{
	Node* ptr=head;
	int index=0;
	while (ptr!=NULL)
	{
		cout<<"index no.:"<<index<<" and value:"<<ptr->data<<endl;
		ptr = ptr->next;
		index++;
	}
}

void deleteKey(Node* head, int K)
{
	Node* first=head, *second, *temp;

	while (first!=NULL)
	{
		//first is the one to be deleted
		if (first->data==K)
		{
			temp = first;
			first=first->next;
			delete temp;
		}
		else
		{
			break;
		}
	}
	//the ends of link list
	if (first==NULL)
	{
		return;
	}

	//now first is not the key
	second = first->next;
	while (second!=NULL)
	{
		if (second->data==K)
		{
			temp = second;//hold it then delete it.
			first->next = second->next;
			second = first->next;
			delete temp;
		}
		else
		{
			first=second;
			second=first->next;
		}
	}
}


                         So, I am correct.

Hi,
You're correct. I overlooked this detail. Please give me your
midterm and I'll correct this error in marking.

Thomas.

Can you show me something?

Hi sir,

Thank you for your praise and I wish in future you might be kind enough to
give me some advice if I run into some problems in programming.

By the way, just at the time I write this message, I solved a small problem
of my doubt with template functions.
http://www.staroceans.com/templateArray.htm

The question is like this: suppose we have a series of template functions,
say various sorting algorithms, all with same parameter type. It is
convenient for us to put them in a function array for continual calling
during the comparison of different algorithms. (This is actually an
assignment of comp352.) But for VC++, compiler simply won't compile or even
check template function until the last minute. So, there is no way to
initialize function array with these template functions. See following:

//three different sorting function declared in template
template <class Elem>
void bubbleSort(Elem array[], int size);

template <class Elem>
void selectSort(Elem array[], int size);

template <class Elem>
void quickSort(Elem array[], int size);

And the following won't work! We cannot initialize array with these template
functions.
void (*sortFun[3])(int array[], int size)={bubbleSort<int>, selectSort<int>,
quickSort<int>};

I have to declare 3 function pointers to represent these template functions.
And then put these pointers into array:
//here I have to declare function pointer to "instanciate the template"
//otherwise compiler won't start compile template until it is in use
void (*fun1)(int array[], int size)=bubbleSort<int>;
void (*fun2)(int array[], int size)=selectSort<int>;
void (*fun3)(int array[], int size)=quickSort<int>;

//this is really what I intend to use---to declare a function array to
//hold the function pointer to
void (*sortFun[3])(int array[], int size)={fun1, fun2, fun3};



Conclusion: I remembered in your notes, you asked a question that is C++
template really passing type as parameter? (Something like this, I am not
sure.)  Any relation between these?

Thank you for your time,

Have a nice day,

Nick Huang/Qingzhe Huang

#include <iostream>
using namespace std;

class Test
{
public:
	Test(int n, char c='N') : val(n), name(c)
	{
		id = ++idNum;
		cout << "Construct " << id << " " << val <<"     "<<name<< endl;
	}

	Test(const Test & x) : val(x.val)
	{
		id = ++idNum;
		cout << "Copy " << id << " " << val <<"     "<<x.name<< endl;
	}

	~Test()
	{
		cout << "Delete " << id << " " << val <<"     "<<name<< endl;
	}
private:
	int id;
	int val;
	static int idNum;
	char name;
};

int Test::idNum = 0;

Test fun(Test t)
{
	t = Test(5);
	cout<<"-----------------\n";
	return t;
}

void main()
{
	Test a(3, 'a');
//	fun(a);
	cout<<"-----------------\n";
	Test b = fun(a);
}

运行结果：

Construct 1 3 a
-----------------
Copy 2 3 a
Construct 3 5 N
Delete 3 5 N
-----------------
Copy 4 5 N
Delete 3 5 N
Delete 4 5
Delete 1 3 a
Press any key to continue

问题：Could you figure out why there are two lines of "Delete 3 5 N"?

Is template in C++ implemented by a preprocessor?

Templates are expanded more or less like macros, that is, with no 
semantic processing.  Roughly, variables like <class T> are replaced by 
actual class names.  Then the whole mess is paased over to the compiler.

The problem with this is that the compiler's error messages relate to 
the expanded text.  If you write tricky template code, the error 
messages can be hard to understand.

<example>
error C2440: 'initializing' : cannot convert from 'class 
std::_Tree<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> >,class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,struct std::set<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,struct std::less<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > >,class std::allocator<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > > >::_Kfn,struct std::less<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > >,class std::allocator<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > > >::const_iterator' to 'class std::_Tree<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> >,struct 
std::set<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> >,struct 
std::less<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> > >,class 
std::allocator<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> > > >::_Kfn,struct 
std::less<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> > >,class 
std::allocator<class std::basic_string<char,struct 
std::char_traits<char>,class std::allocator<char> > > >::iterator'

No constructor could take the source type, or constructor overload 
resolution was ambiguous
</example>

Another problem with templates is that there is no standard way that 
compilers handle them.  As you say, some compilers require template 
declarations to be in the .h file, but this is not always true.

Blitz++ is a modern template library for numeric programming:

http://www.oonumerics.org/blitz/

If you click on "supported platforms", you will see that only some 
compilers can handle blitz code.  For Visual C++ 6.0, it says:

"Does not support member templates outside of class declarations, and 
crashes (CRASHES!) if you try to do so. Definitely not recommended."

A problem with tempates in header files is that the compiler may expand 
them every time it reads the header file, leading to the well-known 
phenomenon of "code bloat".

Hope this helps,
Peter


Hotmail wrote:
> Hi Professor,
>  
> I remembered that you said "c++ compiler doesn't understand template".  
> As I am taking comp442 compiler design, it hits me that maybe template 
> is only implemented with a preprocessor of c++ which treats template 
> more or less like a complicated Macro. Because only the semantic 
> analyzer understand the meaning of  program and the preprocessor is only 
> a scanner and parser. And what's more, the template part of codes can 
> never be compiled to object code for others. If we want to include a 
> template, we have to write it in the .h file. Whileas for other code, we 
> can compile the code to be .obj file and give out .h file for 
> interface.  Therefore, I highly suspect that template is only a kind of 
> Macro by a special preprocessor to convert.
>  
> I have a blur impression that you mentioned something about this in 
> lecture, but not quite sure.
>  
> Thank you for your time,
>  

If it is our professor's typical, luxury method of wasting precious memory by declaring useless

data structures as usual,  then just forget my question.

operator void*()

Please see following code segment:

	ifstream in("fileName");
	if (!in)
	{
		cout<<"file fileName  cannot open\n";
	}
	char buffer[256];
	while (in)
	{
		in.getline(buffer, 256);
		if (!in)
		{
			break;
		}
		cout<<buffer<<endl;
	}

This is quite simple code, and I believe almost everybody can tell me what is going on except for the "red line" part----    while (in)

Can anybody explain this line? ((///Disregard the following paragraph because what I want to say is not here.)

It is not so simple after you think carefully. You see a name for an instance is just like a variable which by

default has value of its address. We all know this by "cout<<in;" which will output an address. How can we break

the while loop by this "if" statement. The address of variable "in" never changes and will never become 0 unless

the file open operation fails. But if it DID FAIL, then it would never enter "while" loop, right?

It seems to make no sense, but this code works!!!

So, what on earth is going on? (The following is true even the above paragraph looks like garbage.)

The answer is overloading of "operator void*", I guess most of you have never heard about that because it is the

first time I hear about it today. :)  Let's use a simple example to explain it:

#include <iostream>

using namespace std;

class myTest
{
private:
	int data;
public:
	myTest(int num=5);
	void setData(int num){ data=num;}
	operator void*();  //operator void*
};


myTest::myTest(int num)
{
	data=num;
}

myTest::operator void *()
{
	if (data=4)
	{
		return NULL;
	}
	return this;
}

int main()

{

	myTest T;
	cout<<"ususally T will return its address---'this' pointer:"<<T<<endl;
	cout<<"but if you set data to be 4 and it will return NULL"<<endl;
	T.setData(4);
	cout<<(T==NULL?"it is NULL":"it is not null")<<endl;

        return 0;

}

1. There is such kind of "operator void*" that it almost makes the function like an variable itself. This is

also called "user-defined convertion operator".  This member function will only be invoked if you try to

evaluate it as an pointer. So, the "if" statement actually invoked the function.

2. IOSTREAM overloading the "operator void*" member function to make it return "NULL" ONLY IF the read operation

fails or the internal "failbit" is set. You can get detail about this by browsing the help on "basic_ios::fail".

(The following are also true...)        Sorry, I made some mistakes about above question...

    if (!in) ...    and while(in) are calling completely different functions of "ifstream" class:

"if (!in)" is calling "operator !()" and will return same value of "fail()" which is a bool-value-member method.

"while(in)" calling "operator void*()" which is only converted to 0 when "fail()&rdstate()".

    how to merge two sorted link list ?

void List::mergeTwoSortedLinkedLists(const List& aList,const List& bList)
{
	ListNode* mPtr, *aPtr=aList.head, *bPtr=bList.head, *nxtPtr;
	bool first=true;
	head=NULL;//you don't have to, but it is safe
	while (aPtr!=NULL||bPtr!=NULL)//at least one is not null
	{
		//to determine the next ptr to be inserted
		if (aPtr==NULL)//
		{
			nxtPtr=bPtr;
			bPtr=bPtr->next;//move to next
		}
		else
		{
			if (bPtr==NULL)
			{
				nxtPtr=aPtr;
				aPtr=aPtr->next;
			}
			else
			{
				//both are not NULL
				if (aPtr->item<bPtr->item)//suppose you have overloaded operator "<"
				{
					nxtPtr=aPtr;
					aPtr=aPtr->next;
				}
				else
				{
					nxtPtr=bPtr;
					bPtr=bPtr->next;
				}
			}
		}
		//we have to do the first specially
		if (first)
		{
			head=new ListNode;			
			head->item=nxtPtr->item;
			head->next=NULL;//initialize
			mPtr=head;
			first=false;
		}
		else
		{
			mPtr->next=new ListNode;
			mPtr=mPtr->next;
			mPtr->item=nxtPtr->item;
			mPtr->next=NULL;
		}
	}//end while
}

			
A simple example of initializing constant in class

#include <iostream>

using namespace std;

const int DefaultRoomNumber=10;

class Room
{
private:
	const int RoomNumber;
public:
	Room(int roomNumber=DefaultRoomNumber);
	void display();
};

class Floor
{
private:
	const int FloorNumber;
	Room room;
public:
	Floor(int floorNumber, int roomNumber);
	void display();
};



class APT
{
private:	
	Floor floors;
	const int APTNumber;
public:
	APT(int aptNumber, int floorNumber, int roomNumber);
	void display();
};


int main()
{
	APT apt(6644, 2, 4);
	apt.display();
	return 0;
}

Floor::Floor(int floorNumber, int roomNumber):room(roomNumber), FloorNumber(floorNumber)
{
	;
}

void Floor::display()
{
	cout<<"My floor number is "<<FloorNumber<<endl;
	room.display();
}

Room::Room(int roomNumber):RoomNumber(roomNumber)
{
	;
}

void Room::display()
{
	cout<<"My room number is "<<RoomNumber<<endl;
}

APT::APT(int aptNumber, int floorNumber, int roomNumber):
APTNumber(aptNumber), floors(floorNumber, roomNumber)
{
	;
}

void APT::display()
{
	cout<<"my address is apt# "<<APTNumber<<endl;
	floors.display();
}

The running result is like following:

my address is apt# 6644
My floor number is 2
My room number is 4
Press any key to continue

	The base class usually need a default constructor, but not always...

Question: Do you need a default constructor for your base class?

Answer: You do need a default constructor for your base class as your derived class need to choose a constructor of his 

"father's" unless you make some adjustment in constructor of derived class. See below:

#include <iostream>

using namespace std;


class Father
{
protected:
	char* name;
public:
	Father(const char* theName);
	void display();
	//Father();//you don't need a default constructor
};

class Son : public Father
{
public:
	Son(const char* theName);
};

int main()
{
	Son S("nick huang");
	S.display();
	return 0;
}

Father::Father(const char* theName)
{
	name=new char[strlen(theName)+1];
	strcpy(name, theName);
}

void Father::display()
{
	cout<<name<<endl;
}

//You need to initialize the base class's constructor properly
Son::Son(const char* theName):Father(theName)
{

}

The running result:

nick huang
Press any key to continue

	How to reverse a linked list?

question: You are given a linked list, or more precisely the pointer of type Link which points to the beginning of a linked list.

Write a function to reverse the elements in list.

void reverse(Node* head);

for example, the linked list is originally -1,41,67,34,0,69,24,78,58,62,64,
now reverse -1,64,62,58,78,24,69,0,34,67,41.

The -1 represents the head pointer. 

answer: There are many possible ways to solve this simple question, however, I found I am completely rely on compiler and tracer.

#include <iostream>

using namespace std;


struct Node
{
	Node* next;
	int data;
};

const int MaxNumber=10;

ostream& operator<<(ostream& out, Node* ptr);

void createNode(Node* head);
void destroyNode(Node* head);
void reverse(Node* ptr);

int main()
{
	Node head;
	head.data=-1;
	createNode(&head);
	cout<<&head<<endl;
	cout<<"now reverse\n";
	reverse(&head);
	cout<<&head<<endl;
	destroyNode(&head);

	
	return 0;
}

//to reverse a linked list, you first need to find the 
//new head and insert one by one.
void reverse(Node* ptr)
{
	//there are three cases that you don't have to do anything:
	//1. there is no head
	//2. there is no element in linked list
	//3. there is only one element in total linked list
	if (ptr==NULL ||ptr->next==NULL||ptr->next->next==NULL)
	{
		return;
	}
	Node* head, *tail, *oldTail, *oldHead;
	//tail is pointing to the first of linked list
	tail=ptr->next;
	head=ptr;
	//try to pin point head to the end of linked list
	while (head->next!=NULL)
	{
		head=head->next;
	}
	//remember the head
	ptr->next=head;
	//loop until the tail meets head...
	while (tail!=head)
	{
		//you need to remeber the sublist after new head
		oldHead=head->next;
		//you also need to remember the old sublist after tail
		oldTail=tail->next;
		//insert tail after head
		head->next=tail;
		tail->next=oldHead;
		//tail goes to next
		tail=oldTail;
	}
	//head->next=NULL;
}

//this is a good habit to release all those
//dynamic memory allocation
void destroyNode(Node* head)
{
	Node* temp1=head->next, *temp2;
	if (temp1==NULL)
	{
		return;
	}
	temp2=temp1->next;
	while (temp2!=NULL)
	{
		delete temp1;
		temp1=temp2;
		temp2=temp1->next;
	}
	delete temp1;
	head->next=NULL;
}

void createNode(Node* head)
{
	Node* temp=head;
	for (int i=0; i<MaxNumber; i++)
	{
		temp->next=new Node;
		temp=temp->next;
		temp->data=rand()%100;
		temp->next=NULL;
	}
}


ostream& operator<<(ostream& out, Node* ptr)
{
	Node* temp=ptr;
	while (temp!=NULL)
	{
		out<<temp->data<<",";
		temp=temp->next;
	}
	return out;
}

The running result is like following:

-1,41,67,34,0,69,24,78,58,62,64,
now reverse
-1,64,62,58,78,24,69,0,34,67,41,




    Even C++ forbids you to create instance of abstract class, but they don't forbid you to do it by array...

	See below, I can even instantiate it! 

#include <iostream>

using namespace std;

const int DefaultAge=20;
const int ArraySize=3;

class Father
{
protected:
	char* name;
public:
	Father(const char* theName);
	virtual void display()=0;
	void speak(){cout<<name<<endl;}
	//Father();//you don't need a default constructor
};

class Son : public Father
{
private:
	int age;
public:
	Son(const char* theName);
	void setAge(int theAge){age=theAge;}
	void display();
};

int main()
{
	Father fatherArray[ArraySize]=
	{
		Son("zhu chunming"), Son("huang yong"), Father("nick huang")
	};
	for (int i=0; i<ArraySize; i++)
	{
		fatherArray[i].speak();
	}	
	
	//Father F("okok");
	return 0;
}

Father::Father(const char* theName)
{
	name=new char[strlen(theName)+1];
	strcpy(name, theName);
}

/*
void Father::display()
{
	cout<<name<<endl;
}
*/

void Son::display()
{
	//Father::display();
	cout<<"my age is:"<<age<<endl;
}

//You need to initialize the base class's constructor properly
Son::Son(const char* theName):Father(theName)
{
	age=DefaultAge;
}

The running result is like this:

zhu chunming
huang yong
nick huang
Press any key to continue

        The template of VC6.0 has many problems, at least it is my personal view

The following simple example shows you how to pass with undetermined number of parameters and how to get them.

The macro in VC6.0 simply hide you the way they cope with different platform and compiler. In win32, vc6.0, you

can simply treat the parameter as null-terminated string and move the pointer with size of type, if the

alignment is what you immagined.

/* VA.C: The program below illustrates passing a variable
 * number of arguments using the following macros:
 *      va_start            va_arg              va_end
 *      va_list             va_dcl (UNIX only)
 */

#include <stdio.h>
#include <stdarg.h>

const int MaxItemLength=20;



class IntTest
{
public:
	void set(int first, ...);
};

class sonTest: public IntTest
{

};

int main()
{
	sonTest I;
	I.set(23, 45, 67, 3, -1);
	return 0;
}

void IntTest::set(int first, ...)
{
	int count = 0, i = first, test;
	va_list marker;
	char* ptr;
	ptr=(char*)(&first);
	
	//printf("%s\n", ptr);
	va_start( marker, first );     // Initialize variable arguments. 
	while( i != -1 )
	{
		test=*((int*)(ptr));
		printf("no. %d is:%d\n", count+1, i);
		printf("no. %d is:%d\n", count+1, test);
		ptr+=sizeof(int);
		count++;
		i = va_arg( marker, int);
	}
	va_end( marker );              // Reset variable arguments.      
 
}

The result is like this:

no. 1 is:23
no. 1 is:23
no. 2 is:45
no. 2 is:45
no. 3 is:67
no. 3 is:67
no. 4 is:3
no. 4 is:3
Press any key to continue

However, when I try to use template class, there is a problem. See the below code, the trick of char pointer

doesn't work!!! You will be only retrieve the first parameter. I have no idea why it happens except to attribute

it to the bugs of VC6.0.

/* VA.C: The program below illustrates passing a variable
 * number of arguments using the following macros:
 *      va_start            va_arg              va_end
 *      va_list             va_dcl (UNIX only)
 */

#include <stdio.h>
#include <stdarg.h>

const int MaxItemLength=20;

template<class T>
class VarList
{	
private:
	T buffer[MaxItemLength];
protected:
	virtual bool isEnd(T& item) =0;
public:
	T* set(const T& items, ...);
	virtual void display(T* list)=0;
};



class IntList : public VarList<int>
{
protected:
	virtual bool isEnd(int& item){ return item==-1;}
public:
	virtual void display(int* list);
};



int main( )
{
	
	IntList L;
	int* temp;
	temp=L.set(34,45, 23, 0, 9, -1);
	
	L.display(temp);
	
	return 0;
}


void IntList::display(int* list)
{
	int count=0;
	//item=list[count];
	while (!isEnd(list[count]))
	{
		printf("no. %d is: %d\n", count+1, list[count]);
	}
}

template<class T>
T* VarList<T>::set(const T& items, ...)
{	
	int count=0;
	char* ptr;
	ptr=(char*)(&items);
	
	//buffer[count]=items;
	//va_list marker;
	//va_start(marker, items);
	while (!isEnd(buffer[count])) 
	{
		
		for (int i=1; i<10; i++)
		{
			char* temp=ptr;
			int j;
			temp+=i;
			j=*((T*)(temp));
			printf("offset %d is:%d\n", i, j);
		}
		ptr+=sizeof(T)*2;
		buffer[++count]=*((T*)(ptr));
		
		//buffer[++count]=va_arg(marker, T);
	}
	//va_end(marker);
	return buffer;
}
		

 It is my greatest honour to receive encouragement from respectable professor Mr. Cliff Shaffer

Sorry to be so long in replying to your email!

Thank you for sharing your project code with me. I hope you learned from
doing this, and from the book.

Its a bit of a struggle to decide what to include in the book and what not
to include. Space is of course an issue. So is keeping focus for the
students by limiting what I include. One consideration is that I leave
enough potential exercises for students to work on. There's a lot of data
structures that I do not include code for in the book, but which I
mention. AVL trees is one of those. Certainly there are implementations of
AVL trees on the Internet. But I don't, and wouldn't, gather together a
collection of implementations for all of the data structures I mention.
Because if I did, that would reduce the number of good projects that
students could work on to learn things. 2-3 trees is another example where
I include some code but deliberately leave parts out. Because I, or
another instructor, might need a project to give out to the students. Or
an energetic student like yourself might wish to do the work on their own
so as to learn more.

Good luck with your studies!

--
Cliff Shaffer, Associate Professor          Phone: (540) 231-4354
Department of Computer Science              Email: shaffer@cs.vt.edu
Virginia Tech, Blacksburg, VA 24061-0106    WWW:   www.cs.vt.edu/~shaffer
-------------------------------------------------------------------------


On Wed, 14 Jul 2004, nick huang wrote:

Re: It is said that everyone can contribute a word, so my version of AVLTree maybe has some usage for others...

> Dear Professor Shaffer,
>
> It is difficult and disturbing to make a decision on whether to write to you or not.
> It has been almost one year since I study your book <A Practical Introduction to Data Structures and Algorithm Analysis> for my undergraduate "data structure" course in Concordia University, Montreal, Canada. I was so deeply impressed by your sample code which is so compact and concise, clear and clean that I practised for a lot.  However, for the AVLTree, you didn't give a sample code for implementation and I try to write some code following your theme. The insertion operation is OK, but the deletion is quite beyond my ability since no algorithm is introduced in your book. My modest wish is just to share my little experience and work with other students.  Of course I realized how naive the idea seems to be, however, it is the enthusiasm for C++ programming and computer science that encourage me to do this.
> The following link is my little code page of AVL tree:
> http://www.staroceans.com/AVLTree-remove.htm
>
> Thank you for your time and attention,
>
> have a nice day,
>
> Nick Huang/Qingzhe Huang
>
> Undergraduate, Computer Science Dept.
> Concordia University, Montreal, Canada
>
>
> 我的征尘是星辰大海。。。(Chinese)
> http://www.staroceans.com/
>
> The dirt and dust from my pilgrimage become oceans of stars...(English)
> http://www.staroceans.com/english.htm
　

    The approach seems beyond ability of compiler...

Hi professor,

Thank you so much for your reply and it is my greatest honour to receive a
message from whom I respect so much in programming! I simply don't know how
to express myself properly in English which is my second language.
It is the obvious reason for you to deliberately "hide" some wonderful code
from students and I didn't realize that. :) Thank you so much for your
explanation!

I understand you are very busy. However, still I am curious if you can give
me some advice on this particular question on "template" of VC++6.0 which is
so powerful.

Yesterday I am trying to write a little program on "set" using template so
that my "set class" would be flexible for any type. And I found your way of
"passing a class as function pointer" quite useful. It allows user to define
the "comparison method" for their own type of set. see below:

template<class T, class methods>//method defines comparison and displaying
methods of elements
class MySet
{
private:
    T members[MaxSetMember];
    int size;
....
};

It seems quite perfect and then it came my problem: How to define "power
set" which is the set of all its sub sets? For the above example, its power
set should be defined as:
template<class T,class methods>
MySet<MySet<T,methods>, someOtherMethods> powerSet;

It seems the compiler cannot handle such kind of definition even though I
managed to make "methods" to be same as "someOtherMethods" like:

MySet<MySet<T,methods>, methods> powerSet;

Still compiler won't recognize my intention. My preliminary conclusion is
that this question is beyond ability of compiler. I am sure you have full
experience of template and could you possibly enlighten me on some way?

Thank you so much for your time and attention,

Nick Huang/Qingzhe Huang
　

        Find the maximum matching (A simple DFS)

simply covering by Bondy and Murty) in the graph with vertices

1, 2, 3, 4, 5, 6, 7, 8, 9, A,B,C,D,E, F, G,H, J

1B, 1C, 1E, 2F, 2J, 3B, 3E, 3H, 4F, 4G, 5D, 5E,

5H, 6C, 6D, 6H, 7A, 7F, 7J, 8A, 8G, 9A, 9G, 9J.

#include <stdio.h>
#include <stdlib.h>

const int Row=9;
const int Col=9;

int graph[Row][Col]={0};
int result[Row]={-1};

void initialize();
bool doSearch(int index);
void printResult();

int main()
{
	initialize();
	doSearch(0);

	return 0;
}


void printResult()
{
	for (int i=0; i<Row; i++)
	{
		if (result[i]!=-1)
		{
			if (result[i]==8)
			{
				printf("%c%c,", i+'1', 'J');
			}
			else
			{
				printf("%c%c,", i+'1', result[i]+'A');
			}
		}
		
	}
	printf("\n");
}

bool isColFull(int col)
{
	for (int i=0; i<Row; i++)
	{
		if (result[i]==col)
		{
			return true;
		}
	}
	return false;
}

bool doSearch(int index)
{
	bool isColFull(int col);

	if (index==Row-1)
	{
		printResult();
		//return true;
	}
	for (int i=0; i<Col; i++)
	{
		if (graph[index][i]==1)
		{
			if (!isColFull(i))
			{
				result[index]=i;

				if (doSearch(index+1))
				{
					return true;
				}
				else
				{
					result[index]=-1;
				}
			}
		}
	}
	return false;
}


void initialize()
{
	FILE* stream;
	char num, ch;
	stream=fopen("graph.txt", "r");
	
	while (true)
	{
		fscanf(stream, "%c%c,", &num, &ch);
		graph[num-'1'][ch-'A']=1;
		if (feof(stream))
		{
			break;
		}
	}
	fclose(stream);
	for (int i=0; i<Row; i++)
	{
		result[i]=-1;
	}
}

The input file "graph.txt"

1B,1C,1E,2F,2I,3B,3E,3H,4F,4G,5D,5E,5H,6C,6D,6H,7A,7F,7I,8A,8G,9A,9G,9I,

And the result: (I only print the matching of size of 8 because there is no matching of size of 9)

1B,2F,3E,4G,5D,6C,7J,8A,
1B,2F,3E,4G,5D,6H,7J,8A,
1B,2F,3E,4G,5H,6C,7J,8A,
1B,2F,3E,4G,5H,6D,7J,8A,
1B,2F,3H,4G,5D,6C,7J,8A,
1B,2F,3H,4G,5E,6C,7J,8A,
1B,2F,3H,4G,5E,6D,7J,8A,
1B,2J,3E,4F,5D,6C,7A,8G,
1B,2J,3E,4F,5D,6H,7A,8G,
1B,2J,3E,4F,5H,6C,7A,8G,
1B,2J,3E,4F,5H,6D,7A,8G,
1B,2J,3E,4G,5D,6C,7F,8A,
1B,2J,3E,4G,5D,6H,7F,8A,
1B,2J,3E,4G,5H,6C,7F,8A,
1B,2J,3E,4G,5H,6D,7F,8A,
1B,2J,3H,4F,5D,6C,7A,8G,
1B,2J,3H,4F,5E,6C,7A,8G,
1B,2J,3H,4F,5E,6D,7A,8G,
1B,2J,3H,4G,5D,6C,7F,8A,
1B,2J,3H,4G,5E,6C,7F,8A,
1B,2J,3H,4G,5E,6D,7F,8A,
1C,2F,3B,4G,5D,6H,7J,8A,
1C,2F,3B,4G,5E,6D,7J,8A,
1C,2F,3B,4G,5E,6H,7J,8A,
1C,2F,3B,4G,5H,6D,7J,8A,
1C,2F,3E,4G,5D,6H,7J,8A,
1C,2F,3E,4G,5H,6D,7J,8A,
1C,2F,3H,4G,5E,6D,7J,8A,
1C,2J,3B,4F,5D,6H,7A,8G,
1C,2J,3B,4F,5E,6D,7A,8G,
1C,2J,3B,4F,5E,6H,7A,8G,
1C,2J,3B,4F,5H,6D,7A,8G,
1C,2J,3B,4G,5D,6H,7F,8A,
1C,2J,3B,4G,5E,6D,7F,8A,
1C,2J,3B,4G,5E,6H,7F,8A,
1C,2J,3B,4G,5H,6D,7F,8A,
1C,2J,3E,4F,5D,6H,7A,8G,
1C,2J,3E,4F,5H,6D,7A,8G,
1C,2J,3E,4G,5D,6H,7F,8A,
1C,2J,3E,4G,5H,6D,7F,8A,
1C,2J,3H,4F,5E,6D,7A,8G,
1C,2J,3H,4G,5E,6D,7F,8A,
1E,2F,3B,4G,5D,6C,7J,8A,
1E,2F,3B,4G,5D,6H,7J,8A,
1E,2F,3B,4G,5H,6C,7J,8A,
1E,2F,3B,4G,5H,6D,7J,8A,
1E,2F,3H,4G,5D,6C,7J,8A,
1E,2J,3B,4F,5D,6C,7A,8G,
1E,2J,3B,4F,5D,6H,7A,8G,
1E,2J,3B,4F,5H,6C,7A,8G,
1E,2J,3B,4F,5H,6D,7A,8G,
1E,2J,3B,4G,5D,6C,7F,8A,
1E,2J,3B,4G,5D,6H,7F,8A,
1E,2J,3B,4G,5H,6C,7F,8A,
1E,2J,3B,4G,5H,6D,7F,8A,
1E,2J,3H,4F,5D,6C,7A,8G,
1E,2J,3H,4G,5D,6C,7F,8A,
Press any key to continue

                  Is it semantically reasonable?

Look at the following simple code which is OK in vc++6.0 and cannot compile in g++ in Linux. In function "increment" which takes an argument of reference of class First. And g++ considers there is a mismatch of type because the return type of "first+second" is "value" of class First.

I argued fiercely with Mr. Zhang who considers this is semantically unreasonable for vc++ and it maybe some source of bugs. My argument is that since expression is always evaluated as a temporary variable internally there can never be any problem for compiler to pass this temporary object as parameter. We cannot persuade each other.

From perspective of reference as in/out parameter, he is right. This is semantically wrong as expression can never be used as in/out parameter. However, from perspective of mode of passing parameter, reference is simply an efficient way of passing by value and reference has nothing to do with in/out parameter. Just imagine that all functions with return value can always be called without using that return value. Therefore the temporary value is discarded. Passing a parameter by reference is not ALWAYS expected to get a result from it. And this is always true for expression which acts as a parameter.

Notes: For those who are not familiar with OOP of C++, the following code will be executed like this:

1. Friend function of operator + overloading will be executed to generate a temporary object class First.

2. The temporary object will be passed by reference to friend function "increment".

3. The function "increment" increments the temporary object.

However, I also agree with Mr. Zhang that it is not very good for vc++ to allow such flexibility. For example,

void test(int&) is the function "test" and you cannot pass an expression like "a+5" where a is an integer variable. So, vc++ is inconsistent with its theme in allowing you to pass temporary object as reference.

#include <stdio.h>

class First
{
	friend First operator+(First&, First&);
	friend void increment(First& );
private:
	int data;
public:
	First(int mydata=5);
	void display();
};


int main()
{
	First first(6), second(19);
	first.display();
	second.display();
	increment(first+second);
	first.display();
	second.display();

	return 0;
}

void First::display()
{
	printf("data=%d\n", data);
}

First::First(int mydata)
{
	data=mydata;
}

First operator+(First& first, First& second)
{
	First result;
	result.data=first.data+second.data;
	return result;
}

void increment(First& first)
{
	first.data++;
}

Running result:

data=6
data=19
data=6
data=19
Press any key to continue

            关于弹性碰撞的讨论

（我犯了一个低级错误，李向东关于勾股定理的证明是对的，即一个球静止，碰撞后的夹角必定为90度。但是我其他的结论保持不变，即其他情况不一定是直角。）

这个问题看起来非常简单，而我们也过度相信自己的不可靠的知觉。我花了一个晚上时间终于认识到向东同学的运用勾股定理证明的错误，这是一个非常诱人的陷阱：速度是矢量，当一个运动的球碰撞一个静止的球时候，他们碰撞后的速度的“绝对值”的平方和的确是等于原来速度的平方，这是根据能量守恒定律，是正确的。但是我们的错误在于由此导出结论速度的方向也就是要符合这个所谓的“勾股定理”却是毫无意义的，因为速度的绝对值符合勾股定理并不代表速度的“方向”也符合勾股定理，这是毫无逻辑可言的。（真正的结论是这是完全符合逻辑的，我的批评是毫无逻辑可言的。我收回我的评论。）速度的方向要用动量守恒定律结合能量守恒定律一起求解，并且还有一个小小的细节就是我昨天说的碰撞的那一刻两个球的接触点一定在当时两个球的球心连线上，这可以用简单的几何定理证明，此处略。

1。求解碰撞时刻的两球的位置。

这个很容易，就是计算两个球飞行时间市的两个球心间距离恰好等于半径之和。

其中两个球的坐标分别为(x1,y1)，(x2,y2)，他们的速度分别为(vx1,vy1)，(vx2,vy2)。因为可以把速度分解为x,y坐标得分速度。

assume P{(x1,y1),(vx1,vy1)}, Q{(x2,y2),(vx2,vy2)}

假定飞行时间为 t
flying time t

飞行后的坐标变为：
P{x1+vx1*t, y1+vy1*t}, Q{x2+vx2*t,y2+vy2*t}

两球心这时候的距离为半径之和 r1+r2：
The distance between P,Q should be (r1+r2)

运用两点之间距离公式：
So, square(x2-x1+t(vx2-vx1))+square(y2-y1+t(vy2-vy1))=square(r1+r2)

化简后是一个关于t的一元二次方程，因为有可能有两个点都满足以上条件，我们只取碰撞发生的“前点”，也就是t>0并且取t较小的那个根。以下为一元二次方程的三个系数a,b,c
a=square(vx2-vx1)+square(vy2-vy1)
b=2*((vy2-vy1)(y2-y1)+(vx2-vx1)(x2-x1))
c=square(x2-x1)+square(y2-y1)-square(r1+r2)

t1=(-b+sqrt(b*b-4*a*c))/2/a

t2=(-b-sqrt(b*b-4*a*c))/2/a

2。运用两个守恒定律求解碰撞后的速度方向和大小。

假定两个球现在处于碰撞位置，则作用力与反作用力一定在球心的连线上，可以把这个冲量表达为一个矢量，就是两个球心坐标所组成的“矢量”在乘以某一个系数，因此我们的问题归结于求这个系数，因为，求出了冲量，自然可以运用矢量的加法来求解球的速度。

球心坐标

assume the collision point is p1(x1,y1), p2(x2,y2)

这就是冲量delta
the delta speed vector should be on the line of p1_p2
delta=scalor*(x1-x2,y1-y2) is exerted on Quantum Q
-delta should be exerted on Quantum P

动量守恒定律自动得到满足，只要分别作用在两个球上的冲量方向相反，绝对值相等。
the conservation of moment is satisfied since |delta|=|-delta|
or delta+(-delta)=0 moment

现在只要满足动能守恒定律就可以了，请注意，运用矢量的概念自动解决了符号问题。
the conservation of energy should also be satisfied
(sq stands for square):
sq(vx1)+sq(vy1)+sq(vx2)+sq(vy2)=sq(vx1+scalor*(x1-x2))+sq(vy1+scalor*(y1-y2))
+sq(vx2+(scalor*(x2-x1))+sq(vy2+(scalor*(y2-y1))
simplify and get:

化简后，scalor也就是我们要求的系数由两个解，忽略0解，得到：
a=(sq(x1-x2)+sq(y1-y2))
b=(x1-x2)(vx2-vx1)+(y1-y2)(vy2-vy1)
scalor=b/a

这里我全部运用自定义的矢量类的操作符重载，比如(x1-x2)，(y1-y2)等价于球心坐标的两个矢量之差。

(vx2-vx1)，(vy2-vy1)等价于两个球的速度的矢量之差。我有重载了矢量的乘法操作符定义为矢量对应元素乘积之和，我记得这应该是线性代数里面的dot product，中文也许叫做内乘积吧？

delta=coord-other.coord;
scalor= ((other.speed-speed)*delta)/(delta.sqrLength());

3。设计让两个小球以任意的速度方向飞行期待着他们在某一点相撞是一件很繁琐的事情，于是我就写了一个简单的控制程序，让若干个小球在一个固定大小的长方形区域飞行，追踪他们的碰撞事件，当然更多的是他们撞墙的事件，我并且输出他们碰撞前后的夹角，经过观察否定了郑署昭同学的直觉，我不记得我是否观察到台球碰撞后的夹角是否为直角，但是，可以肯定地说，这不是真实地感觉。以下为一些运行结果。

elapsed=0.000000,
****************************************
**1*************************************
****************************************
****************************************
*******1********************************
****************************************
****************************************
***********1***************1************
****************************************
****************************************
****************************************
***********1****************************
************************1***************
*****1**********1***********************
****************************************
**********1************************1****
****************************************
****************************************
****************************************
****************************************
one quantum speed is zero
Angle after collision:90.002654 degree

elapsed=0.812902,collision{11.260000,7.480000}collision{9.803221,6.109674}
****************************************
**1*************************************
****************************************
****************************************
****************************************
****************************************
*********1******************************
***********1***************1************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
***************1************************
**********1************************1****
*****************1*********1************
*******1********************************
****************************************
****************************************

elapsed=1.042105,bounce{8.425789, 19.000000}
****************************************
**1*************************************
****************************************
****************************************
****************************************
****************************************
*********1******************************
***************************1************
***********1****************************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
**********1******1*****************1****
****************************************
*****************1*********1************
****************************************
********1*******************************

elapsed=1.283168,bounce{28.730297, 19.000000}
****************************************
**1*************************************
****************************************
****************************************
****************************************
**********1*****************************
****************************************
***************************1************
************1***************************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
**********1*******1****************1****
****************************************
*********1******************************
*****************1**********************
****************************1***********

elapsed=1.334831,bounce{17.914831, 19.000000}
****************************************
**1*************************************
****************************************
****************************************
****************************************
**********1*****************************
****************************************
***************************1************
************1***************************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
**********1************************1****
******************1*********************
*********1******************************
****************************1***********
*****************1**********************
one quantum speed is zero
Angle after collision:90.002654 degree

elapsed=1.407472,collision{10.120000,15.040000}collision{9.430549,16.917407}
****************************************
**1*************************************
****************************************
****************************************
****************************************
**********1*****************************
****************************************
***************************1************
****************************************
************1***************************
****************************************
****************************************
****************************************
****************************************
****************************************
**********1************************1****
*********1*********1********************
****************************************
*****************1***********1**********
****************************************

elapsed=2.264516,bounce{24.280968, 19.000000}
****************************************
**1*************************************
****************************************
****************************************
****************************************
**********1*****************************
****************************************
***************************1************
****************************************
***********1****************************
****************************************
***************1************************
****************************************
****************************************
******************1************1********
***********************************1****
****************************************
*********1******************************
****************************************
************************1***************

elapsed=3.782093,bounce{15.275988, 1.000000}
****************************************
**1************1************************
****************************************
****************************************
***********1****************************
****************************************
************************************1***
***************************1************
********************1*******************
****************************************
****************************************
****************************************
****************************************
****************************************
*********************************1******
*******************1***************1****
****************************************
**********1*****************************
****************************************
****************************************

elapsed=4.443077,bounce{39.000000, 3.042462}
****************************************
**1*************************************
****************************************
***************************************1
***********1****1***********************
*********************1******************
****************************************
***************************1************
****************************************
****************************************
****************************************
****************************************
************************************1***
****************************************
****************************************
***********************************1****
****************************************
***********1*********1******************
****************************************
****************************************

elapsed=4.824348,bounce{39.000000, 11.064522}
****************************************
**1**********************************1**
****************************************
*********************1******************
***********1****************************
****************************************
****************************************
*****************1*********1************
****************************************
****************************************
****************************************
***************************************1
****************************************
****************************************
****************************************
***********************************1****
****************************************
***********1****************************
**********************1*****************
****************************************

elapsed=4.847525,bounce{37.685545, 1.000000}
****************************************
**1**********************************1**
****************************************
*********************1******************
***********1****************************
****************************************
****************************************
*****************1*********1************
****************************************
****************************************
**************************************1*
****************************************
****************************************
****************************************
****************************************
***********************************1****
****************************************
***********1****************************
***********************1****************
****************************************

elapsed=4.999554,bounce{23.506791, 19.000000}
****************************************
**1**********************************1**
*********************1******************
****************************************
***********1****************************
****************************************
****************************************
***************************1************
*****************1**********************
****************************************
*************************************1**
****************************************
****************************************
****************************************
****************************************
***********************************1****
****************************************
***********1****************************
****************************************
***********************1****************

elapsed=5.379775,bounce{21.959775, 1.000000}
****************************************
**1******************1******************
****************************************
***********************************1****
***********1****************************
****************************************
****************************************
***************************1************
****************************************
***********************************1****
******************1*********************
****************************************
****************************************
****************************************
****************************************
***********************************1****
****************************************
***********1************1***************
****************************************
****************************************
Angle before collision:274.441524 degree
Angle after collision:82.054012 degree

elapsed=5.906837,collision{34.242780,6.349526}collision{32.775688,7.708806}
****************************************
**1*************************************
****************************************
***********1**********1*****************
****************************************
****************************************
**********************************1*****
***************************1****1*******
****************************************
****************************************
****************************************
****************************************
****************************************
*******************1********************
****************************************
***********************************1****
**************************1*************
************1***************************
****************************************
****************************************
one quantum speed is zero
Angle after collision:89.992037 degree

elapsed=6.240128,collision{29.953400,7.514897}collision{27.980000,7.840000}
****************************************
**1*************************************
****************************************
************1***************************
**********************1*****************
****************************************
****************************************
***************************1*1****1*****
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
********************1******1*******1****
****************************************
************1***************************
****************************************
****************************************
Angle before collision:273.312783 degree
Angle after collision:93.699242 degree

elapsed=6.679754,collision{23.259754,6.784903}collision{24.396670,8.430327}
****************************************
**1*************************************
****************************************
************1***************************
****************************************
****************************************
***********************1*****1**********
****************************************
************************1********1******
****************************************
****************************************
****************************************
****************************************
****************************************
****************************1***********
***********************************1****
****************************************
****************************************
************1********1******************
****************************************

elapsed=6.826479,bounce{21.886230, 19.000000}
****************************************
**1*************************************
****************************************
************1***************************
****************************************
****************************************
**********************1******1**********
****************************************
*********************************1******
***********************1****************
****************************************
****************************************
****************************************
****************************1***********
****************************************
***********************************1****
****************************************
****************************************
************1***************************
*********************1******************
Angle before collision:5.676226 degree
Angle after collision:2.434235 degree

elapsed=7.432483,collision{23.202040,15.416987}collision{21.580977,14.245597}
****************************************
**1*************************************
****************************************
************1***************************
****************************************
********************1********1**********
****************************************
****************************************
****************************************
****************************************
*********************************1******
****************************************
******************************1*********
****************************************
*********************1******************
***********************1***********1****
****************************************
****************************************
************1***************************
****************************************
Angle before collision:34.879093 degree
Angle after collision:18.731812 degree

elapsed=7.700319,collision{33.288529,10.890265}collision{31.407066,11.568571}
****************************************
**1*************************************
************1***************************
****************************************
*******************1*********1**********
****************************************
****************************************
****************************************
****************************************
****************************************
*********************************1******
*******************************1********
****************************************
****************************************
************************1***************
*******************1***************1****
****************************************
****************************************
*************1**************************
****************************************

elapsed=8.244684,bounce{16.438874, 19.000000}
****************************************
**1*************************************
************1***************************
*****************1***********1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
******************************1****1****
***************************1************
****************************************
****************************************
***********************************1****
****************************************
****************************************
*************1**************************
****************1***********************
Angle before collision:22.586885 degree
Angle after collision:97.764464 degree

elapsed=8.400496,collision{15.452419,18.087920}collision{13.477487,18.403587}
****************************************
**1*************************************
*************1**************************
*****************1***********1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
******************************1*********
***************************1********1***
****************************************
****************************************
****************************************
***********************************1****
****************************************
****************************************
*************1*1************************
****************************************
Angle before collision:289.922483 degree
Angle after collision:75.775825 degree

elapsed=8.458620,collision{28.088211,11.270706}collision{30.026903,10.779306}
****************************************
**1*************************************
*************1**************************
*****************1***********1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
******************************1*********
****************************1*******1***
****************************************
****************************************
****************************************
***********************************1****
****************************************
***************1************************
*************1**************************
****************************************

elapsed=8.924433,bounce{10.745949, 19.000000}
****************************************
**1*************************************
*************1*1*************1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
********************************1*******
***************************1************
**************************************1*
****************************************
****************************************
***************1************************
***********************************1****
****************************************
****************************************
****************************************
**********1*****************************
Angle before collision:283.708612 degree
Angle after collision:85.467110 degree

elapsed=9.018499,collision{15.284104,2.264615}collision{13.288968,2.404013}
****************************************
**1*************************************
*************1*1*************1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
**************************1*****1*******
****************************************
**************************************1*
****************************************
***************1************************
****************************************
***********************************1****
****************************************
****************************************
**********1*****************************
****************************************

elapsed=9.055931,bounce{39.000000, 12.003266}
****************************************
**1*************************************
*************1*1*************1**********
****************************************
****************************************
****************************************
****************************************
****************************************
****************************************
**************************1******1******
****************************************
****************************************
***************************************1
***************1************************
****************************************
***********************************1****
****************************************
****************************************
**********1*****************************
****************************************

elapsed=9.595360,bounce{15.458999, 1.000000}
****************************************
**1************1************1***********
***********1****************************
****************************************
****************************************
****************************************
****************************************
***********************************1****
*************************1**************
**************1*************************
****************************************
****************************************
************************************1***
****************************************
****************************************
***********************************1****
****************************************
****************************************
*******1********************************
****************************************

elapsed=9.625199,bounce{28.880118, 1.000000}
****************************1***********
**1************1************************
***********1****************************
****************************************
****************************************
****************************************
****************************************
***********************************1****
*************************1**************
**************1*************************
****************************************
****************************************
************************************1***
****************************************
****************************************
***********************************1****
****************************************
****************************************
*******1********************************
****************************************

elapsed=10.225379,bounce{39.000000, 5.850923}
****************************************
**1*************************************
*********1*****1************1***********
****************************************
****************************************
**************1************************1
****************************************
************************1***************
****************************************
****************************************
****************************************
****************************************
**********************************1*****
****************************************
****************************************
***********************************1****
****************************************
***1************************************
****************************************
****************************************

这是一个关于template-template的参数的demo，你可以想象你针对一大堆的container想再写一个类这个类实用所有他们通用的方法，比如insert.这个是我暑假买的关于模板的经典的书里看到这样一个匪夷所思的做法，就是模板也可以嵌套模板，当时兴奋地在vc++6.0上法像不支持，现在vc++2005总算可以了！

// dummy.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <list>
#include <iostream>

using namespace std;

template <class Type>
class MyContainer
{
public:
	int number;
	Type array[10];
	void insert(Type data)
	{
		array[number++]=data;
	}
	Type pop()
	{
		return array[--number];
	}
	MyContainer<Type>()
	{
		number=0;
	}
};



template < class Type,  template <typename Type> class Container >
class Algo
{
public:
	//Type array[10];
	Container<Type> container;
	void insert(Type data)
	{
		container.insert(data);
	}
	void print()
	{
		//int temp;
		//temp=container.begin();
		cout<<container.pop()<<endl;
	}
};




int _tmain(int argc, _TCHAR* argv[])
{
	//printf("hello world!");

	Algo<int,MyContainer> algo;
	algo.insert(5);
	algo.print();
	return 0;
}

  Proposition(trivial)

Can you imagine that I define such a complicated data structure for boolean value? Is it really 

necessary? I am not sure, either. But previous experience told me that internally a proposition

will be treated like variable rather than constant since we need to "deduct" and there will be 

a period that proposition is unset. Therefore a third value for "truth" value is needed.

The only remarkable thing is that I overloaded operator "," which will be handy.

proposition.h

#include <iostream>
#include <string>
//#include <stdarg.h>

using namespace std;

enum TruthState
{
	TRUE=1, UNKNOWN=0, FALSE=-1
};

struct Truth
{
	Truth operator &&(const Truth& right) const;
	Truth operator = (bool right);
	Truth operator !();
	Truth operator==(const Truth& right) const;
	Truth operator==(bool right) const;
	Truth(TruthState theTruth=UNKNOWN);		
	TruthState truth;
};


class Proposition
{
	friend Proposition and(const Proposition& first, const Proposition& second)
	{	
		Proposition result=first;
		//result.name+=" ";
		result.name+=second.name;
		result.truth=result.truth&&second.truth;
		return result;
	}	
	friend ostream& operator<<(ostream& os, const Proposition& prop)
	{
		os<<prop.name<<":";
		switch (prop.truth.truth)
		{
		case UNKNOWN:
			os<<"UNKNOWN";
			break;
		case TRUE:
			os<<"TRUE";
			break;
		case FALSE:
			os<<"FALSE";
			break;
		}
		os<<"\n";
		return os;
	}
	//friend Proposition operator,(const Proposition& left, const Proposition& right);
public:
	Proposition(const string& theName="", Truth theTruthValue=Truth(UNKNOWN));
	Proposition(const string& theName, TruthState truthState);
	Proposition(const string& theName, bool theTruthValue);
	Proposition operator ,(const Proposition& other);

	Proposition operator&&(const Proposition& other);
	const string& getName() const;
	Truth operator()() const;



protected:
	string name;
	Truth truth;
};

proposition.cpp

#include <string>
//#include <stdarg.h> 
#include "Proposition.h"
using namespace std;


////////////////////////////////////////////////////////////////////
//It is a bit unbelieveable that I overload a simple truth struct with 
//so many operator overloading. and do we need these seemingly-redundant
//Truth struct?
///////////////////////////////////////////////////////////////////////

Truth::Truth(TruthState theTruth)
{
	truth=theTruth;
}

Truth Truth::operator &&(const Truth& right) const
{
	if (truth==0||right.truth==0)
	{
		return Truth(UNKNOWN);
	}
	else
	{
		return (truth<right.truth)?*this:Truth(right);
	}
}

Truth Truth::operator = (bool right)
{
	truth= right?TRUE:FALSE;
	return *this;
}

Truth Truth::operator !()
{
	if (truth!=UNKNOWN)
	{
		truth=(truth==TRUE)?FALSE:TRUE;
	}
	return *this;
}

Truth Truth::operator ==(const Truth& right) const
{
	if (truth!=UNKNOWN&&right.truth!=UNKNOWN)
	{
		return (truth==right.truth)?Truth(TRUE):Truth(FALSE);
	}
	else
	{
		return Truth(UNKNOWN);
	}
}


Truth Truth::operator == (bool right) const
{
	if (truth!=UNKNOWN)
	{
		if (truth==TRUE&&right||truth==FALSE&&!right)
		{
			return Truth(TRUE);
		}
		else
		{
			return Truth(FALSE);
		}
	}
	else
	{
		return *this;
	}
}

//have at least one arguments




//constructor
Proposition::Proposition(const string& theName, TruthState truthState)
{
	name=theName;
	truth.truth=truthState;
}

Proposition::Proposition(const string& theName, bool theTruthValue)
{
	name=theName;
	truth=theTruthValue;
}


Proposition::Proposition(const string& theName, Truth theTruth)
{
	name=theName;
	truth=theTruth;
}

Truth Proposition::operator () () const
{
	return truth;
}

const string& Proposition::getName() const
{
	return name;
}

Proposition Proposition::operator &&(const Proposition& other)
{
	return and(*this, other);
}

Proposition Proposition::operator ,(const Proposition& other)
{
	return and(*this, other);
}

main.cpp

#include <iostream>
#include <string>
#include "proposition.h"

using namespace std;

int main()
{
	Proposition p("p", true), q("q", false), r("r", UNKNOWN);

	cout<<(p&&q&&r)<<endl;

	//cout<<and((p, q), Proposition("new name"), Proposition("I am false", false))<<endl;



	return 0;
}

The recursion version of permutation in the order of minimal change.

#include <iostream>
#include <ctime>

using namespace std;

const int MaxNumber=4;

int counter=0;

void recurPerm();
void visit(int* array, int size, bool left2right);

int lexRank(int* array, int size);

int factor(int n);

int main()
{
	//int array[MaxNumber]={4,3,2,1};
	//cout<<lexRank(array, 4)<<endl;
	recurPerm();
	return 0;
}

//assume contents in array starts from 1 instead of 0
int lexRank(int* array, int size)
{
	int local[MaxNumber];
	int result=0;
	memcpy(local, array, sizeof(int)*size);
	for (int i=0; i<size; i++)
	{
		result+=(local[i]-1)*factor(size-i-1);
		for (int j=i+1; j<size; j++)
		{
			if (local[j]>local[i])
			{
				local[j]--;
			}
		}
	}
	return result;
}

int factor(int n)
{
	int result=1;
	for (int i=1; i<=n; i++)
	{
		result*=i;
	}
	return result;
}


void recurPerm()
{
	time_t start, finish;
	int data[1]={1};
	start=time(0);
	visit(data, 1, false);
	finish=time(0);
	
	cout<<"\nthe total number of permutation is:"<<counter<<endl;
	cout<<"the total running time in seconds is:"<<finish-start<<endl;
}

void insert(int* array, int size, int pos, int value)
{
	//right shift by one from pos
	for (int i=size; i>pos; i--)
	{
		array[i]=array[i-1];
	}
	array[pos]=value;
}

void displayArray(int* array, int size)
{
	cout<<"[";
	for (int i=0; i<size; i++)
	{
		cout<<array[i];
		if (i!=size-1)
		{
			cout<<",";
		}
	}
	cout<<"]\n";
}

void visit(int* array, int size, bool left2right)
{
	if (size==MaxNumber)
	{
		counter++;
		if (MaxNumber<6)
		{
			displayArray(array, size);
		}
			
		return ;
	}
	int local[MaxNumber];
	int pos=left2right?0:size;
	int shift=left2right?1:-1;
	int boundary=left2right?size+1:-1;
	//this is the most tricky part and I cannot figure it out for one hour
	//finally I tried and tested and get this unexplanable format
	bool temp=size%2==0?left2right:false;

	do
	{
		memcpy(local, array, size*sizeof(int));
		insert(local, size, pos, size+1);
		//visit(local, size+1, (size+pos)%2==1);
		visit(local, size+1, temp);
		temp=!temp;
		pos+=shift;
	}
	while (pos!=boundary);
	/*
	if (size==MaxNumber-1)
	{
		cout<<"\n";
	}
	*/
}
		

The running result:

[1,2,3,4]
[1,2,4,3]
[1,4,2,3]
[4,1,2,3]
[4,1,3,2]
[1,4,3,2]
[1,3,4,2]
[1,3,2,4]
[3,1,2,4]
[3,1,4,2]
[3,4,1,2]
[4,3,1,2]
[4,3,2,1]
[3,4,2,1]
[3,2,4,1]
[3,2,1,4]
[2,3,1,4]
[2,3,4,1]
[2,4,3,1]
[4,2,3,1]
[4,2,1,3]
[2,4,1,3]
[2,1,4,3]
[2,1,3,4]

the total number of permutation is:24
the total running time in seconds is:0
Press any key to continue

And the discussion between students and professor is more interesting than the program itself.

One student wrote:
> Dear Sir,
>
> I wanted to ask you about the largest number which your recursive
> program can accept to generate all permutations. You told us in last
> session that if we get a stack overflow then the recursive algorithm is
> not correct, but there is a point, to generate p(n) (let us consider p
> as a recursive implementation of algorithm p of knuth)  based on p(n-1),
> we should have at least (n-1)! objects in the stack, so because
> (obviously) the stack does not have an infinite memory so in some point
> we would have a stack overflow, is there anything wrong whit this
> observation?
　

Professor wrote:

The generation of the Trotter-Johnson sequence of permutation is easiest
to define recursive as adding the number n in a systematic manner to all
the sequences on n-1 letters. However, this is NOT a good way to
implement the algorithm, because one should avoid having to store all
the (n-1)! permutations before generating the permutations on n letters.

I just tried some experiment with my own recursive implementation of
Knuth's alg P. With n=10, it finishes almost instantenously. With n=11,
it takes a few seconds. With n=12, it looks like a minute. The largest
n is bounded by the amount of CPU time I wish to spend, and is not
bounded by the stack size.

In my implementation, the arrays, c, o and a are all global variables.
There are only 3 local int variables in the actual recursive function.
With n=12, the deepest recursive level is 13, and the amount of stack
space used is minimal, probably less than 1 kilobyte.
　

I wrote:

My version runs a little bit slower than your case, 96seconds for n=12. And I guess it is due to that I pass array as parameter in each recursive call. It uses up a bit more memory but the maximum usage memory is only the maximum depth of stack. i.e. my array is fixed size of x and maximum recursion deption is d, then the memory is d*x.
My question is that if you don't pass array as parameter in recursive call, does that mean you pre-allocate a collection of arrays with number of maximum number of  stack depth? Because I think in each stack frame or recursion call, you have to maintain a local array, right? If you want to save stack memory space by declaring them as global, you need to declare one for each depth of recursion, is it?
I am just curious about your implementation.

Thank you for your time,
　

note about understanding N-Queen problem

Once a month, I spend a few hours thinking about problems in comb. algo. which is always like puzzles to me, especially when I try to understand Knuth's notes. Sometimes I do feel annoyed against Knuth because like all genius he just simply assume everybody else understand those simple facts like himself without even giving out basic definition of what he is talking about. For example, in his unique way of solving N-Queen problem, he is trying his beautiful idea of "dancing links" which is intended to defeat sparse matrix by using doubly link data structure to "link" those isolated elements in sparse matrix. This is a very general idea to fight huge sparse matrix during operations like back track which repeatedly pass-in and return-out these data structures. However, what he is doing is more  than this. He transforms N-Queen problem to an exact-cover problem which is a more profound idea in my view point because almost all of our searching problem is done by "matching exact conditions to guarantee deterministic property" otherwise we are living a chaotic world. And all these strictly constraint searching conditions can be transformed to an exact cover problem by using these conditions as row and column in a relation matrix. The only problem is that for most of cases, this huge matrix is a huge sparse matrix as many of the conditions are not so "close" related. So, this generalization seems impractical to use unless we convert our sparse matrix representation to such a "compact" data structure like what Knuth has done. In 4-Queen problem, Knuth gives an example of doing this. And please note that a simple "commonsense" that we are supposed to cover all row, column, diagonals exactly once. This can be naively translate to a 22x22 matrix. (4rows+4column+7primary-diagonal+7reverse-diagonal=22 and it takes me more than half hours to understand this simple assumption because Knuth doesn't bother to spend a single word to explain this, not mention that he doesn't give definition of primary-diagonal, reverse-diagonal.) To solve exact cover problem, you can also use "live-vector" technique to solve it as a max-clique problem. However, this matrix is too big and has so many empty places. It is not worthwhile to translate classic problem into such matrix unless you can "reduce" matrix. And this is why he introduces the doubly link structure to "reduce" matrix.

There will be no magic unless you see what Knuth has seen about doubly link structure. I now copy his idea as following:

Let's define L(x) R(x)  as pointer to left and right of a node, then R(L(x))=R(x), L(R(x))=L(x) will remove node x from link. However, you can rejoin the node as long as the link is not further damaged by R(L(x))=x, L(R(x))=x

This is a beautiful operation if you are comfortable with pointers.

But I haven't touched the hardcore of N-Queen problem yet. Maybe I should write a demo program...
　

Sometimes...

Sometimes I feel myself like those invincible heroes who can see through nature with keen eyes. Sometimes I wake up and realize what I see is exactly common senses that every one with average IQ can figure out. However, this is the process of understanding because if this never happens to you it simply means that either you can never learn or you never need to learn.

I try to answer myself the question that why we need majority replies from a group of replicated servers when using "wrapper" technique which maintains a dynamic group view acting as an agent between client and the group of replicated servers. If Byzantine-failure is non-detectable to this wrapper then we can always choose one of any reply from replicates without waiting a consensus of majority.  Then I realized during my jogging that this majority is the upper bound of error-correcting mechanism which is exactly like those used in Hamming-code or whatever. We actually take this advantage to tolerate up to maximum Byzantine failure by waiting a consensus from majority of replies from replicates. Crash-failure is benign and easy to be detected by "wrapper" or group manager, but Byzantine failure is "almost only" possible to be sure at application level by differentiate the "traitor" from "patriots". The only suitable timing is at examination of collected replies from replicates. We sacrifice performance a little by waiting redundant number of replies in order to "catch" spies up to a maximum number. Of course a natural operation after spies are spotted is to expel spies out of group. This is not mentioned in slides, but it is an implication.

However another question float up when I am satisfied with my explanation. It is said that there is only one "updator" who multicast his updates to all members of replicates. Then what if this sender fails? This seems to be no solution because when we suspect everyone is a possible "spy" we can trust no one even including ourselves. At least I need one reliable stone to step on.

Another senseless question is that if there is difference between these two kinds of men: One kind is a common man with a common wish to want to look like uncommon. The other kind is an uncommon man with an uncommon wish to want to look like common. (I am joking.) 

Sometimes when I feel my mind is as clear as the blue sky and I want to write down what is in my mind. Suddenly clouds cover the sky and I am in chaos. 

Sometimes when I feel I am in chaos and I try to write down my puzzle. Suddenly the clouds are wiped away and I am under the sunshine and the blue sky.

So, just write down whatever you think may help.

        The Great Mokhov figures out the riddle...

Nick writes:

By the way, I am working to migrate my windows project to Linux and I have a
question about "g++" compiler. You see, I did some "dangerous" type-casting
in windows and the compiler of VC6 gives warning and allow me to do that.
However, it seems GCC is more strict in syntax and simply gives error. Is
there compiler options to relax g++ to not to give error like VC6 compiler?
For example, I am using STL vector and for efficiency purpose I treat
"iterator.begin()" like starting address of array. I know this is not the
purpose of vector, but I check the source of vector and it seems ok to do
that. It works fine also in windows. But now g++ simply gives error in this
type-casting.
　

Nick writes:

I write a simple test indicating the problem. See the attached source code
file.
Here is the compilation error in "alamanni":

[qingz_hu@alamanni ~/linux] % g++ arrayTest.cpp -o arrayTest.exe
arrayTest.cpp:51:2: warning: no newline at end of file
arrayTest.cpp: In function 'int main()':
arrayTest.cpp:24: error: invalid cast from type
'__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> >
 >' to type 'int*'
　

Mokhov:

Ah, I see. This works:

   ...
   display(&intVector.begin()[0], intVector.size());
   ...

No wonder I hate C++.
　

Nick writes:

You are amazing! How do you figure it out? I mean this seems like
meaningless. It reminds me what Dr. Grogono commented some examples of
difference between VC6 and G++ I sent to him a couple of years ago. He said
it was "nuisance".

VC6 basically always works whatever I make changes on any type, say int
array[] or int*array.
And I made it a bit easy reading based on your way like this:

display(&(*intVector.begin()), intVector.size());

Can you give me some clue why it behaviors like this? Thank you in advance.

Thanks  so much and I really appreciate your help!!!

　

And here is the riddle:

#include <vector>
#include <cstdio>

using namespace std;

typedef vector<int> IntVector;

void display(IntVector& intVector);

void display(int array[], int size);


int main()
{
	int arraySize=rand()%100+1;//make it at least one
	int i;
	IntVector intVector;
	for (i=0; i<arraySize; i++)
	{
		intVector.push_back(rand()%100);
	}

	display(intVector);
	display(&(*intVector.begin()), intVector.size());

	return 0;
}

void display(IntVector& intVector)
{
	printf("display as vector\n");
	for (int i=0; i<intVector.size(); i++)
	{
		printf("%d#%d\n", i, intVector[i]);
	}
}

void display(int array[], int size)
{
	printf("display as int array\n");
	for (int i=0; i<size; i++)
	{
		printf("%d#%d\n", i, array[i]);
	}
}





	The Silly Simple Find

I feel frustrated with the "find" command. In most cases, I can't understand what the man page is talking about. It seems the easiest way 

is just writing my own simple tool. And I find a strange thing in Linux that the command line parameter cannot have string with "*" which

will confuse the "argc". This is insane!

<<<<<<<<Actually this is a BUGGY program in linux and you should know that if you are familiar with Linux. There are at least two big 

problems with Linux version. What is it? I will post the correct one tomorrow below and also keep the following buggy one for comparsion.>>>>

#ifndef LINUX_VERSION

#include <windows.h>
#include <stdio.h>

//assume dir is directory 
void genericFind(char* dir, char* pattern)
{
	HANDLE handle;	
	char*src, *tgt;
	char curFileName[256];
	char wildFileName[256];
	
	WIN32_FIND_DATA ffd;

	sprintf(wildFileName, "%s\\*.*", dir);
	handle=FindFirstFile(wildFileName, &ffd);
	if (handle==INVALID_HANDLE_VALUE)
	{
		printf("findfirst failed of error code =%d\n", GetLastError());
		exit(19);
	}
	do
	{	
		if (strcmp(ffd.cFileName, ".")!=0 && strcmp(ffd.cFileName, "..")!=0)
		{
			sprintf(curFileName, "%s\\%s", dir, ffd.cFileName);
			if  (GetFileAttributes(curFileName)&FILE_ATTRIBUTE_DIRECTORY)
			{
				genericFind(curFileName, pattern);
			}
			else
			{			
				src=ffd.cFileName;
				tgt=pattern;
				while (*src && *tgt && *src==*tgt)
				{
					src++;
					tgt++;
				}
				if (*tgt==0 || *tgt=='*')
				{
					printf("find matching %s\n", ffd.cFileName);
				}				
			}
		}
	}
	while (FindNextFile(handle, &ffd));	
	
	FindClose(handle);
}

#else

#include <cstdio>
#include <cstdlib>
#include <dirent.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>


void genericFind(char* dirName, char* pattern)
{
	struct stat buf;	
	char curFileName[256];
	int nameLen;

	char* src, *tgt;
	DIR* dirPtr;
	struct dirent* direntPtr;
	printf("begin searching %s...\n", dirName);

	if ((dirPtr=opendir(dirName))==NULL)
	{
		//perror("read dir");
		//exit(1234);
		//printf("unable open %s\n", dirName);
		return;
	}
	nameLen=strlen(dirName);
	strcpy(curFileName, dirName);
	while ((direntPtr=readdir(dirPtr))!=NULL)
	{
		if (strcmp(direntPtr->d_name, ".")!=0&&strcmp(direntPtr->d_name, "..")!=0)
		{
			curFileName[nameLen]='/';
			strcpy(curFileName+nameLen+1, direntPtr->d_name);
			lstat(curFileName, &buf);
	
			if (S_ISREG(buf.st_mode))
			{
				src=direntPtr->d_name;
				tgt=pattern;
				while (*src && *tgt && *tgt!='*'&& toupper(*src)==toupper(*tgt))
				{
					src++;
					tgt++;
				}
				if (*tgt==0 || *tgt=='*')
				{
					printf("find matching of %s\n", curFileName);
				}
			}
			else
			{
				if (S_ISDIR(buf.st_mode))
				{	
					genericFind(curFileName, pattern);
							
				}
			}
		}
	}
}

#endif

int main(int argc, char** argv)
{
	int i;
	if (argc==3)
	{
		genericFind(argv[1], argv[2]);
	}
	else
	{
		printf("argc=%d error\n", argc);
		for (i=0; i<argc; i++)
		{
			printf("[%d]=%s\n", i, argv[i]);
		}	
	}

	return 0;
}

<<<<<<<<<<<<<<<<<<<<<<<<<<This is the correct version for linux.>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Originally I plan to do the "quiet" mode by hide error message options. but NBD(no big deal)

#define LINUX_VERSION 1

#ifndef LINUX_VERSION

#include <windows.h>
#include <stdio.h>

//assume dir is directory 
void genericFind(char* dir, char* pattern)
{
	HANDLE handle;	
	char*src, *tgt;
	char curFileName[256];
	char wildFileName[256];
	
	WIN32_FIND_DATA ffd;

	sprintf(wildFileName, "%s\\*.*", dir);
	handle=FindFirstFile(wildFileName, &ffd);
	if (handle==INVALID_HANDLE_VALUE)
	{
		printf("findfirst failed of error code =%d\n", GetLastError());
		exit(19);
	}
	do
	{	
		if (strcmp(ffd.cFileName, ".")!=0 && strcmp(ffd.cFileName, "..")!=0)
		{
			sprintf(curFileName, "%s\\%s", dir, ffd.cFileName);
			if  (GetFileAttributes(curFileName)&FILE_ATTRIBUTE_DIRECTORY)
			{
				genericFind(curFileName, pattern);
			}
			else
			{			
				src=ffd.cFileName;
				tgt=pattern;
				while (*src && *tgt && *tgt!='*'&& toupper(*src)==toupper(*tgt))
				{
					src++;
					tgt++;
				}
				if (*tgt==0 || *tgt=='*')
				{
					printf("find matching %s\n", ffd.cFileName);
				}				
			}
		}
	}
	while (FindNextFile(handle, &ffd));	
	
	FindClose(handle);
}

#else

#include <cstdio>
#include <cstdlib>
#include <dirent.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>


void genericFind(char* dirName, char* pattern)
{
	struct stat buf;	
	char curFileName[256];
	int nameLen;
	int startPos;

	char* src, *tgt;
	DIR* dirPtr;
	struct dirent* direntPtr;
	//printf("begin searching %s...\n", dirName);

	if ((dirPtr=opendir(dirName))==NULL)
	{
		perror("read dir");
		//exit(1234);
		printf("unable open %s\n", dirName);
		return;
	}
	nameLen=strlen(dirName);
	strcpy(curFileName, dirName);
	while ((direntPtr=readdir(dirPtr))!=NULL)
	{
		if (strcmp(direntPtr->d_name, ".")!=0&&strcmp(direntPtr->d_name, "..")!=0)
		{
			if (nameLen>1)
			{
				curFileName[nameLen]='/';
				startPos=nameLen+1;
			}
			else
			{
				startPos=1;
			}
			strcpy(curFileName+startPos, direntPtr->d_name);
			lstat(curFileName, &buf);
	
			if (S_ISREG(buf.st_mode))
			{
				src=direntPtr->d_name;
				tgt=pattern;
				while (*src && *tgt && *tgt!='*' && *src==*tgt)
				{
					src++;
					tgt++;
				}
				if (*tgt==0 || *tgt=='*')
				{
					printf("find matching of %s\n", curFileName);
				}
			}
			else
			{
				if (S_ISDIR(buf.st_mode))
				{	
					genericFind(curFileName, pattern);
							
				}
			}
		}
	}
	closedir(dirPtr);
}

#endif

int main(int argc, char** argv)
{
	int i;
	if (argc==3)
	{
		printf("begin search directory %s for pattern %s...\n\n", argv[1], argv[2]);
		genericFind(argv[1], argv[2]);
	}
	else
	{
		printf("argc=%d error\n", argc);
		for (i=0; i<argc; i++)
		{
			printf("[%d]=%s\n", i, argv[i]);
		}	
	}

	return 0;
}

         Copy or Reference?

This is a small question. (Don't blame me, the original code style is like this.)

here it comes...

the result:

<1,2,0> <1,2,0> <1,2,0>
but I expect:
<0,0,0><1,0,0><1,2,0>
 

import java.util.*;


public class ArrayListTest { 

public static void main(String[] args){

ArrayList<int[]> events_da0 = new ArrayList<int[]>(); 


int[] eventID_da0={0,0,0}; 

events_da0.add(eventID_da0); 

eventID_da0[0]=1; 

events_da0.add(eventID_da0); 

eventID_da0[1]=2;

events_da0.add(eventID_da0);


for (int i = 0; i < events_da0.size(); i++){

int[] event=(int [])events_da0.get(i);

System.out.print("\t"+"<"+event[0]+","+event[1]+","+event[2]+">"); 

}

System.out.print("\n");

}

}

here it goes...

It is very simple. Without running your program, I think you are confused with "copy" and "reference" in java. Actually all objects in java are using "reference" which means unless you use "new", you are referring to same object.
 
The "eventID_da0" is an object and you add the "reference" of this object three times to your "events_da0". So, you are just printing three times of the same object in final display. 
 
The correct way is to declare a simple "pointer" without "new" until you are going to add it to your "events_da0 ".
 
for example,
//int[] eventID_da0={0,0,0}; 

int[] eventID_da0; //don't initialize

...

 

eventID_da0=new int[3]; //exact syntax,you can check by yourself, I don't use java for many months.

eventID_da0[0]=1; 

events_da0.add(eventID_da0); 

...

 

eventID_da0=new int[3]; //exact syntax,you can check by yourself, I don't use java for many months.

eventID_da0[1]=2; 

events_da0.add(eventID_da0); 

...

 

by doing this, you are actually creating new objects every time and add them into your "list".

 

If it is not like this, let me know.