public static void main(String[] args) { //int x[] = {4, 7, 10}; int x[] = {4, 8, 18}; System.out.println(JsonUtils.toJsonString(fun(x, 0, 2014))); } public static int max(int... numberArray) { if (ArrayUtil.isEmpty(numberArray)) { throw new IllegalArgumentException("Number array must not empty !"); } else { int max = numberArray[0]; int j = 0; for (int i = 1; i < numberArray.length; ++i) { if (max < numberArray[i]) { max = numberArray[i]; j = i; } } return j; } } public static int[] fun(int[] x, int step, int max) { if (step == max) { if (allEq(x)) { System.out.println("suc:" + step); return x; } else { System.out.println("fail:" + step); return x; } } while (step < max) { if (allEq(x)) { System.out.println("suc:" + step); return x; } int index = max(x); if (index == 0) { x[0] = x[0] - 2; x[1] = x[1] + 1; x[2] = x[2] + 1; } else if (index == 1) { x[1] = x[1] - 2; x[0] = x[0] + 1; x[2] = x[2] + 1; } else { x[2] = x[2] - 2; x[1] = x[1] + 1; x[0] = x[0] + 1; } step++; System.out.println("step=" + step+","+JsonUtils.toJsonString(x)); } System.out.println("step=" + step); return x; } private static boolean allEq(int[] x) { return x[0] == x[1] && x[1] == x[2]; }
通过模拟,step=1,[5,9,16]
step=2,[6,10,14]
step=3,[7,11,12]
step=4,[8,12,10]
step=5,[9,10,11]
step=6,[10,11,9]
step=7,[11,9,10]
step=8,[9,10,11]发现规律,
5次操作后3次一循环。
∵
G2014=[11,9,10]
数学推导:
结论:
1)三个数的和如果不能被3整除,那么无法通过若干次操作,变为三数相等;
2)三个数的和如果能被3整除,那么不是所有初始状态通过若干次操作能使得三数相等;
Gi=ai,bi,ci, max(i)=max{ai,bi,ci} min(i)=min{ai,bi,ci},mid(i)为三者的中间数
记di=max(i)-min(i), 那么当d(i)>=3 时,d(i+1)<=d(i) ,等号成立当且仅当mid(i)=max(i);
证明:d(i+1)=max(i+1)-min(i+1),G(i+1)= max(i)-2, mid(i)+1,min(i)+1,推出min(i+1)=min(i)+1,
d(i+1)=max(i+1)-min(i)-1;
若max(i+1)=max(i)-2,那么d(i+1)=max(i)-min(i)-3=d(i)-3<d(i);
若max(i+1)=mid(i)+1,那么,d(i+1)=mid(i)-min(i)<=d(i), 当max(i)=mid(i) 等号成立
所以d(i)是递减序列,不断减小,第n次变换后,当d(n)<3
d(n)=0,这种情况三数相同,结束
d(n)=1, 有2种情况,a,a,a+1 和a,a+1,a+1;这两种情况后面都会以3次操作为循环
d(n)=2, 有3种情况,a,a,a+2; (a,a+1,a+2), a,a+2,a+2,这三种,这三个也是会以3次操作为循环,(a,a+1,a+2)比较特殊,他三个的和能被3整除,但是无法变化为三数相同