/*---------------------------------------------------------------------------
File name: C76-48.cpp
Author: HJin
Created on: 6/18/2007 15:15:52

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

经典 76 道编程题 之 48:

48. 将４个红球，３个白球与３个黄球排成一排，共有多少种排法？

Answer: binomial(10, 4) * binomial(6, 3) * binomial(3, 3) = 4200.

Analysis:

Allocate r+w+y (=10) slots. The job can be done in three steps:
(1) we put all r red balls into the r+w+y slots --- total is binomial(r+w+y, r)
(2) we put all w white balls into the remaining w+y slots --- total is binomial(w+y, y)
(3) we put all y yellow balls into the remaining y slots --- total is binomial(y, y) = 1

All in all, total is binomial(r+w+y, r) * binomial(w+y, y) * 1.

Programming thoughts:

Generate all 3^(r+w+y) possible choices (since each slot can have one of the
three colors ) and check if a choice is valid. A choice is valid if and only
if there are r red balls, w white balls, and y yellow balls.

We used a set in the implementation, since set does not store duplicates.

Sample output:

1 rrwy
2 rryw
3 rwry
4 rwyr
5 ryrw
6 rywr
7 wrry
8 wryr
9 wyrr
10 yrrw
11 yrwr
12 ywrr
total number of different combinations are 12
Press any key to continue . . .

Reference:

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

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

string buffer;

/**
Time complexity is O(3^(r+w+y)) --- very inefficient.

build the set of all combinations.
*/
void buildSet(int r, int w, int y, int n, set<string>& s);

/**
wrap the function buildSet() and outputs results.
*/
int combination(int r, int w, int y, bool print = true);
/**
check if the string is valid.

A choice is valid if and only if there are r red balls, w white balls, and
y yellow balls.
*/
bool isValid(int r, int w, int y, string& str);

int main(int argc, char** argv)
{
// test #3
//int r=4;
//int w=3;
//int y=3;

// test #2
//int r=3;
//int w=2;
//int y=2;

// test #1
int r=2;
int w=1;
int y=1;

cout<<"total number of different combinations are "<<combination(r, w, y, true)<<endl;

return 0;
}

void buildSet(int r, int w, int y, int n, set<string>& s)
{
if(n==0)
{
if(isValid(r, w, y, buffer))
{
s.insert(buffer);
}

return;
}

string temp = buffer; // keep previous state

buffer+="r";
buildSet(r, w, y, n-1, s);

buffer = temp; // recall previous state
buffer+="w";
buildSet(r, w, y, n-1, s);

buffer = temp; // recall previous state
buffer+="y";
buildSet(r, w, y, n-1, s);
}

int combination(int r, int w, int y, bool print)
{
set<string> s;
int n = r+w+y;
int counter = 0;

buildSet(r, w, y, n, s);

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

return s.size();
}

bool isValid(int r, int w, int y, string& str)
{
int r_=0; // store # of red balls
int w_=0;
int y_=0;
bool res = false;

for(size_t i =0; i<str.size(); ++i)
{
switch(str[i])
{
case 'r':
++r_;
break;
case 'w':
++w_;
break;
case 'y':
++y_;
break;
}
}

res = (r_==r) && (w_==w) && (y_==y);

return res;
}

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

/*---------------------------------------------------------------------------
File name: C76-10.cpp
Author: HJin
Created on: 6/18/2007 15:15:52

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

经典 76 道编程题 之 10:

10. 如图１所示，编写程序计算 ┎┰┰┰┰┰┰┰┰┰┒
大大小小正方形共有多少？当最小 ┠╂╂╂╂╂╂╂╂╂┨
正方行边长为１时，它们的总面积 ┠╂╂╂╂╂╂╂╂╂┨
共为多少？ ┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┠╂╂╂╂╂╂╂╂╂┨
┖┸┸┸┸┸┸┸┸┸┚

Analysis:

i | # of squares with side length i | total area
----+------------------------------------------------
n | 1^2 | n*1^2
n-1 | 2^2 | (n-1)*2^2
n-2 | 3^2 | (n-2)*3^2
.....................................................
2 | (n-2)^2 | 2*(n-2)^2
1 | n^2 | 1*n^2

total number of squares is 1^2 + 2^2 +... +n^2 = n*(n+1)*(2*n+1)/6
total area is 1*n^2 + 2*(n-1)^2 + ... + n*1^2 = n*(n+1)^2*(n+2)/12

Sample output:

n | # of squares | total area | # of squares 2 | total area 2
-----+--------------+--------------+----------------+---------------
1 | 1 | 1 | 1 | 1
2 | 5 | 6 | 5 | 6
3 | 14 | 20 | 14 | 20
4 | 30 | 50 | 30 | 50
5 | 55 | 105 | 55 | 105
6 | 91 | 196 | 91 | 196
7 | 140 | 336 | 140 | 336
8 | 204 | 540 | 204 | 540
9 | 285 | 825 | 285 | 825
10 | 385 | 1210 | 385 | 1210
11 | 506 | 1716 | 506 | 1716
12 | 650 | 2366 | 650 | 2366
13 | 819 | 3185 | 819 | 3185
14 | 1015 | 4200 | 1015 | 4200
15 | 1240 | 5440 | 1240 | 5440
16 | 1496 | 6936 | 1496 | 6936
17 | 1785 | 8721 | 1785 | 8721
18 | 2109 | 10830 | 2109 | 10830
19 | 2470 | 13300 | 2470 | 13300
-----+--------------+--------------+----------------+---------------
Press any key to continue . . .

Reference:

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

#include <iostream>
#include <iomanip>
using namespace std;

int numOfSquares(int n);
int totalArea(int n);

int numOfSquares2(int n);
int totalArea2(int n);

int main(int argc, char** argv)
{
cout<<"n | # of squares | total area | # of squares 2 | total area 2\n";
cout<<"-----+--------------+--------------+----------------+---------------\n";

for(int i=1; i<20; ++i)
cout<<std::left<<setw(4)<<i<<" | "
<<setw(12)<<numOfSquares(i)<<" | "
<<setw(12)<<totalArea(i)<<" | "
<<setw(14)<<numOfSquares2(i)<<" | "
<<setw(12)<<totalArea2(i)
<<endl;
cout<<"-----+--------------+--------------+----------------+---------------\n";

return 0;
}

int numOfSquares(int n)
{
int sum =0;
for(int i=1; i<=n; ++i)
sum += i*i;

return sum;
return n*(n+1)*(2*n+1)/6;
}

int numOfSquares2(int n)
{
// don't write n/6*(n+1)*(2*n+1)
// this could give you 0, since 1/6 = 0
return n*(n+1)*(2*n+1)/6;
}

int totalArea(int n)
{
int area = 0;

for(int i=1; i<=n; ++i)
{
area += i*(n+1-i)*(n+1-i);
}

return area;
}

int totalArea2(int n)
{
return n*(n+1)*(n+1)*(n+2)/12;
}

/*---------------------------------------------------------------------------
File name: C76-13.cpp
Author: HJin
Created on: 6/18/2007 15:15:52

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

经典 76 道编程题 之 13:

13. 有N个硬币（N为偶数）正面朝上排成一排，每次将 N-1 个硬币翻过来放在原位
置， 不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。编程让计算机把
翻币的最简过程及翻币次数打印出来（用＊代表正面，O 代表反面）。

Analysis:

Since we are changing the states of N-1 items each time, there is one coin which
keeps its previous state.

1 --- 正面 (or ＊)
0 --- 反面

1 1 1 1 (original state: #0)
0 0 0 1 (#1 --- keeps N = 4)
1 1 0 0 (#2 --- keeps N-1 = 3)
0 1 1 1 (#3 --- keeps N-2 = 2)
0 0 0 0 (#4 --- keeps N-3 = 1)

This is true for the general case N.

Sample output:

＊ ＊ ＊ ＊
0 0 0 ＊
＊ ＊ 0 0
0 ＊ ＊ ＊
0 0 0 0
Press any key to continue . . .

Reference:

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

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

void print(const vector<bool>& v);
int tossCoins(int n);

int main(int argc, char** argv)
{
tossCoins(4);

return 0;
}

int tossCoins(int n)
{
vector<bool> v;
int i;
int j;

// orginal state
v.resize(n);
for(i=0; i<n; ++i)
v[i] = true;
print(v);

for(i=n-1; i>=0; --i)
{
for(j=0; j<n; ++j)
v[j] = !v[j];
v[i] = !v[i]; // keeps v[i]

print(v);
}

return n;
}

void print(const vector<bool>& v)
{
for(vector<bool>::const_iterator iter = v.begin(); iter != v.end(); ++iter)
{
if(*iter)
cout<<setw(4)<<"＊";
else
cout<<setw(4)<<"0";
cout<<" ";
}
cout<<endl;
}

/*---------------------------------------------------------------------------
File name: C76-17.cpp
Author: HJin
Created on: 6/18/2007 18:21:10

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

经典 76 道编程题 之 17:

17. 编写一个程序，当输入不超过６０个字符组成的英文文字时，计算机将这个句子
中的字母按英文字典字母顺序重新排列，排列后的单词的长度要与原始句子中的长度
相同。例如：

输入：

ＴＨＥ ＰＲＩＣＥ ＯＦＢＲＥＡＤ ＩＳ ￥１ ２５ ＰＥＲ ＰＯＵＮＤ

输出：

ＡＢＣ ＤＤＥＥＥ ＥＦＨＩＩＮＯ ＯＰ ￥１ ２５ ＰＰＲ ＲＲＳＴＵ

并且要求只对Ａ到Ｚ的字母重新排列，其它字符保持原来的状态。

Analysis:

This is really a counting sort problem --- count how many letters A to Z.

Sample output:

THE PRICe OFBREAD IS $1.25 PER POUND
ABC DDEEE EFHIINO OP $1.25 PPR RRSTU
Press any key to continue . . .

Reference:

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

#include <iostream>
#include <iomanip>
using namespace std;

/**
counting sort to sort the letters 经典 76 道编程题 之 17.

Space complexity: O(1).
Time complexity: O(strlen(s)).
*/
void counting_sort(char* s);

int main(int argc, char** argv)
{
char s[] = "THE PRICe OFBREAD IS $1.25 PER POUND";

cout<<s<<endl;

counting_sort(s);
cout<<s<<endl;

return 0;
}

void counting_sort(char* s)
{
/**
c[0] --- stores how many letter A in s
c[1] --- stores how many letter B in s
...
c[25] --- stores how many letter Z in s
*/
int c[26];
int n =strlen(s);
int i;
int j;

// initiate counters to 0
for(j=0; j<26; ++j)
{
c[j] = 0;
}

for(i=0; i<n; ++i)
{
// toupper() does not affect non-alpha letters.
s[i] = toupper(s[i]);
}

// count number of different capital letters
for(i=0; i<n; ++i)
{
if(s[i] >='A' && s[i] <='Z')
{
j = 0+ (s[i] - 'A') ;
++c[ j ];
}
}

i=0;

/**
Although there are two loops here, it is NOT O(25* n).
It is O(n), since i is incremented c[j] times for each j,
and c[0] + c[1] + ... +c[25] <= n.
*/
for(j=0; j<25; ++j)
{
while (c[j] > 0)
{
if(s[i]>='A' && s[i]<='Z')
{
s[i] = 'A'+j;
--c[j]; // used 1 letter, so counter goes down by 1
}
++i;
}
}
}

哇~这么强啊!!!厉害

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

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

经典 76 道编程题 之 1:

1. 给定等式 A B C D E 其中每个字母代表一个数字，且不同数字对应不
D F G 同字母。编程求出这些数字并且打出这个数字的
+ D F G 算术计算竖式。

───────

X Y Z D E

Analysis:

Let A = a[0], B = a[1], ..., Z = a[9], where the array a
is a permutation of the ten digits. The easist way is to
loop over all 10! = 3,628,800 possible permutations for the array a,
and check if the result holds.

C++ has a next_permutation (or prev_permutation) function template
for permutations.

A B C D E F G X Y Z
==============================
a[ 0 1 2 3 4 5 6 7 8 9 ]

Sample output:

A = 2, B = 9, C = 7, D = 8, E = 6,
F = 5, G = 0, X = 3, Y = 1, Z = 4.

2 9 7 8 6
8 5 0
+ 8 5 0
--------------------------------------
= 3 1 4 8 6
Press any key to continue . . .

Reference:

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

#include <iostream>
#define DIM(x) sizeof((x)) / sizeof ( (x)[0] )
#include <algorithm>

using namespace std;

/**
check the result for a permutation.
*/
bool check(int *a);

/**
print result.
*/
void print(int *a);

int main(int argc, char** argv)
{
int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
bool res = check(a);
if(res)
print(a);

// when next_permutation returns false, we permute
// all 10! choices. Time complexity is O(10!)
while( std::next_permutation(a, a+DIM(a)) )
{
res = check(a);
if(res)
print(a);
}

return 0;
}

bool check(int *a)
{
int carry; // carry
bool res;
int temp;

// 1st vertical equation
temp = a[4] + 2*a[6];
res = ( ( temp % 10) == a[4] );
if(!res)
return false;
carry = temp / 10;

// 2nd vertical equation
temp = a[3] + 2*a[5] + carry;
res = res && ( (temp % 10) == a[3] );
if(!res)
return false;
carry = temp / 10;

// 3rd vertical equation
temp = a[2] + 2*a[3] + carry;
res = res && ( ( temp % 10) == a[9] );
if(!res)
return false;
carry = temp / 10;

// 4th vertical equation
temp = a[1] + carry;
res = res && ( ( temp % 10) == a[8] );
if(!res)
return false;
carry = temp / 10;

// 5th vertical equation
temp = a[0] + carry;
res = res && ( ( temp % 10) == a[7] );
if(!res)
return false;

return true;
}

void print(int *a)
{
cout<<"A = "<<a[0]<<", ";
cout<<"B = "<<a[1]<<", ";
cout<<"C = "<<a[2]<<", ";
cout<<"D = "<<a[3]<<", ";
cout<<"E = "<<a[4]<<",\n";
cout<<"F = "<<a[5]<<", ";
cout<<"G = "<<a[6]<<", ";
cout<<"X = "<<a[7]<<", ";
cout<<"Y = "<<a[8]<<", ";
cout<<"Z = "<<a[9]<<".\n\n";

cout<<" "<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<"\n";
cout<<" "<<a[3]<<" "<<a[5]<<" "<<a[6]<<"\n";
cout<<"+ "<<a[3]<<" "<<a[5]<<" "<<a[6]<<"\n";
cout<<"--------------------------------------\n";
cout<<"= "<<a[7]<<" "<<a[8]<<" "<<a[9]<<" "<<a[3]<<" "<<a[4]<<"\n";
}

I just saw aipb2007's solution to #17 --- very clever. Although your space complexity is 2n, the algorithm is easy to follow. Time complexity is O(n lg n ), n = strlen(s) --- since you used a sort (the standard algorithm) which is a comparison sorting, which is necessarily eat least O(n lg n).

My soln is a little hard to understand for a beginner, but it uses only strlen(s) + const space and most importantly, time compelexity is only O(n).

[此贴子已经被作者于2007-6-21 5:56:20编辑过]

第三题挑个简单的

#include "stdio.h"

main()
{
char s[21][21];
char c[]={'T','J','1','2','3','4','5','6','7','8','9'};
int input,i,j;
printf("enter the number betweent 3 to 20");
scanf("%d",&input);
if(input<3||input>20)
{
printf("what you want ");
getch();
return;
}
for(i=0;i<=input;i++)
{
for(j=0;j<=input;j++)
s[i][j]='0';

}
for(i=0;i<=input;i++)
{
for(j=0;j<=input;j++)
printf("%c",s[i][j]);
printf("\n");
}

for(i=input;i>=0;i--)
{
for(j=i;j<=input-i;j++)
{
s[j][i]=c[i];
s[i][j]=c[i];
s[input-i][input-j]=c[i];
s[input-j][input-i]=c[i];
}

}
for(i=0;i<=input;i++)
{
for(j=0;j<=input;j++)
printf("%c",s[i][j]);
printf("\n");
}
getch();
}

To HJin :
Actually I know a little abt algorithms, but I'm really interesting in it. Most of these questions are base on an algorithm, I just found the way to get the answer, abt the efficiency, I didn't consider it.

Recently I have to prepare for the examination.So I have no time to do the subjects.I'll study algorithms during summer holiday. After that I think I can catch your step.

I will see all your solutions above when I come to the same subject.