2
有一個任務來計算總和，加號是even number of ones in bin和每個數字提高到4次冪的數字。問題是最後一個加數是2 ，所以通常的計算需要很長時間。 我認爲動態編程可以在這裏幫助，但我不知道如何在這裏使用它。
下面是一個例子：
計算與大量的加數
請，誰能幫助我解決這個問題？
Q
計算與大量的加數
A
回答
1
有一個formula to calculate the sum of the powers of 4 of all integers from 1 to n：
總和（K ） = K < = N =（6 * N + 15 * N + 10 * N - n）/ 30
在你的問題中，你只需要總結出4個k的冪數，它們的二進制表示有偶數個。這個公式並不排除有奇數個的k。然而，我的直覺告訴我，具有奇數個k的k箇中的4個的冪的總和應該與k箇中的4個的冪的和與偶數個的總和大致相同。
事實證明，如果計算這兩個和一個範圍K公司的，這些款項將在每32 K公司的完全相同曾經在一段時間，一旦：
n= 0 OddSum= 0 EvenSum= 0 = =
n= 1 OddSum= 1 EvenSum= 0
n= 2 OddSum= 17 EvenSum= 0
n= 3 OddSum= 17 EvenSum= 81
n= 4 OddSum= 273 EvenSum= 81
n= 5 OddSum= 273 EvenSum= 706
n= 6 OddSum= 273 EvenSum= 2002
n= 7 OddSum= 2674 EvenSum= 2002
n= 8 OddSum= 6770 EvenSum= 2002
n= 9 OddSum= 6770 EvenSum= 8563
n= 10 OddSum= 6770 EvenSum= 18563
n= 11 OddSum= 21411 EvenSum= 18563
n= 12 OddSum= 21411 EvenSum= 39299
n= 13 OddSum= 49972 EvenSum= 39299
n= 14 OddSum= 88388 EvenSum= 39299
n= 15 OddSum= 88388 EvenSum= 89924
n= 16 OddSum= 153924 EvenSum= 89924
n= 17 OddSum= 153924 EvenSum= 173445
n= 18 OddSum= 153924 EvenSum= 278421
n= 19 OddSum= 284245 EvenSum= 278421
n= 20 OddSum= 284245 EvenSum= 438421
n= 21 OddSum= 478726 EvenSum= 438421
n= 22 OddSum= 712982 EvenSum= 438421
n= 23 OddSum= 712982 EvenSum= 718262
n= 24 OddSum= 712982 EvenSum= 1050038
n= 25 OddSum= 1103607 EvenSum= 1050038
n= 26 OddSum= 1560583 EvenSum= 1050038
n= 27 OddSum= 1560583 EvenSum= 1581479
n= 28 OddSum= 2175239 EvenSum= 1581479
n= 29 OddSum= 2175239 EvenSum= 2288760
n= 30 OddSum= 2175239 EvenSum= 3098760
n= 31 OddSum= 3098760 EvenSum= 3098760 = =
n= 32 OddSum= 4147336 EvenSum= 3098760
n= 33 OddSum= 4147336 EvenSum= 4284681
n= 34 OddSum= 4147336 EvenSum= 5621017
n= 35 OddSum= 5647961 EvenSum= 5621017
n= 36 OddSum= 5647961 EvenSum= 7300633
n= 37 OddSum= 7522122 EvenSum= 7300633
n= 38 OddSum= 9607258 EvenSum= 7300633
n= 39 OddSum= 9607258 EvenSum= 9614074
n= 40 OddSum= 9607258 EvenSum= 12174074
n= 41 OddSum= 12433019 EvenSum= 12174074
n= 42 OddSum= 15544715 EvenSum= 12174074
n= 43 OddSum= 15544715 EvenSum= 15592875
n= 44 OddSum= 19292811 EvenSum= 15592875
n= 45 OddSum= 19292811 EvenSum= 19693500
n= 46 OddSum= 19292811 EvenSum= 24170956
n= 47 OddSum= 24172492 EvenSum= 24170956
n= 48 OddSum= 24172492 EvenSum= 29479372
n= 49 OddSum= 29937293 EvenSum= 29479372
n= 50 OddSum= 36187293 EvenSum= 29479372
n= 51 OddSum= 36187293 EvenSum= 36244573
n= 52 OddSum= 43498909 EvenSum= 36244573
n= 53 OddSum= 43498909 EvenSum= 44135054
n= 54 OddSum= 43498909 EvenSum= 52638110
n= 55 OddSum= 52649534 EvenSum= 52638110
n= 56 OddSum= 62484030 EvenSum= 52638110
n= 57 OddSum= 62484030 EvenSum= 63194111
n= 58 OddSum= 62484030 EvenSum= 74510607
n= 59 OddSum= 74601391 EvenSum= 74510607
n= 60 OddSum= 74601391 EvenSum= 87470607
n= 61 OddSum= 88447232 EvenSum= 87470607
n= 62 OddSum= 103223568 EvenSum= 87470607
n= 63 OddSum= 103223568 EvenSum= 103223568 = =
n= 64 OddSum= 120000784 EvenSum= 103223568
...
n=4062 OddSum= 110517674755433207 EvenSum= 110790187795938168
n=4063 OddSum= 110790187795938168 EvenSum= 110790187795938168 = =
n=4064 OddSum= 111062969223019384 EvenSum= 110790187795938168
n=4065 OddSum= 111062969223019384 EvenSum= 111063237807788793
n=4066 OddSum= 111062969223019384 EvenSum= 111336556602699529
n=4067 OddSum= 111336556999378505 EvenSum= 111336556602699529
n=4068 OddSum= 111336556999378505 EvenSum= 111610413558992905
n=4069 OddSum= 111610683334189626 EvenSum= 111610413558992905
n=4070 OddSum= 111885079246199626 EvenSum= 111610413558992905
n=4071 OddSum= 111885079246199626 EvenSum= 111885079246980586
n=4072 OddSum= 111885079246199626 EvenSum= 112160014909822442
n=4073 OddSum= 112160285082869867 EvenSum= 112160014909822442
n=4074 OddSum= 112435761292440443 EvenSum= 112160014909822442
n=4075 OddSum= 112435761292440443 EvenSum= 112435761691463067
n=4076 OddSum= 112711778845418619 EvenSum= 112435761691463067
n=4077 OddSum= 112711778845418619 EvenSum= 112712050215144108
n=4078 OddSum= 112711778845418619 EvenSum= 112988609908991164
n=4079 OddSum= 112988609908992700 EvenSum= 112988609908991164
n=4080 OddSum= 112988609908992700 EvenSum= 113265712541951164
n=4081 OddSum= 113265984311095421 EvenSum= 113265712541951164
n=4082 OddSum= 113543630682195597 EvenSum= 113265712541951164
n=4083 OddSum= 113543630682195597 EvenSum= 113543631082001485
n=4084 OddSum= 113821821591246733 EvenSum= 113543631082001485
n=4085 OddSum= 113821821591246733 EvenSum= 113822094560202110
n=4086 OddSum= 113821821591246733 EvenSum= 114100830807798926
n=4087 OddSum= 114100830808584494 EvenSum= 114100830807798926
n=4088 OddSum= 114380113196106030 EvenSum= 114100830807798926
n=4089 OddSum= 114380113196106030 EvenSum= 114380386566045167
n=4090 OddSum= 114380113196106030 EvenSum= 114660215895655167
n=4091 OddSum= 114660216297816991 EvenSum= 114660215895655167
n=4092 OddSum= 114660216297816991 EvenSum= 114940592970302463
n=4093 OddSum= 114940867546334192 EvenSum= 114940592970302463
n=4094 OddSum= 115221793169753088 EvenSum= 114940592970302463
n=4095 OddSum= 115221793169753088 EvenSum= 115221793169753088 = =
...
沒有正式證明我提議因此答案是：
（（6 * N + 15 * N + 10 * n個 - N）/ 30）/ 2
其中n = 2 -1。
+0
如果我正確地理解了這個'n'表示位數？因此，對於表中的每一行，奇數總和是奇數奇偶校驗中所有n位數的四次冪的總和;甚至對於偶數奇偶校驗的n位數的總和？如果我的理解是正確的，那麼表中的第一個錯誤是n = 2，偶數和應該是81（11進制== 3小數，3^4 = 81）。該表在其他地方也是錯誤的，其中n的3個連續值的偶數和是相同的（例如，n = 24,25,26）。如果我誤解了，請澄清。除了這個問題，我喜歡答案。 – 2012-04-24 10:13:05
+0
'n'是我們在總和中增加到4的次冪的最大數目。在問題陳述中，它從0到3到5,6,9,10,12,15，...，2^64-1。用小數字手工操作4個數字的奇數和偶數，以查看錶中的內容。我的表格精確地複製了4個數字的權數和偶數個數的和。 「dups」在那裏，因爲下一個'n'對「奇數」總數或「偶數」總和做出貢獻，但不能同時出現，因爲'n'不能同時有偶數和奇數。 – 2012-04-24 10:21:40
+0
我提高了，因爲你建議使用數學提出一個封閉形式的解決方案（恆定時間！），而不是通過暴力計算總和。我不一定相信你的解決方案是正確的，但這至少是解決這個問題的正確思路。 – 2012-04-24 10:22:13
1
以下是如何計算值。
您可以爲上限的二進制表示中的每個數字位數計算值。對於每個數字位數，分別計算其二進制表示中具有偶數個1的數字和具有奇數個1的數字的度數1到4的和。有了這些值，您應該能夠計算n + 1的值，其中n是二進制表示中的位數。
下面是關於如何做到這一點的一些意見：如果你有第k個數的度數與偶數個數之和，然後乘以2^k，你會得到這些數的總和加倍。這些數字仍然會有偶數。實際上，每個具有偶數個n的n位的數字或者是具有偶數個1的n-1個數字的雙倍數，或者是x * 2 + 1，其中x是具有奇數個1的數並且具有n - 1位數字。因此，在二進制表示中具有偶數個且具有n個數字的數字的第k個度數的總和爲Se(n,k) = 2^k * Se(n-1, k) + Sum(a : number with odd number of ones and n-1 digits){(2*a + 1)^k}。在這裏我用Se來表示偶數個數的總和。現在有趣的部分是第二個加法器。它可以使用二項式計算：
（2 * a + 1）^ k = 2^k * a * k + combination（1，k）*（2 * a）^（k-1）+ ...重組之後你1等有： Sum(a : number with odd number of ones and n digits){(2*a + 1)^k} = 2^k*So(n-1,k) + combination(1, k) * 2^(k-1)*So(n-1,k) + combination(2, k) * 2^(k-2)*So(n-1,k) + ...
現在，如果你認爲你有這樣（在他們的二進制表示奇數個的數量的總和）計算N-1還可以計算這個總和。
你必須寫類似的公式用於所以（N，K）：
所以（N，K）= 2^K *（所以第（n-1，K））+薩姆（A：數與偶數個1和n-1個數字）{（2 * a + 1）^ k
請記住，您必須爲k = 1，... 4計算此值，以便您可以將它們用於下一次迭代。只有一個音符 - 對於So（n，1），您有So（n，1）= So（n-1,1）* 2 + Se（n-1,1）* 2 + 1，同樣Se（n，1 ）= Se（n-1，1）* 2 + So（n-1,1）。
使用這些公式，您應該能夠快速計算所需的值。你需要總結Se（1,4）+ Se（2,4）+ ... Se（64，4）。該算法將適用於比給定約束更高的值。請注意，您搜索的值不適合任何「常規」整數類型。您將需要使用某種BigInteger實現。
希望這回答你的問題。
相關問題
- 1. 大數的計算加權平均數
- 2. 計算機科學與量子計算有多大關係
- 3. 計算最大值的數量
- 4. CSS計算與計算的變量
- 5. 計算與測量
- 6. 計算反彈的數量與PostgreSQL的
- 7. 加速大量數組相關的計算，visual studio
- 8. Android的計算與數學變量
- 9. 計算從大量數據幀
- 10. Python計算出最大數量？
- 11. 與XOR的變量計算
- 12. C/C++大量計算
- 13. 計算數量
- 14. 計算數量
- 15. 計算數量
- 16. 計算數量
- 17. 計算大數的模數
- 18. 計算與大數據文件
- 19. 計算行總數與選擇全部然後計算大小
- 20. 是計算大數
- 21. 總數量與jQuery計算插件
- 22. AngularJS計算大括號中的變量的動態數量
- 23. 計算數組的大小
- 24. 計算數組的大小
- 25. 計算大數的組合
- 26. 函數的大O計算
- 27. 如何計算大熊貓分類變量的滾動計數
- 28. ％與FMOD計算模量
- 29. 計算泛與刷卡量
- 30. 計算與隨機變量
每秒鐘的數字有偶數位，所以會有大約2^63 = 9223372036854775808這樣的數字。如果你打算遍歷它們，動態編程將無法幫助你。我認爲在開始編寫「for」-loops之前，你必須在數字之間找到一些切割數學關係並簡化問題。 – aioobe 2012-04-24 08:25:35