/* FILE: randHanoi_2_configs.cpp last change: 29-Aug-2012 author: Romeo Rizzi * generates a random instance for exercise 2 "hanoi" of the 03-Sept-2012 exam in Algorithms. * Usage syntax: * > randHanoi_2_configs (filename, number of disks, random seed generator) */ #include #include #include #include #include using namespace std; const int MAX_N = 1000; const int MAX_BOOP = 30; int n; // number of disks: the disks are numbered from 1 (the smallest) to n (the biggest) int cpd[MAX_N +1], tpd[MAX_N +1]; //current and target position of each disk int boop; // name of the biggest out of place disk // (when n is large, cpd[i] == tpd[i] for all the large i, otherwise too many moves are needed). // boop is the largest i such that cpd[i] != tpd[i] int RandNumber(int min, int max) { /* returns an integer in [min, max] * see Stroustrup "The c++ Programming Language" 3th edition pg. 685 * for comments on the following manipulation choice. * In particular, considerations on the bad quality of low bits come into account. */ return min + (int) ( (max-min) * (double(rand()) / RAND_MAX) ); } int main(int argc, char** argv) { srand(time(NULL)); ofstream fout(argv[1]); assert( fout ); boop = n = atoi(argv[2]); if(argc > 3) boop = atoi(argv[3]); if(argc > 4) srand( atoi(argv[4]) ); assert( n >= 0 ); assert( n <= MAX_N ); assert( boop >= 0 ); assert( boop <= n ); for(int i = 1; i <= n; i++) tpd[i] = cpd[i] = RandNumber(1, 3); tpd[boop] = 1 + ( cpd[boop] + RandNumber(0,1) ) % 3; for(int i = 1; i < boop; i++) tpd[i] = RandNumber(1, 3); fout << n << endl; for(int p = 1; p <= 3; p++) { for(int i = n; i; i--) if(cpd[i] == p) fout << i << " "; fout << "0" << endl; } for(int p = 1; p <= 3; p++) { for(int i = n; i; i--) if(tpd[i] == p) fout << i << " "; fout << "0" << endl; } /* in compact form: for(int i = 1; i <= n; i++) fout << cpd[i] << " "; fout << endl; for(int i = 1; i <= n; i++) fout << tpd[i] << " "; fout << endl; */ fout.close(); return 0; }