征求一算法. (看来都嫌分少,这样吧再加300,一共400了) (100分)

大虾大虾！`````
我还帮不上忙就踢一下吧

原来大家都来这里开动脑筋的呀！

哪！我这么理解
a,b,m=a,b,a+b-m中间是不能用等号，不过m>(a+b)/2的时候可以这么代替，只是每一步的a,b值颠倒一下显示就行了。
这下m<(a+b)/2成立了。
连续翻动m个硬币两次，实际翻动的硬币数可能是0，2，4..2m，对吧
例如每次翻5个，可以
01111100000
00111110000
以上这样翻两次，扣除翻过去又翻回来的，其实只翻动了两个，也可以
01111100000
00011111000
以上这样翻两次，其实只翻了4个，有三个翻过去又翻回来了
其余情况以此类推....
接下来我们只要把a(或者b)变成2m之内的偶数，那么根据以上知道就剩下两步了。
除了a(或b)是奇数，m是偶数的情况没办法之外，其他情况如下
1）a>m，那就a-m直到a<2m且a是偶数
2）a是奇数且0<a<m，那就a+m就行了
以上都是对a翻动m个（就是m的倍数）
现在a(或b)是2m之内的偶数了，就剩下两步，最后一步也不用说了，
a肯定等于m，然后一步翻m个a就翻过来了
现在就剩下倒数第二步怎么翻的问题了。
叶描述的定理二说的就是这里的倒数第二步的存在。
就是怎么翻的问题
若0<a<m且a是奇数时需要两步，a=a+m以后，i=a/2，然后a=a-i+m-i=m
若0<a<m且a是偶数，一步，i=a/2，然后a=a-i+m-i=m
若a>m，则 i=(m-(km-a))/2 a=a-i+m-i=km---------(ii)
其中：
1)a是偶数，m当然也要偶数，根据(ii)式，在(0<i<min(a,b))，取最小的倍数k
2)a要是奇数，m是偶数，根据(ii)式k就该是奇数，那么翻一次，就可以翻到奇数k倍的m，k要取其中最小的奇数(0<i<min(a,b))
3)a要是奇数，m也是奇数，根据(ii)式k就该是偶数，那么翻一次，就可以翻到偶数k倍的m，k要取其中最小的偶数(0<i<min(a,b))

DarwinZhang大侠：您看看这个可以不可以？
公理一：奇数个奇数之和为奇数，偶数个奇数之和为偶数
公理二：任意个偶数之和为偶数
公理三：奇数个奇数与任意个偶数的和为奇数
推论一：对于任意整数x,m，且m为偶时x不为奇，存在整数t∈[0,m]，使得x+m-2t为m的倍数。
证明：先证(1)在闭区间[-x/m, 2-x/m]内存在整数k，使得x+km为偶数
若x为奇，m为奇，则若Int(-x/m)为奇，取k=Int(-x/m)+1
若Int(-x/m)为偶，取k=Int(-x/m)，由公理一得x+km为偶；
若x为偶，m为奇，则若Int(-x/m)为奇，取k=Int(-x/m)+1
若Int(-x/m)为偶，取k=Int(-x/m)，由公理一二得x+km为偶
若x为偶，m为偶，则取k=Int(-x/m)+1或取k=Int(-x/m)都可由公理一得x+km为偶；
（题外话：若x为奇，m为偶，则x+km必为奇，不可得证）
得证(1)
取t=(x+km)/2，则t为整数，且t∈[0,m]
由题设，可知对于x，移动t个硬币后
x的值为x'= x-t+(m-t)=x+m-2t=(x+m-x-km)=(1-k)m，即x'为m的倍数。

to 叶兄:
您说的没有问题,但请考虑 a>m>b或 b>m>a的情况.
我上面确实写错了,手误,sorry,应该是:
对于任意整数x为偶数，如果m为偶数,则x可以不超过一次就变化为m的倍数.
您的那个程序 a=10, b=1, m=3时输出有问题.而且最后还多一个'-'.不过是小问题.

#include<iostream.h>
#include<math.h>
//------------------------------------------------------------------------------------
main()
{
unsigned a,b,c,a1,b1,turnnum,firstturnnum = 0;
//说明：
/*
1）a枚向上，b枚向下，每次翻c枚，turnnum表示最少翻动次数，firstturnnum第一次翻动a或b的枚数，
2）a1,b1分别表示第一次翻动后向上和向下枚数
3）我第一次给出答案的时候，未考虑：c>=(a+b)/2的情况，后来有几位朋友提出互补也就是叶不归朋友提出的定理1，使问题得到解决
4）DarwinZhang朋友提出的a>m>b或 b>m>a的情况，本程序可以给出答案
*/
char ch = 'a';
bool t1 = false,t2 = false;
while(ch != 'q')
{
cout<<"a = ";
cin>>a;
cout<<endl;
cout<<"b = ";
cin>>b;
cout<<endl;
cout<<"c = ";
cin>>c;
cout<<endl;
if((c == 0)||(c >= a + b))
{
cout<<"INPUT ERROR!";
continue;
}
if(c >=(a + b)/2)
{
c = a + b - c;
}
if(!fmod(a,c)&amp;&amp;(!fmod(b,c)))
{
turnnum = (a > b?b:a) / c;
t1 = true;
}
else
if(!fmod(a,c))
{
turnnum = a / c;
t1 = true;
}
else
if(!fmod(b,c))
{
turnnum = b / c;
t1 = true;
}
else
for(int k = 0;(k <= c)&amp;&amp;(k <= a)&amp;&amp;(c - k <= b);k++)
{
a1 = a + c - 2 * k;
b1 = b - c + 2 * k;
cout<<"("<<a1<<","<<b1<<"),";
if(!fmod(a1,c)&amp;&amp;(!fmod(b1,c)))
{
turnnum = (a1 > b1?b1:a1) / c + 1;
if(!t2)firstturnnum = k;
t2 = true;
}
else
if(!fmod(a1,c))
{
turnnum = a1 / c + 1;
if(!t2)firstturnnum = k;
t2 = true;
}
else
if(!fmod(b1,c))
{
turnnum = b1 / c + 1;
if(!t2)firstturnnum = k;
t2 = true;
}
}
cout<<endl;
if(t1)
{
cout<<"turn num is : "<<turnnum<<endl;
}
else
if(t2)
{
cout<<"turn num is : "<<turnnum<<endl;
cout<<"first turn num is : "<<firstturnnum<<endl;
cout<<"a1 = "<<a<<" + "<<c<<" - 2 * "<<firstturnnum<<" = "<<a + c - 2 * firstturnnum<<endl;
cout<<"b1 = "<<b<<" - "<<c<<" + 2 * "<<firstturnnum<<" = "<<b - c + 2 * firstturnnum<<endl;
cout<<"(a1/c,b1/c) = ("<<(float)(a + c -2 * firstturnnum)/c<<","<<(float)(b - c + 2 * firstturnnum)/c<<")"<<endl;
}
else
cout<<"can not finish!"<<endl;
cout<<"quit ? yes = q ";
cin>>ch;
}
}

DarwinZhang大侠：
>>您的那个程序 a=10, b=1, m=3时输出有问题.而且最后还多一个'-'.不过是小问题.
程序输出(10,1)-(2,9)-(3,8)-(0,11)-是没有问题的。
你认为应该是输出(10,1)-(9,2)-(8,3)-(11,0)是吗？这也是显示上的问题，跟算法没什么
关系的。2,9跟9,2差不多啦，凑合。

to kerbcurb:
你是一步把a(或b)翻成c的整数倍的，要是一步翻不成呢？
例如1，100，3

1,100,3是可以的，翻动34次，第一次，a全翻，b翻2，翻完之后，变成2，99，99/3 = 33，所以是34次，又如1，10，3的情况是4次
在ZDNet可以下载Dev-c++,最新版本好像有问题，4.9.6版本可以在98下运行，我的那个就是用Dev-C++编的，当然，在BCB下也可以运行，如果哪位希望要PASCAL的代码，请留言或地址
希望大家给出反例，谢谢！

我仔细想过了,实际上定理二可以在各种情况下成立的.
可以到达O(1)复杂度,不过实现起来比较复杂.
用叶兄的办法也不失为一个好办法.
请叶兄到:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1963372
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1963373
来拿分. []

to hfghfghfg:
all: 21
正: 9
每次翻4个是有解的,您的程序说没有解.
我有一点觉的奇怪,您的程序为什么从初始状态往后只搜索了翻4个正面和翻3个正面两种情况?
翻2个的翻一个的也得试试吧.

翻2个=没变化//所以去掉
翻一个正面 和 翻3个正面的改变都是 2个
// 注 我的程序是单向的，就是目标全是正面的

是随机翻动还是可以有选择把它排序后再翻?

to ：kerbcurb：
1,100,3--2,99--3,98--0,101 共三次

to 叶不归
不好意思，我没看明白，我不太明白你的意思，是否可以具体点

to kerbcurb:
第一次，a全翻，b翻2，翻完之后，变成2，99
第二次，a翻1，b翻2，翻完之后，变成3，98
第三次，……

明白了

各位都是大哥：）

"2,9跟9,2差不多啦，凑合。 "
天,这个您最好还是仔细的研究一下.包括那个详细证明.还是有很多东西的.
希望有严谨的作风.[]

这个题目，是小学奥林匹克的题目。

to c96301:
确实，有相当部分数论的的题目看起来都好象很容易，可是做起来却很难。象哥德巴褐猜想就是这样。
糟糕的是象数学分析，高等代数，高等几何学这些东西对许多数论题也没有太多的直接用途。所以小学，中学，大学生做起来都可以。[]
本人怀疑楼主是做MIS的，不象我喜欢数值计算和图形图象。说起话来都觉得不搭股。[]