下载文档原格式
【伪造硬币问题】给你一个装有n个硬币的袋子。
n个硬币中有一个是伪造的。
你的任务是找出这个伪造的硬币。
为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。
试用分治法的思想写出解决问题的算法，并计算其时间复杂度# include <iostream># include <ctime> //随机给数组中的某一项赋予其他的值using namespace std;const int M=30; //硬币的个数const int WEIGHT=5; //正常硬币的重量const int FWEIGHT=6; //伪币的重量bool match(int p,int q) //判断重量是否相等{return (p==q)?true:false;}int sumweight(int *p,int n) //求n个数的总和{int sum=0;for (int i=0;i<n;i++)sum+=*(p+i);return sum;}void find(int* p,int n) //找伪造硬币{int sum1=sumweight(p,n/3);int sum2=sumweight(p+n/3,n/3);int sum3=sumweight(p+2*n/3,n/3);if(match(sum1,sum2))if(match(sum1,sum3)) //伪币在多余的几个硬币里{for(int j=0;j<n%3;j++)if(p[n-j]!=p[0]){cout<<"这个是伪币"<<endl;break;}}else find(p+2*n/3,n/3); //伪币在sum3里else if(match(sum1,sum3))find(p+n/3,n/3); //伪币在sum2里else find(p,n/3); //伪币在sum1里}int main (){if(M>=3){int a[M];for(int i=0;i<M;i++) //数组初始化a[i]=WEIGHT;srand (time(NULL));int t=rand()%M; //随机选择出一个值用来放伪币a[t]=FWEIGHT;find(a,M);// cout<<t<<endl;}else cout<<"无法判断";return 0;}int t=rand()%M; //随机选择出一个值用来放伪币a[t]=fweight;find(a,M);// cout<<t<<endl;}else cout<<"无法判断";return 0;}。
算法-经典趣题-寻找假银币⼀、问题寻找假银币是⼀个⾮常有趣的智⼒题⽬，寻找假银币的⼤意如下：现在有8枚银币，其中有⼀枚是假币。
但是，从外观和做⼯上⽆法分辨哪枚是真币哪枚是假币，只知道假币的重量要⽐真币稍轻。
则要求仅使⽤⼀个天平，如何以最少的步骤寻找到假银币？⼆、分析我们来分析下寻找假银币问题。
其实寻找假银币并不难，⼀种最基本的⽅法便是⾸先给硬币编上序号（1～8），然后通过天平进⾏两两⽐较，操作步骤如下：（1）⾸先⽐较第1枚银币和第2枚银币的重量，如果天平两边平衡，则进⾏下⼀步操作，否则较轻的⼀边的硬币为假币；（2）接着⽐较第3枚银币和第4枚银币的重量，如果天平两边平衡，则进⾏下⼀步操作，否则较轻的⼀边的硬币为假币；……重复上述步骤，直到8枚银币都⽐较完为⽌，便可以找到假银币。
这种两两⽐较的⽅法简单，但是效率不⾼，需要的步骤⽐较多。
这⾥需要寻找最少的操作步骤。
可以采⽤递归分治的思想来求解这个问题，操作步骤如下：（1）⾸先为每个银币编号，然后可以将所有的银币等分为两份，放在天平的两边。
（2）因为假银币的分量较轻，因此天平较轻的⼀侧中⼀定包含假银币。
（3）再将较轻的⼀侧中的硬银币等分为两份，重复上述做法。
（4）直到剩下两枚硬银币，可⽤天平直接找出假银币来。
这种⽅法在银币个数⽐较多的时候便显⽰出了优势。
可以按照此思路来编写相应的寻找假银币问题的求解算法。
三、编程package com.joshua317;import java.util.Scanner;public class Main {public static void main(String[] args) {int n;int position;System.out.println("分治算法求解假币问题");System.out.println("请输⼊银币的总个数");Scanner scanner = new Scanner(System.in);n = scanner.nextInt();int[] coin = new int[n];System.out.println("请输⼊银币的真假，有且只能有⼀个假币，,2代表真，1代表假");boolean flag = false;for (int i = 0; i < n; i++) {coin[i] = scanner.nextInt();//接收银币的真假if (coin[i] == 1) {flag = true;}}if (!flag) {System.out.println("必须得有⼀个假币");return;}position = FindFakeCoin.getFakeCoin(coin, 0, n-1);System.out.println("在上述" + n + "个银币中，第" + position + "个银币是假的！");}}class FindFakeCoin {public static int getFakeCoin(int coin[], int low, int high) {int i, sum1, sum2, sum3;int re = 0;sum1 = sum2 = sum3 = 0;//最后两枚if (low + 1 == high) {if (coin[low] < coin[high]) {re = low + 1;return re;} else if (coin[low] > coin[high]) {re = high+1;return re;} else {return re;}}//硬币是偶数if ((high - low + 1) % 2 == 0) {//前半断的和for (i = low; i <= low + (high - low) / 2; i++) {sum1 += coin[i];}//后半断的和for (i = low + (high - low) / 2 + 1; i <= high; i++) {sum2 += coin[i];}if (sum1 < sum2) {re = getFakeCoin(coin, low, low + (high - low) / 2);return re;} else if (sum1 > sum2) {re = getFakeCoin(coin, low + (high - low) / 2 + 1, high); return re;} else {}} else {//前半断的和for (i = low; i <= low + (high - low) / 2 - 1; i++) {sum1 += coin[i];}//后半断的和for (i = low + (high - low) / 2 + 1; i <= high; i++) {sum2 += coin[i];}sum3 = coin[low+(high-low)/2];if (sum1 < sum2) {re = getFakeCoin(coin, low, low + (high - low) / 2 - 1); return re;} else if (sum1 > sum2) {re = getFakeCoin(coin, low + (high - low) / 2 + 1, high); return re;} else {}if (sum1 + sum3 == sum2 + sum3) {re = low + (high - low) / 2 + 1;return re;}}return re;}}。
论分治算法在信息学竞赛中的应用绍兴县鲁迅中学教技处夏红军一、问题的提出【例1】寻找假币（Noip2006初赛普及组问题求解第二题）【问题描述】现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。
二、问题的分析1、直接的想法是将这些硬币2枚一组分为40组，每次只称一组硬币，若发现轻的则为假币，最坏情况下称40次才可找出假币。
2、仔细思考上面的分法比较一次只能排除2枚硬币，利用只有一枚假币的性质，我们试着改变一下方法：将所有硬币平均分为两组，每次称两组硬币，这样比较一次可排除一半硬币，最坏情况下只需称7次。
3、显然每比较一次能排除的硬币越多越好，朝着这个目标对怎样分组进一步思考。
三、问题的解决把所有的硬币尽量平均地分成三组，至少有两组硬币数是相同的，每次称相同的两组，这样每比较一次可排除约2/3的硬币数，最坏情况下只需称4次。
四、算法的引入通常我们将这种以大化小的设计思想称之为分治算法，即“分而治之”的意思。
也就是说，当我们处理大规模问题时，可以将原问题分解成k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解。
分治算法一般分为三个步骤：①分解(Divide)：将原问题分成一系列子问题。
②求解(Conquer)：若子问题足够小，则可直接求解。
③合并(combine)；将子问题的结果合并成原问题的解。
可以看出，为实现分治算法，一个方法是借助递归结构，另一个方法是从已知的小问题出发进行递推，小问题层层合并成大问题后解决。
递归大致过程如下：Divide-and-Conquer(P)1. if |P|≤n02. then return(ADHOC(P))3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk4. for i←1 to k5. do yi ← Divide-and-Conquer(Pi) △递归解决Pi6. T ← MERGE(y1,y2,...,yk) △合并子问题7. return(T)其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。
本栏目责任编辑：王力计算机教学与教育信息化算法教学问题的探讨石少俭，徐乙富（山东理工大学计算机科学与技术学院，山东淄博255049）摘要：算法是计算机程序员必备的技术之一。
大学的计算机算法课一般讲授经典的算法，主要是分治算法、动态规划算法、贪心算法等。
算法就是解决问题的方法。
关键词：算法；分治算法；动态规划算法；贪心算法中图分类号：TP319文献标识码：A文章编号：1009-3044(2019)27-0164-02开放科学（资源服务）标识码（OSID ）：1引言算法，晦涩难懂，却又是IT 领域最受重视的素养之一。
可以说，算法能力往往决定了一个程序员能够走多远。
国内外各大名企非常喜欢在面试环节考核求职者的算法编程，这也成为无数准程序员们过不去的一道“坎”。
大学的计算机算法课一般讲授经典的算法，主要是分治算法、动态规划算法、贪心算法等。
对算法的定义，一般都是给出了计算机算法的特性，但作为算法的定义不太合适。
可以用算法就是解决问题的方法作为算法的定义。
下面通过几个例子来解释这个定义。
2算法的一般问题1）分苹果问题：有n 个苹果，两个人分。
规定：两人依次取，每次最多取1~m 个，最后取到苹果者获胜，给出具体的获胜策略。
这是一个运筹学方面的例子。
解题思路：从最后结果向前倒推。
具体实例n=10，m=3。
一个人如果想获胜，倒数第二次取后，需要给对方剩4个苹果。
以此倒推，结论是先取者获胜。
一般的情况下结论是整除问题。
设n=a （m+1）+b ，a 是偶数，b=0后取者获胜；b≠0，先取者获胜。
a 是奇数，b=0后取者获胜；b≠0，先取者获胜。
算法就是给出了解题的方法。
2）已知A={1,2,3,4,5,6,7,8,9,10}，求A 的所有子集的元素之和。
这是一个组合数学的问题。
可以用穷举的方法分类计算子集的元素个数之和，但n=10可以，如果n=10000000，时这样计算就不合适了。
算法是解决问题的方法。
所以主要是找到解决问题的简单方法。
