題目：

從1到N(100000)中任意拿掉兩個數(shù)，把剩下的99998個數(shù)順序打亂，并且放入數(shù)組A中。要求只掃描一遍數(shù)組，把這兩個數(shù)找出來。可以使用最到不超過5個局部變量，不能用數(shù)組變量，并且不能改變原數(shù)組的值。

思路：

遍歷一次數(shù)組，求出這兩個數(shù)的和a+b 與積a*b
a+b = 1+2+3+4+...+N- sum(A[]);??? (1)
a*b =? 1*2*3*4*...*N / multi(A[]);?? (2)

主要解決sum與multi的溢出問題

(1) 可化為 (N-A[0]) + (N-1-A[1]) + ...+ (3-A[N-3]) + 2 + 1

(2) 可以用對數(shù)來代替原數(shù)進行求積的等價運算,避免溢出的問題，但是這種方法會產(chǎn)生一些精度上的問題，不知道大家有什么更好的方法！
先求出log(a*b)?:
?????????????????????????= log(1*2*3*4*....*N)/log(A[0]*A[1]*A[2]*...*A[N-3])
?????????????????????????= log(N)-log(A[0]) + log(N-1)-log(A[1]) + ... +log(3)-log(A[N-3]) + log(2) + log(1)
?????????
知道了兩數(shù)的和與積,由此就可以計算出a跟b的值來.

代碼如下：



PS（謝謝枝~的幫助）請大家指導(dǎo)

//................................
通過大家的幫助：
得到另一個寫法，不會產(chǎn)生精度問題

(1+N)*N /2 - S = a + b
1/6 * n*(n + 1)*(2n + 1) - X = a*a + b*b

注：
1/6 * n*(n + 1)*(2n + 1)=1*1 + 2*2 + 3*3 +...+N*N
X = A[0]*A[0] + A[1]*A[1] +...A[N-3]*A[N-3]
?
==>
a + b = m
a*a + b*b = n

由于可解出a,b

看了兩三天的KMP算法,一直看的迷迷糊糊的.現(xiàn)在把這些資料貼在這里...以備日后之需
?
1.串的模式匹配的改進算法(這個網(wǎng)站對我的理解幫助很大,特別是右邊的那塊說明部分,以前自己腦筋老是轉(zhuǎn)不過來) http://cist.dhu.edu.cn/kejian/%CA%FD%BE%DD%BD%E1%B9%B9%BE%AB%C6%B7%BF%CE%B3%CC/%D4%DA%CF%DF%D1%A7%CF%B0/text/chapter04/section3/c5.htm

2.KMP 算法的注記 http://www.cublog.cn/u/20/showart_136705.html?

3.KMP算法中推導(dǎo)next[],nextval[]--手記 http://jiasimon040510.t8log.ccut.cn/blog-htm-do-showone-tid-6983.html


4.算法原理：

在匹配過和中，當主串中第i個字符與模式串中第j個字符“失配”時（s[i]!=t[j])，將模式串盡量向右移動，讓模式串中第k（k<j)個字符與si對齊繼續(xù)比較,

要讓這個條件成立，那么在k之前的k個t字符[0 到 k-1]必須在i之前的k個s字符[i-k 到 i-1]相匹配即：

?? t[0, 1, 2...k-1] == s[i-k, i-k+1, i-k+2...i-1]???? ---(1)

而由之前的部分匹配成功的結(jié)果可知：
??
?? t[0, 1, 2...j-1] == s[i-j, i-j+1, i-j+2...i-1]???? ---(2)
==>
?? t[j-k, j-k+1, j-k+2...j-1] == s[i-k, i-k+1, i-k+2...i-1]?? --(3)

由(1)與(3)可得：

?? t[0, 1, 2...k-1] == t[j-k, j-k+1, j-k+2...j-1]???? ---(4)

求出k值,就是next[j]的值了

總之,相對我來說,算法不是很好懂.但是大家看到我這么笨的人到最后都能明白一二.大家就更沒有理由看不懂了,祝大家成功附上我的測試源碼:

?

既然這樣可以運行，那為什么內(nèi)置的類型如：int float之類的不能取臨時對象的值呢？
我重載的+號運算符應(yīng)該沒有寫錯吧、、
請大家指教。。謝謝我還只是一個初學(xué)者