安徽文达信息工程学院学生实验报告（计算机语言编程类适用）
一、【实验目的】
1.熟悉分治算法思想。

2.验证具体问题算法的设计及程序实现。

二、【实验内容】
1、有N枚硬币，其中一枚是假币，假币和真币重量不同，可以用一个没有刻度的天平测，求出假币是哪一枚，现要求采用分治法解决，请写出算法设计思路。

(不需要编程)
答：（1）N为偶数时，将N枚硬币分成N/2，N/2的两份将第一份分成N/4，N/4的两份，分别置于天平两端，如果天平倾斜，则假币在第一份N/2中，反之水平，则假币在第二份N/2中;
（2）N为奇数时，将N枚硬币分成（N+1）/2，（N-1）/2的两份,将第一份分成（N+1）/4，(N+1)/4的两份，分别置于天平两端，如果天平倾斜，则假币在第一份(N+1)/2中，反之水平，则假币在第二份(N-1)/2中，
（3）将含假币的的币数赋值给N，N为偶数执行步骤（1），N为奇数执行步骤（2），如此执行直至找出含假币的2或3枚硬币，如果是2枚硬币则找1枚硬币构成3枚，3枚则直接两两置于天平两端，找到使天平水平的两枚硬币，则假币是剩下的硬币。

2、格雷码问题：
对于给定的正整数n，格雷码为满足如下条件的一个编码序列：
(1) 序列由2n个编码组成，每个编码都是长度为n的二进制位串。

(2) 序列中无相同的编码。

(3) 序列中位置相邻的两个编码恰有一位不同。

例如：n=1时的格雷码为：{0, 1}。

n=2时的格雷码为：{00, 01, 11, 10}。

n=3时的格雷码为：{000, 001, 011, 010,110,111,101,100}。

gray码问题求解思想：
将一个规模n位gray码序列表示为G(n), G(n)以相反顺序排列的序列表示为G’(n)。

则gray 码的构造规则即子问题的划分规则为：G(n+1)= 0G(n) 1G’(n) 或G(n+1)= G(n) 0G’(n)1。

请尝试编写程序，完成格雷码问题的处理。

三、【实验步骤】（可附页）
体会：教师评语：。