温故而知新。昨天再看到这个题目又想了想，发现还是有点意思的。
LeeChange，如果下面的回答还满意的话，就给分了吧。
下面给出三种算法解答这个问题。
第一、广度优先遍历法（楼上认为不可用广度的可以看看）
第二、数学规律直接找最小过程解（速度极快但可能存在隐患问题）
第三、队列（也是一层层求解，类似广度，不过效率很好）
同时，在验证三种算法的正确性时，发现楼主LeeChange给的算法有bug
LeeChange,您的算法不能正确解出2,6,4（2上6下翻4个）等组合（其他几个不记得了）
记a,b,m（a上b下，翻m个）
算法一：利用Tree实现广度优先
优点：层次分明，代码简炼，准确易懂
缺点：当a且b除以m的倍数较大时，速度较慢，但可以同时让a,b减去m的i次和再计算，可以
提高相当可观的效率，本例中未实现这个优化。
算法二：数学规律直接找最小过程解
优点：速度一流，一般递归三次即可找到倍数
缺点：不严密，可能存在无法考虑到的情况
算法三：队列求解（是我的一个同学用java写的）
优点：利用队列特性，巧妙的实现逐层求解。
缺点：队列占用间开销比较大
以下为代码，附有详细原理说明和实现说明：
算法一：利用Tree实现广度优先
type
TPath = set of 0..255;
var
Path: TPath;
//a或b的变化范围
a, b, m: Integer;
Succ: Boolean;
{ 增加子结点 }
procedure AppendChildNode(Level: Integer);
var
i, x, y, L, Count: Integer;
Path: TPath;
S: string;
N: TTreeNode;
procedure GetPath(Node: TTreeNode);
begin
Path := [a, b];
while Node.Level > 0do
begin
Include(Path, StrToInt(Node.Text));
Include(Path, a+b-StrToInt(Node.Text));
Node := Node.Parent;
end;
end;
begin
Count := Form1.Tree.Items.Count;
for L := 0 to Count-1do
begin
N := Form1.Tree.Items[L+Form1.Tree.Items.Count-Count];
if N.Level = Level then
begin
GetPath(N);
//不重复搜寻已用过的结点
x := StrToInt(N.Text);
y := a+b-x;
for i := mdo
wnto 0do
if not (x-i+m-i in Path) and (x>=i) and (y>=m-i) then
begin
Form1.Tree.Items.AddChild(N, IntToStr(x-i+m-i));
if x-i+m-i in [0, m, a+b-m, a+b] then
//谁的结点先找到谁就是最优解
begin
Succ := True;
while N.Level > 0do
begin
S := '-(' + N.Text + ',' + IntToStr(a+b-(StrToInt(N.Text))) + ')' + S;
N := N.Parent;
end;
S := '(' + IntToStr(a) + ',' + IntToStr(b) + ')' + S;
if x-i+m-i in [m,a+b-m] then
S := S + '-('+IntToStr(m)+','+IntToStr(b)+')';
S := S + '-(0,' + IntToStr(a+b) + ')';
Form1.Memo1.Lines.Add(S);
Break;
end;
Include(Path, x-i+m-i);
Include(Path, y+i-m+i);
end;
if Succ then
Break;
end;
end;
end;
procedure SetTree(N: TTreeNode);
begin
if (N <> nil) and not Succ then
begin
AppendChildNode(N.Level);
//增加子结点
SetTree(N.GetFirstChild);
//搜寻下一结点
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
a := StrToInt(Edit1.Text);
//上
b := StrToInt(Edit2.Text);
//下
m := StrToInt(Edit3.Text);
//翻
Succ := False;
SetTree(Tree.Items.Add(nil, inttostr(a)));
end;
算法二：数学规律直接找最小过程解
原理:
1. a不管如何变化只能变为[0, a+b]中的某个值，设为a1,a2,a3...，且a,b等同于b,a
2. 将a,b变过的值保存在Path中，下次如果a,b在Path中，就不处理a,b的这个变化。
3. 检查a或b每次变完成的值是否可以再变一次就成为m的倍数，如果可以,并且倍数<3或m是偶数,就Succ=True，
否则a继续变。（为什么要倍数<3呢？因为有可能另一个虽然不是m的倍数，但转换一或两次就可成为m的倍数,
为什么要或m是偶数呢？因为如果m是偶数,另一个数不管怎么变都不可成为m的倍数了）
4. 递归结束后，a,b肯定有一数是m的倍数，依次让a-m或b-m就可达到0
5. 由于1和2，因此递归遍历很快去除了所有重复变化；由于3, 递归遍历很快就到达了4，因此，
只遍历了极小部分就找到了最小解，效率应该是很高的。也因为3，这个算法应该就不能算是遍历算法
，
顶多只能算是递归找最小解的算法，因为每次a,b变化后的值就是过程解!!更无需回溯遍历过程。
实现：
1. 将a,b传入递归函数Turn(a,b)中，如果a>b，则传入Turn(b,a)，以保证最小倍数处理时得到最小值
2. 在递归中 a). 保存a和b的值到Path中，下次不处理a或b变为Path中的值的情况
b). a每次都有[0, a+m]种变化，因此有 for i := mdo
wnto 0 处理每次变化
c). 在for j := ido
wnto 0do
中限制了a,b是朝着最优的方式变化的(原理3)，因此，
a,b变化的值就是最小解过程，可以直接显示出a,b的值来做为答案。
d). a-j+m-j或a-i+m-i就是a下一个变化值
}
type
TPath = set of 0..255;
var
Path: TPath;
//a或b的变化范围
a, b, m: Integer;
Succ: Boolean;
procedure Turn(a, b: Integer);
var
i, j, k, t1, t2: Integer;
begin
if Succ then
Exit;
Form1.Memo1.Lines.Add(IntToStr(a) + ',' + IntToStr(b));
Include(Path, a);
Include(Path, b);
//因为(a,b)和(b,a)没什么区别，所有就不处理a变成b的情况了。
Succ := (( (a mod m = 0) and ( (a div m<2)or(m mod 2=0)and((a+b) mod 2=1) )) or
( (b mod m = 0) and ( (b div m<2)or(m mod 2=0)and((a+b) mod 2=1) )));
for i := mdo
wnto 0do
begin
for j := ido
wnto 0do
//决定a,b每次都是朝最优方式（即可能成为倍数）的方向变化。
if (a-j+m-j) mod m = 0 then
if (a>=j) and (b>=m-j) and not (a-j+m-j in Path) and (((a-j+m-j) div m <2) or (m mod 2=0) and ((a+b) mod 2=1)) then
Turn(a-j+m-j, b+j-m+j)
else
else
if (b-j+m-j) mod m = 0 then
if (b>=j) and (a>=m-j) and not (b-j+m-j in Path) and (((b-j+m-j) div m <2) or (m mod 2=0) and ((a+b) mod 2=1)) then
Turn(b-j+m-j, a+j-m+j);
for k := ido
wnto 0do
begin
t1 := a-k+m-k;
t2 := b+k-m+k;
if (a>=k) and (b>=m-k) then
for j := ido
wnto 0do
begin
if (t1-j+m-j) mod m = 0 then
if (t1>=j) and (t2>=m-j) and not (t1-j+m-j in Path) and (((t1-j+m-j) div m <2) or (m mod 2=0) and ((a+b) mod 2=1)) then
Turn(t1, t2)
else
else
if (t2-j+m-j) mod m = 0 then
if (t2>=j) and (t1>=m-j) and not (t2-j+m-j in Path) and (((t2-j+m-j) div m <2) or (m mod 2=0) and ((a+b) mod 2=1)) then
Turn(t2, t1);
end;
end;
if not Succ then
if (a>=i) and (b>=m-i) and not (a-i+m-i in Path) then
Turn(a-i+m-i, b+i-m+i);
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
procedure ListEx(x: Integer);
begin
while x>0do
begin
Dec(x, m);
Memo1.Lines.Add(IntToStr(x) + ',' + IntToStr(a+b-x));
end
end;
begin
Memo1.Clear;
a := StrToInt(Edit1.Text);
//上
b := StrToInt(Edit2.Text);
//下
m := StrToInt(Edit3.Text);
//翻
if (m mod 2=0) and (a mod 2=1) and (b mod 2=1) or (a+b<m) or (a+b=m) and (a*b<>0) then
Exit;
if a > b then
begin
a := a+b;
b := a-b;
a := a-b;
end;
if m>a+b-m then
m := a+b-m;
Path := [];
Succ := False;
Turn(a, b);
b := a+b;
a := StrToInt(Copy(Memo1.Lines[Memo1.Lines.Count-1], 1,
Pos(',', Memo1.Lines[Memo1.Lines.Count-1])-1));
b := b-a;
if (a mod m=0) and ((b mod m<>0) or (b mod m=0) and (b>a)) then
ListEx(a) else
ListEx(b);
end;
算法三：队列求解
/*********************************************************************
问题描述:
有N个硬币(1<=N<=255),有一些正面向上,另外一些背面向上,没有竖着的.可以对这些
硬币进行翻动,每次可以且仅可以翻动M个硬币(1<=M<=N).每次翻动必须翻M个硬币(硬
币不同),不能多也不能少. 问最少翻多少次可以将所有硬币翻成同一面向上(既可以
正面向上,也可以背面向上).
输入:
字符串s,由字符'0'或'1'构成,'0'表示背面向上,'1'表示正面向上.
整型M,表示一次翻动的硬币的数目.
输出:
每次翻动后的字符串,直到字符串为全'0'或全'1'.
如果无解,则提示用户无解.
**********************************************************************/
/**
Demo program
Date:2003-6-11
Author:wcxlily
Note:Everyone can modify this program.
Modify:
2003-6-11 15:15 修改输出每次翻动的方法。
2003-6-11 17:15 修改程序isIntegerTimes()中的一个逻辑错误。
*/
import java.util.*;
import java.io.*;
/* 每次翻动后硬币的状态 */
class Node
{
/*Default constructor()*/
public Node(){ upCounter =do
wnCounter = prev = -1;
status = -1;
}
/*Copy constructor()*/
public Node(Node node)
{
up = node.up;
do
wn = node.down;
times = node.times;
upCounter = node.upCounter;
do
wnCounter = node.downCounter;
prev = node.prev;
status = node.status;
}
public boolean equals(Object o) {
if (!(o instanceof Node))
return false;
Node node = (Node)o;
return (up == node.up &&
down == node.down
&&
times == node.times
&&
upCounter == node.upCounter
&&
downCounter == node.downCounter
&&
prev == node.prev
&&
status == node.status);
}
//确定节点是朝上的或者朝下的是否是M的整数倍,如果是的话就返回倍数，
//并记录下要朝上还是朝下翻，如果不是的话返回－1
public int isIntegerTimes(int M)
{
int upTimes,do
wnTimes;
//朝上的为M的倍数
if(up - M == 0) {
status = 1;
return up/M;
}
//朝下的为M的倍数
if(down - M == 0){
status = 0;
returndo
wn/M;
}
status = -1;
return -1;
}
public String toString()
{
String str;
str = times + " Up = " + up + "do
wn =" +do
wn
+ " upCounter = " + upCounter
+ "do
wnCounter = " +do
wnCounter
+ " Prev = " + prev
+ " Status =" + status;
return str;
}
int up;
//硬币朝上的个数
intdo
wn;
//硬币朝下的个数
int times;
//在进行这次翻动的时候，前面已经翻动的多少次了
int upCounter;
//用于记录前一次到这一次，向上翻了多少个硬币
intdo
wnCounter;
//用于记录前一次到这一次，向下翻了多少个硬币
int prev;
//我用另外的Vector保存遍历信息，这个仅为了找
//回翻动硬币这次硬币的前一次在Vector中的索引而已
int status;
//如果朝上或者/和朝下为M的倍数的话，要向下翻还是
//向上翻，使得翻动次数最少。（-1：不为M的倍数，0
//向上，1向下）
}
/**
主程序类，只有一个主函数，用于以下算法求解
算法说明：
1：我们可以知道如果朝上或者朝下的数目的个数是M的倍数的话，我们就可以马上确定出问题的解。
2：对于这个问题可以用队列来解决。
初始化队列：在队头插入最早的时候，就是用户给我们的状态。
Node start = new Node();
start.up = upNum;
//开始时候向上的硬币的个数
start.down = totalNum - upNum;
//开始时候向下的硬币的个数
start.times = 0;
//在这个状态，它前面没有翻动过硬币
v.add(start);
//插入到队尾
对于每次翻动，我们可以有M＋1个翻法，0个翻上，M个翻下；一个翻上，M－1翻下；两个翻上，M－2翻下
...M-2个翻上，2个翻下；M－1个翻上，1个翻下；M个翻上，0个翻下。（说明：对于一个翻下，其他翻上
的情况，会在M－1个翻上的时候发生，还有个需要说明的就是每次都要翻M下，我是把每次朝下的硬币向上
翻，这样就有一种情况，朝下的硬币不够翻，就需要把朝上的硬币朝下翻，这个时候就会会到硬币刚刚好够
向上翻的情况，所以每必要在对这种情况做遍历，这程序中有做说明）。
（1）、我们从初始状态开始，把每它可能的M中翻动方法插入到队列中，并记下它是前面翻过了0下。
（2）、然后在从队头取出一个元素（注意队列不会发生为空的情况，每对一次状态的操作，就会在队列中加人
M个元素，但仅减少一个元素），对取出的元素进行判断，看它是否满足说明1，如果满足就可以有前面翻了几
下＋朝上（朝下）/M 确定要多少下可以都朝上或朝下。（当然这个时候可能发现朝上和朝下都为M的倍数，我们
取Min(朝上/M，朝下/M)，使得翻动的次数最少），如果不满足说明1，则对它进行M＋1次翻转操作（M＋1次中
并不是每次都可以，有些情况会重复，在前面说明过），记下它前面翻动了1下，每次的状态都插入到队列中。这
样我们就遍历了翻动一下的所有情况，而每次的翻动都在队列中保存着。
（3）、从队列中取出队首的元素，它是翻动过1次后硬币的状态。对它我们也进行如上的M＋1次翻动，这就
会队第3次的硬币所有翻动做了遍历。
（4）、周而复始，对硬币翻动，直到得到解或者内存不足。（说明：如果没有解或者要翻动太多次了，就会发现
内存不足。）
说明：对于这个算法，如果在内存或时间满足的情况下，可以确定最少的操作次数。但是对于这个问题有没有解，
就比较难确定，可以用1：确定最大的移动次数Counter，如果移动的次数大于它，我们认为没有解，2：因
为每次对列中都只减少一个元素，加入M个元素，这样迟早内存会被耗空，可以每次捕获这个例外，当捕获的
时候就认为没有解。由于Java中没有必要捕获内存耗空的例外，所有，我这边就是使用方法2，如果程序程序
运行过程发生例外，就表明这个问题在空间上没有解。
*/
public class UpAndDown
{
static int debug = 0;
public static void main(String[] args)
{
int totalNum = 37;
//总的硬币个数
int upNum = 35;
//朝上的硬币个数
int M = 7;
//每次翻动的硬币个数
if(args.length != 3){
System.out.println("Usage: java UpAndDown totalNum upNum trunoverNum");
System.exit(1);
}
totalNum = Integer.parseInt(args[0]);
upNum = Integer.parseInt(args[1]);
M = Integer.parseInt(args[2]);
if(debug == 1){
System.out.println(totalNum + " " + upNum + " " + M);
}
/*在这里要对参数的合法性做判断，这些细节被我省略了 ：）*/
Vector v = new Vector();
//用于保存每次翻动所操作的硬币状态，队头会被删除掉
Vector path = new Vector();
//用于保存每次翻动所操作的硬币状态，只做插入，用于恢复每次操作的硬币状态
//初始化队列，把最先的硬币状态加入。
Node start = new Node();
start.up = upNum;
start.down = totalNum - upNum;
start.times = 0;
v.add(start);
if(debug == 1){
System.out.println("<<Add>> " + start);
}
path.add(new Node(start));
//所有可能的翻动遍历
while(true){
//出队，并且判断是否满足算法说明1，如果满足，找到解，退出遍历
start = (Node)v.remove(0);
if(debug == 1){
System.out.println("<<Remove>> " + start);
}
if(start.isIntegerTimes(M) != -1) {
//System.out.println(start.times + start.isIntegerTimes(M, status));
break;
}
int iUp, iDown;//向上翻iUp个，向下iDown个
//所有可能的翻动都做遍历，发生重复的被忽略过，向上翻动从0到M个。
for(iUp = 0;
iUp <= M;
iUp++){
Node node = new Node();
iDown = M - iUp;
//如果前面那一次的朝下硬币个数比要往上翻的少，就会让朝下都往上翻，朝上有被
//往下翻了，这样就和朝下的硬币＝要朝上翻的情况相同了。
if(iUp <= start.down &&
iDown <= start.up){
iDown = M - iUp;
if(iDown <= iUp){//向下翻比向上的少，等同于向上翻iUp－iDown个硬币
node.up = start.up + iUp - iDown;
node.down = start.down - iUp + iDown;
}
else
{//向上翻比向下的少，等同于向下翻iDown－iUp个硬币
if(start.up > (iDown - iUp)){//向下的硬币个要够向上翻。
node.up = start.up - iDown + iUp;
node.down = start.down + iDown - iUp;
}
else
//如果不够向下翻，会于前面的某次等同，所以忽略。
continue;
}
//记下翻动的状态，加入队列中
node.upCounter = iUp;
node.downCounter = iDown;
node.times = start.times + 1;
node.prev = path.indexOf(start);
v.add(node);
path.add(new Node(node));
//拷贝一个信息到Vector中，用于回溯翻动遍历的过程
if(debug == 1){
System.out.println("<<Add>> " + node);
}
}
}
}//end while()
int totalTimes = start.times + start.isIntegerTimes(M);
//总共翻动的次数
if(debug == 1){
Node node;
int i = 0;
Enumeration e = path.elements();
while(e.hasMoreElements()){
node = (Node)e.nextElement();
System.out.println(++i + " Up = " + node.up
+ "do
wn = " + node.down
+ " Times = " + node.times
+ " Turn up = " + node.upCounter);
}
}
//输出要翻动的次数
System.out.println("At least turn over " + totalTimes + " times");
Vector action = new Vector();
String str = "";
//连续向上或者向下翻的次数
if(start.status == 0){
str = "Next,we continue turnning coin up " + start.down / M + " times";
action.add(str);
}
else
if(start.status == 1){
str = "Next, we continue turnning coindo
wn " + start.up / M + " times";
action.add(str);
}
else
{
System.err.println("Have some error.");
System.exit(1);
}
while(start.prev != -1){
action.add(0, start.toString());
start = (Node)path.elementAt(start.prev);
}
action.add(0,start.toString());
//输出每次翻动的状态
System.out.println("-------------------Action:--------------------");
Enumeration e = action.elements();
while(e.hasMoreElements()){
str = (String)(e.nextElement());
System.out.println(str);
}
}
}
/*
输出说明：
如总共6个，五个朝下，翻3个，输出结果如下
3
---------------------------------------------------------
3 Up = 3do
wn =3 Times = 2 upCounter = 2do
wnCounter = 1 Prev = 1
2 Up = 2do
wn =4 Times = 1 upCounter = 2do
wnCounter = 1 Prev = 0
0 Up = 1do
wn =5 Times = 0 upCounter = -1do
wnCounter = -1 Prev = -1
第一行的3表示最少要多少下
下面的行表示每次翻动的状态，从最后一下到第一下。
前面的数字表示它是第几次
Up：这次硬币的朝上个数
Down：朝下个数
Times：在它前面已经翻动了次数，上一次要朝上翻upCounter个，朝下翻downCounter个会出现现在
硬币状态。
Prev：它前一次在path中的索引。
最后一行表示的是初始的状态，Turn up ＝ －1。
后来整数个翻转的就不输出了。
*/
=================================================================
还有一个有意思的问题，a,b,m的解==a,b,a+b-m的解，就是说比如9,9,17
就等于9,9,1，口算得出翻9次，分别为9,9--8,10--7,11--...--1,17--0,18
好了，就写到这。
