[全民编程]76道高难度C++练习题.含NOI竞赛题.欢迎挑战(页 4) - C++论坛 - C++教室

HJin 发表于 2007-6-19 04:45

/*--------------------------------------------------------------------------- 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 <a href="http://bbs.bc-cn.net/viewthread.php?tid=147853" target="_blank" >http://bbs.bc-cn.net/viewthread.php?tid=147853</A> */

#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; } 
[align=right][color=#000066][此贴子已经被作者于2007-6-19 6:17:01编辑过][/color][/align]

HJin 发表于 2007-6-19 06:55

/*--------------------------------------------------------------------------- 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 <a href="http://bbs.bc-cn.net/viewthread.php?tid=147853" target="_blank" >http://bbs.bc-cn.net/viewthread.php?tid=147853</A> */

#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; }

HJin 发表于 2007-6-19 07:31

/*--------------------------------------------------------------------------- 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 <a href="http://bbs.bc-cn.net/viewthread.php?tid=147853" target="_blank" >http://bbs.bc-cn.net/viewthread.php?tid=147853</A> */
 #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; }

aipb2007 发表于 2007-6-19 08:24

[em09][em17]

HJin 发表于 2007-6-19 09:21

/*--------------------------------------------------------------------------- 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 <a href="http://bbs.bc-cn.net/viewthread.php?tid=147853" target="_blank" >http://bbs.bc-cn.net/viewthread.php?tid=147853</A> */

#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; } } }

HCL 发表于 2007-6-19 12:50

哇~这么强啊!!!厉害[em17]

HJin 发表于 2007-6-19 14:02

/*--------------------------------------------------------------------------- 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 <a href="http://bbs.bc-cn.net/viewthread.php?tid=147853" target="_blank" >http://bbs.bc-cn.net/viewthread.php?tid=147853</A> */

#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"; }

HJin 发表于 2007-6-19 14:14

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).
[align=right][color=#000066][此贴子已经被作者于2007-6-21 5:56:20编辑过][/color][/align]

tianma8778 发表于 2007-6-19 16:26

第三题挑个简单的 #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(); }

aipb2007 发表于 2007-6-19 16:28

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.[em04] 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.[em02] I will see all your solutions above when I come to the same subject.[em17]

HJin 发表于 2007-6-19 17:06

/*--------------------------------------------------------------------------- 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 <a href="http://bbs.bc-cn.net/viewthread.php?tid=147853" target="_blank" >http://bbs.bc-cn.net/viewthread.php?tid=147853</A> */

#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; }

yuyunliuhen 发表于 2007-6-19 17:17

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!
[align=right][color=#000066][此贴子已经被作者于2007-6-19 17:20:02编辑过][/color][/align]

HJin 发表于 2007-6-19 17:26

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

野比发表于 2007-6-19 19:46

HJin...I 服了 You... 受我一拜.. orz 继续消化...

aipb2007 发表于 2007-6-19 20:39

To HJin : Where are you?

love154139 发表于 2007-6-20 13:14

都是高手啊。...参考参考
[align=right][color=#000066][此贴子已经被作者于2007-6-20 13:18:05编辑过][/color][/align]

kai 发表于 2007-6-20 21:28

关于第一题给出另一种解法： 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 一个套一个，但是免去了很多的测试，效率应该高一些。

野比发表于 2007-6-20 22:05

有点意思....

kai 发表于 2007-6-24 05:23

关于第二题，其实是数字电路的问题。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]

HJin 发表于 2007-6-24 06:51

/*--------------------------------------------------------------------------- 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 <a href="http://bbs.bc-cn.net/viewthread.php?tid=147853" target="_blank" >http://bbs.bc-cn.net/viewthread.php?tid=147853</A>
2. <a href="http://en.wikipedia.org/wiki/Latin_square" target="_blank" >http://en.wikipedia.org/wiki/Latin_square</A> */
#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; } 
[align=right][color=#000066][此贴子已经被作者于2007-6-24 7:23:26编辑过][/color][/align]

页: 1 2 3 [4] 5 6 7 8 9 10 11 12 13