bobchennan 2008-08-05 03:03:00
点我顶贴
收藏
删除
解法一：将表达式都表示成标准形式：比如先按a的降幂排列，a的幂相同的时候再按b的降幂排列，a、b的幂都相同的时候再按照c的降幂排列……
标准形式可以自己定义，只要相等的表达式化简得到的结果是唯一的就可以了。这个方法的问题是：标准形式的项数可能很多，比如(a+b)^10^10^10；还可能出现高精度计算。
解法二：对变量都替换成随机的整数值，对每个表达式进行表达式求值，求值的过程中对得到的结果对某个值取模。假设a，b，c……带入作表达式求值的整数值分别是a，b，c……，取模的数是M。假设两个表达式分别是f(a, b,... z)和g(a, b,...z)。
如果f(a, b,... z) MOD M ≠ g(a, b,...z) MOD M，那么一定有f ≠ g。
如果f(a, b,... z) MOD M = g(a, b,...z) MOD M (*)，那么几乎有f = g成立。
因此只用作几次尝试，如果a，b，c，……取不同的值，M取不同的值的时候都有(*)成立，就可以判定f = g。
实际上，如果f = g，那么使得f(a, b,... z) = g(a, b,...z)的a, b,...z只有有限多个（跟表达式的次数有关）。因此当多组不同的a, b,...z都使得f(a, b,... z) = g(a, b,...z)成立，就可以说明f = g。
如果(*)成立，说明f(a, b,... z) ≡ g(a, b,...z) (MOD M)，如果对于同一组a, b,... z有M1，M2，……，Mk，那么f(a, b,... z) ≡ g(a, b,...z) (MOD lcm(M1, M2,... Mk))。由于f(a, b,... z)和g(a, b,...z)都是有界的，因此可知f(a, b,... z) = g(a, b,...z)。
这里对M取模的作用是避免高精度计算。