/*---------------------------------------------------------------------------
File name: C76-24.cpp
Author: HJin
Created on: 6/18/2007 22:53:55

C76-24.cpp --- the cpp source file for solving the 24th of the 76
classical C/C++ problems.

经典 76 道编程题 之 24:

24. 某地街道把城市分割成矩形方格，每一方格叫作块，某人从家中出发上班，
向东要走Ｍ块，向北要走Ｎ块，（见图）。请设计一个程序，由计算机寻找并
打印出所有的上班的路径。

单位

┬ ┌─┬─┬─┬─┬─┬─┬─┐
│ │ │ │ │ │ │ │ │
│ ├─┼─┼─┼─┼─┼─┼─┤
↓ │ │ │ │ │ │ │ │
Ｎ ├─┼─┼─┼─┼─┼─┼─┤
↑ │ │ │ │ │ │ │ │
│ ├─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │ │ │
┴ └─┴─┴─┴─┴─┴─┴─┘
家 ├─────→Ｍ←─────┤

Analysis:

Let us

E --- the person move 1km to the east;
N --- to stand for the person move 1km to the east;

If M= 7, N =4 (as in the figure), then

E E E E E E E N N N N

means that the person travels east 7km first, then he/she travels
north 4km.

A little bit math shows that we have

binomial(M+N, M)

different ways to travel from home to work, since we have to travel
M kms to the east. A way is a choice that how we put the M E's into
M+N slots.

Sample output (for M=5, N=2):

1 EEEEENN
2 EEEENEN
3 EEEENNE
4 EEENEEN
5 EEENENE
6 EEENNEE
7 EENEEEN
8 EENEENE
9 EENENEE
10 EENNEEE
11 ENEEEEN
12 ENEEENE
13 ENEENEE
14 ENENEEE
15 ENNEEEE
16 NEEEEEN
17 NEEEENE
18 NEEENEE
19 NEENEEE
20 NENEEEE
21 NNEEEEE
correct.
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
http://bbs.bc-cn.net/viewthread.php?tid=147853
*/

#include <iostream>
#include <string>
#include <set>
using namespace std;

/**
serious improvment needed: this recursive version is very inefficient.
For M=7, N=4, it takes 3 mintues to compute.

The classical algorithm to permute a string. We use a set to keep
different strings --- some permutations may repeat.

*/
void way_recursive(string& in, string& out, set<string>& ss);

/**
a wrapper of way_recursive.
*/
int way(int M, int N, bool print=true);

/** compute binomial(n, k).
* n >=k
*
*
*/
int binomial(int n, int k); // n choose k

int main(int argc, char** argv)
{
// test #1: --- the recursive way takes long time (3 mintues)
//int M=7;
//int N=4;

// test #2:
int M=5;
int N=2;

int num;

num = way(M, N);

/**
A little bit math shows that the number is binomial(M+N, M).
This is just a check to give you more confidence.
*/
if(num != binomial(M+N, M))
cout<<"wrong number.\n";
else
cout<<"correct.\n";

return 0;
}

void way_recursive(string& in, string& out, set<string>& ss)
{
// in is empty so that all chars are transferred to out buffer
// and out is a permutation of in
if( in.empty() )
{
ss.insert(out); // insert only one copy --- no duplicates
return;
}

// the way to permute a string in one statement
for(size_t i=0; i<in.size(); ++i)
way_recursive(in.substr(0, i) + in.substr(i+1), out+in[i], ss);
}

int way(int M, int N, bool print)
{
set<string> ss;
string in;
string out;
int i;
int counter = 0;

in.resize(M+N);

// the very first way
for(i=0; i<M; ++i)
in[i] = 'E';
for(i=M; i<M+N; ++i)
in[i] = 'N';

// build the set
way_recursive(in, out, ss);

if(print)
{
for(set<string>::const_iterator iter = ss.begin(); iter != ss.end(); ++iter)
{
++counter;
cout<<counter<<"\t"<<*iter<<endl;
}
}

return counter;
}

int binomial(int n, int k)
{
int res = 1;
int i;

if(k>n/2)
k = n-k;

++n;
for(i=1; i<=k; ++i)
{
res *= (n-i);
res /= i;
}

return res;
}

To everybody:
You are good example,I have learned so much from you . I am not good at arithmetic，so I have many things to learn.As aipb2007,I am plan to study arithmetic in the hoilday.Arithmetic is interesting,and I like it.
Exam is coming,I think you are prepareing for exam.so do I.Good luck!
At last,Happy Dragon Boat Festival!

[此贴子已经被作者于2007-6-19 17:20:02编辑过]

Happy holiday to you! Admire you have "zhongzi"..... no Chinese food in this small town for me.

HJin...I 服了 You... 受我一拜.. orz

继续消化...

To HJin :
Where are you?

都是高手啊。...参考参考

[此贴子已经被作者于2007-6-20 13:18:05编辑过]

关于第一题给出另一种解法：

ABCDE + (DFG)*2 = XYZDE <=> (DFG)*2 = XYZDE - ABCDE <=> (XYZ - ABC)*100
<=> DFG = (XYZ - ABC)*50
由此可以看出，E可以取任何数字，只要其他的字母的组合有解。

下面是代码：

[CODE]
#include <iostream>
using namespace std;

int main()
{
int A, B, C, D, E, F, G, X, Y, Z;
int value1, value2, value3;

cout<<"A B C D E F G X Y Z\n";
for(A = 0; A<=8; A++)
{
for(X = A+1; X<=9; X++)
{
for(B = 0; B<=9; B++)
{
if(B==A || B==X)
continue;
for(C = 0; C<=9; C++)
{
if(C==A || C==X || C==B)
continue;
for(Y = 0; Y<=9; Y++)
{
if(Y==A || Y==X || Y==B || Y==C)
continue;
for(Z = 0; Z<=9; Z++)
{
if(Z==A || Z==X || Z==B || Z==C || Z==Y)
continue;
for(D = 0; D<=9; D++)
{
if(D==A || D==X || D==B || D==C || D==Y || D==Z)
continue;
for(F = 0; F<=9; F++)
{
if(F==A || F==X || F==B || F==C || F==Y || F==Z || F==D)
continue;
for(G = 0; G<=9; G++)
{
if(G==A || G==X || G==B || G==C || G==Y || G==Z || G==D || G==F)
continue;
value1 = X*100 + Y*10 + Z;
value2 = A*100 + B*10 + C;
value3 = D*100 + F*10 + G;
if(value3 == ((value1-value2)*50))
{
for(E = 0; E<=9; E++)
{
cout<<A<<" "<<B<<" "<<C<<" "<<D<<" "<<E<<" "<<F<<" "<<G<<" "<<X<<" "<<Y<<" "<<Z<<endl;
}
}
}
}
}
}
}
}
}
}
}

system("pause");
return 0;
}

[/CODE]
这样的代码看上去笨了些，for loop 一个套一个，但是免去了很多的测试，效率应该高一些。

有点意思....

关于第二题，其实是数字电路的问题。5个条件就是第一层的5个门电路，将5个门电路的输出结果在第二层通过一个与门就可以得到最终的结果了。所以代码是很简单的，其中0表示不参加，1表示参加.

listing2.cpp
[CODE]
#include <iostream>
using namespace std;

int main()
{
int A,B,C,D,E;
int out1, out2, out3, out4, out5;
int out;
cout<<"A B C D E\n";
for(A = 0; A<=1; A++)
{
for(B = 0; B<=1; B++)
{
for(C = 0; C<=1; C++)
{
for(D = 0; D<=1; D++)
{
for(E = 0; E<=1; E++)
{
out1 = (A&B) | (!A);
out2 = (!B) | (!C);
out3 = (C&D) | ((!C)&(!D));
out4 = D | E;
out5 = (E & A & D) | (!E);
out = out1 & out2 & out3 & out4 & out5;
if(out == 1)
cout<<A<<" "<<B<<" "<<C<<" "<<D<<" "<<E<<endl;
}
}
}
}
}
return 0;
}

[/CODE]

/*---------------------------------------------------------------------------
File name: C76-4.cpp
Author: HJin
Created on: 6/22/2007 19:33:55

Modification history:

6/23/2007 14:51:02
-----------------------------------------------------------
Apply a recursive technique to construct all Latin Squares of
size n<=6.

This recursive approach gives all the solutions, although it is
fairly slow due to the large number of solutions. For n=7, there
are 61,479,419,904,000 Latin squares. The number 61,479,419,904,000
overflows the integers for 32-bit system.

I consider this problem solved.

6/22/2007 22:34:40
-----------------------------------------------------------
First attack: generate n! Latin squares.

This iterative approach only gives a partial soln, but it is
fast.

C76-4.cpp --- the cpp source file for solving the 4th of the 76
classical C/C++ problems.

经典 76 道编程题 之 4:

4. 在Ｎ行Ｎ列的数阵中, 数Ｋ（１〈＝Ｋ〈＝Ｎ）在每行和每列中出现且仅
出现一次，这样的数阵叫Ｎ阶拉丁方阵。例如下图就是一个五阶拉丁方阵。
编一程序，从键盘输入Ｎ值后，打印出所有不同的Ｎ阶拉丁方阵，并统计个数。

1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

Analysis:

This problem is fairly complex, as it is unsolved for the general case n.
For n<=10, I give the known number of different Latin squares in the
following table

n | # of Latin squares
----+------------------------------------------------------
1 | 1
2 | 2
3 | 12
4 | 576
5 | 161280
6 | 812851200
7 | 61479419904000
8 | 108776032459082956800
9 | 5524751496156892842531225600
10 | 9982437658213039871725064756920320000
11 | 776966836171770144107444346734230682311065600000
>11 | (no one knows the exact number)
----+------------------------------------------------------

If you want only partial solutions for a fairly large n, please check my

generate_iterative()

procedure, which is based on rotating a permuation of 1 2 ... n.

If you want all solutions for n<=6, please check my

generate_recursive()

procedure.

Sample output

(For test #1, n = 5, only 3 Latin squares are shown.)
Latin squares #161278
5 4 3 2 1
4 5 2 1 3
3 2 1 4 5
2 1 5 3 4
1 3 4 5 2
Latin squares #161279
5 4 3 2 1
4 5 2 1 3
3 2 1 5 4
1 3 5 4 2
2 1 4 3 5
Latin squares #161280
5 4 3 2 1
4 5 2 1 3
3 2 1 5 4
2 1 4 3 5
1 3 5 4 2
There are 161280 different Latin Squares for n = 5
Press any key to continue . . .

(For test #2, n = 7, only 3 Latin squares are shown.)
Latin Square #5038
7 6 5 4 2 3 1
5 4 6 2 3 1 7
6 2 4 3 1 7 5
4 3 2 1 7 5 6
2 1 3 7 5 6 4
3 7 1 5 6 4 2
1 5 7 6 4 2 3
Latin Square #5039
7 6 5 4 3 1 2
5 7 4 3 1 2 6
4 5 3 1 2 6 7
3 4 1 2 6 7 5
1 3 2 6 7 5 4
2 1 6 7 5 4 3
6 2 7 5 4 3 1
Latin Square #5040
7 6 5 4 3 2 1
6 5 4 3 2 1 7
5 4 3 2 1 7 6
4 3 2 1 7 6 5
3 2 1 7 6 5 4
2 1 7 6 5 4 3
1 7 6 5 4 3 2
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
http://bbs.bc-cn.net/viewthread.php?tid=147853

2. http://en.wikipedia.org/wiki/Latin_square
*/

#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

/** buffer for 2d array (n! x n)
This buffer stores all the n! permuations for 1 2 ... n.
You can use a set.

If you want to generate all the permuatations along the way,
you spend more time. My technique is sacrifice space in
favor of speed.
*/
int** g_AllPerms;
int g_nFact; // n!

/**
A recursive algorithm to get all the Latin squares of size n.

The number of different Latin squares of size n is stored in counter.

Space complexity: O( (n+1)! ).
Time complexity: O( (n+1)! ).

*/
void generate_recursive(int** a, int n, int numRSF, int& counter, bool print = false);

/**
This generator can only generate n! different Latin squares. Thus,
it is a partial soln.

I cannot describe the idea in plain text format, you may referr to reference 2
and google for "Latin square".

Space complexity: O( (n+1)! ).
Time complexity: O( (n+1)! ).
*/
void generate_iterative(int** a, int* buffer, int n, bool print=true);

/**
Rotate a sequence one position to the left. For example,

1 2 3 4 --> 2 3 4 1.
*/
void rotate(int *aPerm, int n);

/**
Check if the first numRSF rows of a matrix is valid for a Latin
square.

numRSF --- number of Rows So Far
*/
inline bool isValid(int**a, int n, int numRSF);

/**
Copy the content of a buffer to another.
*/
inline void copy(int*dest, int* src, int n);

/**
Compute the facotrial of n.
*/
inline int factorial(int n);

/**
auxilliary functions for 2d array dynamic allocation and deallocation.
*/
template <typename T>
inline T** new2d(int row, int col);

template <typename T>
inline void delete2d(T** arr2d, int row);

int main()
{
/**
All cases for n > 6 cannot be solved by the recursive version, using
32-bit intergers.

If you use the iterative version, you can let n be fairly large.
*/
int n=4;
int i;
int* buf; // buffer for 1d array of size n
int** a;
int counter = 0;

g_nFact = factorial(n);

buf = new int[n];
for(i=0; i<n; ++i)
{
buf[i] = i+1;
}

a = new2d<int>(n, n);
g_AllPerms = new2d<int>(g_nFact, n);

i=0;
copy(g_AllPerms[i], buf, n);
while(next_permutation(buf, buf+n))
{
++i;
copy(g_AllPerms[i], buf, n);
}

// test #1 --- recursive (complete soln)
generate_recursive(a, n, 0, counter, true);
cout<<"There are "<<counter<<" different Latin Squares for n = "<<n<<endl;

// test #2 --- iterative (partial soln)
generate_iterative(a, buf, n);

delete [] buf;
delete2d<int>(a, n);
delete2d<int>(g_AllPerms, n);

return 0;
}

void generate_recursive(int** a, int n, int numRSF, int& counter, bool print)
{
// if all rows are filled
if(numRSF == n )
{
++counter; // update counter

if(print) // print this Latin square
{
cout<<"Latin squares #"<<counter<<endl;
for(int i=0; i<n; ++i)
{
for(int j=0; j<n; ++j)
{
cout<<setw(4)<<a[i][j];
}
cout<<endl;
}
}

return;
}

for(int k=0; k<g_nFact; ++k)
{
for(int i=numRSF; i<n; ++i)
{
// fill in the current row
copy(a[i], g_AllPerms[k], n);

// if the matrix is valid up to row i
// then we fill in the next row
if(isValid(a, n, i))
generate_recursive(a, n, i+1, counter, print);
}
}
}

void generate_iterative(int** a, int* buf, int n, bool print)
{
int i;
int j;
int k;

for(k=0; k<g_nFact; ++k)
{
copy(buf, g_AllPerms[k], n);
for(i=0; i<n; ++i)
{
int value = g_AllPerms[k][buf[0]-1];

for(int j=0; j<n; ++j)
{
a[j][ buf[j]-1 ] = value;
}

rotate(buf, n);
}

// print the matrix
cout<<"Latin Square #"<<k+1<<endl;
for(i=0; i<n; ++i)
{
for(j=0; j<n; ++j)
{
cout<<setw(4)<<a[i][j];
}
cout<<endl;
}
}
}

void rotate(int *aPerm, int n)
{
int i;
int temp = aPerm[0];

for(i=0; i<n-1; ++i)
aPerm[i] = aPerm[i+1];

aPerm[n-1] = temp;
}

bool isValid(int**a, int n, int numRSF)
{
int i;
int j;

for(i=0; i<numRSF; ++i)
{
for(j=0; j<n; ++j)
{
if(a[i][j] == a[ numRSF ] [j])
{
return false;
}
}
}

return true;
}

void copy(int*dest, int* src, int n)
{
int i;

for(i=0; i<n; ++i)
dest[i] = src[i];
}

int factorial(int n)
{
int res = 1;

for(int i=2; i<=n; ++i)
res *= i;

return res;
}

template <typename T>
T** new2d(int row, int col)
{
T** arr2d = new T*[row];
for(int i=0; i<row; ++i)
arr2d[i] = new T[col];

return arr2d;
}

template <typename T>
void delete2d(T** arr2d, int row)
{
for(int i=0; i<row; ++i)
delete [] arr2d[i];

delete [] arr2d;
}

[此贴子已经被作者于2007-6-24 7:23:26编辑过]