《第十讲最后一讲》由会员分享，可在线阅读，更多相关《第十讲最后一讲（29页珍藏版）》请在金锄头文库上搜索。
1、程序设计实习程序设计实习1习题课习题课2951 浮点数高精度求幂2775 文件结构图2787 算24acm3278 catch the cowAcm1321棋盘问题22951题目描述：有一个实数 R ( 0.0 R 99.999 ) ,要求写程序精确计算 R 的 n 次方。n 是整数并且 0 n 951233.求9512312 = 54888318698527214.重新点小数点5488830194541.8992186985272152951 代码代码#include#includeconst int MAX=100;char s7;int aMAX,e,p,b,be,en,i;void m
2、ul()int i,w=0;for(i=0;iMAX;i+)ai=ai*b+w;w=ai/10;ai=ai-w*10;6int main()while (scanf(%s %d,s,&e)!=EOF)memset(a,0,sizeof(a);b=0;/Step 1 and Step 2for(i=0;istrlen(s);i+)if (si=.) p=strlen(s)-i-1;else b=b*10+si-0;a0=1;/Step 3for(i=0;i=p-1;be-);for (en=0;aen=0&en=p;i-) printf(%d,ai);if (en=en;i-) printf(%
3、d,ai);printf(n);return 0;72775 文件结构图文件结构图file1file2dir3dir2file1file2file4dir1file3*file2file1*#DATA SET 1:DATA SET 1:ROOTROOT| dir3| dir3| | dir2| | dir2| | file1| | file1| | file2| | file2| dir1| dir1file1file1file2file2file3file3file4file4DATA SET 2:DATA SET 2:ROOTROOTfile1file1file2file282775 文件
4、结构图文件结构图file1file2dir3dir2file1file2file4dir1file3*file2file1*#回想表达式处理的题目回想表达式处理的题目, , 没有必要没有必要在内存生成整个目录树在内存生成整个目录树, ,因为整个因为整个目录树已经以递归的结构存储在输目录树已经以递归的结构存储在输入数据里了入数据里了. .因此递归处理输入数据的过程就是因此递归处理输入数据的过程就是递归遍历整个目录树的过程。递归遍历整个目录树的过程。递归过程中，碰到目录名就立刻输递归过程中，碰到目录名就立刻输出，按题目要求，碰到文件名不能出，按题目要求，碰到文件名不能立刻输出，要存起来，等整个目录
5、立刻输出，要存起来，等整个目录处理完后，再排序输出。处理完后，再排序输出。9#include #include #include #include using namespace std;void ListDir( const char * root); /处理文件夹int nCurLevel = 0; /记录当前所在的目录层次int MyCompare( const void * e1, const void * e2)/对文件名排序的比较函数return strcmp( (const char * ) e1, (const char * ) e2);10int main() int nDa
6、tasetNo = 1;do cout DATA SET nDatasetNo : endl;nCurLevel = 0;ListDir(ROOT); /处理根目录/下面处理下一个test casechar c;do /跳过回车换行符c = cin.peek();if( c = r | c = n )cin.get();while( c = r | c = n);if( c = #)break;else cout endl;nDatasetNo +;while(1);return 0;11void ListDir( const char * root)char sLine200;char vF
7、iles20030 ; int nTotalFiles = 0;int i,j;for( i = 0;i nCurLevel; i + )cout | ;cout root sLine;switch( sLine0 ) case *:case :qsort( vFiles, nTotal);for( j = 0 ; j nTotalFiles; j + ) for( i = 0;i nCurLevel; i + )cout | ;cout vFilesj endl;nCurLevel -;/处理完一个文件夹，退到上一层return;12case f:strcpy( vFilesnTotalFi
8、les +,sLine);break;case d:nCurLevel +;/要进入一个文件夹，层次增加ListDir( sLine);break;while(1);132787 算算24输入：5 5 5 1 1 1 4 2 0 0 0 0 输出：YESNO142787 算算24子问题：k个数算24递归：从k个数算24，规约到k-1个数算24方法：从k个数中选2个数a和b，及一种运算op；将a和b从k个数中删除，再将(a op b)加入15#include using namespace std;double Numbers5;bool Calc( double * pNumbers, int
9、 n );/用pNumbers数组里的n个数算24看能否成功int main() int a4;int nZeroNum = 0;while(true) for( int i = 0;i Numbersi;if( Numbersi = 0 )nZeroNum +;if( nZeroNum = 4 )break;if( Calc( Numbers,4)cout YES endl;elsecout NO 23.99999 & pNumbers0 24.00001 )return true;elsereturn false;for( i = 0;i n - 1;i + ) for( j = i +
10、1; j n; j + ) /枚举两个数先算int m = 0;for( k = 0; k n; k + ) /把剩下的数留住if( k != i & k != j )aNumberm+ = pNumbersk;/用枚举出的两个数的和，以及剩下的数，继续算24aNumberm = pNumbersi + pNumbersj;if( Calc( aNumber, n -1 ) return true;17aNumberm = pNumbersi * pNumbersj;if( Calc( aNumber, n -1 )return true;aNumberm = pNumbersi - pNum
11、bersj;if( Calc( aNumber, n -1 )return true;aNumberm = pNumbersj - pNumbersi;if( Calc( aNumber, n -1 )return true;if( pNumbersi != 0) aNumberm = pNumbersj / pNumbersi;if( Calc( aNumber, n -1 )return true;if( pNumbersj != 0) aNumberm = pNumbersi / pNumbersj;if( Calc( aNumber, n -1 )return true;return
12、false; /各种方法都算不出来，则断定不成功18acm1321 棋棋盘问题在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。Input输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n = 8 , k = n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行
13、或者空白列）。 Output对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C231）。19acm1321 棋棋盘问题Sample Input2 1 #. .# 4 4 .# .#. .#.#.-1 -1 Sample Output2 1 20acm1321 棋棋盘问题思路：思路：和八皇后几乎一和八皇后几乎一样，不同之，不同之处在于可以有不在于可以有不摆棋子的空行棋子的空行所以要两个所以要两个变量量记录一下已一下已经摆了多少空行了多少空行,和多少个棋子已和多少个棋子已经摆好好21#include using namespace std;char Grid99; int n,k;
14、int nTotal = 0; /总方案数int anPos9;int nBlankRows = 0; int nDoneNum = 0; /已摆好的棋子数目void Queen(int nRow);int main() int i,j;while( true) cin n k;if( n = -1 & k = -1 ) break;for( i = 0;i n;i + )for( j = 0;j Gridij;nTotal = 0;nBlankRows = 0;nDoneNum = 0;Queen(0); /从第0行开始摆cout nTotal endl;return 0;22void Qu
15、een(int nRow)if( nRow = n | nDoneNum = k) /如果已经摆到第n行（行号从0开始），或者已经没有棋子要摆了，/ 则说明成功，总方案数要加1nTotal +;return ;int i,j;for( i = -1; i n; i + ) /逐个尝试摆放位置，摆在位置-1就代表该行是空行if( i = -1 ) if( nBlankRows n - k ) /如果还能放空行anPosnRow = -1;/放空行nBlankRows +;Queen( nRow + 1 ) ;/尝试本行新位置前，已摆放的空行数要复原nBlankRows -; 23else if(
16、 GridnRowi = # ) for( j = 0; j nRow; j + )if( anPosj = i ) /和前面的同列break;if( j = nRow ) anPosnRow = i; /第nRow行摆位置inDoneNum +; /已摆好棋子数加1Queen(nRow + 1 );/摆下一行/尝试本行新位置前，已摆好棋子数/要复原nDoneNum -; 24acm3278 Catch That CowFarmer John has been informed of the location of a fugitive cow and wants to catch her i
17、mmediately. He starts at a point N (0 N 100,000) on a number line and the cow is at a point K (0 K 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute* Teleporti
18、ng: FJ can move from any point X to the point 2 X in a single minute.If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?25acm3278 Catch That Cow广度优先搜索如果忘了判重，就会RLE如果不剪枝，就会RLE剪枝：1)没必要走到 x0的位置2)如果已经在牛的右边，就不该再往右走3)如果往右跳后，和牛的距离变得更远了，那就不要往右边跳如果没有
19、注意到人可能需要走到牛的右边，判重的标志数组不够大，就会RLE 26#include #include #include using namespace std;int n,k;struct SNode int x;int nSteps;SNode aQueue3000000;int anRepeated300000;int nHead,nTail;int main()cin n k;memset( anRepeated,0,sizeof(anRepeated);nHead = 0;nTail = 1;aQueue0.x = n;aQueue0.nSteps = 0;27while( nHea
20、d != nTail ) if( aQueuenHead.x = k ) cout aQueuenHead.nSteps;return 0;if ( aQueuenTail.x = 0 ) aQueuenTail.x = aQueuenHead.x - 1;if( anRepeatedaQueuenTail.x = 0 ) aQueuenTail.nSteps = aQueuenHead.nSteps + 1;anRepeatedaQueuenTail.x = 1;nTail+;if( aQueuenHead.x * 2 - k = k - aQueuenHead.x ) /往右跳得太远没有意
21、义aQueuenTail.x = aQueuenHead.x * 2;if( anRepeatedaQueuenTail.x = 0 ) aQueuenTail.nSteps = aQueuenHead.nSteps + 1;anRepeatedaQueuenTail.x = 1;nTail+;nHead +;28if( aQueuenHead.x * 2 - k = k - aQueuenHead.x ) /往右跳得太远没有意义aQueuenTail.x = aQueuenHead.x * 2;if( anRepeatedaQueuenTail.x = 0 ) aQueuenTail.nSteps = aQueuenHead.nSteps + 1;anRepeatedaQueuenTail.x = 1;nTail+;nHead +;29
