基础

为简单起见，用(x,y)表示变量a和b在某一时刻的一组值。

以交换a和b的值为例

(a,b)-->(a+b,b)-->(a+b,a)-->(b,a)

引申一

如果是改变三个变量的值呢？比如(a,b,c)-->(c,a,b)（向右循环移一位）

(a,b,c)-->(a+b,b,c)-->(a+b,b+c,c)-->(a+b,b+c,a+b+c)-->(c,b+c,a+b+c)-->(c,a,a+b+c)-->(c,a,b)

(a1,a2,...,an)-->(a1+a2+...+an-1,a2,...,an-1,an)（第1个数等于前n-1个数之和）

-->(a1+a2+...+an-1, a2+...+an,...,an-1+an,an)（第2个到第n-1个数分别加上其后所有的数）

-->(a1+a2+...+an-1, a2+...+an,...,an-1+an, a1+a2+...+an)（最后一个数为所有数的和）

-->(an, a1, a1+a2, a1+a2+a3, ...,a1+a2+...+an-2, a1+a2+...+an)（最后一个数分别减去前面所有的数）

-->(an, a1, a2, a1+a2+a3, ...,a1+a2+...+an-2, a1+a2+...+an)（第三个数等于第三个数减去第二个数）

-->(an, a1, a2, a3, ...,an-2, an-1)（类似地，依次求得后面的数）

感觉好复杂！有没有简单的思路呢？

(a1,a2,...,an)-->(a1+a2+...+an,a2, a3, ...,an-1,an)（第一个数为所有数字之和）

-->(a1+a2+...+an,a1, a3, ...,an-1,an)（第二个数等于第一个数减去所有其他数字之和得到a1）

-->(a1+a2+...+an,a1, a2, ...,an-1,an)（第三个数等于第一个数减去所有其他数字之和得到a2）

同理可得所需结果。

分析：

给出的第二个算法简单明了，但每次都需要所有数字的参与。

对比两种算法，突然觉得，实际上可以构造出无数种计算的方法的，只要保证每次计算之后，n个数字所含的信息量不变，都是可以经过有限次运算恢复出所有数字的。

引申二

如果是无序地变换呢？(a1,a2,...,an)-->(b1,b2,...,bn)，(b1,b2,...,bn)是(a1,a2,...,an)的一个排列

实际上，(a1,a2,...,an)和(b1,b2,...,bn)构成了(a1,a2,...,an)的一个置换。（离散数学、近世代数）

以下分析基于引申一中的第二个算法，目的是为了减少总的运算次数（加减法），使用了置换群中的相关知识。

一个定理：一个置换可分解为不相交的轮换之积。（应用近世代数第二版P63）

可以按照算法二依次处理每个轮换。

当然了，这样会增加总的赋值次数。效率是否有提升有待验证，毕竟增加了置换分解的操作。

引申三

在笔试、面试题中，一般还需要考虑a+b的溢出情况，由此而得到的解决方案是

(a,b)-->(a^b,b)-->(a^b,a)-->(b,a)

通过观察可以发现，只需把+、- 替换为^即可。

更多思考

如何优化算法？围绕赋值次数，总的运算次数（加减等操作）等。

1、引申一中给出的第二个算法的总的赋值次数为n+1，这个是最小的赋值次数了。但如何证明？

2、同时，这个算法每次都需要所有数字的参与，肯定可以通过增加赋值次数来减小总的运算次数，何时算法运行效率最佳？

3、更进一步，如何根据赋值次数为k的算法，构造出赋值次数为k+1的算法？是否可行？

反过来，如何根据赋值次数为k+1的算法，构造出赋值次数为k的算法？

4、给定k（k大于等于n+1），构造赋值次数为k的算法。是否任意的k都有一个算法呢？

给定k，构造赋值次数为k的，总的运算次数最少的算法。

5、编程实现。

后记

在看《计算机程序设计艺术》时，1.1算法的习题部分的第一个习题提到用最少的替代次数实现(a,b,c,d)-->(b,c,d,a)，就想到了不使用中间变量的(a,b)-->(b,a)，好奇地看了下答案，答案引入一个中间变量……也是五次替代。然后就思维发散了一下。

“更多思考”部分貌似是一大坑啊。

不知网上是否已经有过相关的分析，简单搜了下，暂时没有发现。