?

題目:

找到滿足條件的數組
給定函數d(n)=n+n的各位之和，n為正整數，如d(78)=78+7+8=93。這樣這個函數可以看成一個生成器，如93可以看成由78生成。
定義數A：數A找不到一個數B可以由d(B)=A，即A不能由其他數生成。現在要寫程序，找出1至10000里的所有符合數A定義的數。
回答：
申請一個長度為10000的bool數組，每個元素代表對應的值是否可以有其它數生成。開始時將數組中的值都初始化為false。
由于大于10000的數的生成數必定大于10000，所以我們只需遍歷1到10000中的數，計算生成數，并將bool數組中對應的值設置為true，表示這個數可以有其它數生成。
最后bool數組中值為false的位置對應的整數就是不能由其它數生成的。

?

---------------------------------------------------------

我嘗試用解方程的思路來看一下:

先把問題的范圍縮小到: 找出1至1000里的所有符合數A定義的數, (為了便于表達, 定義數A構成一個集合SA, SA的補集為RA)

?

對于小于1000的正整數n(n的各位用ni表示), 有: n =? n0 + n1 * 10 + n2 * 10^2 =?∑ni * 10^i ;? i∈{0~2}, ni∈{0~9}

?

考察函數 y?≡ f(n, x) = n2 * x^2 + n1 * x + n0; (x = 10, 因為是十進制數)

其中, 向量n=(n2, n1, n0), ni∈{0~9}, i∈{0~2};

上述問題里的d(n) = n + ∑ni = f(n, x)+ ∑ni; (x = 10)

對于1至1000里的正整數N, 如果存在另一個正整數n, 使得d(n) = N, 那么N∈RA; 反之, 如果找不到另一個正整數n, 使得d(n) = N, 那么N?SA. .

考察方程(1): d(n) - N = 0; (即: n2 * x^2 + n1 * x + n0 + (n2 + n1 +n0) - N = 0) ..............(1)

如果把方程(1)看做是關于x的方程, 那么問題變為: 當ni和N取哪些正整數時, 方程(1)至少有一個值為10的根.

?

?根據二次方程(A*x^2 + B*x +C = 0)求根公式:

x0 = (-b + sqrt(Δ)/(2a),? x1 = (-b - sqrt(Δ)/(2a);

Δ = B^2 - 4AC;

A = n2;

B = n1;

C = n0 + (n2 + n1 +n0) - N;

當x = 10時, 得到N, ni的關系式:

N = 101*n2 + 11*n1 + 2*n0; ...........................(2)

這與1~1000時找N的方法是一致的.

?

?

現在考察問題范圍擴大至1~10000, 這時就要涉及三次方程求根的方法了. 看看能得到什么結果

參考盛金公式:

一元三次方程aX³+bX²+cX+d=0，（a,b,c,d∈R，且a≠0） 重根判別式

總判別式Δ=B²－4AC

盛金判別法:

1.當A=B=0時，方程有一個三重實根。 2,當Δ=B²－4AC>0時，方程有一個實根和一對共軛虛根。 3,當Δ=B²－4AC=0時，方程有三個實根，其中有一個二重根。 4,當Δ=B²－4AC<0時，方程有三個不相等的實根。

?

考察函數 y?≡ f(n, x) = n3 * x^3 + n2 * x^2 + n1 * x + n0; (x = 10, 因為是十進制數)

考察方程(3): d(n) - N = 0; (即: n3 * x^3 + n2 * x^2 + n1 * x + n0 + (n3 + n2 + n1 +n0) - N = 0) ..............(3)

由盛金公式得:

a = n3;?????? b = n2; ? ? ?? c = n1;??????? d = n0 + (n3 + n2 + n1 +n0) - N = (n3 +n2 +n1 +2*n0 -N);

A = b^2 - 3ac = n2^2 - 3*n3*n1;

B = bc - 9ad = n2*n1 - 9* n3*(n3 + n2 + n1 +2*n0 - N);

C = c^2 - 3bd = n1^2 - 3* n2* (n3 + n2 + n1 +2*n0 - N);

Δ = B^2 - 4AC;

盛金判別法:

1.當A=B=0時，方程有一個三重實根。

?

令x1 = x2 = x3 = 10, 得:

?

?

30a +b = 0;......(1.1)
10b +c = 0;......(1.2)
10c +3d = 0;......(1.3)
同時, A=0, B=0;得:
b^2 - 3ac = 0;......(1.4)
bc - 9ad = 0;......(1.5)
連立方程組得:
N = 2*n0 + 1271*n3;
考慮到a, b,c都是正整數, 實際上可從(1.1), (1.2), (1.3) 得出a=b=c=0, 這和a≠0的假設矛盾, 所以這種情況下沒有我們想要的數.

3.當Δ=B²－4AC=0時，方程有三個實根，其中有一個二重根。 ......(3.1) ......(3.2) 其中 。 由(3.1)得:N = n2^3/(9*n3^2) - 4/9 * n2*n1/n3 + n3 +n2 - 7/3*n1 +2*n0 +10/9* n2^2/n3; 由(3.2)得: N = -(n3 + n2 + n1 + 2n0) + 20 *n2^2/(9*n3) - 20/3*n1 + 1/9* n2*n1/n3; (推導到這里已經變得很惡心了啊.) 注意到, 如果令每一個加和項都為整數的話, 須滿足: n1 = 3 * i; n2 = 3* n3 *j; (i, j為正整數), 同時還要滿足N>0, 即使這樣, 得到的也只是答案的一個子集而以. 2.當Δ=B²－4AC>0時，方程有一個實根和一對共軛虛根。 4.當Δ=B²－4AC<0時，方程有三個不相等的實根。 至于2和4的解里面牽扯到sqrt, arccos等函數, 在這些情況下要考慮整數解的話.........我還是決定放棄了:)

?哎, 結果不就是個 N = 1001*n3 + 101*n2 + 11*n1 + 2*n0嘛; 看來用解方程的方法還是繞遠了啊,

?

轉載于:https://www.cnblogs.com/yaoyansi/p/4113002.html

總結

以上是生活随笔為你收集整理的一道算法题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。