实验五-8枚硬币问题

实验报告实验项目：8枚硬币问题班级:计算机姓名： 一、 实验题目：在8枚外观相同的硬币中，有一枚是假币，并且一直假币与真币的质量不同但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个搞笑的算法來检测出这枚假币。二、 实验目的：进一步掌握递减治法的设计思想：提高应用减治法设计算法的技能：(2)理解这样一个观点：建立正确的模型对于问题的求解是非常重要的。三、 实验要求：(1〉设计实验算法实现8枚硬币问题：设计实验程序，考察用减治技术设计的算法是否高效：扩展算法，使之能处理n枚硕币中有1枚假币的问题。四、 算法描述(对算法主要部分进行伪代码描述或画出流程图)伪代码：intcoin(inta[]){输入硕币的质量；if(a[1]+a[2]+a[3]>a[4]+a[5]+a[6])if(a[l]+a[2]>a[4]+a[5])if(a[l]>a[4]){if(a[l]=a[3]){retuin4;}elseretiun1;}elseif(a[l]==a[4])if(a[2]=a[3])letuin5;}elsereturn2;}}if(a[l]+a[2]==a[4]+a[5]){if(a[3]=a[2]){retuin6;}elsereturn3;}}if(a[l]+a[2]+a[3]<a[4]+a[5]+a[6]){if(a[l]+a[2]<a[4]+a[5]){if(a[l]<a[4]){if(a[l]=a[3]){letuin4;}elsereturn1;}elseif(a[l]=a[4])if(a[2]=a[3])retuin5;}elsereturn2;}}if(a[l]+a[2]=a[4]+a[5]){if(a[3]=a[2]){retuin6;}elsereturn3;}}elseif(a[7]==a[3]){retuin8;}elsereturn7;}五、实验结果与结论：(给出测试数据以及程序运行结果，并进行比较，得出自己的结论)减治法算法解决8枚硬币的时间复杂度为：0(logzn)

源程序：intcoin(inta[])if(a[l]+a[2]+a[3]>a[4]+a[5]+a[6])if(a[l]+a[2]>a[4]+a[5])if(a[l]>aL4j)if(a[l]=a[3])return4;}elsereturn1;}elseif(a[l]=a[4j)return5;}elsereturn2;}}if(a[l]+a[2]==a[4]+a[5]){if(a[3]=a[2]){return6;}elsereturn3;}}if(a[l]+a[2]+a[3]<a[4]+a[5]+a[6]){if(a[l]+a[2]<a[4]+a[5]){if(a[l]<a[4]){if(a[l]=a[3]){return4;}elsereturn1;}elseif(a：l]==a[4])return5;}elsereturn2;}}if(a[l]+a[2]=a〔4]+a[5]){if(a[3]=a[2j){return6;}elsereturn3;}}elseif(a[7]=a[3]){return8;}elsereturn7;}intmainO{whiled){inta[9];cout«*输入硬币括人小*«end